本研究は、Lifelong Multi-Agent Path Finding (LMAPF) におけるエージェントの移動を誘導するための Guidance Graph Optimization (GGO) を拡張したものである。従来の GGO は双方向の重み付きグラフを対象としており、エッジの重みを調整する「ソフトな誘導」に留まるため、対向するエッジでの衝突（head-on collision）を完全に防ぐことができなかった。これに対し、本研究ではエッジの方向性を決定する要素を導入した Mixed Guidance Graph (MGG) を定義し、エッジの方向と重みの両方を最適化する Mixed Guidance Graph Optimization (MGGO) を提案している。これにより、衝突回避と移動距離の増大（迂回）のトレードオフを制御し、スループットの向上を目指している。
第一に、エッジの方向と重みを同時に扱う Mixed Guidance Graph (MGG) の枠組みを定義した。第二に、グラフの強連結性を維持しつつエッジ方向を決定するための高速な修復アルゴリズムである Edge Reversal Search (ERS) を導入した。第三に、進化計算を用いた二段階最適化手法である MGGO-DS と、Quality Diversity (QD) アルゴリズムと CNN を組み合わせた Joint MGGO-PU という二つの最適化手法を提案した。第四に、実験を通じて、エッジ方向の最適化が回転アクションを減少させ、特に PIBT のようなルールベースのプランナーのスループットを向上させることを明らかにした。
提案手法には、最適化の性質が異なる二つのアプローチがある。MGGO-DS は、第1段階で進化計算 (EA) を用いて非ブリッジ辺の方向を決定し、第2段階で既存の GGO-DS を用いて辺の重み $\mathbf{w}$ を最適化する二段階構成をとる。Joint MGGO-PU は、CMA-MAE アルゴリズムを用いた QD ベースの手法であり、事前計算されたトラフィックパターンを 3 層の CNN（カーネルサイズ $3 \times 3, 5 \times 5, 7 \times 7$）に入力して方向と重みを同時に生成する。この際、モデルが常に有効な決定を下せるよう、出力に依存的な表現 (Dependent Representation) を採用している。また、グラフの強連結性を保証するため、縮約グラフ上のソースとなるメタ頂点から出る辺の半分を反転させる ERS を用いて、実現可能性を担保している。
実験では、LMAPF アルゴリズムとして PIBT および RHCR を用い、5 つのマップ（warehouse, random, room, den, empty）において評価を行った。比較対象として、CMA-ES を用いた GGO-DS や Directed Crisscross などの既存手法を用いた。PIBT を用いた実験では、MGGO-DS が単方向エッジの数を最大化することで回転アクションの比率を下げ、`random-32-32-20` 等のマップで最高のスループットを達成した。RHCR においては、エッジ重みの最適化が主たる効果を持つが、方向情報を考慮した GGO-PU が依然として高い性能を示すことが確認された。アブレーション研究により、Joint MGGO-PU において QD (Quantized Determinant) とエッジ類似度による正則化を用いることが、CMA-ES による直接最適化を上回るために不可欠であることが示された。
本研究の結果、エッジ方向の最適化は、回転アクションを減少させることで PIBT のようなルールベースのプランナーに対して特に高い効果を発揮することが示された。一方で、RHCR のような探索ベースの手法に対する利得は限定的であった。また、MGGO はエッジ方向と重みの両方を扱うため、複雑性の増大に伴うサンプル効率の低下という課題も浮き彫りになった。すべての GGO 変種に対して一貫して優れているわけではないという限界も示されており、今後の展望として、代理モデル (surrogate modeling) を導入することで、最適化のサンプル効率を改善することが挙げられている。
Lifelong Multi-Agent Path Finding (LMAPF) において、エージェントの移動を誘導するための Guidance Graph Optimization (GGO) は、移動や待機を表す双方向の重み付きグラフを最適化するが、エッジの重みはコストを増大させる「ソフトな誘導」に留まり、特定の経路を禁止することはできない。本研究では、エッジの方向性を最適化することで「厳密な誘導」を可能にする Mixed Guidance Graph Optimization (MGGO) を提案し、エッジの方向と重みの両方を最適化する手法へと一般化している。提案手法には、エッジの方向と重みを二段階に分けて個別に最適化する手法と、Quality Diversity アルゴリズムを用いてエッジの方向と重みを生成するニューラルネットワークを最適化する手法の二種類が存在する。さらに、エッジの方向に関連するトラフィックパターンを GGO に組み込むことで、エッジの方向性を考慮したガイダンスグラフの生成を可能にしている。
本研究は、Lifelong Multi-Agent Path Finding (LMAPF) において、エッジの重みと方向を最適化することでスループット（単位時間あたりのゴール到達数）を向上させる Mixed Guidance Graph (MGG) を提案している。従来の Guidance Graph は双方向の重み付きグラフであり、エッジの重みによって移動コストを表現するが、対向するエッジでの衝突（head-on collision）を完全に防げない課題があった。本論文では、エッジの方向（一方通行化）を決定する要素を導入した Mixed Guidance Graph Optimization (MGGO) を提案し、エッジの重みと方向の両方を最適化することで、衝突回避と移動距離の増大（迂回）のトレードオフを制御する。具体的には、グラフの強連結性（strong connectivity）を保証するための修復アルゴリズムを導入するとともに、既存の GGO 手法にエッジ方向に関する情報を組み込むことで、方向を考慮した最適化を実現する 2 つの MGGO 手法を提示している。実験を通じて、提案手法が従来の最先端の GGO 手法と比較して優れた性能を示すことを明らかにし、LMAPF におけるエッジの重みと方向が果たす役割の違いについて考察している。
本セクションでは、回転運動モデルに基づくLifelong Multi-Agent Path Finding (LMAPF) の背景と、エッジの重みおよび方向をガイダンスとして利用する手法について述べている。LMAPFは、エージェントが目標に到達するたびに新しい目標が割り当てられる問題であり、スループット（単位時間あたりの目標到達数）の最大化を目的とする。先行研究のGuidance Graph Optimization (GGO) において、Zhang et al. (2024) は、CMA-ESを用いて全エッジの重み $\mathbf{w}$ を直接探索するGGO-DSと、ニューラルネットワークを用いて重みを反復更新するGGO-PIUを提案しているが、GGO-PIUはシミュレーションの計算コストが高く、初期値がすべて $1$ であるという課題がある。また、エッジの方向に関する最適化は、強連結性を維持しつつ距離を最適化するStrong Network Orientation Problem (SNOP) として知られるが、これはNP困難な問題であり、既存のMILPや近傍探索手法では大規模なグラフやスループットの最適化に対応できない。さらに、本研究の基盤となるQuality Diversity (QD) アルゴリズムは、目的関数の最適化と多様性の確保を同時に行うものであり、CMA-MAEなどの手法を用いて、多様な解の集合（アーカイブ）におけるQD-scoreの最大化を図る。
連結な無向グラフ $G = (V, E)$ に対し、混合ガイダンスグラフ（Mixed Guidance Graph）は、各非ブリッジ辺 $\{u, v\} \in E$ に対して向き $(u, v)$ または $(v, u)$ もしくはその両方を、ブリッジ辺に対しては両方の向きを、さらに自己ループ $(u, u)$ を追加した有向重み付きグラフとして定義される。各辺の重みはベクトル $\mathbf{w}_{uv} \in \mathbb{R}^d$ で表され、実現可能性を損なわずに計画を行うため、MAPFの目的関数を従来の合計コスト（sum-of-costs）から、混合ガイダンスグラフ上の行動コストの総和 $\sum_{i} \text{cost}(a_i)$ へと変更する。混合ガイダンスグラフ最適化（MGGO）問題は、連結な非重み付きグラフ $G$、目的関数 $f(\mathcal{G})$、混合ガイダンスグラフの空間 $\mathcal{G}$、および辺の重みの上下限 $w_{\min}, w_{\max}$ が与えられたとき、最適な混合ガイダンスグラフを探索する問題である。
本セクションでは、Lifelong Multi-Agent Path Finding (LMAPF) における混合ガイダンスグラフ（Mixed Guidance Graph）の辺の方向と重みを最適化するための3つの手法が提案されている。まず、グラフの強連結性を修復する貪欲法として、縮約グラフ（Condensation Graph）上のソースとなるメタ頂点から出る辺の半分を反転させる Edge Reversal Search (ERS) を導入している。次に、二段階の最適化手法である MGGO-DS を提案しており、第1段階では進化計算（EA）を用いて非ブリッジ辺の方向を決定し、第2段階では GGO-DS を用いて辺の重みを最適化する。さらに、辺の方向と重みを同時に最適化する手法として、CMA-MAE を用いた QD（Quality-Diversity）ベースの Joint MGGO-PU を提案しており、これは事前計算された交通パターンを CNN モデルに入力することで、高スループットかつ強連結に近いグラフを生成する。この Joint MGGO-PU では、出力に依存的な表現（Dependent Representation）を用いることで、モデルが常に有効な決定を下せるように設計されており、目的関数にはスループット $f_{tp}$ と、ERS による反転率を考慮した正則化項を含む多様性指標 $f_{div}$ が用いられている。
本実験では、LMAPFアルゴリズムであるPIBTおよびRHCRに対し、提案手法であるMGGO-DS（2段階最適化）およびJoint MGGO-PU（QDベースの結合最適化）の有効性を、CMA-ESを用いたGGO-DSやDirected Crisscrossなどの既存手法と比較検証している。実験設定では、5つのマップ（warehouse, random, room, den, empty）を用い、更新モデルとして3層の畳み込み層（カーネルサイズ $3 \times 3, 5 \times 5, 7 \times 7$、パラメータ数 3,479）を持つCNNを採用している。PIBTを用いた実験では、MGGO-DSが単方向エッジの数を最大化することで回転アクションの比率を下げ、`random-32-32-20` 等のマップで最高のスループットを達成した一方、`empty-48-48` ではエッジの重みに特化したGGO-PUが優位であった。RHCRにおいては、低レベルプランナーの性能が高いためエッジ重みの最適化が主たる効果を持つが、エッジ方向の情報を考慮したGGO-PUが依然として高いスループットを示すことが確認された。アブレーション研究では、Joint MGGO-PUにおいてQD（Quantized Determinant）とエッジ類似度による正則化を用いることが、CMA-ESによる直接最適化よりも高いスループットを実現するために不可欠であることを示している。
本研究では、GGOを拡張してエッジの方向と重みの両方を最適化するMGGOを提案し、エッジの反転によって強連結性を強制する高速アルゴリズムであるERSを導入した。実験の結果、提案手法はベースラインを上回り、Lifelong Multi-Agent Path Finding (LMAPF) におけるガイダンス手法の新たなSOTAを確立した。エッジ方向の最適化は、回転アクションを減少させることでPIBTのようなルールベースのプランナーに対して特に有効であるが、RHCRのような探索ベースの手法に対する利得は限定的であることが明らかになった。一方で、MGGOは複雑性の増大に伴うサンプル効率の低下により、すべてのGGO変種に対して一貫して優れているわけではないという課題も示された。今後の展望として、代理モデル（surrogate modeling）を用いることでサンプル効率を改善することが挙げられている。