Randomized kinodynamic planning

S. M. LaValle, J. J. Kuffner

Research output: Contribution to journalArticlepeer-review


This paper presents the first randomized approach to kinodynamic planning (also known as trajectory planning or trajectory design). The task is to determine control inputs to drive a robot from an initial configuration and velocity to a goal configuration and velocity while obeying physically based dynamical models and avoiding obstacles in the robot's environment. The authors consider generic systems that express the nonlinear dynamics of a robot in terms of the robot's high-dimensional configuration space. Kinodynamic planning is treated as a motion-planning problem in a higher dimensional state space that has both first-order differential constraints and obstacle based global constraints. 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. The authors have developed a randomized planning approach that is particularly tailored to trajectory planni ng problems in high-dimensional state spaces. The basis for this approach is the construction of rapidly exploring random trees, which offer benefits that are similar to those obtained by successful randomized holonomic planning methods but apply to a much broader class of problems. Theoretical analysis of the algorithm is given. Experimental results are presented for an implementation that computes trajectories for hovercrafts and satellites in cluttered environments, resulting in state spaces of up to 12 dimensions.

Original languageEnglish (US)
Pages (from-to)378-400
Number of pages23
JournalInternational Journal of Robotics Research
Issue number5
StatePublished - May 2001
Externally publishedYes


  • Algorithms
  • Collision avoidance
  • Motion planning
  • Non-holonomic planning
  • Trajectory planning

ASJC Scopus subject areas

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


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

Cite this