Kinodynamic Planning

In robotics and motion planning, kinodynamic planning is a class of problems for which velocity, acceleration, and force/torque bounds must be satisfied, together with kinematic constraints such as avoiding obstacles. The term was coined by Bruce Donald, Pat Xavier, John Canny, and John Reif. Donald et al. developed the first polynomial-time approximation schemes (PTAS) for the problem. By providing a provably polynomial-time ε-approximation algorithm, they resolved a long-standing open problem in optimal control. Their first paper considered time-optimal control ("fastest path") of a point mass under Newtonian dynamics, amidst polygonal (2D) or polyhedral (3D) obstacles, subject to state bounds on position, velocity, and acceleration. Later they extended the technique to many other cases, for example, to 3D open-chain kinematic robots under full Lagrangian dynamics. More recently, many practical heuristic algorithms based on stochastic optimization and iterative sampling were developed, by a wide range of authors, to address the kinodynamic planning problem. These techniques for kinodynamic planning have been shown to work well in practice. However, none of these heuristic techniques can guarantee the optimality of the computed solution (i.e., they have no performance guarantees), and none can be mathematically proven to be faster than the original PTAS algorithms (i.e., none have a provably lower computational complexity).