Robust distributed coordination of heterogeneous robots through temporal plan networks

Real-world applications of autonomous agents require coordinated groups to work in collaboration. Dependable systems must plan and carry out activities in a way that is robust to failure to and uncertainty. Previous work has produced algorithms that provide robustness at the plan-ning phase, by choosing between functionally redundant methods, and at the execution phase, by dispatching tem-porally flexible plans. However, these algorithms use a centralized architecture in which all computation is per-formed by a single processor. As a result, these imple-mentations suffer from communication bottlenecks at the master processor, require significant computational capa-bilities, and do not scale well. This paper introduces the plan extraction component of a robust, distributed executive for contingent plans. Con-tingent plans are encoded as Temporal Plan Networks (TPNs), which compose temporally flexible plans hier-archically and provide a choose operator. First, the TPN is distributed over multiple agents, by creating a hierar-chical ad-hoc network and mapping the TPN onto this hierarchy. Second, candidate plans are extracted from the TPN with a distributed, parallel algorithm that exploits the structure of the TPN. Third, temporal consistency of the candidate plans is tested using a distributed Bellman-Ford algorithm. This algorithm is empirically validated on randomized contingent plans. Key words: distributed AI; planning; plan execution and monitoring. 1