k-Robust multi-agent path finding Academic Article uri icon


  • Abstract 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 show how to convert a popular optimal MAPF solver–Conflict-Based Search (CBS)–to solve the k-robust MAPF problem. To handle cases where there are more than k unexpected delays, we analyze several execution policies that can complement using a k-robust plan. The proposed algorithms and execution policies are evaluated experimentally, and we discuss their pros and cons. In particular, finding a krobust solution is shown to reduce the overall number of replans needed when executing a plan.

publication date

  • January 1, 2017