Publication

S.-H. Chan, Z. Chen, D.-L. Lin, Y. Zhang, D. Harabor, S. Koenig, T-W. Huang and T. Phan. Operation Parallelism in Large Neighborhood Search for Anytime Multi-Agent Path Finding. In IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS), pages 1-7, 2025.

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 minimizing the sum of travel time. Since solving the MAPF problem optimally is NP-hard, anytime algorithms based on Large Neighborhood Search (LNS) are promising for finding good-quality solutions in a scalable manner by iteratively destroying and repairing paths. We propose Destroy-Repair Operation Parallelism for LNS (DROP-LNS), a parallel framework that performs multiple destroy and repair operations concurrently to explore more regions of the search space within a limited time budget. Unlike classic MAPF approaches, DROP-LNS can leverage multi-threading hardware to enhance solution quality. We also formulate two variants of parallelism and conduct experimental evaluations. The empirical results show that DROP-LNS significantly outperforms the leading MAPF-LNS and LaCAM*, as well as other parallelism variants.

Download the paper in pdf.