# Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities

arXiv: https://arxiv.org/abs/2404.16162 · HTML: https://mlsanity.com/paper/2404.16162/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 40 references that are in the map.
- First posted on arXiv 24 Apr 2024.

## Builds on (most cited first, 17 of 17)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [PRIMAL2: Pathfinding via Reinforcement and Imitation Multi-Agent Learning -- Lifelong](https://mlsanity.com/paper/2010.08184/) (2020)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Multi-Agent Path Finding with Delay Probabilities](https://mlsanity.com/paper/1612.05309/) (2016)
- [Multi-Robot Coordination and Layout Design for Automated Warehousing](https://mlsanity.com/paper/2305.06436/) (2023)
- [Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2308.11234/) (2023)
- [Guidance Graph Optimization for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2402.01446/) (2024)
- [Arbitrarily Scalable Environment Generators via Neural Cellular Automata](https://mlsanity.com/paper/2310.18622/) (2023)
- [Toward Efficient Physical and Algorithmic Design of Automated Garages](https://mlsanity.com/paper/2302.01305/) (2023)
- [Anytime Multi-Agent Path Finding using Operation Parallelism in Large Neighborhood Search](https://mlsanity.com/paper/2402.01961/) (2024)
- [X*: Anytime Multi-Agent Path Finding for Sparse Domains using Window-Based Iterative Repairs](https://mlsanity.com/paper/1811.12598/) (2018)
- [Leveraging Experience in Lifelong Multi-Agent Pathfinding](https://mlsanity.com/paper/2202.04382/) (2022)
- [Analysis Of The Anytime MAPF Solvers Based On The Combination Of Conflict-Based Search (CBS) and Focal Search (FS)](https://mlsanity.com/paper/2209.09612/) (2022)

## Built on by (most cited first, 10 of 10)

- [Deploying Ten Thousand Robots: Scalable Imitation Learning for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2410.21415/) (2024)
- [Destination-to-Chutes Task Mapping Optimization for Multi-Robot Coordination in Robotic Sorting Systems](https://mlsanity.com/paper/2510.03472/) (2025)
- [Optimization of Edge Directions and Weights for Mixed Guidance Graphs in Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2602.23468/) (2026)
- [Planning over MAPF Agent Dependencies via Multi-Dependency PIBT](https://mlsanity.com/paper/2603.23405/) (2026)
- [From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding](https://mlsanity.com/paper/2511.21886/) (2025)
- [GRAND: Guidance, Rebalancing, and Assignment for Networked Dispatch in Multi-Agent Path Finding](https://mlsanity.com/paper/2512.03194/) (2025)
- [A Lightweight Traffic Map for Efficient Anytime LaCAM*](https://mlsanity.com/paper/2603.07891/) (2026)
- [Lifelong Multi-Subsystem Pickup and Delivery with Buffer-Limited Handover Stations](https://mlsanity.com/paper/2607.17724/) (2026)
- [Scalable Long-Horizon Planning with Staggered Updates for Lifelong MAPF](https://mlsanity.com/paper/2608.06702/) (2026)
- [Reinforcement Learning for Large-Scale Lifelong Multi-Agent Path Finding with Shared Spatial Fields](https://mlsanity.com/paper/2610.18186/) (2026)

## Abstract (arXiv)

Multi-Agent Path Finding (MAPF) is the problem of moving multiple agents from starts to goals without collisions. Lifelong MAPF (LMAPF) extends MAPF by continuously assigning new goals to agents. We present our winning approach to the 2023 League of Robot Runners LMAPF competition, which leads us to several interesting research challenges and future directions. In this paper, we outline three main research challenges. The first challenge is to search for high-quality LMAPF solutions within a limited planning time (e.g., 1s per step) for a large number of agents (e.g., 10,000) or extremely high agent density (e.g., 97.7%). We present future directions such as developing more competitive rule-based and anytime MAPF algorithms and parallelizing state-of-the-art MAPF algorithms. The second challenge is to alleviate congestion and the effect of myopic behaviors in LMAPF algorithms. We present future directions, such as developing moving guidance and traffic rules to reduce congestion, incorporating future prediction and real-time search, and determining the optimal agent number. The third challenge is to bridge the gaps between the LMAPF models used in the literature and real-world applications. We present future directions, such as dealing with more realistic kinodynamic models, execution uncertainty, and evolving systems.