Principal Investigator: Edmund H. Durfee
Graduate Research Assistants:
Thomas Bartold Sponsor: DARPA Control of Agent-Based Systems Initiative
This project is exploring techniques with which computational agents can search through the space of alternative representations of their plans and the plans of others to find a level of detail that strikes a good balance between coordinating well without getting bogged down in commitments they will later regret making.
I – Background:
When multiple computational agents share a task environment, interactions between the agents generally arise. An agent might make a change to some feature of the environment that in turn impacts other agents, for example, or might commandeer a non-sharable resource that another agent desires. When the decisions that an agent makes might affect what other agents can or should decide to do, agents will typically be better off if they coordinate their decisions.
Numerous techniques exist for coordinating decisions about potential interactions. These include appealing to a higher authority agent in an organizational structure, instituting social laws that avoid dangerous interactions, using computational markets to converge on allocations, explicitly modeling teamwork concepts, using contracting protocols to strike bargains, and iteratively exchanging tentative plans until all constraints are satisfied. There is a rich literature on these and other mechanisms for coordinating agents; the interested reader can see the Multiagent Systems book edited by Weiss (MIT Press, 1999).
However, each of these mechanisms takes as its starting point that the agents requiring coordination know, at the outset, either with whom they should coordinate, or what issues they should coordinate about. As examples, an organizational structure inherently defines how agents are related to each other, and a computational market corresponds to some resource or “good” that was somehow known to be contentious.
A central thrust of our research at the University of Michigan is in pushing back the boundaries of what is assumed known in a multiagent setting in order to bootstrap the coordination process. That is, we want to develop techniques by which agents can discover whom they should coordinate with, or what they should coordinate about, so that the rich variety of coordination techniques can then be employed. Our project as part of the DARPA Control of Agent Based Systems initiative specifically looks at scalable strategies for discovering coordination needs and controlling the interactions between agents in open, dynamic environments.
II – Project 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. In a coalition, for example, objectives and responsibilities are distributed among multiple functional teams, where operational choices by one team can infrequently and unintentionally affect another team. The repercussions of unintended interactions can range from merely delaying the accomplishment of objectives (such as waiting for assets that were unexpectedly borrowed by someone else) to more catastrophic outcomes (such as so-called friendly fire). We have been developing computational techniques in which each team is represented by a computational agent, and these agents predict the unintended interactions and resolve them before they occur. The resulting coordinated plans of the agents should be efficient (e.g., agents should not have to wait unnecessarily for others), flexible (e.g., agents should retain room in their plans to improvise around changing local circumstances), and realizable (e.g., agents should not have to message each other at runtime in a manner that outstrips communication capabilities).
The goal of this project is therefore 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 are being evaluated in analytical and empirical studies, and demonstrated through integrated experiments in simulated coalitions operations tasks.
III – Technology overview
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.
Conceptually, our techniques begin by assuming that each agent can represent its plans in a hierarchical task network (HTN), capturing the possible decompositions of abstract plan steps into more detailed plans. As a simple example, consider the case of agent A moving through a grid world to reach a destination (Figure 1). The HTN for this agent is in Figure 2. At the most abstract level (blue arrow in Figure 1, blue node in the HTN), the plan is simply to go from the initial location to the destination. This is in turn composed of the three sequential steps of going to the door, through the door, and beyond the door (green, purple, and aqua arrows/nodes respectively). The ordering constraints are captured in the HTN (Figure 2) by the arrows labeled B for before. For both the first and last step at this level, there are two ways of accomplishing the step. For example, for getting to the door, the red route or the orange route could be chosen. Each of these in turn can be decomposed into a sequence of two movements; red, for example, is to the right and then down).
Unlike traditional approaches where detailed plans are formulated in their entirety before execution, hierarchical 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.
The ability to detect and resolve unintended interactions at any of many levels of detail promises to improve scalability (Durfee, 2001), 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. In an open environment populated by numerous agents, being able to communicate about and exchange abstract information can enable agents to quickly determine which (small) subset of agents in the world they actually could potentially interact with (Figure 3a to Figure 3b). In the simple movement task example, for instance, the grid might be much larger, and the subset of agents is small whose planned movements, even abstractly defined, indicate a potential collision with agent A. For those agents, it might even be possible to impose constraints at the abstract level to ensure against unintended collisions, such as sequentializing the overall plans so that only one of the affected agents moves at a time. Or, for the remaining agents, additional details of the HTNs can be exchanged. As a result, agents that were potentially interacting might be determined to not interact at all, reducing the number of agents further and introducing constraints between only substeps of plans leaving agents to do their other substeps as they wish (Figure 3c). Finally, further investigation might indicate that the potential conflict can be isolated to a particular choice that an agent might make; a commitment by the agent to forbid that choice leaves the plans coordinated without imposing any ordering constraints between the agents’ plans at all (Figure 3d).
This example illustrates that, by working from the top down, agents can more efficiently identify and zoom in on the problematic interactions. By digging down deeply, they might be able to impose commitments (on relative timing or on choices of ways in which they will accomplish their tasks) that lead to very crisp coordination. However, in dynamic environments, sometimes it is better to impose constraints at more abstract levels: while this might require more sequential operation than desired, it also allows agents to avoid commitments to details that they might regret. As is intuitive in human coordination, each agent retains more flexibility for improvising when it makes more vague commitments to others. Moreover, digging down deeply requires more rounds of communication and analysis, so coordinating at abstract levels incurs less overhead. Among our ongoing research activities are developing methods for quantitatively evaluating tradeoffs between coordination “crispness”, overhead, and flexibility.
IV – Technical Accomplishments
We have developed techniques for formulating summaries in HTNs that permit the kind of top-down reasoning that we have just described, and have shown that both the summarization and the top-down coordination algorithms are sound and complete. Using analysis and experiments, we have determined that the techniques can indeed much more efficiently coordinate agents (Clement and Durfee, 1999). As brief examples, Figure 4 indicates how the computational time needed for coordination grows exponentially with the average depth in the HTN at which coordination commitments are made, and Figure 6 illustrates how the use of summary information to identify potential threats between plans can provide a valuable heuristic for refining plans compared to making refinements more randomly.
At the cost of completeness, we have also developed a version of these techniques that can be used on-line (Pappachan and Durfee, 2001). The on-line techniques allow agents to postpone decisions about which of the alternative ways they will use to accomplish a task until that task is the next to be done. This in turn provides increased flexibility to the agents, leading to more reliable agent operation in dynamic domains than methods that require agents to make selections before execution begins. Our empirical studies to date on an example dynamic scenario built on the coalition application has indicated that this approach is 112% more reliable than the “plan then execute” approach, that it is 11% faster on average (for example, by avoiding synchronization constraints that, based on run-time choices, are unnecessary), and that it incurs 24% less overhead. More experimentation is planned.
To amortize the computational costs of these techniques, an additional innovation in this project is to enable agents to store previously computed coordination solutions for reuse under similar future circumstances. This requires that the agents themselves are able to modify their libraries of potential plans, and retrieve appropriate plans given different multiagent contexts. We have done this using the UM-PRS agent architecture (Cox et al, 2001).
Finally, we have implemented the summarization and top-down coordination mechanisms into the Multilevel Coordination Agent (MCA), which is a service on the CoABS Grid. The MCA accepts hierarchical plan descriptions from other agents, and can provide summary information back, ultimately to be used during the coordination process to detect and resolve possible conflicts between agents’ plans. The MCA has been applied to abstract NEO applications, and is part of the CoAX TIE, serving to discover and recommend resolutions to conflicts among the plans of coalition partners and of NGOs operating in the same area. An example of the information provided by the MCA to a commander is in Figure 6, where the commander can select among the possible resolutions found so far, or can wait as the MCA continues to search at more detailed levels (which, as previously described, takes longer). Note that the degree to which the plans are interleaved increases with each solution found.
A subset of the publications providing more details of the technical accomplishments of this project follows:
Bradley J. Clement and Edmund H. Durfee. “Top-Down Search for Coordinating the Hierarchical Plans of Multiple Agents.” In Proceedings of the Third International Conference on Autonomous Agents, pages 252-259, May 1999.
Bradley J. Clement and Edmund H. Durfee. “Theory for Coordinating Concurrent Hierarchical Planning Agents Using Summary Information.” In Proceedings of the National Conference on Artificial Intelligence (AAAI-99), pages 495-502,July 1999.
Bradley J. Clement, Anthony C. Barrett, Gregg R. Rabideau, and Edmund H. Durfee. “Using Abstraction in Planning and Scheduling.” In Proceedings of the Sixth European Conference on Planning (ECP-01), September 2001.
Jeffrey S. Cox, Bradley C. Clement, Pradeep M. Pappachan, and Edmund H. Durfee. “Integrating Multiagent Coordination with Reactive Plan Execution.” (abstract) Proceedings of the ACM Conference on Autonomous Agents (Agents-01), June 2001.
Edmund H. Durfee. “Scaling Up Agent Coordination Strategies.” IEEE Computer 34(7):39-46, July 2001.
Pradeep M. Pappachan and Edmund H. Durfee. “A satisficing multiagent plan coordination algorithm for dynamic domains.” (abstract) Proceedings of the ACM Conference on Autonomous Agents (Agents-01), June 2001.
V – 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. 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 the CoAX effort itself transitions, as planned, into military applications across multiple branches of the forces (and internationally), this project’s coordination technology will transition with it.
STRATCOM: The principal investigator has held preliminary discussions with STRATCOM regarding STRATCOM’s C2 modernization concepts, and the role of this project’s automated plan coordination technology as part of their concept and prototype development. Further discussions are planned, when STRATCOM reaches a point where this moves to the front of their priority queue, and when CoAX experience will help in determining the viability and effort required to realize this transition.
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.
VI – Presentations: