This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Citation Map Services Email this article to a friend Similar articles in this journal Similar articles in Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via HighWire Citing Articles via Web of Science (1) Citing Articles via Google Scholar Citing Articles via Scopus Google Scholar Articles by Lavalle, S. M. Articles by Konkimalla, P. Search for Related Content Social Bookmarking                         What's this?

Algorithms for Computing Numerical Optimal Feedback Motion Strategies

Department of Computer Science, University of Illinois, Urbana, IL 61801, USAlavalle{at}cs.uiuc.edu

Prashanth Konkimalla

Department of Computer Science, Iowa State University, Ames, IA 50011, USA

The authors address the problem of computing a navigation function that serves as a feedback motion strategy for problems that involve generic differential constraints, nonconvex collision constraints, and the optimization of a specified criterion. The determination of analytical solutions to such problems is well beyond the state of the art; therefore, the authors focus on obtaining numerical solutions that are based on discretization of the state space (although they do not force trajectories to visit discretized points). This work improves classical optimal control techniques for problems of interest to the authors. By introducing a simplicial complex representation, the authors propose a novel interpolation scheme that reduces a key bottleneck in the techniques from O(2n) running time to O(n lg n), in which n is the state space dimension. By exploiting local structure in the differential constraints, the authors present a progressive series of three improved algorithms that use dynamic programming constraints to compute an optimal navigation function. Each makes an assumption that is more restrictive than the previous one, and exploits that assumption to yield greater efficiency. These improvements yield a practical increase in the applicability of dynamic programming computations by one or two dimensions over classical techniques. Theoretical convergence to the optimal solution is established for these proposed algorithms. The algorithms are implemented and evaluated on a variety of problems. Several computed results are presented.

Key Words: motion planning • algorithms • nonholonomic planning • mobile robotics • navigation functions • dynamic programming • optimal control

The International Journal of Robotics Research, Vol. 20, No. 9, 729-752 (2001)
DOI: 10.1177/02783640122067633


CiteULike    Complore    Connotea    Del.icio.us    Digg    Reddit    Technorati    Twitter    What's this?

This article has been cited by other articles:

				S. R. Lindemann and S. M. LaValle Simple and Efficient Algorithms for Computing Smooth, Collision-free Feedback Laws Over Given Cell Decompositions The International Journal of Robotics Research, May 1, 2009; 28(5): 600 - 621. [Abstract] [PDF]