Randomized kinodynamic planning

TLDR

The kinodynamic planning problem is formulated as a 2n‑dimensional nonholonomic problem derived from an n‑dimensional configuration space, with the state space playing the same role as the configuration space in basic path planning. The study introduces a randomized path planning technique that computes collision‑free kinodynamic trajectories for high‑degree‑of‑freedom problems from a state‑space perspective. The method builds a rapidly and uniformly exploring tree over the state space, extending randomized planning benefits to a broader class of kinodynamic problems. Preliminary experiments on hovercrafts and satellites in cluttered environments demonstrate the approach can handle state spaces up to twelve dimensions.

Abstract

The 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. The bases for the 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 the kinodynamic trajectories for hovercrafts and satellites in cluttered environments resulting in state spaces of up to twelve dimensions.