Robust execution of contingent, temporally flexible plans
Stephen A. Block, Andreas F. Wehowsky, Brian Charles Williams · 2006
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.