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 that must visit different locations to pick up civilians and evacuate them to safety points (Sa and Sb). Suppose the agents must also destroy routes (e.g. burn bridges) to protect from being followed by an enemy and are restricted from travelling 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.
Above, a red agent and a green agent must visit several locations and return to their starting points, Sa and Sb. The bright colored nodes are the current locations of the agents. Dark colored nodes are the locations the respective colored agents must visit. Multicolored nodes must be visited by all agents of those colors. Black edges are routes between locations, and dark colored routes are bridges that the respective colored agents must destroy.
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.
To start the simulation in the applet, press the spacebar. (Click inside the applet if you get no response.) Pause execution at any time with the spacebar and resume with the spacebar. To reset the simulation after it has finished, press the 's' key.
Decentralized preprocessing of plan hierarchiesThe following three simulations show 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 syncronizations 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. Centralized preprocessing of plan hierarchiesEach of the following three scenarios illustrate the results of different coordination choices at different levels of abstraction that the agents made during plan execution. The coordination algorithm centrally preprocesses the plan hierarchies of all of the agents to discover temporal relationships that can hold between any two abstract or primitive plans. The agents use this information at runtime to efficiently make coordination decisions as they execute their plans. |
If you have questions, comments, or suggestions, email Brad Clement at bradc@umich.edu.