MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search

Authors

  • Jiaoyang Li University of Southern California
  • Zhe Chen Monash University
  • Daniel Harabor Monash University
  • Peter J. Stuckey Monash University
  • Sven Koenig University of Southern California

DOI:

https://doi.org/10.1609/aaai.v36i9.21266

Keywords:

Search And Optimization (SO), Planning, Routing, And Scheduling (PRS), Multiagent Systems (MAS)

Abstract

Multi-Agent Path Finding (MAPF) is the problem of planning collision-free paths for multiple agents in a shared environment. In this paper, we propose a novel algorithm MAPF-LNS2 based on large neighborhood search for solving MAPF efficiently. Starting from a set of paths that contain collisions, MAPF-LNS2 repeatedly selects a subset of colliding agents and replans their paths to reduce the number of collisions until the paths become collision-free. We compare MAPF-LNS2 against a variety of state-of-the-art MAPF algorithms, including Prioritized Planning with random restarts, EECBS, and PPS, and show that MAPF-LNS2 runs significantly faster than them while still providing near-optimal solutions in most cases. MAPF-LNS2 solves 80% of the random-scenario instances with the largest number of agents from the MAPF benchmark suite with a runtime limit of just 5 minutes, which, to our knowledge, has not been achieved by any existing algorithms.

Downloads

Published

2022-06-28

How to Cite

Li, J., Chen, Z., Harabor, D., Stuckey, P. J., & Koenig, S. (2022). MAPF-LNS2: Fast Repairing for Multi-Agent Path Finding via Large Neighborhood Search. Proceedings of the AAAI Conference on Artificial Intelligence, 36(9), 10256-10265. https://doi.org/10.1609/aaai.v36i9.21266

Issue

Section

AAAI Technical Track on Search and Optimization