mlsanityData to 7 Oct 2026

An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms

arXiv 2511.18604 ↗First posted 23 Nov 2025cs.RO cs.AI cs.MAcited by 0

Not on the map. Why?

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

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

Builds on

11 of 72 references.

References · 11

  1. 2019Multi-Agent Pathfinding: Definitions, Variants, and Benchmarkscited by 197
  2. 2018Searching with Consistent Prioritization for Multi-Agent Path Findingcited by 80
  3. 2020EECBS: A Bounded-Suboptimal Search for Multi-Agent Path Findingcited by 67
  4. 2022LaCAM: Search-Based Algorithm for Quick Multi-Agent Pathfindingcited by 50
  5. 2019Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Searchcited by 16
  6. 2020Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planningcited by 13
  7. 2022Multi-Goal Multi-Agent Pickup and Deliverycited by 12
  8. 2024LNS2+RL: Combining Multi-Agent Reinforcement Learning with Large Neighborhood Search in Multi-Agent Path Findingcited by 7
  9. 2020Moving Forward in Formation: A Decentralized Hierarchical Learning Approach to Multi-Agent Moving Togethercited by 4
  10. 2020Scalable and Safe Multi-Agent Motion Planning with Nonlinear Dynamics and Bounded Disturbancescited by 4
  11. 2021DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologiescited by 1

Built on by

Not cited yet.