TY - JOUR
AU - Atzmon, Dor
AU - Stern, Roni
AU - Felner, Ariel
AU - Sturtevant, Nathan R.
AU - Koenig, Sven
PY - 2020/06/01
Y2 - 2021/02/28
TI - Probabilistic Robust Multi-Agent Path Finding
JF - Proceedings of the International Conference on Automated Planning and Scheduling
JA - ICAPS
VL - 30
IS - 1
SE - Main Track
DO -
UR - https://ojs.aaai.org/index.php/ICAPS/article/view/6642
SP - 29-37
AB - <p>In a multi-agent path finding (MAPF) problem, the task is to move a set of agents to their goal locations without conflicts. In the real world, unexpected events may delay some of the agents. In this paper, we therefore study the problem of finding a <em>p</em>-robust solution to a given MAPF problem, which is a solution that succeeds with probability at least <em>p</em>, even though unexpected delays may occur. We propose two methods for verifying that given solutions are <em>p</em>-robust. We also introduce an optimal CBS-based algorithm, called <em>p</em>R-CBS, and a fast suboptimal algorithm, called <em>p</em>R-GCBS, for finding such solutions. Our experiments show that a <em>p</em>-robust solution reduces the number of conflicts compared to optimal, non-robust solutions.</p>
ER -