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

2016/03/10 by Christopher M. Dellin, Dellin, Christopher M., Siddhartha S Srinivasa +1 · 5 citations
Computer Science · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Machine Learning and Data Classification #Optimization and Search Problems #Robotic Path Planning Algorithms #Robotics (cs.RO)

paper · pdf · doi:10.48550/arxiv.1603.03490

openalex publication_date 2016/03/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Citations

• Probabilistic roadmaps for path planning in high-dimensional configuration spaces
• A note on two problems in connexion with graphs

Cited by

• Effective Game-Theoretic Motion Planning via Nested Search
• Near-Optimal Edge Evaluation in Explicit Generalized Binomial Graphs
• Learning Heuristic Search via Imitation
• Posterior Sampling for Anytime Motion Planning on Graphs with Expensive-to-Evaluate Edges
• Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions

Related

• The Provable Virtue of Laziness in Motion Planning
• Leveraging Experience in Lazy Search
• Generalized Lazy Search for Robot Motion Planning: Interleaving Search\n and Edge Evaluation via Event-based Toggles
• Leveraging Experience in Lazy Search
• Generic and Efficient Solution Solves the Shortest Paths Problem in Square Runtime