日本フィジカルAI新聞

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

探索アルゴリズムarXiv:2606.20644

多値ヒューリスティクスと次元削減を橋渡しする多目的探索

Bridging Multi-Valued Heuristics and Dimensionality Reduction in Multi-Objective Search

シェア:XThreadsFacebookLINEはてブBluesky

多目的最短経路探索において、多値ヒューリスティクスと次元削減を安全に統合する理論的枠組みを提案し、正確性を保証するアルゴリズムを開発した。

詳しい要約

1. どんなもの?

- 多目的最短経路 (MOSP) 問題を対象に、multi-valued heuristics (MVHs) と dimensionality reduction (DR) を安全に統合する理論的枠組みを提案。 - 従来の single-valued heuristics (SVHs) では捉えられない Pareto frontier のトレードオフ構造を MVHs で近似。 - 主な貢献は NAMOA*dr-mvh と L-NAMOA*dr-mvh の2アルゴリズム。 - 特に L-NAMOA*dr-mvh は lazy で楽観的な DR アプローチにより、admissible MVH のみで正確性を保つ。

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

- 従来の MOSP アルゴリズムは SVHs に依存し、探索ガイダンスが弱い。 - MVHs はより豊かな近似を可能にするが、DR との単純な組み合わせは順序不変条件を破壊し、探索が unsound かつ incomplete になる。 - 本研究は初めて MVHs と DR を安全に統合する理論的枠組みを提供。 - L-NAMOA*dr-mvh は最先端 MOSP アルゴリズムと同等以上で、10倍以上の高速化を達成。

3. 技術・手法の肝は?

- NAMOA*dr-mvh: heuristic consistency を強制することで探索の正確性を回復する理論的ベースライン。 - L-NAMOA*dr-mvh: DR に対して lazy で楽観的なアプローチを採用。 - 局所的な順序違反を動的に検出・修復し、admissible MVH のみで正確性を保持。 - これにより DR の効率性を活かしつつ、MVH のガイダンスを活用。

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

- 複数のベンチマークで評価。 - L-NAMOA*dr-mvh は最先端 MOSP アルゴリズムと同等かそれ以上。 - MVH の追加ガイダンスが強い枝刈りにつながるインスタンスでは10倍以上の speedup を達成。

5. 議論はある?

- MVHs と DR の単純な組み合わせが順序不変条件を破壊し、unsound/incomplete になることを示す。 - NAMOA*dr-mvh は heuristic consistency を強制するが、実用的な制限がある。 - L-NAMOA*dr-mvh はその制限を克服し、admissible MVH のみで正確性を保つ。 - 理論的枠組みの詳細や限界については要旨からは不明。

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

- NAMOA*dr-mvh (本研究のベースライン) - L-NAMOA*dr-mvh (本研究の主要貢献) - 従来の MOSP アルゴリズム (SVHs を用いるもの) - dimensionality reduction (DR) 技術 - multi-valued heuristics (MVHs) に関する研究

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

著者: Maya Wolff, Ariel Felner, Oren Salzman

分類: cs.AI, cs.RO

原文アブストラクト

Multi-objective shortest-path (MOSP) algorithms traditionally rely on single-valued heuristics (SVHs), which associate each state with a single admissible cost vector. While SVHs provide safe lower bounds, they fail to capture the trade-off structure of the Pareto frontier and often yield weak search guidance. Multi-valued heuristics (MVHs) address this limitation by mapping states to sets of cost estimates, enabling a richer approximation of possible trade-offs. Modern MOSP algorithms are highly dependent on dimensionality reduction (DR) techniques to efficiently perform dominance checks. However, integrating MVHs with DR introduces subtle correctness challenges. We show that naively combining DR with MVHs destroys the ordering invariants required for DR, leading to unsound and incomplete search. To address this issue, we develop the first theoretical frameworks for safely integrating MVHs with DR. First, we introduce $\text{NAMOA}^*{\text{dr}\text{-}\text{mvh}}$, a theoretical baseline that restores search correctness by enforcing heuristic consistency. Recognizing the practical limitations of this approach, we then introduce our primary contribution, $\text{L}\text{-}\text{NAMOA}^*{\text{dr}\text{-}\text{mvh}}$. This algorithm employs a "lazy," optimistic approach to DR, preserving exact correctness with only an admissible MVH by dynamically detecting and repairing local ordering violations. Across a range of benchmarks, $\text{L}\text{-}\text{NAMOA}^*{\text{dr}\text{-}\text{mvh}}$ matches or improves over state-of-the-art MOSP algorithms, and achieves speedups of over 10x in instances where the additional guidance provided by the MVH translates into stronger pruning.

関連論文

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

PR・アフィリエイト広告

OZ GAMING(GPU搭載BTOゲーミングPC)

OZ GAMING(GPU搭載BTOゲーミングPC)の公式広告バナーOZ GAMINGで完成品PCを見る ↗
PR本紙発行元 EmplifAI