# An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 72 references that are in the map.
- First posted on arXiv 23 Nov 2025.

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

- [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)
- [EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Finding](https://mlsanity.com/paper/2010.01367/) (2020)
- [LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfinding](https://mlsanity.com/paper/2211.13432/) (2022)
- [Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search](https://mlsanity.com/paper/1909.13352/) (2019)
- [Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning](https://mlsanity.com/paper/2006.08845/) (2020)
- [Multi-Goal Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2208.01223/) (2022)
- [LNS2+RL: Combining Multi-Agent Reinforcement Learning with Large Neighborhood Search in Multi-Agent Path Finding](https://mlsanity.com/paper/2405.17794/) (2024)
- [Moving Forward in Formation: A Decentralized Hierarchical Learning Approach to Multi-Agent Moving Together](https://mlsanity.com/paper/2011.02373/) (2020)
- [Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbances](https://mlsanity.com/paper/2012.09052/) (2020)
- [DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies](https://mlsanity.com/paper/2111.06494/) (2021)

## Abstract (arXiv)

This study informs the design of future multi-agent pathfinding (MAPF) and multi-robot motion planning (MRMP) algorithms by guiding choices based on constraint classification for constraint-based search algorithms. We categorize constraints as conservative or aggressive and provide insights into their search behavior, focusing specifically on vanilla Conflict-Based Search (CBS) and Conflict-Based Search with Priorities (CBSw/P). Under a hybrid grid-roadmap representation with varying resolution, we observe that aggressive (priority constraint) formulations tend to solve more instances as agent count or resolution increases, whereas conservative (motion constraint) formulations yield stronger solution quality when both succeed. Findings are synthesized in a decision flowchart, aiding users in selecting suitable constraints. Recommendations extend to Multi-Robot Motion Planning (MRMP), emphasizing the importance of considering topological features alongside problem, solution, and representation features. A comprehensive exploration of the study, including raw data and map performance, is available in our public GitHub Repository: https://GitHub.com/hannahjmlee/constraint-mapf-analysis