非同期アクションを用いたマルチエージェント・パスファインディングのための衝突ベース探索（CBS）

要旨: Multi-Agent Path Finding (MAPF) は、それぞれの開始地点からそれぞれのゴール地点へと、衝突のない経路を見つけつつ、経路コストを最小化することを目的とします。ほとんどの既存のMAPFアルゴリズムは、すべてのエージェントの行動が同時に開始され、常に1つの時間単位を要するという、同期アクションという共通の仮定に依存しています。これは、実際のMAPFプランナーの利用を制限する可能性があります。この仮定を取り除くために、連続時間衝突ベース探索 (CCBS) は、非同期アクションを持つMAPF（MAPF-AA）に対して最適解を見つけることができる一般的な手法です。しかし、CCBSは、待機時間が連続的であることにより生じる無限の状態空間のため、最近不完全であると指摘されています。本論文は、この理論的問題を回避し、完全性と解の最適性保証を備えたMAPF-AAを解くことができる新しい手法 Conflict-Based Search with Asynchronous Actions (CBS-AA) を提案します。CBS-AAを基盤として、CBS-AAのスケーラビリティをさらに向上させるための衝突解決技術も開発します。我々のテスト結果は、提案手法が分岐の数を最大で90%削減できることを示しています。