# Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 36 references that are in the map.
- First posted on arXiv 5 May 2023.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (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)
- [Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search](https://mlsanity.com/paper/2103.07116/) (2021)
- [dRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning](https://mlsanity.com/paper/1903.00994/) (2019)
- [Iterative Refinement for Real-Time Multi-Robot Path Planning](https://mlsanity.com/paper/2102.12331/) (2021)
- [Quick Multi-Robot Motion Planning by Combining Sampling and Search](https://mlsanity.com/paper/2203.00315/) (2022)
- [X*: Anytime Multi-Agent Path Finding for Sparse Domains using Window-Based Iterative Repairs](https://mlsanity.com/paper/1811.12598/) (2018)
- [Rapid Randomized Restarts for Multi-Agent Path Finding Solvers](https://mlsanity.com/paper/1706.02794/) (2017)
- [Two Techniques That Enhance the Performance of Multi-robot Prioritized Path Planning](https://mlsanity.com/paper/1805.01270/) (2018)

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

- [Traffic Flow Optimisation for Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2308.11234/) (2023)
- [Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large Scale Imitation Learning for MAPF](https://mlsanity.com/paper/2409.14491/) (2024)
- [RAILGUN: A Unified Convolutional Policy for Multi-Agent Path Finding Across Different Environments and Tasks](https://mlsanity.com/paper/2503.02992/) (2025)
- [Loosely Synchronized Rule-Based Planning for Multi-Agent Path Finding with Asynchronous Actions](https://mlsanity.com/paper/2412.11678/) (2024)
- [Multi-agent Path Finding for Cooperative Autonomous Driving](https://mlsanity.com/paper/2402.00334/) (2024)
- [Where Paths Collide: A Comprehensive Survey of Classic and Learning-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.19219/) (2025)
- [Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Unassigned Agents](https://mlsanity.com/paper/2509.01022/) (2025)
- [Engineering LaCAM^ast: Towards Real-Time, Large-Scale, and Near-Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2308.04292/) (2023)
- [Anytime Multi-Agent Path Finding with an Adaptive Delay-Based Heuristic](https://mlsanity.com/paper/2408.02960/) (2024)
- [Hybrid Quantum-Classical Multi-Agent Pathfinding](https://mlsanity.com/paper/2501.14568/) (2025)
- [Pathfinding with Lazy Successor Generation](https://mlsanity.com/paper/2408.15443/) (2024)
- [MAPF-World: Action World Model for Multi-Agent Path Finding](https://mlsanity.com/paper/2508.12087/) (2025)
- [Sequence Pathfinder for Multi-Agent Pickup and Delivery in the Warehouse](https://mlsanity.com/paper/2509.23778/) (2025)
- [A Lightweight Traffic Map for Efficient Anytime LaCAM*](https://mlsanity.com/paper/2603.07891/) (2026)
- [CREST: Constraint-Release Execution for Multi-Robot Warehouse Shelf Rearrangement](https://mlsanity.com/paper/2603.28803/) (2026)
- [Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity](https://mlsanity.com/paper/2608.07734/) (2026)
- [A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning](https://mlsanity.com/paper/2608.17928/) (2026)

## Abstract (arXiv)

This study extends the recently-developed LaCAM algorithm for multi-agent pathfinding (MAPF). LaCAM is a sub-optimal search-based algorithm that uses lazy successor generation to dramatically reduce the planning effort. We present two enhancements. First, we propose its anytime version, called LaCAM*, which eventually converges to optima, provided that solution costs are accumulated transition costs. Second, we improve the successor generation to quickly obtain initial solutions. Exhaustive experiments demonstrate their utility. For instance, LaCAM* sub-optimally solved 99% of the instances retrieved from the MAPF benchmark, where the number of agents varied up to a thousand, within ten seconds on a standard desktop PC, while ensuring eventual convergence to optima; developing a new horizon of MAPF algorithms.