Publication

L. Cohen, G. Wagner, D. Chan, H. Choset, N. Sturtevant, S. Koenig and S. Kumar. Rapid Randomized Restarts for Multi-Agent Path Finding Solvers. In Symposium on Combinatorial Search (SoCS), pages 148-152, 2018.

Abstract: 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 rates for given runtime limits. 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* and CBS-CL.Comment: We did not get the polished version of the paper (shown here) submitted in time and thus they published an intermediate version with the same experimental results but less polished text.

Download the paper in pdf.