k-Robust Multi-Agent Path Finding

In the multi-agent path-finding (MAPF) problem a plan is needed to move a set of agents from their initial location to their goals without collisions. In this paper we introduce and study the k -robust MAPF problem, where we seek a plan that is robust to k unexpected delays per agent. We say that a plan π is k -robust if it does not have any k - delay conflicts. Informally, this means that no conflicts will occur even if some of the agents are delayed by up to k time steps. The problem we address in this paper is how to find optimal sum-of-costs k -robust plans.