对比了约束型多智能体路径规划中保守与激进约束的性能差异。
An Analysis of Constraint-Based Multi-Agent Pathfinding Algorithms
- 按约束性质分为保守与激进两类，分析其搜索行为差异。
- 激进约束在高智能体数或高分辨率下求解率更高，保守约束解质量更优。
- 提供决策流程图，适合设计多机器人运动规划算法的研究者参考。
本研究通过约束分类指导未来多智能体路径规划（MAPF）与多机器人运动规划（MRMP）算法的设计。将约束分为保守型（运动约束）与激进型（优先级约束），重点分析了原始冲突基础搜索（CBS）与带优先级的冲突基础搜索（CBSw/P）的搜索行为。在混合网格-路网表示且分辨率可调的场景下发现：随着智能体数量或地图分辨率增加，激进约束形式能解决更多实例；而当两者均成功时，保守约束生成的解质量更高。研究结果被整合为决策流程图，帮助用户根据问题特征选择合适约束。建议扩展至多机器人运动规划，强调需综合考虑拓扑特征与问题、解及表示特征。完整数据与地图表现详见公开仓库：https://GitHub.com/hannahjmlee/constraint-mapf-analysis。
原文摘要 · Abstract (English)
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
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。