.png){kind=icon}
.png){kind=icon}
Return
An Analysis of Constraint-Based Multiagent Pathfinding Algorithms
.png){kind=icon}
PRE
AI
DOI：10.1109/TRO.2025.3641865.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This study informs the design of future multiagent pathfinding and multirobot 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 and conflict-based search with priorities. 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 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:
Motion and path planning
path planning for multiple mobile robots or agents
Journal
IF:
10.5
Papers:
3.3K
Citations:
2.8W