Multi-Dependency PIBTによるエージェント依存関係を考慮したMAPFの計画

要旨: 現代のマルチエージェント経路探索（MAPF）アルゴリズムは、混雑した環境で数百から数千のエージェントを1秒以内に計画する必要があり、非常に効率的なアルゴリズムが求められます。優先度継承付きバックトラッキング（Priority Inheritance with Backtracking; PIBT）は、そのような状況で効果的に計画できることで知られる人気のアルゴリズムです。しかし、PIBTはルールベースの計画手続きに制約があり、少なくとも1体の他のエージェントと衝突する可能性を高々1体に制限するような経路に探索を限定するため、一般性に欠けます。この制限は、PIBTの最近の拡張であるEnhanced PIBT（EPIBT）にも当てはまります。本論文では、エージェント間の依存関係を考慮して計画することでMAPFを解く新しい視点を述べます。PIBTの優先度継承ロジックから着想を得て、エージェント依存関係の概念を定義し、エージェント依存関係を探索するMulti-Dependency PIBT（MD-PIBT）を提案します。MD-PIBTは汎用的な枠組みであり、特定のパラメータ化によってPIBTおよびEPIBTを再現できます。同時に、異なる構成では、PIBTやEPIBTでは表現できない新しい計画戦略が得られます。実験により、MD-PIBTは、ペブル移動、回転移動、速度・加速度制限を持つディファレンシャルドライブロボットなど、さまざまな運動学的拘束（kinodynamic constraints）のもとで、最大1万体の同種エージェントを効果的に計画できることを示します。異なるMAPFのバリアントに対して徹底的な評価を行った結果、MD-PIBTは大規模なエージェントを扱うMAPFにおいて特に有効であることがわかりました。