# LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding

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

## Key facts

- Cited by 51 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 27 references that are in the map.
- First posted on arXiv 24 Nov 2022.

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

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [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)
- [Priority Inheritance with Backtracking for Iterative Multi-agent Path Finding](https://mlsanity.com/paper/1901.11282/) (2019)
- [Pairwise Symmetry Reasoning for Multi-Agent Path Finding Search](https://mlsanity.com/paper/2103.07116/) (2021)
- [Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search](https://mlsanity.com/paper/1909.13352/) (2019)
- [Iterative Refinement for Real-Time Multi-Robot Path Planning](https://mlsanity.com/paper/2102.12331/) (2021)

## Built on by (most cited first, 30 of 51)

- [POGEMA: A Benchmark Platform for Cooperative Multi-Agent Pathfinding](https://mlsanity.com/paper/2407.14931/) (2024)
- [Improving LaCAM for Scalable Eventually Optimal Multi-Agent Pathfinding](https://mlsanity.com/paper/2305.03632/) (2023)
- [MAPF-GPT: Imitation Learning for Multi-Agent Pathfinding at Scale](https://mlsanity.com/paper/2409.00134/) (2024)
- [Improving Learnt Local MAPF Policies with Heuristic Search](https://mlsanity.com/paper/2403.20300/) (2024)
- [Scaling Lifelong Multi-Agent Path Finding to More Realistic Settings: Research Challenges and Opportunities](https://mlsanity.com/paper/2404.16162/) (2024)
- [Work Smarter Not Harder: Simple Imitation Learning with CS-PIBT Outperforms Large Scale Imitation Learning for MAPF](https://mlsanity.com/paper/2409.14491/) (2024)
- [SRMT: Shared Memory for Multi-agent Lifelong Pathfinding](https://mlsanity.com/paper/2501.13200/) (2025)
- [RAILGUN: A Unified Convolutional Policy for Multi-Agent Path Finding Across Different Environments and Tasks](https://mlsanity.com/paper/2503.02992/) (2025)
- [Advancing MAPF Toward the Real World: A Scalable Multi-Agent Realistic Testbed (SMART)](https://mlsanity.com/paper/2503.04798/) (2025)
- [Advancing Learnable Multi-Agent Pathfinding Solvers with Active Fine-Tuning](https://mlsanity.com/paper/2506.23793/) (2025)
- [Graph Attention-Guided Search for Dense Multi-Agent Pathfinding](https://mlsanity.com/paper/2510.17382/) (2025)
- [Lightweight and Effective Preference Construction in PIBT for Large-Scale Multi-Agent Pathfinding](https://mlsanity.com/paper/2505.12623/) (2025)
- [Tracking Progress in Multi-Agent Path Finding](https://mlsanity.com/paper/2305.08446/) (2023)
- [Destination-to-Chutes Task Mapping Optimization for Multi-Robot Coordination in Robotic Sorting Systems](https://mlsanity.com/paper/2510.03472/) (2025)
- [On Computing Makespan-Optimal Solutions for Generalized Sliding-Tile Puzzles](https://mlsanity.com/paper/2312.10887/) (2023)
- [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)
- [Caching-Augmented Lifelong Multi-Agent Path Finding](https://mlsanity.com/paper/2403.13421/) (2024)
- [ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem](https://mlsanity.com/paper/2404.05223/) (2024)
- [Windowed MAPF with Completeness Guarantees](https://mlsanity.com/paper/2410.01798/) (2024)
- [Layered LA-MAPF: a decomposition of large agent MAPF instance to accelerate solving without compromising solvability](https://mlsanity.com/paper/2410.17160/) (2024)
- [Hybrid Quantum-Classical Multi-Agent Pathfinding](https://mlsanity.com/paper/2501.14568/) (2025)
- [LLMDR: LLM-Driven Deadlock Detection and Resolution in Multi-Agent Pathfinding](https://mlsanity.com/paper/2503.00717/) (2025)
- [Local Guidance for Configuration-Based Multi-Agent Pathfinding](https://mlsanity.com/paper/2510.19072/) (2025)
- [Planning over MAPF Agent Dependencies via Multi-Dependency PIBT](https://mlsanity.com/paper/2603.23405/) (2026)
- [Learning to Communicate Locally for Large-Scale Multi-Agent Pathfinding](https://mlsanity.com/paper/2605.07637/) (2026)
- [Discrete Diffusion for Complex and Congested Multi-Agent Path Finding with Sparse Social Attention](https://mlsanity.com/paper/2605.13296/) (2026)
- [Computing Universal Plans for Partially Observable Multi-Agent Routing Using Answer Set Programming](https://mlsanity.com/paper/2305.16203/) (2023)
- [Optimizing Crowd-Aware Multi-Agent Path Finding through Local Communication with Graph Neural Networks](https://mlsanity.com/paper/2309.10275/) (2023)
- [Pathfinding with Lazy Successor Generation](https://mlsanity.com/paper/2408.15443/) (2024)

## Abstract (arXiv)

We propose a novel complete algorithm for multi-agent pathfinding (MAPF) called lazy constraints addition search for MAPF (LaCAM). MAPF is a problem of finding collision-free paths for multiple agents on graphs and is the foundation of multi-robot coordination. LaCAM uses a two-level search to find solutions quickly, even with hundreds of agents or more. At the low-level, it searches constraints about agents' locations. At the high-level, it searches a sequence of all agents' locations, following the constraints specified by the low-level. Our exhaustive experiments reveal that LaCAM is comparable to or outperforms state-of-the-art sub-optimal MAPF algorithms in a variety of scenarios, regarding success rate, planning time, and solution quality of sum-of-costs.