An Analysis of Constraint-Based Multiagent Pathfinding Algorithms
Open Access
- 9 December 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Robotics
- Vol. 42 (15523098) , 362-381
Abstract
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.Keywords
All Related Versions
Funding Information
- National Science Foundation Graduate Research Fellowship (2020297899)
- U.S. National Science Foundation's “Expeditions: Mind in Vitro (IIS-2123781)
- IBM-Illinois Discovery Accelerator Institute and the Center for Networked Intelligent Components and Environments
- University of Illinois
This publication has 66 references indexed in Scilit:
- Conflict-based search with D* lite algorithm for robot path planning in unknown dynamic environmentsComputers and Electrical Engineering, 2022
- Multi-agent path finding with mutex propagationArtificial Intelligence, 2022
- Multi-agent pathfinding with continuous timeArtificial Intelligence, 2022
- Multi-agent Path Finding with Kinematic Constraints via Conflict Based Search2020
- Conflict-based search for optimal multi-agent pathfindingArtificial Intelligence, 2015
- Subdimensional expansion for multirobot path planningArtificial Intelligence, 2015
- The increasing cost tree search for optimal multi-agent pathfindingArtificial Intelligence, 2013
- A faster algorithm for betweenness centrality*The Journal of Mathematical Sociology, 2001
- A Probabilistic Approach to Collaborative Multi-Robot LocalizationAutonomous Robots, 2000
- Theory of Automatic Robot Assembly and Programming1993