Anytime Multi-Agent Path Finding using Operation Parallelism in Large Neighborhood Search

Shao-Hung Chan, Zhe Chen, Dian-Lun Lin, Yue Zhang, Daniel Harabor, Sven Koenig, Tsung-Wei Huang, Thomy Phan.
AAAI Conference on Artificial Intelligence (AAAI), pages 9313-9322, 2022.
[bibtex] [pdf] [publisher]

@inproceedings{ChanAAMAS24,
  author    = {Shao-Hung Chan and Zhe Chen and Dian-Lun Lin and Yue Zhang and Daniel Harabor and Sven Koenig and Tsung-Wei Huang and Thomy Phan},
  title     = {Anytime Multi-Agent Path Finding using Operation Parallelism in Large Neighborhood Search},
  booktitle = {Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)},
  year      = {2024}
}

Abstract

Multi-Agent Path Finding (MAPF) is the problem of finding a set of collision-free paths for multiple agents in a shared environment while improving the solution quality. The state-of-the-art anytime MAPF algorithm is based on Large Neighborhood Search (MAPF-LNS), which is a combinatorial search algorithm that iteratively destroys and repairs a subset of collision-free paths. In this paper, we propose Destroy-Repair Operation Parallelism for MAPF-LNS (DROP-LNS), a parallel framework that performs multiple destroy and repair operations concurrently to explore more regions of the search space and improve the solution quality. Unlike MAPF-LNS, DROP-LNS is able to exploit multiple threads during the search. The results show that DROP-LNS outperforms the state-of-the-art anytime MAPF algorithms, namely MAPF-LNS and LaCAM*, with respect to solution quality when terminated at the same runtime.