Simplicial dijkstra and A * algorithms: From graphs to continuous spaces

Dmitry S. Yershov, Steven M. Lavalle

Research output: Contribution to journalArticle

Abstract

This paper considers the optimal feedback planning problem of a point robot among polygonal obstacles in. In this problem, the Euclidean distance traveled by the robot is minimized. The approximate optimal feedback plan is computed using a piecewise linear approximation of the cost-to-go function. The approximate cost-to-go function, in turn, satisfies the discrete version of dynamic programming principle defined using a simplicial decomposition of the environment. Adaptations of Dijkstras and A * algorithms are introduced that solve the nonlinear system of discrete dynamic programming equations. Interpolation methods are carefully designed and analyzed so that they are proven to converge numerically. As a result, the computed feedback plan 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 Dijkstras algorithm.

Original languageEnglish (US)
Pages (from-to)2065-2085
Number of pages21
JournalAdvanced Robotics
Volume26
Issue number17
DOIs
StatePublished - Dec 1 2012

    Fingerprint

Keywords

  • A algorithm
  • Bellmans principle
  • Dijkstras algorithm
  • feedback motion planning
  • shortest paths

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Human-Computer Interaction
  • Hardware and Architecture
  • Computer Science Applications

Cite this