CBS-Budget (CBSB): マルチエージェント経路探索のための完全かつ有界準最適探索
CBS-Budget (CBSB): A Complete and Bounded Suboptimal Search for Multi-Agent Path Finding
マルチエージェント経路探索において、低レベル探索に予算付きClass-Ordered A*を、高レベル探索に修正焦点探索を用いることで、完全性と有界準最適性を保証しつつ高速化を実現したCBSBを提案。
著者: Jaein Lim, Panagiotis Tsiotras
分類: cs.MA, cs.RO
原文アブストラクト
Multi-Agent Path Finding (MAPF) is the problem of finding a collection of collision-free paths for a team of multiple agents while minimizing some global cost, such as the sum of the time travelled by all agents, or the time travelled by the last agent. Conflict Based Search (CBS) is a leading complete and optimal MAPF solver which lazily explores the joint agent state space, using an admissible heuristic joint plan. Such an admissible heuristic joint plan is computed by combining individual shortest paths found without considering inter-agent conflicts, and which becomes gradually more informed as constraints are added to individual agents' path planning problems to avoid discovered conflicts. In this paper, we seek to speedup CBS by finding a more informed heuristic joint plan which is bounded from above. We first propose the budgeted Class-Ordered A* (bCOA*), a novel algorithm that finds the shortest path with minimal number of conflicts that is upper bounded in terms of length. Then, we propose a novel bounded-cost variant of CBS, called CBS-Budget (CBSB) by using a bCOA* search at the low-level search of the CBS and by using a modified focal search at the high-level search of the CBS. We prove that CBSB is complete and bounded-suboptimal. In our numerical experiments, CBSB finds a near optimal solution for hundreds of agents within a fraction of a second. CBSB shows state-of-the-art performance, comparable to Explicit Estimation CBS (EECBS), an enhanced recent version of CBS. On the other hand, CBSB is easier to implement than EECBS, since only two priority queues at the high-level search are needed as in Enhanced CBS (ECBS).
関連論文
- 双方向情報を用いた垂直展開によるAnyTime Conflict-Based Searchの多目的ノード選択マルチエージェント経路探索
- 超密集環境における未割当エージェントを含む記号計画とマルチエージェント経路探索マルチエージェント経路探索
- PANAMA: デジタルツイン環境におけるネットワーク考慮型マルチエージェント経路探索フレームワークマルチエージェント経路探索
- ニューラルアルゴリズミック推論器で大規模言語モデルを強化するマルチエージェント経路探索マルチエージェント経路探索
- 速度予測とリスク層を考慮した分散型マルチエージェント経路探索A*+Tマルチエージェント経路探索
- 共有探索マップに基づく協調的ハイブリッドマルチエージェント経路探索マルチエージェント経路探索
