日本フィジカルAI新聞

世界のフィジカルAIを、日本語で。

経路計画arXiv:2604.20744

AAC: アーキテクチャにより許容性を保証するALT用微分可能ランドマーク圧縮

AAC: Admissible-by-Architecture Differentiable Landmark Compression for ALT

シェア:XThreadsFacebookLINEはてブBluesky

A*とランドマークを用いた最短経路ヒューリスティック(ALT)向けに、出力が構造的に許容性を満たす微分可能なランドマーク選択モジュールを提案し、学習可能な圧縮を実現した。

詳しい要約

1. どんなもの?

- ALT (A*, Landmarks, and Triangle inequality) 最短経路ヒューリスティックのための微分可能なランドマーク選択モジュール AAC (Architecturally Admissible Compressor) を導入。 - 出力は構成上 admissible であり、各順伝播は三角不等式下界の行確率的混合であるため、パラメータ設定に関わらず admissibility が保証される。 - 展開時には学習された部分集合上の古典的 ALT に帰着し、ニューラルエンコーダとエンドツーエンドで組み合わせ可能で、古典的ツールチェーンを保持する。 - 古典的ヒューリスティック探索における「admissibility を保持しながら圧縮する」伝統の最初の微分可能インスタンスである。

2. 先行研究と比べてどこがすごい?

- 従来の ALT ランドマーク選択は微分不可能で、admissibility を保証するには収束・キャリブレーション・射影が必要だった。 - AAC は任意のパラメータ設定で admissibility を構成上保証し、それらを不要にする。 - 同一頂点あたりメモリプロトコル下で、FPS-ALT がメトリックグラフ上でほぼ最適なカバレッジを持ち、任意のセレクタに数パーセントの余地しか残さないことを証明。 - AAC はこの上限に近い性能(9 道路網で 0.9–3.9 パーセンテージポイント、合成グラフで ≤1.3 パーセンテージポイントのギャップ)を示し、1,500+ クエリと全ログ実行で admissibility 違反ゼロ。 - 同一メモリで DIMACS 道路網の中央値クエリにおいて FPS-ALT より 1.2–1.5 倍高速で、オフラインコストを 170–1,924 クエリで償却する。

3. 技術・手法の肝は?

- AAC は微分可能なランドマーク選択モジュールで、各順伝播が三角不等式下界の行確率的混合を出力する。 - これにより、パラメータ設定に関わらず admissibility が構成上保証される。 - 展開時には学習された部分集合上の古典的 ALT に帰着し、ニューラルエンコーダとエンドツーエンドで組み合わせ可能。 - 制御されたアブレーションにより、結合制約はデフォルト初期化下での訓練目的のドリフトであり、アーキテクチャ容量ではないことを特定。 - identity-on-first-m 初期化が拡張数ギャップを完全に埋める。

4. どうやって有効だと検証した?

- 同一頂点あたりメモリプロトコル下で、9 道路網と合成グラフで評価。 - 9 道路網で 0.9–3.9 パーセンテージポイント、合成グラフで ≤1.3 パーセンテージポイントのギャップで、FPS-ALT のほぼ最適カバレッジに近いことを示す。 - 1,500+ クエリと全ログ実行で admissibility 違反ゼロ。 - 同一メモリで DIMACS 道路網の中央値クエリにおいて FPS-ALT より 1.2–1.5 倍高速で、オフラインコストを 170–1,924 クエリで償却。 - 制御されたアブレーションで訓練目的のドリフトが結合制約であることを特定し、identity-on-first-m 初期化が拡張数ギャップを完全に埋めることを示す。

5. 議論はある?

- 訓練目的のドリフトがデフォルト初期化下での結合制約であり、アーキテクチャ容量ではないことがアブレーションで示された。 - identity-on-first-m 初期化が拡張数ギャップを完全に埋める。 - その他の議論や限界については要旨からは不明。

6. 次に読むべき論文は?

- FPS-ALT (farthest-point-sampling landmarks) との比較が行われている。 - 古典的 ALT (A*, Landmarks, and Triangle inequality) ヒューリスティック。 - 圧縮差分ヒューリスティックの参照ベースライン。 - 関連手法として、微分可能なランドマーク選択や admissibility を保持する圧縮の伝統。

※ AIが要旨から生成した要約です。正確性は原文をご確認ください。

著者: An T. Le, Vien Ngo

分類: cs.AI, cs.LG, cs.RO

原文アブストラクト

We introduce \textbf{AAC} (Architecturally Admissible Compressor), a differentiable landmark-selection module for ALT (A*, Landmarks, and Triangle inequality) shortest-path heuristics whose outputs are admissible by construction: each forward pass is a row-stochastic mixture of triangle-inequality lower bounds, so the heuristic is admissible for \emph{every} parameter setting without requiring convergence, calibration, or projection. At deployment, the module reduces to classical ALT on a learned subset, composing end-to-end with neural encoders while preserving the classical toolchain. The construction is the first differentiable instance of the compress-while-preserving-admissibility tradition in classical heuristic search. Under a matched per-vertex memory protocol, we establish that ALT with farthest-point-sampling landmarks (FPS-ALT) has provably near-optimal coverage on metric graphs, leaving at most a few percentage points of headroom for \emph{any} selector. AAC operates near this ceiling: the gap is $0.9$--$3.9$ percentage points on 9 road networks and ${\leq}1.3$ percentage points on synthetic graphs, with zero admissibility violations across $1{,}500+$ queries and all logged runs. At matched memory, AAC is also $1.2$--$1.5{\times}$ faster than FPS-ALT at the median query on DIMACS road networks, amortizing its offline cost within $170$--$1{,}924$ queries. A controlled ablation isolates the binding constraint: training-objective drift under default initialization, not architectural capacity; identity-on-first-$m$ initialization closes the expansion-count gap entirely. We release the module, a reusable matched-memory benchmarking protocol with paired two-one-sided-test (TOST) equivalence and pre-registration, and a reference compressed-differential-heuristics baseline.

関連論文

  1. 1Boston Dynamics、車輪付きAtlasの研究試作機を紹介研究・技術
  2. 2newmoとKDDIが資本業務提携 2028年に堺市で自動運転タクシー商用化目指す提携・買収
  3. 3GXOとApptronik、Apolloの物流現場試験を拡大 最大1,000台の展開を構想量産・展開
  4. 4NVIDIA、CoRLでGR00T 2とIsaac Lab 3.0を発表新製品・発表
  5. 5UC BerkeleyとNVIDIAの研究者、AIエージェントでロボット制御コードを仮想環境で改善研究・技術

PR・アフィリエイト広告

FRONTIER(GPU搭載BTOパソコン)

FRONTIER(GPU搭載BTOパソコン)の公式広告バナーFRONTIERでGPU搭載PCを見る ↗
PR本紙発行元 EmplifAI