22
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

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

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          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.

          Related collections

          Author and article information

          Journal
          2016-03-10
          2016-06-14
          Article
          1603.03490
          bd4f0110-7e36-4194-acc8-91164fcd2c29

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          Extended version of ICAPS-16 conference paper with proofs and timing results
          cs.DS cs.RO

          Data structures & Algorithms,Robotics
          Data structures & Algorithms, Robotics

          Comments

          Comment on this article