本研究は、Lifelong Multi-Agent Path Finding (LMAPF) におけるエージェントの移動を誘導し、スループットを向上させるためのオンライン・ガイダンス・ポリシーの最適化問題を扱う。LMAPFはグラフ $\mathcal{G}$ 上でエージェントが衝突を避けながら目標を達成し続ける問題であり、既存の再計画型（RHCR等）は大規模環境でのスケーラビリティに欠け、ルールベース型（PIBT等）は計算は高速だが解の質に課題がある。また、従来のオフライン・ガイダンス手法では、時間とともに変化するリアルタイムの交通パターンやタスク分布に柔軟に対応できないという限界がある。本研究では、これらの課題を解決するために、動的なガイダンス・グラフを生成するポリシー $\pi_\theta$ を学習・最適化するアプローチを提案している。
提案手法は、CMA-ES (Covariance Matrix Adaptation Evolutionary Strategy) を用いて、微分不可能なスループット指標を最大化するようにガイダンス・ポリシーのパラメータ $\theta$ を最適化する。実装として、エッジ重みを直接利用する「Direct Planning (on+PIBT)」と、ガイダンス上の最短経路をガイドパスとして利用する「Guide-Path Planning (on+GPIBT)」の2つのパイプラインを設計した。実験により、提案手法はオフライン・ガイダンスと比較して最大 $30.75\%$、人間が設計したオンライン・ガイダンスと比較して最大 $52.42\%$ のスループット向上を達成した。さらに、タスク分布が時間とともに変化する動的なシナリオにおいても、オンライン更新が混雑回避に有効であることを示した。
ガイダンス・ポリシー $\pi_\theta$ は、過去の交通パターン、現在のタスク分布、将来の計画経路を観測として、エッジ重み $w \in \mathbb{R}^{|E|}$ を動的に更新する。最適化には、多変量ガウス分布からサンプリングされた $\theta$ を用いて $N_{eval}$ 回のシミュレーションを行い、平均スループットに基づいて分布を更新するCMA-ESを採用している。Direct Planningでは、エッジ重みを最小化する行動コストを計算し、計算コスト削減のために目標地点を根とする探索木を用いたLazy mechanismを導入している。Guide-Path Planningでは、GPIBTの枠組みを拡張し、ガイダンス・グラフ上の最短経路をガイドパスとして利用することで、全頂点間の距離計算を回避し計算負荷を軽減している。ネットワークアーキテクチャには、CNN（3,119パラメータ）や窓付き二次ネットワーク（560パラメータ）が用いられている。
4種類のマップ（sortation, warehouse, empty, random）および静的・動的なタスク分布を用いて、提案手法の有効性を検証した。実験の結果、動的なタスク分布下において、オンラインガイダンスはリアルタイムの交通状況に応じてグラフを更新できるため、オフライン手法（off+PIBT/GPIBT）よりも高いスループットを達成した。特に、GPIBTにLNS (Large Neighborhood Search) を組み合わせた「on+GPIBT+LNS」が極めて高い性能を示し、評価フェーズのみにLNSを適用した「on+GPIBT+LNS(eval)」も高い性能を維持した。計算コストについては、on+PIBTはoff+PIBTの最大4倍、on+GPIBTはhm+GPIBTの最大7倍の実行時間を要するが、1ステップあたりの平均実行時間は $0.026$ 秒以内であり、実用的な範囲内である。
本研究の成果により、オンライン・ガイダンスがタスク分布に基づいた混雑箇所を正確に捉え、待機コスト（wait cost）を適切に割り当てることで混雑を回避できることが可視化分析によって確認された。しかし、現在のアーキテクチャは4近傍グリッドに限定されているという実装上の限界がある。また、CMA-ESによる最適化はシミュレータでの評価回数が膨大になるという課題があるため、今後はサロゲートモデルを用いた最適化手法（surrogate-assisted optimizers）の導入によるサンプリング効率の向上が期待される。さらに、RHCRやLearn to Followといった他のLMAPFアルゴリズムへのガイダンスポリシーの統合も今後の展望として挙げられている。
本研究では、リアルタイムの交通パターンに基づいてエージェントを動的に誘導する、Lifelong Multi-Agent Path Finding (LMAPF) におけるガイダンス・ポリシーの最適化問題を扱う。既存の最先端のルールベース LMAPF アルゴリズムである PIBT (Priority Inheritance Backtracking) の解の質を向上させるため、適応的なガイダンスを生成するポリシーを最適化する手法を提案している。具体的には、PIBT にガイダンスを組み込むための 2 つの異なるパイプラインを設計しており、最適化されたポリシーが静的なガイダンスや人間が設計したポリシーよりも優れていることを示している。さらに、実世界のアプリケーションで一般的でありながら先行研究ではほとんど探索されてこなかった、タスク分布が時間とともに変化するシナリオについても調査を行っている。
本研究は、Lifelong Multi-Agent Path Finding (LMAPF) において、エージェントの移動を誘導しスループットを向上させるため、リアルタイムの交通状況に基づいてエッジ重みを動的に更新するオンライン・ガイダンス・ポリシーの最適化を目的としている。従来の再計画型アルゴリズムは小規模問題では高品質だが大規模環境でのスケーラビリティに欠け、一方でPIBTに代表されるルールベース型アルゴリズムは高速だが解の品質に課題があり、既存のオフライン・ガイダンス手法では混雑エリアの動的な変化に対応できないという限界がある。提案手法では、CMA-ES (Covariance Matrix Adaptation Evolutionary Strategy) を用いて、動的なガイダンス・グラフを生成するオンライン・ポリシーを最適化する。実装として、生成されたグラフの重みを直接利用するパイプラインと、ガイダンス・パスに沿ってエージェントを移動させるパイプラインの2種類を提案している。シミュレーション実験の結果、提案手法はオフライン・ガイダンスと比較して最大 $30.75\%$、人間が設計したオンライン・ガイダンスと比較して最大 $52.42\%$ のスループット向上を達成しており、動的なタスク分布下においても有効であることが示された。
Lifelong Multi-Agent Path Finding (LMAPF)は、グラフ $\mathcal{G}$ 上でエージェントが衝突を避けながら、目標に到達するたびに新たな目標へ移動し続ける問題であり、スループット（単位時間あたりの平均目標到達数）の最大化を目的とする。既存手法には、時間窓 $T$ 内で経路を再計画するRHCRのような再計画型（replan-based）と、最短距離ヒューリスティックと優先度ルールを用いるPIBTのようなルール型（rule-based）がある。RHCRは小規模環境では高性能だが、200エージェントを超える大規模環境や制限時間内ではスループットが著しく低下する課題があり、一方でPIBTは計算速度に優れるものの解の質に課題がある。エージェントの動きを制御する「ガイダンス」には、エッジの重み $w \in \mathbb{R}^{|E|}$ を用いてコストを定義するオフライン型（Guidance Graphなど）と、リアルタイムの交通状況に応じて更新するオンライン型がある。オンライン型は交通パターンの変化に柔軟に対応できるが、ヒューリスティック値の頻繁な更新に伴う計算コストが課題となる。本研究では、PIBTやその派生であるGPIBTに対し、自動最適化されたオンラインガイダンスを組み込むことで、計算効率とスループットの両立を目指している。
本手法は、Lifelong Multi-Agent Path Finding (LMAPF) において、過去の交通パターン、現在のタスク分布、および将来の計画経路を観測として用いるガイダンス・ポリシー $\pi_\theta$ を導入し、ガイダンス・グラフ $\mathcal{G}$ のエッジ重みを動的に更新するものである。統合手法として、PIBT等の直接計画（Direct Planning）では、エッジ重みを最小化するように行動コストを計算し、全頂点間の最短経路を保持するヒューリスティック・テーブルを更新するが、計算コスト削減のために目標地点を根とする探索木を用いたLazy mechanismが採用されている。一方、ガイドパス計画（Guide-Path Planning）では、GPIBTの枠組みを拡張し、ガイダンス・グラフ上の最短経路をガイドパスとして利用することで、全頂点間の距離計算を回避し、計算負荷を大幅に軽減している。ガイダンス・ポリシーのパラメータ $\theta$ の最適化には、スループットを最大化することを目的として、微分不可能な単一目的最適化アルゴリズムであるCMA-ESが用いられる。具体的には、多変量ガウス分布からサンプリングされた $\theta$ を用いて $N_{eval}$ 回のシミュレーションを行い、平均スループットに基づいて分布を更新する。実装では、パラメータ数を抑えるためにCNN（3,119パラメータ）や窓付き二次ネットワーク（560パラメータ）が使用されているが、現在のアーキテクチャは4近傍グリッドに限定されている点が限界である。
本実験では、提案手法であるオンラインガイダンス（on+PIBTおよびon+GPIBT）の有効性を、4種類のマップ（sortation, warehouse, empty, random）および静的・動的なタスク分布を用いて検証している。実験の結果、動的なタスク分布下において、オンラインガイダンスはリアルタイムの交通状況に応じてガイダンスグラフを更新できるため、オフライン手法（off+PIBT/GPIBT）よりも高いスループットを達成することが示された。特に、GPIBTにLNS（Large Neighborhood Search）を組み合わせた手法（on+GPIBT+LNS）は極めて高い性能を示し、LNSを評価フェーズのみに適用したon+GPIBT+LNS(eval)も高い性能を維持したことから、提案するオンラインガイダンス・ポリシーの汎用性が証明された。計算コストに関しては、オンライン更新によりoff+PIBTの最大4倍、on+GPIBTではhm+GPIBTの最大7倍の実行時間を要するが、1ステップあたりの平均実行時間は $0.026$ 秒以内であり、実用的な範囲に収まっている。また、可視化分析により、オンラインガイダンスがタスク分布に基づいた混雑箇所を正確に捉え、待機コスト（wait cost）を適切に割り当てることで混雑を回避していることが確認された。
本研究では、Lifelong Multi-Agent Path Finding (LMAPF) における混雑問題を解決するため、交通パターンから学習して動的に生成されるガイダンスグラフを用いたオンラインガイダンス手法を提案している。提案手法は、交通の混雑を緩和しスループットを向上させることを目的としており、4種類の異なるマップにおいて2つの最先端のLMAPFアルゴリズムのスループットを改善することに成功した。今後の展望として、RHCRやLearn to Followといった他のLMAPFアルゴリズムへのガイダンスポリシーの統合が挙げられる。また、現在は最適化にCMA-ESを用いており、シミュレータでの評価回数が膨大になるという課題があるため、サロゲートモデルを用いた最適化手法（surrogate-assisted optimizers）を導入することで、サンプリング効率を向上させることが期待される。