A Unifying Formalism for Shortest Path Problems with Expensive Edge\n Evaluations via Lazy Best-First Search over Paths with Edge Selectors

While the shortest path problem has myriad applications, the computational\nefficiency of suitable algorithms depends intimately on the underlying problem\ndomain. In this paper, we focus on domains where evaluating the edge weight\nfunction dominates algorithm running time. Inspired by approaches in robotic\nmotion planning, we define and investigate the Lazy Shortest Path class of\nalgorithms which is differentiated by the choice of an edge selector function.\nWe show that several algorithms in the literature are equivalent to this lazy\nalgorithm for appropriate choice of this selector. Further, we propose various\nnovel selectors inspired by sampling and statistical mechanics, and find that\nthese selectors outperform existing algorithms on a set of example problems.\n