Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results
Full Text: 3237383.3238020.pdf
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.
Citation
L. Cohen, S. Koenig, T. Kumar, G. Wagner, H. Choset, D. Chan, N. Sturtevant. "Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results". Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), (ed: Elisabeth André, Sven Koenig, Mehdi Dastani, Gita Sukthankar), pp 1909-1911, July 2018.| Keywords: | |
| Category: | In Conference |
| Web Links: | ACM Digital Library |
BibTeX
@incollection{Cohen+al:AAMAS18,
author = {Liron Cohen and Sven Koenig and T.K. Satish Kumar and Glenn Wagner
and Howie Choset and David M. Chan and Nathan R. Sturtevant},
title = {Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary
Results},
Editor = {Elisabeth André, Sven Koenig, Mehdi Dastani, Gita Sukthankar},
Pages = {1909-1911},
booktitle = {Joint Conference on Autonomous Agents and Multi-Agent Systems
(AAMAS)},
year = 2018,
}Last Updated: July 05, 2020Submitted by Sabina P
