Rapid Randomized Restarts for Multi-Agent Path Finding Solvers
Full Text: 17977-78083-1-PB.pdf
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.
Citation
L. Cohen, G. Wagner, D. Chan, H. Choset, N. Sturtevant, S. Koenig, T. Kumar. "Rapid Randomized Restarts for Multi-Agent Path Finding Solvers". Symposium on Combinatorial Search, (ed: Vadim Bulitko, Sabine Storandt), pp 148-152, July 2018.| Keywords: | |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Cohen+al:SoCS18,
author = {Liron Cohen and Glenn Wagner and David M. Chan and Howie Choset and
Nathan R. Sturtevant and Sven Koenig and T.K. Satish Kumar},
title = {Rapid Randomized Restarts for Multi-Agent Path Finding Solvers},
Editor = {Vadim Bulitko, Sabine Storandt},
Pages = {148-152},
booktitle = {Symposium on Combinatorial Search},
year = 2018,
}Last Updated: July 03, 2020Submitted by Sabina P
