| 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 planning 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. |
