Algorithms for computing numerical optimal feedback motion strategies

Steven M. LaValle, Prashanth Konkimalla

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)729-752
Number of pages24
JournalInternational Journal of Robotics Research
Volume20
Issue number9
DOIs
StatePublished - Jan 1 2001

Keywords

  • Algorithms
  • Dynamic programming
  • Mobile robotics
  • Motion planning
  • Navigation functions
  • Nonholonomic planning
  • Optimal control

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Mechanical Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Algorithms for computing numerical optimal feedback motion strategies'. Together they form a unique fingerprint.

  • Cite this