本研究は、Lifelong MAPF において、エージェントが目標に到達するたびに新たな目標が割り当てられる環境下でのスループット（単位時間あたりの目標到達数）の最大化を目的としている。従来の MAPF アルゴリズムは、個々のエージェントの最短経路に依存するため、長期的・全体的な視点が欠如しており、混雑や正面衝突による流量低下を招く課題がある。本研究では、グラフ $\mathcal{G}=(V, \mathcal{E}, \mathcal{W})$ 上の各エッジの移動コストおよび各頂点での待機コストを調整する「有向ガイダンスグラフ」を導入する。これにより、逆方向の移動コスト差を拡大して正面衝突を抑制し、混雑エリアのコストを上げることで交通分散を促す。既存の「ハイウェイ」や「Crisscross」といった手動設計のルールに対し、エッジの選択・方向・コストを自動決定する GGO 問題を定義した。
第一に、Lifelong MAPF のスループットを最大化するための新しい最適化タスクである Guidance Graph Optimization (GGO) を定式化した。第二に、マップ固有の最適化を行う CMA-ES と、交通情報から重みを更新するモデルを学習する PIU という2つの異なるアプローチを提案した。第三に、PIU が学習した更新モデルを、同様のレイアウトを持つより大きなマップへ転移できることを示した。第四に、提案手法が RHCR, DPP, PIBT といった異なるカテゴリの主要な Lifelong MAPF アルゴリズムの性能を共通して向上させることを実証した。特に、ルールベースの PIBT の性能を、中央集権的な探索ベースの RHCR に極めて近い水準まで引き上げることに成功した。
GGO は、無向グラフ $G$、目的関数 $f$、およびエッジ重みの範囲 $[w_{\min}, w_{\max}]$ が与えられたとき、スループット $f(\mathcal{G})$ を最大化する $\mathcal{G}$ を探索する問題である。手法として、まず CMA-ES を用い、多変量ガウス分布からエッジ重みをサンプリングしてシミュレータでの平均スループットを直接最適化する。次に、高次元空間でのスケーラビリティ問題を解決するため、PIU を提案する。PIU は、現在のエッジ重み $w_t$ とエッジ使用量 $u_t$ から次の重みを決定する更新モデル $f(w_t, u_t; \theta)$ を最適化する。このモデル $\theta$ には 4,231 個のパラメータを持つ 3 層の CNN が採用されており、探索空間の次元をマップサイズではなくパラメータ数 $\theta$ に依存させることで、大規模マップへの適用を可能にしている。
4 つのベンチマークマップ（warehouse 20 17, warehouse 33 36, random 32 32, room 64 64）を用い、1,000 タイムステップのシミュレーションを通じて評価を行った。比較対象として Unweighted, Crisscross, HM Cost, Traffic Flow の 4 つのベースラインを設定した。実験の結果、CMA-ES と PIU はすべての設定でベースラインを上回るスループットを達成した。特に、PIBT のスループットと RHCR との差を 24.2% から 4.2% 未満へと大幅に縮小させた。また、PIU Transfer 実験では、特定のレイアウトで学習したモデルを異なるサイズのマップへ転用しても、すべてのベースラインを凌駕する性能を維持できることを確認した。
提案手法は、異なる MAPF アルゴリズムやマップに対して汎用的に機能し、大規模なマップに対しても効果的なガイダンスを生成できる。しかし、CMA-ES および PIU の学習には多数の Lifelong MAPF シミュレーションを必要とするため、計算コストが非常に高いという限界がある。今後の展望として、計算要件の削減に向けた研究や、既存のオンライン更新メカニズムと GGO を統合することで、動的な環境下でのガイダンスの有用性をさらに高めることが挙げられる。
本研究では、Lifelong Multi-Agent Path Finding (MAPF) において、スループットを向上させるための「有向ガイダンスグラフ (directed guidance graph)」を提案し、そのエッジの重みを最適化する Guidance Graph Optimization (GGO) というタスクを定義している。GGOを解く手法として、ブラックボックス最適化アルゴリズムである CMA-ES を用いて直接最適化を行う手法と、ガイダンスを生成する更新モデルを最適化する PIU という2つのアルゴリズムを提示している。PIU は、最適化されたガイダンスグラフを、同様のレイアウトを持つより大きなマップへと転移させる能力を持つ。実験の結果、提案手法は4つのベンチマークマップにおいて3つの代表的な lifelong MAPF アルゴリズムのスループットを向上させ、さらに PIU を用いることで、最大 3000 エージェントが存在する大規模なマップに対してもガイダンスグラフを生成できることが示された。
本研究では、Lifelong Multi-Agent Path Finding (MAPF) において、エッジの重みを最適化した「ガイダンスグラフ」を用いることで、スループット（単位時間あたりの目標到達数）を向上させる手法を提案している。従来のLifelong MAPFは、各エージェントに与えられた現在の目標のみを考慮する逐次的な解法をとるため、長期的・全体的な視点が欠如しており、個別のMAPFインスタンスが最適であっても全体の流量が最大化されるとは限らない。提案するガイダンスグラフは、グラフ $\mathcal{G}$ 上の各エッジの移動コストおよび各頂点での待機コストを変化させる有向重み付きグラフであり、逆方向の移動コスト差を拡大することで正面衝突を抑制し、混雑エリアのコストを上げることで交通分散を促す役割を持つ。既存の「ハイウェイ」手法（特定の集合の枝に方向と低コストを割り当てる手法）や、行・列ごとに方向を交互に変える「Crisscross」手法に対し、本研究ではエッジの選択、方向、およびコストを自動決定するGuidance Graph Optimization (GGO) 問題を定義した。具体的な解決策として、ブラックボックス最適化手法であるCMA-ESを用いたマップ固有の最適化手法と、ニューラルネットワークを用いて交通情報から更新モデルを学習し、異なるマップへも適用可能なParameterized Iterative Update (PIU) の2手法を提案している。
Lifelong MAPFは、エージェントが目標に到達するたびに新たな目標が割り当てられる問題であり、単位時間あたりの目標到達数の平均であるスループットの最大化を目的とする。既存のアルゴリズムは、全エージェントを再計画する「Replan all」（例：RHCR）、新目標を持つエージェントのみを再計画する「Replan new」（例：DPP）、衝突をルールに基づき後手に解決する「Reactive」（例：PIBT）の3種に分類される。本研究では、元のグラフ $G=(V, E)$ と同じ頂点集合を持ち、エッジの重みがアクションコストを表す有向重み付きグラフ $\mathcal{G}=(V, \mathcal{E}, \mathcal{W})$ をガイダンスグラフとして定義する。ガイダンスグラフを用いた計画では、従来の最短経路探索を、$\mathcal{G}$ 上でのアクションコストの総和を最小化する問題へと拡張する。ガイダンスグラフ最適化（GGO）は、無向グラフ $G$、目的関数 $f$、およびエッジ重みの範囲 $[w_{\min}, w_{\max}]$ が与えられたとき、スループット $f(\mathcal{G})$ を最大化する最適な $\mathcal{G}$ を探索する問題として定式化される。
本セクションでは、MAPFにおける「ガイダンス」の表現、生成、利用に関する既存研究の分類と、提案手法であるGuidance Graph Optimization (GGO) との差異が述べられている。既存のガイダンス表現は、方向マップを用いた移動コストの調整、エッジの単方向化、高速道路（highway）概念による特定エッジの低コスト化、および自己ループ（self-edges）を用いた表現に大別されるが、これらは待機コスト（wait costs）を表現できないという共通の限界を持つ。ガイダンスの生成手法についても、既存研究は手動設計されたルールやヒートマップに基づく手続きに依存しているが、本研究はガイダンスを自動生成する手法を初めて提案している。実験では、比較対象としてUnweighted、Crisscross、HM Cost（Work 4のHMを適応）、Traffic Flow（Work 7を適応）の4つのベースラインが設定されている。特に、Lifelong MAPFにおいてはゴール位置が事前に未知であるため、Work 4のような最短経路に基づく交通流予測は現実的ではなく、またWork 7のようなリアルタイム更新を前提とする手法とは異なり、本研究ではオフラインで最適化されたガイダンスグラフを扱う。既存手法は特定のMAPFアルゴリズムに依存しており、待機アクションを考慮しない設計がLifelong MAPFへの汎用性を制限しているが、提案手法は異なるカテゴリの3つの主要なLifelong MAPFアルゴリズムを用いてその汎用性を検証している。
本手法は、Lifelong Multi-Agent Path Finding (MAPF) におけるガイダンスグラフの最適化問題を解決するために、CMA-ESとParameterized Iterative Update (PIU) を提案している。まず、エッジの重みを多変量ガウス分布からサンプリングし、Lifelong MAPFシミュレータでの平均スループットを評価指標としてCMA-ESにより直接最適化する手法を検討するが、制約条件の処理にはパスの解に影響を与えないmin-max正規化を用いる。しかし、CMA-ESは高次元空間でのスケーラビリティに課題があるため、本研究では更新モデル $f(w_t, u_t; \theta)$ を最適化するPIUを導入する。ここで、$w_t$ は現在のエッジの重み、$u_t$ はエッジの使用回数、$\theta$ は更新モデルのパラメータベクトルである。PIUは、シミュレーションから得られる交通情報（エッジ使用量等）を用いてエッジの重みを反復的に更新するプロセスであり、CMA-ESはこのパラメータ $\theta$ を最適化するために用いられる。このアプローチにより、探索空間の次元がマップのサイズに依存せずパラメータ数 $\theta$ に依存するようになり、計算量 $O(n^2)$ の問題を回避しつつ、異なるマップにも適用可能な汎用的な更新モデルの獲得が可能となる。
本実験では、CMA-ESおよび提案手法であるPIUを用いて最適化されたガイダンスグラフ（GGO）の性能を、複数のLifelong MAPFアルゴリズム（RHCR, DPP, PIBT）および既存のベースライン（Unweighted, Crisscross, HM Cost, Traffic Flow）と比較評価している。実験は、4近傍グリッドマップ（warehouse 20 17, warehouse 33 36, random 32 32, room 64 64）を用い、各シミュレーションは1,000タイムステップ実行される。PIUの更新モデルには、4,231個のパラメータを持つ3層のCNNが採用されており、マップサイズに依存せず低次元の探索空間を維持できることが特徴である。結果として、CMA-ESとPIUはすべての設定においてベースラインを上回るスループットを達成しており、特に高次元な探索空間を要する大規模マップ（room 64 64など）では、探索空間の制約を受けにくいPIUがCMA-ESと同等の性能を示す。また、最適化されたガイダンスグラフを用いることで、PIBTのスループットとRHCRとの差を24.2%から4.2%未満へと大幅に縮小させ、高速なルールベース手法でも中央集権的な探索ベース手法に匹敵する性能を実現できることを示した。さらに、PIU Transfer実験では、特定のレイアウトで学習した更新モデルを異なるサイズのマップへ転用しても、すべてのベースラインを凌駕するスループットを維持できることが確認された。
本研究では、Lifelong MAPFののスループットを最大化することを目的として、汎用性の高いGuidance GraphおよびGuidance Graph Optimization (GGO) を定義した。GGOの手法として、異なるアルゴリズムやマップに対して最適化を行うCMA-ESとPIUの2つのアプローチを提案しており、さらに学習モデルを用いて類似のパターンを持つ大規模マップに対してもGuidance Graphを生成できることを示した。しかし、CMA-ESおよびPIUは多数のLifelong MAPFシミュレーションを必要とするため計算コストが高いという限界がある。今後の展望として、計算要件の削減や、既存研究（Chen et al., 2024; Yu and Wolf, 2023）で導入されているオンライン更新メカニズムとGGOを統合することで、MAPFにおけるガイダンスの有用性をさらに高めることが挙げられる。