---
title: "Anytime Multi-Agent Path Finding via Large Neighborhood Search"
authors:
  - "Jiaoyang Li"
  - "Zhe Chen"
  - "Daniel Harabor"
  - "Peter J. Stuckey"
  - "Sven Koenig"
doi: "10.24963/ijcai.2021/568"
url: "https://ijcai.org/proceedings/2021/568"
pdf: "https://ijcai.org/proceedings/2021/0568.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "4127-4135"
track: "Main Track"
keywords:
  - "Agent-based and Multi-agent Systems: Multi-agent Planning"
  - "Planning and Scheduling: Search in Planning and Scheduling"
  - "Robotics: Motion and Path Planning"
---

# Anytime Multi-Agent Path Finding via Large Neighborhood Search

Jiaoyang Li, Zhe Chen, Daniel Harabor, Peter J. Stuckey, Sven Koenig

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 4127-4135. DOI: [10.24963/ijcai.2021/568](https://doi.org/10.24963/ijcai.2021/568)

## Abstract

Multi-Agent Path Finding (MAPF) is the challenging problem of computing collision-free paths for multiple agents. Algorithms for solving MAPF can be categorized on a spectrum. At one end are (bounded-sub)optimal algorithms that can find high-quality solutions for small problems. At the other end are unbounded-suboptimal algorithms that can solve large problems but usually find low-quality solutions. In this paper, we consider a third approach that combines the best of both worlds: anytime algorithms that quickly find an initial solution using efficient MAPF algorithms from the literature, even for large problems, and that subsequently improve the solution quality to near-optimal as time progresses by replanning subgroups of agents using Large Neighborhood Search. We compare our algorithm MAPF-LNS against a range of existing work and report significant gains in scalability, runtime to the initial solution, and speed of improving the solution.