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.
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).
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.
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.
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.
Some recent 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.