An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms
Hannah Lee, James D. Motes, Marco Morales,, and Nancy M. Amato
AI summary
Problem
Selecting appropriate constraints for constraint-based multi-agent pathfinding is challenging due to varying problem difficulties and representation topologies. Traditional analyses do not generalize well to complex representations like roadmaps used in multi-robot motion planning.
Approach
The study classifies constraints as conservative or aggressive, evaluates vanilla CBS and CBSw/P algorithms across a hybrid grid-roadmap representation at varying resolutions, and synthesizes findings into a decision flowchart for constraint selection.
Key results
- Aggressive constraints improve solvability and runtime efficiency at higher scales
- Conservative constraints yield stronger solution quality when both methods succeed
- Environment topology dictates optimal constraint choice, with open spaces favoring aggressive constraints
- Decision flowchart guides constraint selection based on topology, scale, resolution, and time constraints
Why it matters
Provides actionable guidelines for researchers and practitioners designing or deploying constraint-based pathfinding algorithms in multi-agent and multi-robot systems.
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 clas- sification 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 con- straint) 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 Repository3.