Rapid Randomized Restarts for Multi-Agent Path Finding Solvers

Autor: Liron Cohen, Glenn Wagner, David Chan, Howie Choset, Nathan Sturtevant, Sven Koenig, T. K. Kumar
Rok vydání: 2021
Zdroj: Proceedings of the International Symposium on Combinatorial Search. 9:148-152
ISSN: 2832-9163
2832-9171
DOI: 10.1609/socs.v9i1.18469
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: