Abstract:
In a multi-agent path-finding (MAPF) problem, the task is to find a plan for moving a set of agents to their goals without collisions. In the real world, unexpected events may delay some of the agents, and following the intended plan may not
be possible. In this paper, we study the problem of finding a p-robust plan, which is a plan that succeeds with probability at least p, even though unexpected delays may occur. We propose two methods for verifying that a given plan is p-robust and introduce an optimal algorithm and a fast, suboptimal algorithm for finding such a plan. Our experiments show that using a p-robust plan reduces the number of collisions that occur during executions compare to optimal, non-robust plans.
