Planning for dynamic systems is trajectory exploration through nonconvex state spaces. These non-convexities often include configuration space obstacles and regions of inevitable collision [12]. While sample-based planning algorithms differ in many ways, they commonly conduct many short trajectory explorations to connect or nearly connect a large number of stochastically sampled states with the goal of connecting a start state to a final state or goal region. Earlier algorithms like RRT [12] guarantee under certain conditions [11] with probability one that if a connecting trajectory exists, that the algorithm will find it. Newer planners like RRT~*, PRM~*, SST~*, and FMT~* [8-10, 13, 14] guarantee asymptotic convergence to the globally optimal connecting trajectory. For planning dynamic systems, [16] directly tackles the theoretical issues associated with the differential constraints. However, planners for dynamic systems are still in need of computationally efficient methods to compute distances, e.g. for assessing nearest neighbors, and to steer, i.e. to extend to sampled states. Furthermore, each method must be able to handle numerical issues like sensitivities to initial conditions so that the steering trajectories can be of significant time horizon.
展开▼