連続時間における最適マルチエージェント経路探索
Optimal Multi-Agent Path Finding in Continuous Time
連続時間マルチエージェント経路探索(CCBS)の完全性・最適性の欠陥を指摘し、厳密性の十分条件を定式化した上で、それを満たすOC-CBSを提案した論文。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ AIが要旨から生成した要約です。正確性は原文をご確認ください。
著者: Alvin Combrink, Sabino Francesco Roselli, Martin Fabian
分類: cs.MA, cs.DM, cs.RO
原文アブストラクト
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.
