In environments with limited resources, cooperative agents may need to coordinate their actions in order to avoid costly, irreversible decisions and accomplish their goals. 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.
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. 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.