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

Understand

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.