Anytime Multi-Agent Path Finding using Operation Parallelism in Large Neighborhood Search
<|reference_start|>Anytime Multi-Agent Path Finding using Operation Parallelism in Large Neighborhood Search: 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 to find good-quality solutions in a scalable way by iteratively destroying and repairing the 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 exploit parallelized hardware to improve the solution quality. We also formulate two variants of parallelism and conduct experimental evaluations. The results show that DROP-LNS significantly outperforms the state-of-the-art and the variants.<|reference_end|>
@article{chan2024anytime,
    title={Anytime Multi-Agent Path Finding using Operation Parallelism in Large
  Neighborhood Search},
    author={Shao-Hung Chan, Zhe Chen, Dian-Lun Lin, Yue Zhang, Daniel Harabor,
  Tsung-Wei Huang, Sven Koenig, Thomy Phan},
    journal={arXiv preprint arXiv:2402.01961},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.01961},
    primaryClass={cs.MA}
}