解决带非单位整数代价的多智能体路径规划问题，兼顾效率与现实性。
Multi-Agent Pathfinding with Non-Unit Integer Edge Costs via Enhanced Conflict-Based Search and Graph Discretization
- 基于时间区间冲突检测和改进SIPP算法，提升路径规划效率
- 在多个基准场景中，求解速度更快且成功率更高
- 适合需要真实成本建模的机器人调度与交通系统
多智能体路径规划（MAPF）在诸多领域具有关键作用。传统方法通常假设边代价为单位值且动作发生在离散时间步，限制了其在现实场景中的应用。MAPFR虽支持实数值边代价和连续时间动作，但其几何碰撞模型导致状态空间无界，影响求解效率。本文提出MAPFZ，一种在非单位整数边代价图上定义的新型MAPF变体，保持有限状态空间的同时提升现实性。为高效求解MAPFZ，我们设计了CBS-NIC框架，融合基于时间区间的冲突检测与改进的安全部分路径规划（SIPP）算法。此外，提出贝叶斯优化图设计（BOGD）方法，对非单位边代价进行离散化，在效率与精度间取得平衡，并具备次线性误差界。大量实验表明，该方法在运行时间和成功率上均优于现有先进方法。
原文摘要 · Abstract (English)
Multi-Agent Pathfinding (MAPF) plays a critical role in various domains. Traditional MAPF methods typically assume unit edge costs and single-timestep actions, which limit their applicability to real-world scenarios. MAPFR extends MAPF to handle non-unit costs with real-valued edge costs and continuous-time actions, but its geometric collision model leads to an unbounded state space that compromises solver efficiency. In this paper, we propose MAPFZ, a novel MAPF variant on graphs with non-unit integer costs that preserves a finite state space while offering improved realism over classical MAPF. To solve MAPFZ efficiently, we develop CBS-NIC, an enhanced Conflict-Based Search framework incorporating time-interval-based conflict detection and an improved Safe Interval Path Planning (SIPP) algorithm. Additionally, we propose Bayesian Optimization for Graph Design (BOGD), a discretization method for non-unit edge costs that balances efficiency and accuracy with a sub-linear regret bound. Extensive experiments demonstrate that our approach outperforms state-of-the-art methods in runtime and success rate across diverse benchmark scenarios.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。