AAAI

Association for the Advancement of Artificial Intelligence

Home > Proceedings / Proceedings of the International Symposium on Combinatorial Search, 11

Rapid Randomized Restarts for Multi-Agent Path Finding Solvers

Authors

Liron Cohen,Glenn Wagner,David Chan,Howie Choset,Nathan Sturtevant,Sven Koenig,T. K. Kumar

University of Southern California,Carnegie Mellon University,University of Denver,Carnegie Mellon University,University of Denver,University of Southern California,University of Southern California


Proceedings:

Proceedings of the International Symposium on Combinatorial Search, 11

Volume

Issue:

Vol. 11 No. 1 (2018): Eleventh Annual Symposium on Combinatorial Search

Track:

Short Papers

Downloads:

Download PDF

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 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.

DOI:

10.1609/socs.v9i1.18469


SOCS

Vol. 11 No. 1 (2018): Eleventh Annual Symposium on Combinatorial Search