Track:
Contents
Downloads:
Abstract:
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.