The USC Viterbi School of Engineering’s Information Sciences Institute is playing a $5.9 million part in a Defense Advanced Research Projects Agency (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 might look around and recruit additional computing resources if the situation were too dire or 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 interweaves 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 operator's 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 a commander’s visualization and adaptive execution, yielding 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 involved, noted 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 said. “The pieces occupy fixed positions for long intervals, then move instantaneously.”

The battlefield is a very different place, he said. 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 is creating tools by analyzing a last-man-standing free-for-all struggle called “Arena War.”

A parallel supporting effort by Robert Lucas, director of ISI’s computational science division, and Dan Davis, project director of the ISI’s Joint Experimentation on Scalable Parallel Processors program, will take Cohen and Chang’s work out of laboratory situations by finding ways to put the huge computational resources necessary into a system that Cohen could actually be used in chaotic wartime conditions – “in a tent,” Davis said.

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 do not 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, such as "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.

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, Davis said, “we feel 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.”

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 20 processors on scene, or hundreds within the battlespace, or thousands across the globe,” Lucas explained.

“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 said.

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,” Cohen said.