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 language | English (US) |
---|---|
Pages (from-to) | 2065-2085 |
Number of pages | 21 |
Journal | Advanced Robotics |
Volume | 26 |
Issue number | 17 |
DOIs | |
State | Published - Dec 1 2012 |
Keywords
- A algorithm
- Bellmans principle
- Dijkstras algorithm
- feedback motion planning
- shortest paths
ASJC Scopus subject areas
- Control and Systems Engineering
- Software
- Human-Computer Interaction
- Hardware and Architecture
- Computer Science Applications