分散型MAPFは、各エージェントが局所的な観測 $\mathcal{O}_{i,t}$ に基づき独立して意思決定を行うため高いスケーラビリティを持つが、将来の混雑を予測できず、ボトルネックでのデッドロックや深刻な混雑を招く課題がある。既存の学習ベース手法（PRIMAL2やMAPF-GPT等）は、固定された重み関数 $w$ に基づくコスト・トゥ・ゴー $c_{i,t}(v) = \text{dist}_w(v, g_i)$ を用いるため、他エージェントの将来の動きを考慮できない。本研究は、現在のcost-to-goマップから最短経路をロールアウトして将来の混雑ホットスポットを特定し、これに対処するフレームワークを提案する。これにより、既存の学習済みポリシーの構造を維持したまま、高密度環境下での成功率と協調効率を向上させる。
本研究の主な貢献は、学習済み分散型MAPFポリシーに対して、再学習やアーキテクチャの変更を一切必要とせずに混雑回避能力を付与するSTEAMフレームワークを提案したことである。STEAMは、空間的、時間的、および局所的な3つのレベルで混雑を解消するメカニズムを備えている。具体的には、空間的に回避可能な混雑にはエージェント固有のcost-to-goマップの修正を行い、回避困難なボトルネックには時間的なlogit correctionを、さらに創発的な局所混雑には密度依存の補正を適用する。実験により、成功率において最大60%の向上を達成しつつ、計算オーバーヘッドを最小限に抑えられることを示した。
STEAMは、以下の3つの補完的なレベルで混雑を解消する。第一に、空間的解消として、将来の衝突が予測される地点が回避可能な場合は、エージェントの重み関数 $w_i$ を更新してcost-to-goマップを修正し、回避経路への誘導を行う。第二に、時間的解消として、空間的回避が困難なボトルネックに対しては、アクションのロジット $\text{logits}_i$ に対し、衝突地点へ向かう動きを抑制する修正 $\Delta \text{logits}_{i, \text{temp}}$ を適用し、エージェント間の時間的なずれを促す。第三に、局所的解消として、近傍エージェントの修正済みcost-to-goマップに基づき、候補アクションの移動先が近傍エージェントにとっても魅力的である度合いを示す局所密度スコア $D_{i,a}$ を算出し、ロジットに $\Delta \text{logits}_{i, \text{loc}}$ を加算する。最終的なロジットは $\text{logits}_{i, \text{final}} = \text{logits}_{i, \text{temp}} + \Delta \text{logits}_{i, \text{loc}}$ となり、計算量はエージェント数に対して指数関数的ではなく、検出された混雑点や近傍エージェント数に依存する。
PRIMAL2およびMAPF-GPTをベースラインとし、Random（エージェント数64〜96）、Maze（障害物密度0.3〜0.8、エージェント数32〜160）、Warehouse（最大192エージェント）の3種類のマップを用いて検証を行った。実験の結果、STEAMはMAPF-GPTの学習外分布（OOD）であるWarehouse環境においても成功率を大幅に向上させ、特に高密度シナリオにおいてボトルネックや局所的な混雑を緩和した。局所密度 $\frac{1}{T \cdot |\mathcal{E}| \cdot N} \sum_{e \in \mathcal{E}} \sum_{t=1}^{T} \sum_{i=1}^{N} \text{count}(i, t, r)$ の分析により、STEAMがエージェントを混雑領域から分散させていることが確認された。実行時間のオーバーヘッドは僅かであり、PRIMAL2においては意図的な待機により累積報酬が微減する場合があるものの、成功率やmakespanといった実質的な性能は向上する。
STEAMは、既存の学習ベースの分散型MAPFアルゴリズムに対し、ネットワーク構造の変更や再学習を行うことなく統合可能な、極めて実用性の高い手法である。本手法の限界またはトレードオフとして、PRIMAL2を用いた実験において、将来の混雑回避のためにエージェントが意図的な待機を行うことで、累積報酬がわずかに減少する場合があることが示されている。しかし、これは成功率やmakespanの向上という、MAPFにおけるより本質的な性能改善と引き換えに得られるものである。計算コストについても、オンライン実行に適した軽量な設計となっており、大規模なマルチエージェント環境への適用可能性が高い。
STEAMは、学習済み分散型MAPF（Multi-Agent Path Finding）ポリシーに対して、再学習やアーキテクチャの変更を必要とせずに、軽量な混雑回避ガイダンスを注入する学習不要（training-free）なテスト時強化フレームワークである。本手法は、現在のcost-to-goマップから導出される最短経路をロールアウトすることで将来の混雑ホットスポットを特定し、空間的に回避可能な混雑に対してはエージェント固有のcost-to-go情報を更新することで対処する。また、空間的に回避不可能なボトルネックに対しては時間的なlogit correctionを行い、さらに近傍エージェントの修正済みcost-to-goマップに基づく密度依存のlogit correctionを用いることで、創発的な局所混雑を抑制する。代表的な学習ベースの分散型MAPFアルゴリズムを用いた広範な実験により、STEAMは成功率、makespan、および解のコストを継続的に改善し、成功率において最大60%の向上を達成しつつ、計算オーバーヘッドを最小限に抑えられることが示されている。
MAPF（Multi-Agent Path Finding）は、共有環境内で複数のエージェントに衝突のない経路を計算する問題であり、大規模かつ高密度なシナリオでは計算量が爆発的に増加するNP困難な問題である。従来の集中型手法（CBSやLaCAM等）は完全性や最適性を保証できる一方で、全エージェントの結合状態空間の組み合わせ爆発によりスケーラビリティに課題がある。一方、学習ベースの分散型手法（PRIMAL2やMAPF-GPT等）は、局所的な観測に基づき独立して意思決定を行うため高いスケーラビリティを持つが、将来の混雑を予測できず、ボトルネックでのデッドロックや深刻な混雑を招く欠点がある。本研究では、既存の学習済み分散型ポリシーを一切再学習・変更することなく、テスト時の実行時に軽量なガイダンスを注入する、トレーニング不要かつポリシーに依存しない拡張フレームワーク「STEAM」を提案する。STEAMは、現在のcost-to-goマップから最短経路をロールアウトして将来の混雑点を特定し、空間的に回避可能な場合はエージェント固有のcost-to-goマップを修正して回避を促し、空間的回避が困難な場合は時間的なlogit補正（temporal logit correction）によってエージェントの遅延や抑制的な行動を誘導する。さらに、近傍エージェントの修正済みcost-to-goマップを用いた局所的な密度ベースの補正を組み合わせることで、グローバルな混雑認識と局所的な密集回避を両立させる。MAPF-GPTやPRIMAL2を用いた実験の結果、提案手法は計算オーバーヘッドを最小限に抑えつつ、特に高密度な環境において成功率と協調効率を継続的に向上させることが示された。
本セクションでは、無向グラフ $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 上での分散型マルチエージェント経路探索（MAPF）問題が定義されており、エージェント集合 $\mathcal{A}$ の各エージェント $i$ は開始点 $s_i$ から目標点 $g_i$ への経路 $\tau_i = (v_{i,0}, v_{i,1}, \dots, v_{i,T_i})$ を求め、衝突およびエッジスワップを回避する制約 $v_{i,t} \neq v_{j,t}$ および $(v_{i,t}, v_{i,t+1}) \neq (v_{j,t+1}, v_{j,t})$ を満たす必要がある。分散型手法では、各エージェントは局所観測窓 $\mathcal{O}_{i,t} \subseteq \mathcal{V}$ 内の情報を含む多チャネルの観測 $o_{i,t}$ に基づき、事前学習済みの方策 $\pi$ を用いてアクション・ロジット $z_{i,t} = \pi(o_{i,t})$ を出力し、Softmax関数を通じて行動を選択する。観測 $o_{i,t}$ には、障害物情報、近傍エージェント情報、および頂点重み関数 $w(v)$ に基づく局所的なコスト・トゥ・ゴー（cost-to-go）チャネル $c_{i,t}$ が含まれ、ここで $c_{i,t}(v) = \text{dist}_w(v, g_i)$ である。従来の分散型手法は、固定された $w$ に基づくコスト・トゥ・ゴーを使用するためスケーラブルであるが、他エージェントの将来の動きを考慮できないため、狭い通路等での混雑（congestion）を誘発するという限界がある。これに対し、本研究が提案する問題設定は、既存の学習済み方策 $\pi$ のパラメータや構造を変更せず、テスト時に提供する情報（コスト・トゥ・ゴーチャネルやロジット）のみを修正することで性能を向上させる、方策に依存しない（policy-agnostic）強化フレームワークの構築を目指している。
STEAMは、学習済みの方策（policy）を一切変更せず、テスト時の実行プロセスのみを修正することで、分散型マルチエージェント経路探索（MAPF）における混雑を回避する学習不要（training-free）のフレームワークである。本手法は、空間的、時間的、および局所的な3つの補完的なレベルで混雑を解消する。まず、空間的解消として、将来の衝突が予測される地点を回避可能な場合は、エージェントの重み関数 $w_i$ を更新してコスト・トゥ・ゴー（cost-to-go）マップを修正し、回避経路への誘導を行う。空間的回避が困難なボトルネック等の場合は、時間的解消として、アクションのロジット $\text{logits}_i$ に対して、衝突地点へ向かう動きを抑制する修正 $\Delta \text{logits}_{i, \text{temp}}$ を適用し、エージェント間の時間的なずれを促す。さらに、局所的な解消として、近傍エージェントの修正済みコスト・トゥ・ゴーマップに基づき、候補アクションの移動先が近傍エージェントにとっても魅力的である度合いを示す局所密度スコア $D_{i,a}$ を算出し、ロジットに $\Delta \text{logits}_{i, \text{loc}}$ を加算することで、突発的な高密度状態の形成を防ぐ。最終的なロジットは $\text{logits}_{i, \text{final}} = \text{logits}_{i, \text{temp}} + \Delta \text{logits}_{i, \text{loc}}$ となり、計算量はエージェント数に対して指数関数的ではなく、検出された混雑点や近傍エージェントの数に依存するため、オンライン実行に適した軽量な設計となっている。
本研究では、学習ベースの分散型MAPF（Multi-Agent Path Finding）のベースラインであるPRIMAL2およびMAPF-GPTに対し、再学習やネットワーク構造の変更を一切行わずに適用可能な、訓練不要の混雑回避フレームワーク「STEAM」の有効性を検証している。実験は、Random（エージェント数を64から96へ増強）、Maze（障害物密度0.3〜0.8、エージェント数32〜160）、Warehouse（最大192エージェント）の3種類のマップタイプを用いて、成功率（success rate）、makespan、実行時間（runtime）、およびMAPF-GPTにおける合計コスト（sum of costs）やPRIMAL2における累積報酬（cumulative reward）を指標として評価した。結果として、STEAMはMAPF-GPTの学習外分布（OOD）であるWarehouse環境においても成功率を大幅に向上させ、特にエージェント密度が高いシナリオにおいて、ボトルネックや局所的な混雑を緩和することで主要な性能指標を改善することを示した。また、局所的なエージェント密度を $\frac{1}{T \cdot |\mathcal{E}| \cdot N} \sum_{e \in \mathcal{E}} \sum_{t=1}^{T} \sum_{i=1}^{N} \text{count}(i, t, r)$ と定義して分析したところ、STEAMの導入により局所密度が継続的に減少しており、エージェントを混雑領域から分散させる効果が確認された。実行時間のオーバーヘッドは僅かであり、PRIMAL2においては、将来の混雑回避のために意図的な待機を許容することで累積報酬が微減する場合があるものの、成功率やmakespanといった実質的なMAPF性能は向上するというトレードオフが明らかになった。
本論文では、学習ベースの分散型MAPF（Multi-Agent Path Finding）を対象とした、追加学習を必要としない混雑回避強化フレームワークであるSTEAMを提案している。STEAMは、空間的・時間的、および創発的な局所的混雑への認識を組み込むことで、テスト実行時におけるエージェントの混雑予測と緩和を可能にする。具体的には、空間的に解決可能な混雑に対してはエージェント固有のコスト・トゥ・ゴー（cost-to-go）マップを更新し、空間的に解決困難なボトルネックや局所的な混雑に対してはロジットレベルでの補正を行うことで対処する。本手法はポリシーに依存しない（policy-agnostic）ため、既存の学習ベースの分散型MAPFアルゴリズムに対し、ネットワーク構造の変更や再学習を行うことなく統合が可能である。複数のベースラインおよび環境を用いた実験の結果、STEAMはわずかな計算オーバーヘッドのみで、特に高密度かつ混雑が発生しやすい設定において、成功率と協調効率の継続的な向上を達成した。