Stephen A. Block, Brian C. Williams
Many applications of autonomous agents require groups to work in tight coordination. To be dependable, these groups must plan, carry out and adapt their activities in a way that is robust to failure and uncertainty. Previous work has produced contingent plan execution systems that provide robustness during their execution phase, by dispatching temporally flexi- ble plans, and during their plan extraction phase, by choosing between functionally redundant methods. Previous contin- gent plan execution systems use a centralized architecture in which a single agent conducts planning for the entire group. This can result in a communication bottleneck at the time when plan activities are passed to the other agents for exe- cution, and state information is returned. This paper introduces a robust, distributed executive for tem- porally flexible plans. To execute a plan, the plan is first dis- tributed over multiple agents, by creating a hierarchical ad- hoc network and by mapping the plan onto this hierarchy. Second, the plan is reformulated using a distributed, parallel algorithm into a form amenable to fast dispatching. Finally, the plan is dispatched in a distributed fashion. We then extend the distributed executive to handle contingent plans. Contingent plans are encoded as Temporal Plan Net- works (TPNs), which use a non-deterministic choice operator to compose temporally flexible plan fragments into a nested hierarchy of contingencies. A temporally consistent plan is extracted from the TPN using a distributed, parallel algorithm that exploits the structure of the TPN. At all stages of the distributed executive, the communication load is spread over all agents, thus eliminating the commu- nication bottleneck. In addition, the distributed algorithms reduce the computational load on each agent and provide op- portunities for parallel processing, thus increasing efficiency.
Subjects: 1.11 Planning; 7.1 Multi-Agent Systems
Submitted: Jun 1, 2006