Multiagent Plan Coordination in a Network Domain


This page was last updated 5/22/00.

In environments with limited resources, cooperative agents may need to coordinate their actions in order to avoid costly, irreversible decisions and accomplish their goals. Imagine two agents moving within a network (see below). Suppose they are transporter agents (red and yellow midsize circles) that must visit different locations to pick up civilians (small circles) and evacuate them to safety points (green locations). Suppose the agents must also destroy routes (the white edge is a destroyed route) to protect from being followed by an enemy and are restricted from traveling the same route between locations at the same time. If the agents do not communicate their intended actions, they may fail to achieve their goals either because they collided on some edge or because they were cut off from their safety destinations.


Below are links to applets showing how two hierarchical plan-merging strategies were used to coordinate the plans of two agents for evacuation problems like that described above.

Plan Coordination Simulations

Reasoning about the external conditions of abstract plans

The link below starts an applet that shows the resulting execution of hierarchical plans coordinated by a top-down search algorithm at different levels of abstraction. Agents individually preprocess their plans to derive summary information for non-primitive plans. This summary information contains the effective pre-, in-, and postconditions of plans in the hierarchy at all levels. Agents can use this information to detect when their plans may conflict and can search for a coordinated global plan at different levels to trade off computation efficiency for solution quality. The search algorithm expands the agents' plans in a breadth-first manner while looking for feasible synchronizations of the subplans and prunes away branches of the search space that will definitely not lead to global plans with shorter completion times. See some papers for details of the approach.

Coordination results for different levels of abstraction

Runtime coordination of hierarchical plans

In this approach, a coordination agent analyzes the temporal dependencies between conflicting primitive operators in various agents' plan spaces. It uses this information captured in a temporal constraint network to incrementally institute constraints on abstract plans as agents refine their abstract plans to primitive actions at runtime. The coordination is interleaved with plan execution and the agents might arrive at a coordinated joint multi-agent plan at any level of abstraction depending on the their performance objectives.

A simulation graphically illustrates the effects of coordinating at various levels of abstraction with the help of a simple, dynamic multi-agent domain.



If you have questions, comments, or suggestions, email Brad Clement at bradc@umich.edu.