エージェントが目的地を繰り返し移動し続けるLifelong MAPFにおいて、衝突を回避しながら高いスループットを維持することが求められる。既存のRolling-Horizon Collision Resolution (RHCR) は高品質な解を提供するが、エージェント数の増加に伴い計算コストが指数関数的に増大し、実用的なエージェント数でも適用が困難になる課題がある。また、単純な分散型手法では、エージェント間の相互作用を無視することで、完了までのステップ数が大幅に増加する問題がある。
L-MAPFを割引報酬型マルコフ決定過程 (MDP) として定式化し、RHCRの計画ホライゾンを広げることでその劣最適性が指数関数的に減少することを理論的に証明した。この理論的基盤に基づき、時間的な制約に基づくRHCRに対し、空間的な分割に基づくGroup Decentralized RHCR (GD-RHCR) という新たな並列化の枠組みを提示した。これにより、分散型では得られない理論的な近最適性の保証と、中央集権型を上回るスケーラビリティを両立させた。
エージェント間の最短経路距離に基づき、Union-Findデータ構造を用いて連結成分を特定することでグループ分割を行う。各グループ内で計画の不一致が生じた場合のみ再計算を行う遅延評価を導入して再計画頻度を制御し、他グループとの衝突回避のために前ステップの計画をソフト制約として低レベルプランナーに導入する。さらに、グループサイズが閾値を超えた場合には、計算負荷を抑えるためにPIBTのような高速な二次ソルバーへ動的に切り替える仕組みを備えている。
倉庫型や部屋型などの多様なマップを用い、MAPDおよびL-MAPFの設定でPIBTおよびRHCRと比較した。評価指標として、各タイムステップにおける並列グループの完了までの平均最大時間を計画時間として用いた。実験の結果、warehouse-10-20-10-2-1マップにおいて、RHCRが計算不能になる高密度な状況下でも、PIBTに対して57.7%のスループット向上を達成し、RHCRに近い性能を維持できることを示した。
マップのトポロジーが性能に影響を与え、障害物が少なくグループが巨大化しやすい環境や、マップが小さい場合には、グループが即座にPIBTへ移行するためGD-RHCRの利点が限定的になる。また、マップが二連結でない場合にPIBTへ移行するとデッドロックが発生する可能性がある。今後の課題として、グループ分散化の概念を学習ベースの手法や他のアルゴリズムと統合し、さらなる並列化を実現することが挙げられる。
Lifelong Multi-Agent Path Finding (L-MAPF) において、エージェントが目的地を繰り返し移動しながら衝突を回避する問題に対し、本論文は既存の Rolling-Horizon Collision Resolution (RHCR) フレームワークの理論的性質を解明し、新たな手法を提案している。まず、L-MAPF を割引報酬型マルコフ決定過程 (MDP) として定式化することで、RHCR が理論的に最適解に極めて近いことを証明した。この結果に基づき、エージェントを推移的な通信スキームによって分割し、各グループに対して並列に計画を行う Group Decentralized RHCR (GD-RHCR) を提案している。理論面では、RHCR が時間的な制約に基づくのに対し、GD-RHCR は空間的な分割に基づくという二重性を持ち、両者が共に最適解に対して指数関数的に近い保証を持つことを示した。実験では、GD-RHCR が多様なマップにおいて、計画あたりの計算コストを大幅に抑えつつ、エージェント数の増加に伴って高いスループットを維持できることを示している。
Lifelong MAPF（L-MAPF）は、エージェントが目的地に到着後すぐに次の目的地が割り当てられる継続的な移動を扱う問題であり、衝突を回避しながら高いスループットを維持することが求められる。既存手法のRolling-Horizon Collision Resolution（RHCR）は高いスループットを実現する一方で、エージェント数の増加に伴い計算コストが指数関数的に増大するという課題がある。本研究では、RHCRを割引報酬型マルコフ決定過程としてモデル化し、計画ホライゾンを広げることでRHCRの性能が最適解に指数関数的に収束することを理論的に示した。この理論的基盤に基づき、エージェントを距離に基づいてグループ分割するGroup Decentralized RHCR（GD-RHCR）を提案する。GD-RHCRは、グループごとの独立した計算や非同期な再計画、さらにはグループの規模に応じた異なるMAPFソルバーの割り当てを可能にすることで、RHCRと同等の性能を維持しつつ計算コストを大幅に削減する。実験の結果、GD-RHCRはRHCRと比較して計画時間を短縮し、かつPIBTや計算コストが膨大になったRHCRよりも高いスループットを維持できることが示された。
マルチエージェント経路計画（MAPF）の研究は、理論的な保証を伴う手法と、計算速度を優先する貪欲法に大別されます。CBSやECBSなどの手法は、最適または近最適な解を提供しますが、問題がNP困難であるため、エージェント数の増加に伴い計算時間が膨大になる傾向があります。一方、PBSやPIBT、LaCAMなどの貪欲法は、高いスケーラビリティを持つ反面、理論的な近最適性は保証されません。Lifelong MAPFの設定においても、RHCRのような高品質だが低速な手法と、PIBTのように高速だがグラフの二連連結性に依存してデッドロックが生じ得る手法が存在します。エージェントをグループ化して計算を高速化する試みには、マップを領域分割する静的な手法や、独立したグループを動的に特定する手法がありますが、これらは主に完全性を維持するアルゴリズムの高速化を目的としています。本研究では、局所的な相互作用を扱うLI-MDPという理論モデルに着目しており、可視性に基づいてエージェントを推移的に接続するグループ分散型設定を用いることで、グループ単位での並列計画を可能にしつつ、分散型では得られない理論的な保証を実現します。
本セクションでは、再計画を伴う継続的なマルチエージェント経路計画（RHCR）の計算負荷を軽減するために、手法を並列化する動機が述べられている。RHCRは、一定の計画期間ごとに衝突のない経路を再計算する手法であるが、本研究ではエージェント間の相互作用を空間的な距離の閾値に基づいて無視することで、エージェントを並列なグループに分割する手法を検討している。通信を行わずエージェントが個別に計算を行う単純な分散型手法では、前方のエージェントが動くまで後方のエージェントが動けないといった状況が生じ、中央集権的な手法に比べて完了までのステップ数が大幅に増加する問題がある。これに対し、提案するグループ分散型設定では、エージェントを頂点とし、指定された距離内にあるエージェント間にエッジを張ったグラフを構築し、その連結成分をグループとして定義することで、各グループを独立して計画する。この手法は、Lifelong MAPFをLocally Independent Multi-Agent MDP（LI-MDP）モデルとして定式化することで、性能を大きく損なうことなく並列化を実現できることを示している。
Lifelong Multi-Agent Path Finding (L-MAPF) を、割引報酬を用いた局所相互作用マルコフ決定過程 (LI-MDP) として定式化しています。各エージェントの状態は、現在の位置、直前の移動方向、および目標地点の集合で構成され、報酬関数は目標到達時の正の報酬と、頂点衝突またはエッジ衝突が発生した際の負のペナルティの総和として定義されます。このモデルにおいて、RHCR がある一定の近最適性を備えた軌道生成器であるならば、計画ホライゾンを大きくすることで、その劣最適性は指数関数的に減少することが示されています。この理論的保証は再計画ウィンドウの幅に依存しないため、計算時間を短縮するために再計画の間隔を広げても、理論的な近最適性が維持されることが裏付けられています。さらに、異なるグループに属するエージェント間では一定ステップ内での衝突が起こり得ないという性質を利用し、計算負荷を抑えつつ近最適性を維持できるグループ分散型ポリシーの正当性が、LI-MDP の枠組みを通じて示唆されています。
提案手法であるGroup Decentralized RHCRは、4つの要素から構成される並列的な生涯マルチエージェント経路計画アルゴリズムである。まず、最短経路距離とUnion-Findデータ構造を用いて、各タイムステップでエージェント間の連結成分を特定し、グループ分割を行う。次に、グループ内の全エージェントが同一の計画を参照している間は既存の計画に従い、計画の不一致が生じた場合のみ再計算を行う遅延評価を導入することで、再計画の頻度を動的に制御し、計算負荷を軽減する。また、他グループのエージェントとの衝突を回避するため、前タイムステップの計画に基づいたソフト制約を低レベルプランナーにコストとして導入し、並列計算時の精度を高める。さらに、グループサイズが特定の閾値を超えた場合に、高コストな計算を避けるためPIBTのような高速な二次ソルバーへ即座に切り替える仕組みを備えている。この設計により、混雑が激しい場合に高速なソルバーが活用されるため、従来のRHCRとは異なり、混雑状況に応じて計算効率が向上するという特性を持つ。
本セクションでは、割引報酬MDPとしてモデル化されたL-MAPF問題に対し、GD-RHCRの近最適性を理論的に解析しています。解析を簡略化するため、二次ソルバーやソフト制約コストを用いない設定を想定していますが、これは実用上の計算効率と理論的保証の整合性を考慮したものです。定理によれば、GD-RHCRが生成する軌道の割引報酬の期待値は、空間的な制限（グループ内のエージェントから一定距離外の存在を無視すること）と時間的な制限（依存関係に基づき衝突が起こり得ない時間範囲）の二面性によって規定されます。グループ分散型スキームにおいて、異なるグループに属するエージェントは特定のタイムステップ内では衝突できないため、並列グループごとに計算を行っても解の質に影響を与えず、計算時間を削減できます。この理論的枠組みは、RHCRにおける再計画ウィンドウの設定に加え、提案するグループ分散型並列化スキームや遅延評価スキームの妥当性を裏付けています。
提案手法であるGD-RHCRの性能を、PIBTおよびPIBTをフォールバックとして用いるRHCRと比較するシミュレーションを行いました。実験は、エージェントがランダムな回収・配送地点間を移動するMAPD設定と、ランダムな開けた空間へ目標が割り当てられるL-MAPF設定の2つの環境で行われ、倉庫型や部屋型など多様なマップ構成が用いられています。評価指標として、各タイムステップにおける並列グループの完了までの平均最大時間を計画時間として比較しています。実験の結果、RHCRの性能が崩壊する高密度な状況下でも、GD-RHCRはRHCRに近いスループットを維持できることが示されました。具体的には、warehouse-10-20-10-2-1マップにおいて、RHCRが崩壊した際のピーク時でPIBTに対して57.7%のスループット向上を達成しています。この優位性は、GD-RHCRがエージェントを小さなグループに限定して計画を行うことで、混雑が生じた際も一部のグループがPIBTへ移行しつつ、他のグループの計画を継続できる点に起因します。一方で、マップのトポロジーが性能に影響を与え、障害物が少なくグループが巨大化しやすい環境や、マップが小さい場合には、グループが即座にPIBTへ移行するため、GD-RHCRの利点が限定的になることも確認されました。
本研究では、限定情報マルコフ決定過程の知見を用いることで、リソース制約付き階層的衝突回避に対する理論的基盤を構築しました。この解析手法に基づき、RHCRと同等の理論的保証を満たしつつ、エージェント数が増加した場合でもRHCRより優れた性能を示すグループ分散型RHCR（GD-RHCR）フレームワークを提案しました。今後の展望として、グループ分散化という概念を、学習ベースの手法やPIBTなどの他のアルゴリズムと統合し、並列化を実現することが挙げられます。また、本研究で構築した、異なる場所や設定において異なるアルゴリズムを適用できる構成は、マルチエージェント経路計画における多くの新たな研究方向を切り拓くものです。