マルチエージェント経路探索（MAPF）は、共有環境内の複数エージェントを衝突させずにそれぞれの目標へ到達させる問題である。自動倉庫や製造だけでなく、交通交差点の調整や空港地上運用など、大規模なロボットシステムの基盤として利用される。従来のMAPFソルバは、離散時間と簡略化されたロボットモデルを使い、経路長の総和やメイクスパンなどの離散目的を最適化する。しかし実世界では、ロボットごとの運動性能、蓄積遅延、通信、低レベル制御、共有場所での相互作用が計画からのずれを生み、離散モデルで良い計画が壁時計時間でも良いとは限らない。
第一の貢献は、離散MAPF解から各動作の実現完了時刻と終了時のキノダイナミック状態を予測する学習型世界モデルExecTimeNetである。第二に、その予測をMAPF探索中に利用して実行性能の高い解を探すREMAPを提案する。第三に、経路の実行可能性を保ったまま、共有場所におけるエージェント間の通過順序を最適化する計画後処理ESADGを導入する。さらに、予測器を必要な場面で選択的に呼び出す適応的ゲーティングにより、REMAPの予測オーバーヘッドを抑える。これらは、詳細なロボットモデルを計画探索へ直接組み込む方法と、実行を無視した離散計画との間を、学習型実行予測とスケジュール最適化で橋渡しする。
ExecTimeNetは、離散MAPF解から構成されるAction Dependency Graph（ADG）を入力とし、同一エージェント内の動作列と、共有場所で生じるエージェント間依存を同時に扱う。各ノードには、エージェント経路上の動作位置、Type-2エッジの入次数と出次数、同じエージェントにおける前後の並進・回転動作の累積数、他エージェントの動作をブロックする出力エッジの有無などを与える。エージェントごとの系列を重み共有の3層一方向LSTMで処理し、その表現を3層のGATv2グラフ注意層へ渡して、エージェント間の依存関係に沿った空間的文脈を集約する。モデルは各動作の完了時刻と実行状態を予測し、真の実行時間を計画時に利用できないため、REMAPはその予測を代理目的としてCBSおよびMAPF-LNSの探索へ組み込む。適応的ゲーティングは予測呼び出しの価値を判断し、タイムアウト時には既知の最良解を返す。ESADGは計画後に切替可能なType-2エッジの向きを反転する候補を評価し、ADGの非巡回性を維持することでデッドロックのない実行を保つ。
評価には、連続的なロボット運動、低レベル制御、ネットワーク通信、エージェント間相互作用をモデル化する物理ベースのSMARTシミュレータと実ロボットが用いられた。シミュレーションでは、MovingAI Benchmarkから変換したempty、maze、random、room、den312d、WH-S、WH-L、bostonの8マップを使い、各マップ25インスタンス、最大300エージェントまでを評価した。ExecTimeNetの学習には6マップ上でMAPF-LNSが生成した、エージェント数10から300までの解を用い、反復ごとの解を保存して合計28,177グラフを収集した。モデルは分布内データと分布外データで評価され、未知のマップとエージェント数への転移、ならびに特徴量のアブレーションも調べられた。実機検証も行われたが、提示された抜粋だけでは全ベースラインの名称、実機の台数と構成、完全な指標表は確定できない。
シミュレーションでは、REMAPがベースラインに対して遅延を最大21％削減し、ESADGが最大40％の正規化改善を達成した。実機では、全パイプラインが総実行時間を最大15.3％削減し、シミュレーションで学習・評価した仕組みを実環境へ移せる可能性を示した。これらの結果は、予測が完全でなくても、計画時の選択と実行順序の調整が有効であり得ることを示唆する。一方、MAPF計画だけからは観測できない物理的要因があるため、実行時間予測には誤差が残る。実機の校正データは実験室の制約により100回の実行に限られており、論文が示す将来課題は、より多様な実行認識目的と、より広いロボットプラットフォームへの拡張である。
標準的なMAPFは無向グラフ上で定義され、各エージェントに開始頂点と目標頂点を与え、均一な離散時間ステップで経路を表す。妥当な解は、同じ時刻に2体が同じ頂点を占有する頂点衝突と、同じ辺を反対方向へ通過する辺衝突を避ける。CBSは制約を追加しながら衝突を解消し、LNSは実行可能解から一部のエージェントを反復的に再計画する。実行時にはADGなどが離散経路を実行可能なスケジュールへ変換し、共有場所の通過順序を表す。
離散計画では、動作が一定の時間単位で完了し、ロボットが理想化された状態遷移に従うと仮定されることが多い。実際には、速度、加速度、角速度、過去の動作からの遅延、通信、共有場所での待機が各動作の完了時刻を変える。あるロボットの遅延は依存関係を通じて別のロボットへ伝播し、長い依存鎖のメイクスパンを悪化させ得る。したがって課題は、衝突のない経路を見つけるだけでなく、その経路が物理システムでどう実行されるかを予測し、改善することである。
ExecTimeNetは、エージェント内の時間的依存を処理する系列エンコーダと、エージェント間依存を処理するグラフ注意機構を組み合わせる。入力特徴には、動作順序、Type-2依存の次数、前後の並進・回転動作数、他エージェントをブロックするかどうかが含まれる。REMAPは計画時に利用できない真の実行時間の代わりに、ExecTimeNetの予測を代理目的として使う。ESADGは経路自体を変えずに共有場所の優先順位を変更し、ADGの非巡回性を守る。
SMARTでは、倉庫ロボットで一般的な運動モデルに従い、ロボットは現在の向きに沿って並進し、方向転換はその場で回転して行う。各インスタンスには開始・目標ペアと、相関のある分布からサンプリングされたエージェントごとの最大線速度、線加速度、最大角速度が設定された。ExecTimeNetの学習データは6マップ上のMAPF-LNS解から収集され、各反復時点の解を含む。評価には未知のマップとエージェント数、特徴量アブレーション、実機検証が含まれるが、抜粋には実機の全条件や比較手法の完全な実装情報はない。
ExecTimeNetは実行情報を正確に予測し、未知のマップとエージェント数へ転移したと報告されている。多様な地形のシミュレーションで、REMAPは遅延をベースラインより最大21％削減し、ESADGは最大40％の正規化改善を達成した。実機では、全パイプラインが総実行時間を最大15.3％削減した。これらは「最大」の値であり、平均、中央値、または常に保証される改善率だとは提示情報から判断できない。
本論文は、離散MAPF計画を現実的な実行性能へ接続する世界モデル駆動型の枠組みを提示した。ExecTimeNetが依存構造から実行時間と状態を予測し、REMAPが探索中の選択を、ESADGが計画後の実行順序を改善する。シミュレーションと実機の結果は、離散目的だけに基づく方法より実行性能を改善できるという主張を支持する。締切付きMAPFも実行認識最適化の例として扱われ、予測された壁時計到着時刻を考慮することで、実用的な時間制約下の性能を改善できることが示された。
予測器は、MAPF計画から得られない物理的な実行変動要因のために誤差を持ち得る。実機の校正データは実験室の制約により100回の実行に限られたが、実運用で得られる大規模なログは追加の微調整に利用できる可能性がある。提示された抜粋からは、多様なロボットプラットフォーム、深刻な通信障害、動的障害物、明示的な計算時間上限に対する挙動は確定できない。したがって、報告された改善率が未検証のハードウェアや条件へどの程度一般化するかは判断できない。
離散目的に関して優れたMAPF解でも、ロボットごとの速度差、共有場所での待機、遅延の蓄積によって、実際の完了時間が悪化し得る。そのため、計画と実行を壁時計時間という共通の性能軸で扱うことは、MAPFを実運用へ移すうえで重要である。本手法は、詳細な運動モデルをすべて探索へ直接組み込むことによる計算量増大を避けながら、実行予測を使って計画とスケジュールを補正する方向を示す。最大300エージェントの現実的なシミュレーションと実機の双方で評価している点は、実環境向けMAPF研究にとって有用である。
離散MAPFの解品質とロボット群の実際の完了時間との差に関心がある研究者に適している。MAPF、CBS、LNS、ADG、学習型世界モデル、実行スケジューリング、倉庫ロボット、締切付きMAPFを研究する読者にも有益である。既存の探索ソルバを実行認識目的へ拡張したい場合はREMAPと適応的ゲーティングを、計画後の協調を扱いたい場合はESADGの通過順序最適化を参照できる。ただし、完全な実機仕様、全ベースラインの定義、広範な機種横断評価を必要とする読者には、提示された抜粋だけでは情報が不足している。