双方向情報を用いた垂直展開によるAnyTime Conflict-Based Searchの多目的ノード選択

本論文は、Multi-Agent Path Finding (MAPF) の完全アルゴリズムである Conflict-Based Search (CBS) において、高レベルノード選択規則を最適化の対象として扱い、新しいポリシー Dual-Informed Vertical Expansion (DIVE) を提案する。DIVE は、各ダイブを現在の最良境界から開始し、有望な子ノードを追跡して親子の局所性を活用し、インカンベント枝刈りで非生産的な探索を制限する。CBS のノード選択を branch-and-bound の観点から形式化し、トラバーサルポリシーを変更しても完全性に影響しないことを証明する。

従来の CBS では、高レベルノード選択は固定された実装詳細として扱われ、標準的な best-first 選択が一般的に用いられてきた。best-first は展開ノード数を最小化し最適性証明を閉じるのに強いが、フロンティアが大きくなり、親子の展開系列が中断され、終了まで実行可能なインカンベントが得られないという欠点がある。本研究はノード選択を第一級の設計選択として扱い、DIVE を導入することで、ダイブ効率を高めつつ、早期インカンベントとメモリ使用量の削減を実現する点が新しい。

手法の核心は、CBS のノード選択を branch-and-bound のトラバーサルポリシーとして捉え、DIVE を設計したことにある。DIVE は、各ダイブを現在の最良境界 (best-bound) のフロンティアから開始し、ダイブ内では深さ優先的に有望な子を追跡する。また、インカンベント枝刈りを用いて非生産的な探索を制限する。理論的には、トラバーサルポリシーを変更しても完全性が保たれることを証明し、best-first、iterative deepening、DIVE の三極のトレードオフを分析する。

標準的な MAPF ベンチマークを用いた実験により、DIVE の有効性を検証した。実験では、DIVE がダイブの中断回数を一貫して減らし、証明付きギャップを持つ早期インカンベントを提供し、best-first 探索よりもキュー使用メモリを大幅に削減することを示した。また、密な環境やメモリ制限のある環境では、ウォームスタートや単純な応答的変種が有効であることも確認した。

議論としては、DIVE はダイブ効率を重視する一方で、展開ノード数が best-first より増える可能性がある。また、実験は標準ベンチマークに限定されており、より多様な環境での評価が望まれる。理論分析は特定の仮定に基づくため、実際の性能は問題の特性に依存する可能性がある。さらに、DIVE のパラメータ調整や、他の MAPF アルゴリズムへの適用可能性については要旨からは不明である。

要旨で参照されている関連研究として、Conflict-Based Search (CBS) の原論文や、MAPF のベンチマークに関する研究が挙げられる。また、branch-and-bound や anytime 探索に関する一般的な研究も関連する。具体的には、CBS の改良版である Enhanced CBS や、MAPF の anytime アルゴリズムに関する論文が次に読むべき候補となる。