多値ヒューリスティクスと次元削減を橋渡しする多目的探索
Bridging Multi-Valued Heuristics and Dimensionality Reduction in Multi-Objective Search
多目的最短経路探索において、多値ヒューリスティクスと次元削減を安全に統合する理論的枠組みを提案し、正確性を保証するアルゴリズムを開発した。
詳しい要約
1. どんなもの?
2. 先行研究と比べてどこがすごい?
3. 技術・手法の肝は?
4. どうやって有効だと検証した?
5. 議論はある?
6. 次に読むべき論文は?
※ 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.
関連論文
- 極座標に基づく差分進化法を用いたUAV搭載ビジョンセンサによる移動目標探索探索アルゴリズム
- 山登り法を用いた迷路探索ロボットの実験探索アルゴリズム
- レヴィロボティクス:生物に学ぶランダム探索の最新動向探索アルゴリズム
