Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results

Liron Cohen (University of Southern California), Sven Koenig (University of Southern California), T. K. Satish Kumar (University of Southern California), Glenn Wagner (Carnegie Mellon University), Howie Choset (Carnegie Mellon University), David Chan (University of Denver), Nathan Sturtevant (University of Denver)

Abstract

Multi-Agent Path Finding (MAPF) is an NP-hard problem with many real-world applications. However, existing MAPF solvers are deterministic and perform poorly on MAPF instances where many agents interfere with each other in a small region of space. In this paper, we enhance MAPF solvers with randomization and observe that their runtimes can exhibit heavy-tailed distributions. This insight leads us to develop simple Rapid Randomized Restart (RRR) strategies with the intuition that multiple short runs will have a better chance of solving such MAPF instances than one long run with the same runtime limit. Our contribution is to show experimentally that the same RRR strategy indeed boosts the performance of two state-of-the-art MAPF solvers, namely M* and ECBS.