Simplicial Dijkstra and A* algorithms for optimal feedback planning

Dmitry S. Yershov, Steven M. LaValle

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper considers the Euclidean shortest path problem among obstacles in ℝ n. Adaptations of Dijkstra's and A* algorithms are introduced that compute the approximate cost-to-go function over a simplicial complex embedded in the free space. Interpolation methods are carefully designed and analyzed so that they are proven to converge numerically to the optimal cost-to-go function. As the result, the computed function produces approximately optimal trajectories. The methods are implemented and demonstrated on 2D and 3D examples. As expected, the simplicial A* algorithm significantly improves performance over the simplicial Dijkstra's algorithm.

Original languageEnglish (US)
Title of host publicationIROS'11 - 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems
Subtitle of host publicationCelebrating 50 Years of Robotics
Pages3862-3867
Number of pages6
DOIs
StatePublished - Dec 29 2011
Event2011 IEEE/RSJ International Conference on Intelligent Robots and Systems: Celebrating 50 Years of Robotics, IROS'11 - San Francisco, CA, United States
Duration: Sep 25 2011Sep 30 2011

Publication series

NameIEEE International Conference on Intelligent Robots and Systems

Other

Other2011 IEEE/RSJ International Conference on Intelligent Robots and Systems: Celebrating 50 Years of Robotics, IROS'11
CountryUnited States
CitySan Francisco, CA
Period9/25/119/30/11

Keywords

  • A* algorithm
  • Bellman's principle
  • Dijkstra's algorithm
  • Optimal control
  • feedback motion planning
  • shortest paths

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Computer Vision and Pattern Recognition
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Simplicial Dijkstra and A* algorithms for optimal feedback planning'. Together they form a unique fingerprint.

  • Cite this

    Yershov, D. S., & LaValle, S. M. (2011). Simplicial Dijkstra and A* algorithms for optimal feedback planning. In IROS'11 - 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems: Celebrating 50 Years of Robotics (pp. 3862-3867). [6048681] (IEEE International Conference on Intelligent Robots and Systems). https://doi.org/10.1109/IROS.2011.6048681