Abstract
多エージェント経路探索（MAPF）は、さまざまな分野で重要な役割を果たします。従来のMAPF手法は通常、辺コストが1に等しいこと（単位コスト）および単一タイムステップの行動のみを前提としていますが、これらは現実世界のシナリオへの適用を制限します。MAPFRは、非単位コスト（実数の辺コスト）と連続時間の行動を扱うことでMAPFを拡張しますが、幾何学的衝突モデルにより状態空間が無制限に広がってしまい、ソルバ効率が損なわれます。本論文では、非単位の整数コストをもつグラフ上でのMAPFの新しい変種であるMAPFZを提案します。MAPFZは有限な状態空間を保ちながら、従来の古典的MAPFよりも現実性を高めています。MAPFZを効率的に解くために、時間間隔ベースの衝突検出と改良されたSafe Interval Path Planning（SIPP）アルゴリズムを組み込んだ、強化Conflict-Based Search（CBS）フレームワークであるCBS-NICを開発します。さらに、非単位辺コストのための離散化手法であるBayesian Optimization for Graph Design（BOGD）も提案します。BOGDは、効率と精度のバランスを取りつつ、劣後（regret）の上界がサブリニアであることを保証します。大規模な実験の結果、提案手法は多様なベンチマークシナリオにおいて、実行時間と成功率の両面で最先端手法を上回ることを示しました。
