Randomized kinodynamic planning

Steven M. LaValle, James J. Kuffner

Research output: Contribution to journalConference articlepeer-review

Abstract

This paper presents a state-space perspective on the kinodynamic planning problem, and introduces a randomized path planning technique that computes collision-free kinodynamic trajectories for high degree-of-freedom problems. By using a state space formulation, the kinodynamic planning problem is treated as a 2n-dimensional nonholonomic planning problem, derived from an n-dimensional configuration space. The state space serves the same role as the configuration space for basic path planning; however, standard randomized path planning techniques do not directly apply to planning trajectories in the state space. We have developed a randomized planning approach that is particularly tailored to kinodynamic problems in state spaces, although it also applies to standard nonholonomic and holonomic planning problems. The basis for this approach is the construction of a tree that attempts to rapidly and uniformly explore the state space, offering benefits that are similar to those obtained by successful randomized planning methods, but applies to a much broader class of problems. Some preliminary results are discussed for an implementation that determines kinodynamic trajectories for hovercrafts and satellites in cluttered environments, resulting in state spaces of up to twelve dimensions.

Original languageEnglish (US)
Pages (from-to)473-479
Number of pages7
JournalProceedings - IEEE International Conference on Robotics and Automation
Volume1
StatePublished - 1999
Externally publishedYes
EventProceedings of the 1999 IEEE International Conference on Robotics and Automation, ICRA99 - Detroit, MI, USA
Duration: May 10 1999May 15 1999

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Randomized kinodynamic planning'. Together they form a unique fingerprint.

Cite this