修复连续时间多智能体路径规划的漏洞，确保找到最优解
Optimal Multi-Agent Path Finding in Continuous Time
- 提出OC-CBS算法，满足精确求解的充分条件
- 实验显示运行效率与原CCBS相当，但能保证最优解
- 为后续算法设计提供可验证的理论框架
连续时间冲突基于搜索（CCBS）是连续时间多智能体路径规划（MAPFR）的精确基准，其正确性保障了众多后续方法的理论基础。然而近期研究发现，CCBS的精确性和解完备性实际上不成立：最优解可能在搜索中被错误移除，导致返回次优解。本文确立了CCBS类算法精确性和解完备性的充分条件，并提出满足这些条件的最优连续时间冲突基于搜索（OC-CBS）。OC-CBS在所有可解的MAPFR实例上均能保证最优解。基准问题上的实验表明，OC-CBS在运行时间上仍保持与CCBS相当的竞争力，同时提供形式化正确性保证。由于OC-CBS可直接替换CCBS，也恢复了依赖于原CCBS正确性的现有方法的理论依据。最后，该框架与正确性标准为未来精确MAPFR求解器的设计与分析提供了通用基础。
原文摘要 · Abstract (English)
Continuous-time Conflict Based Search (CCBS) has been widely used as an exact baseline for Continuous-time Multi-Agent Path Finding (MAPFR), and its correctness guarantees underpin a range of continuation methods built on top of it. Recent work, however, has shown that CCBS's guarantees of exactness and solution completeness do not in fact hold: optimal solutions can be removed from the search, causing the algorithm to return suboptimal solutions. This paper establishes sufficient conditions for exactness and solution completeness in CCBS-style algorithms, and introduces Optimal Continuous-time Conflict-Based Search (OC-CBS) which satisfies these conditions. OC-CBS therefore guarantees an optimal solution on every solvable MAPFR instance. Experiments on benchmark problems show that OC-CBS remains competitive with CCBS in runtime while providing formal correctness guarantees. Because OC-CBS is a drop-in replacement for CCBS, it also restores the theoretical guarantees of existing methods that relied on CCBS's now-invalidated correctness. Finally, the framework and correctness criteria offer a general foundation for analyzing and designing future exact MAPFR solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。