Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results. Cohen, L., Koenig, S., Kumar, S., Wagner, G., Choset, H., Chan, D., & Sturtevant, N. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1909–1911, 2018.
abstract   bibtex   
Multi-Agent Path Finding (MAPF) is an NP-hard problem with many real-world applications. However, existing MAPF solvers are deterministic and perform poorly on MAPF instances where many agents interfere with each other in a small region of space. In this paper, we enhance MAPF solvers with randomization and observe that their runtimes can exhibit heavy-tailed distributions. This insight leads us to develop simple Rapid Randomized Restart (RRR) strategies with the intuition that multiple short runs will have a better chance of solving such MAPF instances than one long run with the same runtime limit. Our contribution is to show experimentally that the same RRR strategy indeed boosts the performance of two state-of-the-art MAPF solvers, namely M* and ECBS.
@INPROCEEDINGS{SKoen18k, 
 AUTHOR= "L. Cohen and S. Koenig and S. Kumar and G. Wagner and H. Choset and D. Chan and N. Sturtevant",
 TITLE= "Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results",
 BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
 YEAR= "2018",
 PAGES= "1909--1911",
 PDF= "http://idm-lab.org/bib/abstracts/papers/aamas18a.pdf",
 FLAGS= ":2018:,:svenkoenig:,:lironcohen:,:satishkumar:,:howiechoset:,:glennwagner:",
 ABSTRACT=
"Multi-Agent Path Finding (MAPF) is an NP-hard problem with many real-world
applications. However, existing MAPF solvers are deterministic and perform
poorly on MAPF instances where many agents interfere with each other in a
small region of space. In this paper, we enhance MAPF solvers with
randomization and observe that their runtimes can exhibit heavy-tailed
distributions. This insight leads us to develop simple Rapid Randomized
Restart (RRR) strategies with the intuition that multiple short runs will have
a better chance of solving such MAPF instances than one long run with the same
runtime limit. Our contribution is to show experimentally that the same RRR
strategy indeed boosts the performance of two state-of-the-art MAPF solvers,
namely M* and ECBS."
}

Downloads: 0