Rapid Randomized Restarts for Multi-Agent Path Finding Solvers


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


Multi-Agent Path Finding (MAPF) is an NP-hard problem that has been well studied in artificial intelligence and robotics. Recently, randomized MAPF solvers have been shown to exhibit heavy-tailed distributions of runtimes, which can be exploited to boost their success rate for a given runtime limit. In this paper, we discuss different ways of randomizing MAPF solvers and evaluate simple rapid randomized restart strategies for state-of-the-art MAPF solvers such as iECBS, M* with highways and CBS-CL.