Beyond chess: Deep green models rapid change for combat commanders

The USC Information Sciences Institute is playing a $7.6 million part in a DARPA research effort called Deep Green aimed at creating a system that can do so, one that might help future combat commanders in the field anticipate enemy moves.

The same system would look around and recruit additional computing resources if the situation were too dire, the problem too difficult.

The Deep Green program, a next-generation battle command and decision support technology, is the vision of Col. John Surdu, who manages the program for the Information Processing Techniques Office of DARPA.

The system interleaves anticipatory planning with adaptive execution to help the commander think ahead, identify when a plan is going awry, and prepare options, before they are needed.

Deep Green will use a human operators hand drawn sketches and words to induce intent. It will generate options for all sides in an operation and predict the likelihood of multiple futures.

By presenting decisions early and allowing the commander to "see the future," Deep Green supports commander's visualization and adaptive execution, enabling correct, timely decisions by the commander.

Deep Green has several components, including novel interfaces for getting guidance from and presenting options to commanders, powerful simulations of the battlespace, and methods for efficiently searching the space of future options. The prime contractor, responsible for all these elements, is SAIC.

ISI researcher Paul Cohen, heading one of the two ISI groups subcontracting on the program, notes that the name is meant to recall Deep Blue, the famous IBM chess playing program that defeated world champion Garry Kasparov in a 1997 match, a landmark in the history of artificial intelligence.

"But chess is a special, artificial situation," Cohen notes. "The pieces occupy fixed positions for long intervals, then move instantaneously." The battlefield is a very different place, Cohen continues. There, units on both sides are in continuous motion. Moreover, chess players can see the whole board, whereas commanders have limited visibility of the battlefield.

A program like Deep Blue visualizes where pieces might move in the future, based on the moves possible for knight, bishop, and so on. The problem for Deep Green is that time and location change continuously, so the very notion of a “state of the board” needs a new formulation.

Cohen, deputy director of ISI's Intelligent Systems Division and director of the ISI Center for Research on Unexpected Events is working with Yu-Han Chang on a $6 million segment of the effort. The pair are creating tools by analyzing a digital last-man-standing free-for-all called "Arena War."

Chang and Cohen’s program, called Adversarial Continuous Time and Space Search, (ACCTS), represents collections of interacting combatants (units) by what are called "fluents,” a concept close to the time-space operators called vectors familiar to first year physics students.

Fluents represent periods in which activities of the units modeled don't conflict or interfere with each other, or complete their mission or arrive at their goal. When they do, a decision point is reached, where new vectors have to be assigned, creating new fluents.

"Rather than relying on copious amounts of sampling to estimate future outcomes," reads a report presented by Chang, Cohen and Wesley Kerr in November 2007, "fluents take advantage of process models that can either be solved in closed form or can be efficiently updated recursively."

The ACTSS system aids a human commander in the Arena War by "generating, evaluating and monitoring possible futures. It identifies potential critical points in these futures, and … ranks the options for possible next actions."

In the words of the report: "To play Arena War with the help of the ACTSS system, the commander [i.e., human operator] first inputs his plan of attack, as well as his expectations about the actions his opponents will take," This can either be in the form of a list of specific actions "first go to point A, then to point b," or by programming simple instructions into the pieces, such as "move away from pieces you see trying to move toward you."

"With the plans inputted, the commander can then start the game and the ACTSS system will immediately generate updated Futures Graphs at fixed intervals." The graphs look ahead in time, detailing how successions of fluents could develop from the fluents in play at the beginning.

And the ACTSS system uses these look-ahead graphs to see whether the commander’s forces are in danger of what would in chess be check, and does so soon enough for the commander to change activity to counter the threat. "Moreover, the look-ahead is very efficient."

Promising as the opening is, says Davis, " the goals of Deep Green can only be met by optimizing the use of remote computational assets. It is clear that the warfighter could use more compute capability than can be carried into the battlespace."

Enter a parallel supporting effort by Robert F. Lucas, director of ISI's computational science division and Dan Davis aimed at finding ways to put the huge computational resources necessary to solve complicated fluents problems into a system that could actually be used in chaotic wartime conditions -- "in a tent," says Davis.

Davis and Lucas are working on a $1.6 million contract trying to create a system that links to portable electronics; a very efficient, bandwidth-saving, distributed computing platform, and an effective method for assessing local computation and communications limitations.

If it can be done - if they can create a very large trans- globally distributed computer network that still requires very little bandwidth, the Deep Green system can be made scalable -- "it will run effectively on one processor to twenty processors on scene, or hundreds within the battlespace, or thousands across the globe," explains Lucas.

"This capability means that the commander will never be without some assistance, no matter the communications situation, but can have the power of remote computers, when conditions permit," he continued.

Davis and Lucas earlier worked on war-game models of unprecedented scale, involving millions of autonomous units moving in continent-scale environments, assembling computer resources from across the country. Key advances realized in that effort, included complementary routers (Web and Tree) that could integrate different simulation modes. This work will be integrated into the Deep Green effort.

ISI researchers acknowledge that many problems remain to be solved. “But we already can play a mean game of Arena War,” says Cohen.

Source: University of Southern California

Related stories:

Turning fungus into fuel
A spidery fungus with a voracious appetite for military uniforms and canvas tents could hold the key to improvements in the production of biofuels, a team of government, academic and industry researchers has announced.
Deep-sea sharks wired for sound
Deep-sea sharks have been tagged and tracked and their habitats precisely mapped in world-first research to test the conservation value of areas closed to commercial fishing.

For the paper trail of life on Mars or other planets, find cellulose
Looking for evidence of life on Mars or other planets? Finding cellulose microfibers would be the next best thing to a close encounter, according to new research from the University of North Carolina at Chapel Hill.
Self-Assembled Materials Form Mini Stem Cell Lab
Imagine having one polymer and one small molecule that instantly assemble into a flexible but strong sac in which you can grow human stem cells, creating a sort of miniature laboratory. And that sac, if used for cell therapy, could cloak the stem cells from the human body’s immune system and biodegrade upon arriving at its destination, releasing the stem cells to do their work.
Researchers give new hybrid vehicle its first test drive in the ocean
Taking a page out of a science fiction story, researchers from the Woods Hole Oceanographic Institution (WHOI) and Webb Research Corporation (Falmouth, Mass.) have successfully flown the first environmentally powered robotic vehicle through the ocean. The new robotic “glider” harvests heat energy from the ocean to propel itself across thousands of kilometers of water.
New NASA Mission to Reveal Moon's Internal Structure and Evolution
At a Monday meeting of the American Geophysical Union, NASA's Associate Administrator for Science Alan Stern announced the selection of a new mission that will peer deep inside the moon to reveal its anatomy and history.
Newfound ancient African megadroughts may have driven the evolution of humans and fishes
From 135,000 to 90,000 years ago tropical Africa had megadroughts more extreme and widespread than any previously known for that region, according to new research.
Botched production of insulin molecule may lead to diabetes
Picture a pretzel factory production line, with conveyer belts carrying the dough, formed into unbaked pretzels, down to the oven to be cooked.

News discussion:

Technology news