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

Titelangaben

Chan, Shao-Hung ; Chen, Zhe ; Lin, Dian-Lun ; Zhang, Yue ; Harabor, Daniel ; Koenig, Sven ; Huang, Tsung-Wei ; Phan, Thomy:
Anytime Multi-Agent Path Finding using Operation Parallelism in Large Neighborhood Search.
In: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems (AAMAS '24). - Richland, SC : International Foundation for Autonomous Agents and Multiagent Systems , 2024 . - S. 2183-2185 . - (ACM Conferences )
ISBN 979-8-4007-0486-4
DOI: https://doi.org/10.5555/3635637.3663101

Volltext

Link zum Volltext (externe URL):

Weitere URLs

Angaben zu Projekten

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.