Anytime Multi-Agent Path Finding via Large Neighborhood Search

Li, Jiaoyang; Chen, Zhe; Harabor, Daniel; Stuckey, Peter J.; Koenig, Sven

doi:10.24963/ijcai.2021/568

Anytime Multi-Agent Path Finding via Large Neighborhood Search

Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J. Stuckey, Sven Koenig

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4127-4135.

https://doi.org/10.24963/ijcai.2021/568

Keywords

Agent-based and Multi-agent Systems: Multi-agent Planning
Planning and Scheduling: Search in Planning and Scheduling
Robotics: Motion and Path Planning

Abstract

Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for multiple agents. Algorithms for solving MAPF can be categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that can find high-quality solutions for small problems. At the other end are unbounded-suboptimal algorithms that can solve large problems but usually find low-quality solutions. In this paper, we consider a third approach that combines the best of both worlds: anytime algorithms that quickly find an initial solution using efficient MAPF algorithms from the literature, even for large problems, and that subsequently improve the solution quality to near-optimal as time progresses by replanning subgroups of agents using Large Neighborhood Search. We compare our algorithm MAPF-LNS against a range of existing work and report significant gains in scalability, runtime to the initial solution, and speed of improving the solution.

Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J. Stuckey, and Sven Koenig. 2021. Anytime Multi-Agent Path Finding via Large Neighborhood Search. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4127–4135. https://doi.org/10.24963/ijcai.2021/568

@inproceedings{ijcai2021p568,
  title     = {Anytime Multi-Agent Path Finding via Large Neighborhood Search},
  author    = {Li, Jiaoyang and Chen, Zhe and Harabor, Daniel and Stuckey, Peter J. and Koenig, Sven},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {4127--4135},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/568},
  url       = {https://doi.org/10.24963/ijcai.2021/568},
}

TY  - CPAPER
TI  - Anytime Multi-Agent Path Finding via Large Neighborhood Search
AU  - Li, Jiaoyang
AU  - Chen, Zhe
AU  - Harabor, Daniel
AU  - Stuckey, Peter J.
AU  - Koenig, Sven
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4127
EP  - 4135
DO  - 10.24963/ijcai.2021/568
UR  - https://doi.org/10.24963/ijcai.2021/568
ER  -