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