Plan First, Diffuse Later: Extrinsic Graph Guidance for Long-Horizon Diffusion Planning

技術的概要：XDiffuser – 長視野拡散計画のための外部グラフガイダンス

問題定義
本論文は、連続状態空間で動作するロボットに対し、短い視野の（かつ潜在的に最適ではない）軌跡のデータセットのみが与えられた場合のオフライン長視野運動計画の課題に取り組む。拡散ベースのプランナー（例：Diffuser）は、一貫した軌跡をサンプリングすることで「推論としての計画」アプローチを提供するが、トレーニング中に長視野の分布が一度も観測されなかった場合、困難に直面する。

既存の構成型拡散手法は、重なり合う短いセグメントを結合（stitching）することでこの問題を解決しようとする。しかし、著者らは、局所的一貫性（隣接するセグメントが重なることを保証する）のみを頼りにすることは、長い連鎖にわたる大域的一貫性を保証するには不十分であると主張する。視野が広がるにつれて、推論プロセスは脆くなる。局所的に妥当なセグメントが互いに相容れない場合があり、タスクの完了や制約の満足に失敗する。さらに、拡散ループ内部で内在的探索（intrinsic search）を行う最近のアプローチは一貫性を向上させるが、計算コストが許容できないほど高く、視野の長さや探索の深さに対してスケーリング性が悪い。

手法：XDiffuser
著者らは、大域的な調整を局所的な軌跡生成から分離するXDiffuser（eXtrinsic search-guided Diffuser）を提案する。拡散プロセス中の探索に代わり、XDiffuser は拡散プロセス外部で外部探索（extrinsic search）を実行し、事前学習された構成型拡散モデルをガイダンスする。この手法は主に 3 つの段階で構成される。

1. 接続グラフの構築:

   • オフラインデータセット上に、疎な無向グラフ $G = (V, E)$ が構築される。
   • 頂点はデータセットからサンプリングされた状態である。
   • 辺は、学習された時間的距離表現（TDR）を用いて決定され、潜在 TDR 空間におけるユークリッド距離が時間的近接性を反映する。
   • このグラフは、滑らかな力学を保証することなく粗い到達可能性を捉える、軽量な「接続オラクル」として機能する。

2. 外部グラフ探索（計画）:

   • テスト時に、タスク固有のグラフアルゴリズム（ゴール到達のためのダイクストラ法、マルチエージェントのための優先度ベースプランナー、または点検のための MILP ソルバーなど）が $G$ 上で実行される。
   • これにより、高レベルの計画が生成される。これは時間的ウェイポイントの列 $W = \{(w_m, \hat{t}_m)\}$ である。
   • 経路はダウンサンプリングされて疎な足場（scaffold）を作成し、タイミングは拡散モデルのチャンキング能力に合わせて時間的に伸長される。

3. ウェイポイント誘導型構成型拡散:

   • 事前学習された短い視野の拡散モデルが連続軌跡を生成する。
   • グラフから導出されたウェイポイントは、硬い制約ではなくソフトエネルギー項（ガイダンス）として機能する。
   • 各ウェイポイントの名义時刻の周りに三角形のガイダンスウィンドウ $\lambda_m(t)$ が定義される。拡散スコアは、ウェイポイントからの逸脱を罰するウェイポイントコスト関数 $E_W(\tau)$ の勾配によって増幅される。
   • これにより、拡散事前分布に従って局所的に妥当であり（diffusion prior）、かつグラフ計画に従って大域的に一貫性のある軌跡へと、ノイズ除去プロセスがバイアスされる。

主要な貢献

• 外部探索対内在的探索: 本論文は、長視野計画における探索モードとして、拡散モデルの内部ではなく外部で行う外部探索の方がより効果的であると主張する。これは、探索の負担を古典的かつ効率的なグラフアルゴリズムに委譲し、内在的手法が要求する拡散モデルの繰り返しかつ高価な評価を回避する。
• モジュール性とスケーラビリティ: 探索層と生成層を分離することで、XDiffuser は適応的視野選択（グラフ経路の持続時間から推定）をサポートし、拡散モデルの再トレーニングなしにテスト時に異なる計画アルゴリズムの統合を可能にする。
• 未観測タスクへの一般化: このフレームワークは、単一の事前学習済み拡散モデルが、高レベルのグラフ目的を変更するだけで、複雑で未観測の組み合わせタスク（例：マルチエージェント協調、巡回セールスマン形式の点検）を解決することを可能にする。

実験結果
著者らは、XDiffuser をOGBenchスイートとカスタムの橋梁点検シミュレーションで評価した。

• 長視野ゴール到達: AntMaze Explore Largeデータセット（低品質なランダムウォークデータ）において、XDiffuser は98.5% の成功率を達成し、ベースの構成型拡散（CD）ベースライン（27%）や CDGS、C-MCTD などの探索拡張ベースラインを大幅に上回った。この改善は、局所的な結合が失敗する低品質データ領域で最も顕著であった。
• マルチエージェント経路探索（MAPF）: 単一エージェントで学習したモデルを使用したゼロショットマルチエージェント設定（2〜4 エージェント）において、XDiffuser（優先度プランナー使用）は 4 エージェントで58.3% の成功率を達成し、Prioritized CDGS の**13.3%**と比較して優れていた。また、内在的探索手法が数分かかるのに対し、計画に数秒しか要さないという優れた効率性も示した。
• 点検計画: 最大 128 個の関心点（POI）を持つ橋梁のドローン点検において、MILP 誘導型の XDiffuser は95% 以上のカバレッジを達成したのに対し、内在的探索ベースライン（IP-CDGS）は 50% 未満のカバレッジで頭打ちとなり、局所的な探索が大域的な組み合わせ制約を解決できないことを浮き彫りにした。

意義と主張
本論文は、純粋な「推論としての計画」の根本的な限界は、長視野分布が未観測である場合、局所的一貫性のみが大域的一貫した動作を保証できない点にあると主張する。XDiffuser は、両方のパラダイムの強みを活用することでこれを解決する。

1. グラフ探索は、必要な大域構造と組み合わせ推論を提供する。
2. 拡散は、滑らかで力学上実現可能な軌跡合成を提供する。

著者らは、この分解が効率的（ノイズ除去呼び出しの指数関数的スケーリングを回避）かつ柔軟であり、トレーニング分布に明示的に含まれていなかった多様で複雑な計画タスク全体で単一の生成モデルを再利用可能であると強調している。この研究は、特に不完全なデータを伴う長視野タスクにおいて、「まず計画し、その後拡散する（Plan First, Diffuse Later）」戦略が、反復的なノイズ除去を通じてのみ大域的一貫性を学習しようとするアプローチよりも優れていることを示唆している。