Publication

S.-H. Chan, Z. Chen, D.-L. Lin, Y. Zhang, D. Harabor, S. Koenig, T.-W. Huang and T. Phan. Anytime Multi-Agent Path Finding Using Operation Parallelism in Large Neighborhood Search. In International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages (in print), 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 (MAPFLNS), 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.

Download the paper in pdf.