Contingent Planning for Robust Multi-Agent Path Finding

Multi-agent Path Finding deals with finding collision-free paths for a set of agents moving in a shared environment. Due to uncertainty during execution, agents might be delayed, which may bring collisions among them. In the paper, we propose using contingent planning to generate plans robust to delays. The initial plan is analyzed to find locations for possible collisions, and alternative paths are planned to divert delayed agents before the collision occurs. This novel concept of robustness guarantees no collisions (until some maximum delay), it does not prolong the execution of plans if the delay does not occur, and it does not significantly extend the planning time.