Distributed Method Selection and Dispatching of Contingent, Temporally Flexible Plans

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 flexible plans, and during their plan extraction phase, by choosing between functionally redundant methods. Previous contingent 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 execution, and state information is returned. This paper introduces a robust, distributed executive for temporally flexible plans. To execute a plan, the plan is first distributed over multiple agents, by creating a hierarchical adhoc 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 Networks (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 communication bottleneck. In addition, the distributed algorithms reduce the computational load on each agent and provide opportunities for parallel processing, thus increasing efficiency