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

Abstract

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.

arXiv commentExtended version of ICAPS-16 conference paper with proofs and timing results

Cited by in corpus (11)

• Sampling-Based Methods for Factored Task and Motion Planning
• Learning Heuristic Search via Imitation
• MPLP: Massively Parallelized Lazy Planning
• Near-Optimal Edge Evaluation in Explicit Generalized Binomial Graphs
• STRIPS Planning in Infinite Domains
• Computationally-Efficient Roadmap-based Inspection Planning via Incremental Lazy Search
• Posterior Sampling for Anytime Motion Planning on Graphs with Expensive-to-Evaluate Edges
• Anytime Motion Planning on Large Dense Roadmaps with Expensive Edge Evaluations
• LTO: Lazy Trajectory Optimization with Graph-Search Planning for High DOF Robots in Cluttered Environments
• Perception-driven sparse graphs for optimal motion planning
• Densification Strategies for Anytime Motion Planning over Large Dense Roadmaps