A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors
A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors
复制标题
通过使用边缘选择器对路径进行惰性最佳优先搜索，实现具有昂贵边缘评估的最短路径问题的统一形式
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
S. Srinivasa
中科院分区：
文献类型：
--
作者：
Christopher M. Dellin;S. Srinivasa
尽管最短的路径问题具有无数的应用，但合适的算法的计算效率密切取决于潜在的问题域。在本文中，我们专注于评估边缘重量函数的域，主导算法运行时间。受到机器人运动计划中的方法的启发，我们定义和研究了算法的最短路径类别，该类别通过选择边选择器函数而区分的算法。我们表明，文献中的几种算法等同于该懒惰算法，以适当选择该选择器。此外，我们提出了受抽样和统计力学启发的各种新型选择器，并发现这些选择器在一组示例问题上的表现优于现有算法。
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.