Randomized Kinodynamic Planning
- Steven M. LaValle
- James Kuffner, Jr.
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.
|
