多数のロボットが衝突を避けながら目的地へ到達する経路を計算するマルチエージェント経路探索（MAPF）を対象とする。従来の多くの手法は、実行前に全経路を決定するオープンループ形式の探索問題として扱われてきた。しかし、実環境では移動の遅延や目標の変更といった不確実性が伴うため、計画と実行を分離して扱う従来のモデルでは、動的な変化への対応や継続的な運用に困難が生じる。
従来の計画と実行が分離したモデルに対し、コントローラ、アクチュエータ、環境の3要素からなる、計画と実行を単一のフィードバックループ内で扱う「MAPFシステム」という統一的なモデルを提案する。また、後退水準制御の考え方を取り入れ、有限の予測期間に基づき問題を階層的に分解するFICOアルゴリズムを導入する。これにより、分解とクローズドループな実行を体系的に統合している。
FICOは、kステップの先読み計画を立て、その最初の1ステップのみを実行しては状態を更新し再計画を行う有限ホライゾン制御を用いる。処理は二段階の因数分解スキームで行われる。まず、空間ハッシュを用いて衝突が発生するエージェントを検出し、衝突フリーなエージェントを分離して固定する。次に、残りの衝突が発生するエージェントを、ホライゾン内の到達可能領域に基づいてグループ化し、並列に計画を行う。各グループの計画は、分解互換性を維持しながら、優先度の高いエージェントや固定されたエージェントと衝突しないように構成される。計画が困難な場合は、近傍の高優先度エージェントをグループに含めて制約を緩和する混雑解消プロセスを実行する。また、動的計画法を用いたタイブレーク手法により、最短経路の分布を均一化する。
単発および生涯（lifelong）のMAPF、および大規模な倉庫ベンチマークを用いて評価を行った。比較手法として、オープンループ手法やPIBTなどのクローズドループ手法を用いた。評価指標には、移動コストの総和（SOC）およびスループットを用いた。結果として、FICOは実行応答時間においてオープンループ手法を最大で2桁高速化し、SOCにおいてもPIBTより優れた結果を示した。生涯MAPFでは、PIBTよりも高いスループットを記録し、実行遅延やエージェントの追加といった不確実な環境下でも、オープンループ手法を大幅に上回るアイテム配送数を実現した。
本手法は、有限の予測期間（ホライゾン）を設定することで計算量と実行可能性のバランスを取っている。今後の課題として、FICOのモジュール構造を利用して既存のMAPFアルゴリズムを閉ループ型へ拡張するFICO+の開発が挙げられる。また、フィードバックや不確実性、継続的な運用をより明示的に考慮した新しいベンチマークおよび評価指標の設計が必要である。さらに、マルチロボット操作や混合自律交通システムといった、より広範な領域への応用が検討されている。
本論文は、マルチエージェント経路探索（MAPF）において、計画と実行を統合し、不確実性を明示的にモデル化するシステムレベルのフレームワークを提案している。提案手法の核となるFICO（Finite-Horizon Closed-Loop Factorization）は、後退ホライゾン制御に着想を得た分解ベースのアルゴリズムであり、有限ステップの先読みを行うことで、構成的な構造を利用した効率的なクローズドループ動作を実現する。この手法は、数千規模のエージェントに対してもスケーラビリティを持ち、実行時の不確実性に対してミリ秒単位でのリアルタイムな応答が可能である。実験の結果、FICOはオープンループのベースラインと比較して計算時間を最大で2桁削減し、エージェントの到着や確率的な遅延が発生する環境下においても、大幅に高いスループットを達成することを示している。
マルチエージェント経路計画（MAPF）は、多数のロボットが衝突を避けながら目的地へ到達する経路を計算する問題であり、従来の多くの手法は実行前に全経路を決定するオープンループ形式の探索問題として扱われてきました。しかし、実環境では遅延や目標の変更といった不確実性が伴うため、本論文では計画と実行を単一のフィードバックループ内で統合する「MAPFシステム」というシステムレベルのモデルを提案しています。このモデルに基づき、後退水準制御の考え方を取り入れたFICOという閉ループアルゴリズムを導入しており、これは有限の予測期間に基づき、空間的・時間的な到達可能性に応じて問題を階層的に分解する二段階の因数分解スキームを用いています。この因数分解により、大規模な問題でも並列計算が可能となり、実行開始までの時間を15ミリ秒以内に抑えつつ、オープンループ手法と比較して計算時間を削減し、不確実な環境下でのスループットや配送効率を向上させています。実験では、古典的な一回限りの問題から、動的な目標変更を伴うライフロングMAPF、大規模な倉庫ベンチマークまで幅広く評価されており、FICOが計算速度、スケーラビリティ、および堅牢性のバランスにおいて優れた性能を示すことが確認されています。
マルチエージェント経路探索（MAPF）の研究は、単一の開始地点と目標地点を扱う単発的な設定から、継続的なタスクを扱うライフロングMAPF、実行時の不確実性への対応、そしてスケーラビリティ向上のための分解や並列化へと発展してきた。単発MAPFにおいて、全エージェントの配置を一つの状態として扱う結合状態空間の探索は、エージェント数や行動の選択肢の増加に伴い計算量が指数関数的に増大するため、最適または準最適な手法であってもNP困難性の問題に直面する。ライフロングMAPFでは、オンラインで次々と与えられる目標に対応するため、単発の計画を繰り返し実行する手法や、一定の予測期間のみを計画するウィンドウ化手法、あるいは軌道を事前に計算せず逐次的に移動を決定するPIBTのような手法が提案されている。実行フェーズにおける動作の遅延などの不確実性に対しては、事前に計算された計画に待機動作を挿入するような事後処理的な対応が一般的だが、これらは計画と実行が分離しているため、ライフロングの設定や未知の不確実性への汎用性に課題がある。また、スケーラビリティ向上のための分解手法は、エージェント間の強い結合により完全な独立性を保つことが難しく、既存の枠組みでは分解とクローズドループな実行を体系的に統合できていない。
本セクションでは、マルチエージェント経路探索（MAPF）における古典的な探索モデルを、一括処理型のOne-shot MAPFと、目標が逐次的に与えられるLifelong MAPFの2つの形式で定義しています。One-shot MAPFは、全エージェントの開始地点と目標地点が事前に固定されており、全ての頂点衝突およびエッジ衝突を回避する一連の軌跡をオフラインで一括計算するタスクです。このモデルにおける解の評価指標には、全エージェントの軌跡の共通長であるMakespanと、全エージェントの移動コストの総和であるSum of Cost (SOC)が用いられます。一方、Lifelong MAPFは、エージェントが目標を達成するたびに次の目標が提示される継続的なシナリオを想定しており、固定された時間地平内でどれだけの目標を達成できたかを示すThroughput（スループット）によって解の質が評価されます。いずれのモデルも、実行中の環境からのフィードバックを計画プロセスに組み込まない探索モデルに基づいているため、Lifelong MAPFにおいても、将来の目標が未知である中でウィンドウ分割などの手法を用いて繰り返し探索を行うといった制約が生じます。
本セクションでは、従来のマルチエージェント経路探索（MAPF）を、計画と実行が相互作用する動的な制御ループとして捉える「MAPFシステム」という統一的なモデルを提案している。このモデルは、移動コマンドを発行するコントローラ、不確実性の中でコマンドを実行するアクチュエータ、および状態やインスタンスを更新する環境の3つの構成要素で定義される。コントローラは、事前に全経路を決定するオープンループ型と、各ステップのフィードバックに基づき逐次的に決定するクローズドループ型に分類される。アクチュエータは、確率的な遅延によって計画通りの移動が妨げられる不完全な実行をモデル化でき、環境はエージェントの動的な追加や目標の更新といった変化を包含できる。このフレームワークを用いることで、従来のOne-shot MAPF、Lifelong MAPF、およびMAPF-DPといった異なる問題設定を、アクチュエータや環境の性質、および終了条件の差異として単一の形式で統合して扱うことが可能となる。
FICOは、マルチエージェント経路探索（MAPF）を制御理論の再帰的ホライゾン制御の枠組みで捉え直し、計算効率と頑健性を両立させた閉ループ型アルゴリズムである。本手法は、全エージェントがゴールに到達するまでの無限ステップの計画を立てる従来のオープンループ型手法とは異なり、有限のステップ数であるkステップの先読み計画を立て、その最初の1ステップのみを実行しては状態を更新し再計画を行う。この有限ホライゾン化により、エージェント間の相互作用を限定的な範囲に抑えることが可能となり、大規模な問題でも計算量を抑えつつ、局所的な混雑を回避できる。
アルゴリズムの核となるのは、階層的な分解と、分解可能であることを保証する「分解互換性のある軌跡」の概念である。まず、空間ハッシュを用いて他者と干渉しない衝突フリー（CF）エージェントを分離して固定し、次に残りの衝突（C）エージェントを到達可能性に基づきグループ化して並列に計画を行う。各グループの計画は、優先度の高いエージェントやCFエージェントの軌跡と衝突しないよう、分解互換性を維持しながら実行される。もしグループ内で実行可能な計画が見つからない場合は、混雑解消プロセスとして、近傍の高優先度エージェントをグループに含めて制約を緩和し、計画の実現可能性を確保する。また、個別の計画段階では、動的計画法を用いて最短経路の分布を均一化するタイブレーク手法を用いることで、エージェント間の意図しない衝突確率を低減させている。
FICOの評価実験では、単発および生涯（lifelong）のマルチエージェント経路探索（MAPF）における性能、各構成要素の寄与、および不確実性下での堅牢性が検証されています。単発MAPFにおいて、FICOは実行応答時間（ERT）でオープンループ手法を大幅に上回る高速性を実現しつつ、解の質（SOC）ではクローズドループ手法のPIBTよりも優れた結果を示し、応答性と質のバランスが取れた性能を達成しています。生涯MAPFの評価では、FICOはPIBTよりも一貫して高いスループットを記録し、特にエージェントが密集する環境や10,000エージェント規模のケースでその優位性が顕著になります。アブレーション研究により、並列計算による高速化、一様性を保つバランスの取れたタイブレーク手法による解の質の向上、および計画ホライゾン（先読み期間）の調整が性能に直結することが示されました。また、実行遅延やエージェントの追加といった不確実性が存在する環境下でも、FICOはオープンループ手法のような頻繁な再計画による遅延を避けつつ、PIBTよりも高いスループットを維持できることが確認されています。
本論文では、計画と実行をフィードバックループ内で統合する実行認識型の統一モデルと、後退水準制御に着想を得た閉ループ分解アルゴリズムであるFICOを提案している。FICOは、有限の予測期間における先読みと二段階の分解手法を組み合わせることで、MAPFの構成的な構造を活用し、スケーラビリティ、応答性、および堅牢性を実現している。一回限りの計画、生涯継続的な運用、および不確実性を考慮した設定における実験の結果、FICOはリアルタイムの応答性を維持しながら、競争力の高い解の質を達成することが示された。今後の展望として、FICOのモジュール構造を利用して既存のMAPFアルゴリズムを閉ループ型へ拡張するFICO+の開発や、フィードバックや不確実性、継続的な運用を明示的に考慮した新しいベンチマークおよび評価指標の設計が挙げられる。さらに、マルチロボット操作や混合自律交通システムといったより広範な領域への応用も検討されている。