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

Christopher Dellin and Siddhartha Srinivasa
Proceedings of the 26th International Conference on Automated Planning and Scheduling, March, 2016.


Download
  • Adobe portable document format (pdf) (797KB)
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

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.

Notes
Sponsor: National Science Foundation IIS (#1409003), Toyota Motor Engineering & Manufacturing (TEMA), Office of Naval Research
Associated Center(s) / Consortia: Quality of Life Technology Center, National Robotics Engineering Center, and Center for the Foundations of Robotics
Associated Lab(s) / Group(s): Personal Robotics

Text Reference
Christopher Dellin and Siddhartha Srinivasa, "A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors," Proceedings of the 26th International Conference on Automated Planning and Scheduling, March, 2016.

BibTeX Reference
@inproceedings{Dellin_2016_8069,
   author = "Christopher Dellin and Siddhartha Srinivasa",
   title = "A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors",
   booktitle = "Proceedings of the 26th International Conference on Automated Planning and Scheduling",
   month = "March",
   year = "2016",
}