Objective:
Agile and rapid teaming, such as in the concerted application of coalition forces in uncertain, confrontational settings, requires efficiently coordinating mission plans that also give team members some room to improvise mission details around unexpected or previously unobservable events. The goal of this project is to develop technologies that enable multi-level coordination: participating agents should be able to decide on the level of plan detail at which to make coordination commitments, based on the current circumstances and their needs to balance predictability to each other with flexibility to react autonomously. By focusing only on details of interactions that matter in particular situations, multi-level coordination techniques will lead to scalable, efficient, and robust coordination outcomes. These benefits will be evaluated in analytical and empirical studies, and demonstrated through integrated experiments in simulated coalitions operations tasks.
Approach:
The principal insight behind this project’s multi-level coordination technologies is that hierarchical models of an agent’s plans and goals can be exploited to support coordination that strikes a balance between predictability and flexibility that is more tailored for particular mission needs. Many problem domains can be effectively planned for in a hierarchical manner, where the broad outlines of behavior are laid out and then incrementally refined in time, space, and scope of participation. Rather than use hierarchy only as a means to an end (a detailed plan), multi-level coordination technologies allow agents to retain information at the various levels, and therefore an agent can represent what it is doing at multiple levels of detail all at once. Because it will need to engage in detailed coordination with some (physically or conceptually proximate) agents while at the same time coordinating in looser ways with other agents, the agent can communicate models of itself at the right level of detail for different coordination relationships simultaneously. By receiving such models from others, an agent can ensure that its decisions fit into the combined efforts of the agent system without getting bogged down in computations at unnecessarily detailed levels.
To represent a plan space, this project has adapted a representation of plans as nested procedures in increasing detail. Unlike traditional approaches where detailed plans are formulated in their entirety before execution, plans can be incrementally elaborated such that the most appropriate procedure to accomplish a particular goal is chosen only when that goal is to be achieved next. By comparing conditions that must hold over different intervals in agents’ plans, timing relations that must hold for the plans to avoid unintentionally interfering with each other can be inferred. By propagating information about conditions that hold and about timing constraints between subplans upward through the hierarchy, relationships between plans at various levels of abstraction can thus be identified. This research includes analyses to ensure soundness and completeness of these methods, along with understanding their computational complexity. To amortize the computational costs, an additional innovation in this project is to enable agents to store previously computed coordination solutions for reuse under similar future circumstances.
The ability to detect and resolve unintended interactions at any of many levels of detail promises to improve scalability [1], because an agent can use abstract models to quickly identify just those agents it needs to coordinate with, and can dynamically select the level of detail at which to coordinate with them. This research includes developing new, principled techniques for making these decisions based on probabilistic models, along with recovery mechanisms for adapting to changing circumstances that mismatch previous coordination decisions.
Introducing the added dimension of being able to decide on the level of detail for agents to model each other at run time will become increasingly critical in the technologically and informationally-rich battlefield of the future. The methods developed here should be widely applicable for systems in which the “right” level for coordination cannot be statically predetermined, but instead must change in response to system needs and time-critical opportunities. The efficacy of our techniques will be demonstrated by implementing them as services in the CoABS Grid, and using them to coordinate the rapid deployment of (simulated) coalition forces where the lack of prior joint training and shared understanding can otherwise lead to uncoordinated activities, with consequences ranging from minor (wasted effort) to major (friendly fire).
Accomplishments:
Demonstrated efficacy of automated techniques for identifying and resolving unintended conflicts as part of the CoAX 2001 demonstration (October 2001).
Developed rudimentary capabilities for identifying redundant efforts across different mission participants, and merging the relevant plan steps to reduce mission cost. Implemented these in a new version of the Multi-level Coordination Agent (MCA) that continues to also be capable of identifying and resolving unintended conflicts between different agents’ plans. For some of our example plans, mechanisms can result in a cost reduction of 50% or more.
Enhanced failure recovery mechanisms to minimize the degree of disruption to existing commitments between agents. Reduces the coordination overhead incurred for instituting new commitments by an average of 39% in our sample test cases.
Provided MCA as part of CoABS Grid release, along with making updates and improvements to the BBN Grid Proxy that allows non-Java-based agents to interact with the Grid.
Integrated updated MCA into the Coalition Agents Experiment (CoAX) 2002, to be demonstrated in the fall of 2002. Worked with other CoAX participants to define the storyline and technology demonstration objectives.
Current Plan:
This project is not expected to receive FY03 funds. As a result the current plan is to see through to successful completion the CoAX 2002 demonstration in the fall of 2002, along with developing completed reports and software packages that aggregate the results and lessons learned from this project. As remaining time and funds allow, further research into effective techniques for discovering synergies between independently-developed agent plans, and for efficiently recovering from failed expectations in dynamic domains, will continue to be explored.
Technology Transition:
Coalition (CoAX) TIE: As part of the CoAX TIE, this project has been integrating its results into that TIE, such that the coalition planning can be assured to be conflict free and can exploit serendipitous opportunities for cooperation. There is speculation among colleagues who have participated in real coalition operations that this kind of technology can lead to improvements in coalition planning processes as well as outcomes. As CoAX transitions, as planned, into military applications across multiple branches of the forces (and internationally), this project’s coordination technology will transition with it.
NASA-JPL: Members of this project have been engaged in transitioning a number of these ideas into NASA applications, especially in planetary rover technology, in which prototype implementations and evaluations have been conducted.
Publications:
D. N. Allsopp, P. Beautement, J. M. Bradshaw, E. H. Durfee, M. Kirton, C. A. Knoblock, N. Suri, A. Tate, and C. W. Thompson. “Coalition Agents Experiment: Multiagent cooperation in international coalitions.” IEEE Intelligent Systems 17(3):26-35, May/June 2002.
B. J. Clement. “Abstract Reasoning for MultiAgent Coordination and Planning.” PhD Thesis, May 2002.
J. S. Cox and E. H. Durfee. “Discovering and Exploiting Synergy Between Hierarchical Planning Agents.” AAAI Workshop on Planning with and for Multiagent Systems, Working Notes, July 2002.
P. M. Pappachan. “Coordinating Plan Execution in Dynamic MultiAgent Environments.” PhD Thesis, May 2002.