辺評価が高コストな最短経路問題のための統一形式:辺セレクタ付き経路上の遅延最良優先探索
A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors
辺の重み評価が支配的な計算コストとなる最短経路問題に対し、辺セレクタ関数で特徴づけられる遅延最短経路アルゴリズム群を定式化し、既存手法の統一と新規セレクタの有効性を示した。
著者: Christopher M. Dellin, Siddhartha S. Srinivasa
分類: cs.DS, cs.RO
原文アブストラクト
While the shortest path problem has myriad applications, the computational efficiency of suitable algorithms depends intimately on the underlying problem domain. In this paper, we focus on domains where evaluating the edge weight function dominates algorithm running time. Inspired by approaches in robotic motion planning, we define and investigate the Lazy Shortest Path class of algorithms which is differentiated by the choice of an edge selector function. We show that several algorithms in the literature are equivalent to this lazy algorithm for appropriate choice of this selector. Further, we propose various novel selectors inspired by sampling and statistical mechanics, and find that these selectors outperform existing algorithms on a set of example problems.
