本研究は、複雑で混雑したマルチエージェント経路計画（MAPF）において、修復ベースの手法であるLNS2の初期解の質が成功率や収束速度を制限するという課題に取り組んでいる。従来のLNS研究は近傍選択に集中しており、学習ベースの手法も高密度環境での厳密な制約遵守に課題があった。DiffLNSは、離散的な結合アクションテンソル $\mathbf{x}_0 \in \mathcal{A}^{N \times T}$ 上で動作する離散拡散モデルを導入し、エキスパートのデモンストレーションから時空間的な事前分布を学習することで、後続のLNS2が修復しやすい高品質なドラフトを生成することを目指している。
提案手法は、離散拡散モデルをMAPFの初期化器として活用する新しいハイブリッドフレームワークを提示した。Sparse Social Attentionを導入することで、衝突に関与する可能性の高いエージェント間の相互作用に計算資源を集中させ、効率的な学習と推論を可能にした。実験では、最大96エージェントのデータで学習したモデルが、推論時に最大312エージェントまでスケールできる汎化性能を示した。20の複雑な設定において、最強のベースラインであるLNS2+RLを平均成功率で9.6ポイント上回る95.8%の成功率を達成した。
DiffLNSは、D3PMによる構造化された初期解生成とLNS2による局所修復を組み合わせる。デノイジングネットワークは、時間的アテンション、環境センシング、および「Sparse Social Attention」で構成される。このアテンションは、拡散ステップ $t$ における軌跡の近接度 $\min_{t' \in [0, T]} \text{dist}(\hat{x}_{i,t'}, \hat{x}_{j,t'})$ に基づき、各エージェント $i$ に対して動的な近傍 $\mathcal{N}_i(t)$ を構築する。学習は、変分下界 $\mathcal{L}_{\text{vlb}}$ と補助損失 $\mathcal{L}_{\text{aux}}$ を組み合わせた $\mathcal{L} = \mathcal{L}_{\text{vlb}} + \lambda \mathcal{L}_{\text{aux}}$ で最適化される。デノイザーは置換等変性 $\text{Denoise}(\mathbf{P}\mathbf{x}_t, \text{cond}) = \mathbf{P}\text{Denoise}(\mathbf{x}_t, \text{cond})$ を持つため、学習時より大規模なエージェント数への対応が可能である。
POGEMAで生成された5つの環境（Small Random, Medium Maze, Medium Room, Medium Warehouse, Large Maze）を用いて、LNS2、LNS2+RL、HMAGAT、LaCAM3と比較実験を行った。結果として、DiffLNSは平均成功率（SR）95.8%を記録し、LNS2+RLを9.6ポイント上回った。アブレーション研究では、Sparse Social Attentionが全対全のDense Attentionと比較して、修復成功率を向上させつつ実行時間を約12%短縮することが確認された。特に迷路や倉庫のような混雑した環境において、高い堅牢性が示された。
本手法は、拡散モデルが下流のプランニングに対して有用な共同事前分布を提供できることを示した。しかし、いくつかの限界も存在する。単純なインスタンスにおいては、LNS2単体と比較して計算コストが過剰になる傾向がある。また、マップサイズの変化に伴う分布シフトの影響や、極めて困難なケースにおいて限られた修復予算内では完全に解決できない場合がある。今後は、これらの計算効率と極端なケースへの対応が課題となる。
本研究では、複雑で混雑したマルチエージェント経路計画（MAPF）において、LNS2（Large Neighborhood Search）の初期解生成を改善するためのハイブリッドフレームワーク「DiffLNS」を提案している。DiffLNSは、離散的なデノイジング拡散確率モデル（D3PM）を初期化器として統合しており、スパースなソーシャルアテンション（Sparse Social Attention）を用いることで、エキスパートのデモンストレーションから協調的なマルチエージェントの行動軌跡に関する時空間的な事前分布を学習する。この離散拡散モデルは、カテゴリカルな行動空間上で直接動作することでMAPFの行動構造を維持し、マルチモーダルな結合計画分布から多様なドラフトをサンプリングして、後続のLNS2による近傍修復（neighborhood repair）のためのウォームスタートとして機能する。実験では、最大96エージェントのインスタンスのみで学習したにもかかわらず、推論時には最大312エージェントのシナリオまで汎化できることが示された。20の複雑かつ混雑した設定において、DiffLNSは平均成功率95.8%を達成し、最強のベースラインを9.6ポイント上回る結果を得ている。
本研究では、LNS2（Large Neighborhood Search 2）のような修復ベースのMAPF手法において、初期解の質が成功率や収束速度に大きく影響するという課題に対し、離散拡散モデルを用いたハイブリッドフレームワークであるDiffLNSを提案している。DiffLNSは、離散的なデノイジング拡散確率モデル（D3PM）を初期化器として統合し、エキスパートのデモンストレーションから協調的なマルチエージェント行動軌跡の時空間的な事前分布を学習する。モデルの効率化のため、現在のデノイジング状態から局所的な近傍を動的に構築する「拡散認識型スパース・ソーシャル・アテンション（diffusion-aware sparse social attention）」を導入しており、衝突に関与する可能性の高いエージェント間の相互作用に計算資源を集中させている。推論時には、D3PMが生成した複数の多様なドラフト候補をLNS2で独立に修復し、最も優れた実行可能解を選択する構成をとることで、大規模なエージェント数へのスケーラビリティと並列化を実現している。実験では、最大96エージェントのデータで学習したモデルが最大312エージェントまでスケールし、20の複雑かつ混雑した設定において平均成功率95.8%を達成、強力なベースラインであるLNS2+RLを平均成功率で9.6ポイント上回る結果を示した。
Multi-Agent Path Finding (MAPF) は、共有グラフ $\mathcal{M}$ 上で、エージェント集合 $\mathcal{A}$ の各個体が開始地点 $s_i$ から目標地点 $g_i$ まで衝突を回避して移動する経路を求める問題であり、解の質は全エージェントの経路コストの総和である Sum of Costs (SOC) で評価される。本研究で用いる離散拡散モデル（D3PM）は、時刻 $t$ における one-hot ベクトル $\mathbf{x}_t$ に対し、遷移確率 $q(\mathbf{x}_t | \mathbf{x}_{t-1})$ を定義する前方マルコフ連鎖に基づき、学習時には変分下界とクリーン状態予測項を組み合わせた損失関数 $\mathcal{L}$ を最小化することで、逆遷移 $p_\theta(\mathbf{x}_{t-1} | \mathbf{x}_t)$ を学習する。また、比較対象となる MAPF-LNS2 は、優先度付き計画法（PP）と SIPPS を用いて初期解を構築した後、エージェントのサブセットを選択して繰り返し再計画を行う Large Neighborhood Search アルゴリズムである。LNS2 は、衝突ペアの数が増加しない場合に更新を受け入れるが、初期解の衝突構造が複雑（entangled）であるほど修復が困難になるという特性を持つ。
DiffLNSは、離散拡散モデル（D3PM）による構造化された初期解生成と、LNS2による局所的な修復を組み合わせたハイブリッドなMAPFフレームワークである。初期化フェーズでは、エージェント数 $N$、計画ホライゾン $T$、行動集合 $\mathcal{A} = \{\text{stay, up, down, left, right}\}$ からなる離散的な結合アクションテンソル $\mathbf{x}_0 \in \mathcal{A}^{N \times T}$ を生成し、D3PMを用いて時空間的な事前分布を学習する。デノイジングネットワークは、時間的アテンション、環境センシング、および「Sparse Social Attention」を用いて構成される。このアテンション機構は、拡散ステップ $t$ における推論軌跡の近接度 $\min_{t' \in [0, T]} \text{dist}(\hat{x}_{i,t'}, \hat{x}_{j,t'})$ に基づき、各エージェント $i$ に対して動的な近傍 $\mathcal{N}_i(t)$ を構築し、計算コストを抑えつつ衝突に関わる局所的な相互作用に集中する。学習は、エキスパート分布への適合を目指す $\mathcal{L}_{\text{vlb}}$ と、目標到達や衝突削減を促す補助損失 $\mathcal{L}_{\text{aux}}$ を組み合わせた目的関数 $\mathcal{L} = \mathcal{L}_{\text{vlb}} + \lambda \mathcal{L}_{\text{aux}}$ によって最適化される。生成されたドラフトは、目標到達後の冗長な動きの削除や最短経路による補完といった前処理を経てLNS2に渡され、頂点・エッジ衝突が解消されるまで反復的に修復される。本手法は、デノイザーがエージェント間でパラメータを共有し、置換等変性 $\text{Denoise}(\mathbf{P}\mathbf{x}_t, \text{cond}) = \mathbf{P}\text{Denoise}(\mathbf{x}_t, \text{cond})$ を持つため、学習時より大規模なエージェント数に対しても推論が可能である。
DiffLNSの性能を評価するため、LNS2、LNS2+RL、HMAGAT、およびLaCAM3をベースラインとして、POGEMAで生成された5つの環境（Small Random, Medium Maze, Medium Room, Medium Warehouse, Large Maze）を用いて実験が行われた。評価指標には成功率（SR）、成功事例における平均コスト（SOC）、および全事例の平均実行時間が用いられ、DiffLNSは平均95.8%のSRを達成し、最強のベースラインであるLNS2+RLを9.6ポイント上回る結果を示した。特に、迷路や倉庫のような混雑した環境において、DiffLNSは古典的な手法よりも高い堅牢性を示し、拡散モデルによる初期化がLNS2の修復可能性を向上させることが確認された。アブレーション研究では、提案手法であるSparse Social Attentionが、全対全のDense Attentionと比較して、修復成功率を向上させつつ生成候補数を削減し、実行時間を約12%短縮できることが示された。一方で、本手法の限界として、単純なインスタンスではLNS2単体と比較して計算コストが過剰になる点、マップサイズの変化による分布シフトの影響、および限られた修復予算内では極めて困難なケースを完全に解決できない点が挙げられている。
従来のMAPFソルバーは、Conflict-Based Search (CBS) や LaCAM のような組合せ探索、あるいは初期解を部分的に再計画する Large Neighborhood Search (LNS) に分類されるが、LNSの研究は主に近傍選択や再計画プロセスに集中しており、高品質な初期解の生成に関する直接的な研究は限定的である。学習ベースの手法（PRIMAL, DHC, MAPF-GPT 等）は、グラフやトークンベースのアーキテクチャを用いて相互作用をモデル化し推論効率を高めているが、高密度な環境において厳密な制約を満たすことが困難であるという課題がある。一方、拡散モデルを用いた生成的な計画手法は、連続的な状態空間における軌道生成には広く適用されているものの、グリッドベースのMAPFが要求する離散的な頂点・エッジの衝突制約への対応が不十分である。本研究では、離散的な結合アクションテンソル上で拡散モデルを定式化することで、多様な初期解を生成し、それを LNS2 による修復プロセスに渡すことで、マルチモーダルな生成事前分布と古典的なハード制約修復を組み合わせている。
本研究では、D3PMをLNS2の学習済み初期化器として利用するハイブリッドMAPFフレームワーク「DiffLNS」を提案した。DiffLNSは、離散拡散プロセスを通じて共同アクションプランをモデル化し、MAPFインスタンスを条件として構造化された修復シードを生成することで、従来の修復のみに焦点を当てた手法から初期化の質へと重点を移している。生成されたドラフトは、それ自体がすべてのハード制約を満たす必要はなく、下流のLNS2による修復をより堅牢にするための協調的な時空間的事前分布として機能する。拡散注意機構を用いた疎なソーシャルアテンション（sparse social attention）とマルチサンプル修復を組み合わせることで、高密度かつ混雑した設定においても、競争力のある解の質を維持しつつ修復成功率を向上させている。本結果は、離散拡散モデルがマルチエージェント意思決定における構造化された反復生成器として機能し、下流のプランニングや制御に対して有用な共同事前分布を提供できることを示唆している。