Robust Execution on Contingent, Temporally Flexible Plans

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 plan extraction phase, by choosing between func-tionally redundant methods, and during their execution phase, by dispatching temporally flexible plans. Previous contingent 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 the plan extraction component of a ro-bust, distributed executive for contingent plans. Contingent plans are encoded as Temporal Plan Networks (TPNs), which use a non-deterministic choice operator to compose tempo-rally flexible plan fragments into a nested hierarchy of con-tingencies. To execute a TPN, the TPN is first distributed over multiple agents, by creating a hierarchical ad-hoc network and by mapping the TPN onto this hierarchy. Second, candi-date plans are extracted from the TPN using a distributed, par-allel algorithm that exploits the structure of the TPN. Third, the temporal consistency of each candidate plan is tested us-ing a distributed Bellman-Ford algorithm. Each stage of plan extraction distributes communication to adjacent agents in the TPN, and in so doing eliminates communication bottlenecks. In addition, the distributed algorithm reduces the computa-tional load on each agent. The algorithm is empirically vali-dated on a range of randomly generated contingent plans.