マルチエージェント経路計画（MAPF）は、複数のエージェントが衝突を避けながら各々の目的地へ到達する経路を求める問題である。エージェント数や混雑度が増すと計算量が指数関数的に増加するため、一定の期間（窓）のみを計画する窓付き手法が用いられる。しかし、多くの窓付き手法は理論的な完全性を欠いており、局所的な判断によってデッドロックやライブロックが発生するという課題がある。既存の完全性を保証するWinC-MAPFフレームワークは、窓内の最適解を求めるソルバーを必要とするため、高密度な環境では計算コストが膨大になる。
従来のWinC-MAPFは完全性を維持するために窓内の最適解を求める必要があったが、本研究は有界劣最適ソルバーを用いても完全性を維持できることを示した。各エージェントグループの解が個別にw-劣最適性を維持することを保証することで、従来の窓付きECBSでは困難だった完全性の証明を可能にしている。これにより、完全性の保証を持たない手法よりも高い成功率を実現し、最適解を求める手法よりも優れたスケーラビリティを提供している。
DAG-ECBSは、エージェントを動的なグループとして管理し、各グループの窓内解がw-劣最適であることを保証しながら計画を行う。まず、各エージェントを個別のグループとして初期化する。次に、各グループに対してGroup-ECBSを実行して窓内の経路を求める。計画されたグループ間で衝突が発生した場合、それらのグループを統合して新たなグループとして再投入し、衝突がなくなるまでこのプロセスを繰り返す。Group-ECBSでは、低レベルおよび高レベルの探索において、ヒューリスティックのペナルティを考慮した修正版のFocal探索を用いる。これにより、エージェント間の相互作用に応じてグループ化が動的に変化しつつ、各グループのヒューリスティックがw-許容であることを維持する。
標準的なベンチマークマップを用い、DAG-ECBS、完全性を保証する最適解法であるSS-CBS、および完全性の保証がないwindowed ECBSと比較した。実験の結果、DAG-ECBSはSS-CBSよりも優れたスケーラビリティを示し、windowed ECBSと比較して、窓サイズが小さい場合や混雑したマップにおいて高い成功率を達成した。また、非最適性の許容度wを大きく設定することで、1イテレーションあたりの実行時間を一貫して短縮できることが確認された。
DAG-ECBSは、混雑の少ない大規模なマップにおいて、計算時間の増大によりタイムアウトが発生しやすい傾向がある。また、ウィンドウサイズを大きくすると1イテレーションあたりの実行時間が増加し、その影響はDAG-ECBSにおいてより顕著に現れる。非最適性の許容度を上げると実行時間は短縮されるが、解のコストが増加するというトレードオフが存在する。今後の課題として、より高度な有界劣最適アルゴリズムへの適用や、分散型アルゴリズムへの拡張が挙げられる。
本研究は、部分的な経路計画を行う窓付きマルチエージェント経路探索（WinC-MAPF）の枠組みにおいて、完全性を維持しつつ計算効率を高める手法であるDynamic Agent Grouping ECBS（DAG-ECBS）を提案している。従来のWinC-MAPFは、完全性を保証するために最適解を求めるソルバーを必要とするという制約があったが、本手法は限定的な劣最適性を許容するソルバーを組み込むことでこの制約を解消している。DAG-ECBSは、エージェントのグループを動的に生成および計画し、各グループの解が限定的な劣最適性の範囲内に収まることを保証しながら、WinC-MAPFの枠組み内で完全性を維持できることを証明している。実験の結果、DAG-ECBSはSS-CBSと比較してスケーラビリティが向上しており、完全性の保証を持たない窓付きECBSを上回る性能を示すことが確認された。
マルチエージェント経路計画（MAPF）は、共有環境内の全エージェントが衝突を回避しながら始点から終点へ移動する経路を求める問題であり、エージェント数が増えると計算量が指数関数的に増大する。混雑時や計算時間が限られる状況では、全行程の経路を計画することは困難なため、一定の時間ステップ分のみを計画するウィンドウ型MAPFが用いられる。しかし、多くのウィンドウ型手法は理論的な完全性を欠いており、局所的な判断によってデッドロックやライブロックが発生するという課題がある。これに対し、WinC-MAPFフレームワークは、エージェントの構成（結合状態）に対するヒューリスティック値を更新することで、ウィンドウ型ソルバーを用いながらも理論的な完全性を保証する手法を提案している。本研究では、このフレームワークを拡張し、有界劣最適性を維持したまま完全性を保証するDynamic Agent Grouping ECBS（DAG-ECBS）を提案する。DAG-ECBSはエージェントのグループを動的に生成・計画する手法であり、各グループのウィンドウ内解が有界劣最適であることを維持しつつ、WinC-MAPFの枠組みにおいて完全性を保てることを証明している。実験の結果、完全性の保証がない従来のウィンドウ型ECBSと比較して、DAG-ECBSは成功率を向上させることが示された。
本セクションでは、衝突のない経路を探索するマルチエージェント経路計画（MAPF）の定義、関連研究、および本研究の基礎となるWindowed Complete MAPF（WinC-MAPF）フレームワークについて述べる。MAPFは、各エージェントを始点から終点へ移動させる問題であり、本稿では、一定のタイムステップ（ウィンドウ）内のみ衝突を解決し、それ以降は個別の経路に従うWindowed MAPFに焦点を当てる。WinC-MAPFは、リアルタイム・ヒューリスティック探索の概念を導入することで、ウィンドウ内での最適解を求めるアクションジェネレータを用い、デッドロックやライブロックを回避して完備性を保証する。
WinC-MAPFの効率化の鍵は、全エージェントの結合状態空間ではなく、相互作用するエージェントのみをまとめた「互いに素なエージェントグループ（Disjoint Agent Groups）」に対してヒューリスティックなペナルティを更新することにある。具体的には、エージェントが特定の構成を通過するたびに、そのグループのヒューリスティック値を増加させることで、同じ状態の繰り返しを防ぐ。先行研究のSingle-Step CBS（SS-CBS）は、ウィンドウ内の最適解を求めるアクションジェネレータとして機能するが、高密度な混雑状況下では計算時間が膨大になるという限界がある。本研究は、このWinC-MAPFの枠組みを拡張し、制約に基づいた探索（CBS）の枠組みにおいて、完備性を維持しつつスケーラビリティを向上させることを目指している。
Dynamic Agent Grouping ECBS (DAG-ECBS)は、WinC-MAPFフレームワークにおいて、各エージェントグループの解が個別にw-劣最適性を維持することを保証する手法である。従来のECBSをそのまま適用した場合、全体のコストはw倍の範囲内に収まっても、個別のグループのコストが各グループの最適値のw倍を超えてしまう可能性があり、これがWinC-MAPFの完全性の証明を妨げる要因となる。DAG-ECBSは、各エージェントを個別のグループとして初期化し、衝突やヒューリスティック上の競合が発生したグループ同士を動的に統合して再計画を繰り返すことで、各グループが互いに独立した状態になるまで処理を行う。Group-ECBSと呼ばれる内部アルゴリズムでは、低レベルおよび高レベルの両方の探索において、ヒューリスティックのペナルティを考慮した修正版のFocal探索を用いることで、グループのヒューリスティックが常にw-許容であることを維持する。この設計により、エージェント間の距離に応じてグループ化が動的に変化しつつ、WinC-MAPFの枠組みにおける完全性を保ったまま、計算効率の高いw-劣最適解を導出できる。
標準的なベンチマークマップを用い、提案手法であるDAG-ECBS、従来のwindowed ECBS、および完全性を保証する最適解法であるSS-CBSの比較実験を行っています。スケーラビリティの評価において、DAG-ECBSはSS-CBSよりも優れた性能を示しており、これはエージェントのグループ化や非最適性の導入が有効であることを示しています。windowed ECBSはウィンドウサイズが小さい場合にデッドロックやライブロックに陥りやすく性能がウィンドウサイズに強く依存しますが、DAG-ECBSはヒューリスティックの更新によりこれらの問題を軽減しています。ただし、DAG-ECBSは混雑の少ない大規模なマップにおいて、計算時間の増大によりタイムアウトが発生しやすい傾向があります。ウィンドウサイズを大きくすると、DAG-ECBSとwindowed ECBSのいずれも1イテレーションあたりの実行時間は増加しますが、DAG-ECBSにおいてその影響がより顕著です。また、DAG-ECBSは非最適性の許容度を大きく設定することで、1イテレーションあたりの実行時間を一貫して短縮できる一方、解のコストは増加する傾向にあります。
本研究では、窓関数を用いた計画においても完全性を保証するWinC-MAPFフレームワークに対し、有界劣最適ソルバーを適用可能にする手法としてDynamic Agent Grouping ECBS (DAG-ECBS)を提案している。DAG-ECBSは、エージェントをグループ化して独立に計画を行うことで各グループのヒューリスティックの許容性を維持し、衝突が発生した際にグループを統合して再計画を行う。この手法は、既存の劣最適MAPFアルゴリズムをWinC-MAPFのAction Generatorへと変換するためのテンプレートとして機能する汎用性を備えている。実験の結果、DAG-ECBSは単一ステップの最適解を用いる手法と比較してスケーラビリティを向上させ、さらに窓サイズが小さい場合や混雑したマップにおいても、完全性の保証がないWindowed ECBSを上回る性能を示した。今後の展望として、より高度な有界劣最適アルゴリズムへの適用や、分散型アルゴリズムへの拡張が挙げられる。