Jump to content

Kinodynamic planning

From Wikipedia, the free encyclopedia

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.[1] 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.[2] [3] 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).

References

[edit]
  1. ^ Donald, B.; Xavier, P.; Canny, J.; Reif, J. (1993), "Kinodynamic motion planning" (PDF), Journal of the ACM, 40 (5): 1048–1066, CiteSeerX 10.1.1.51.1443, doi:10.1145/174147.174150
  2. ^ Donald, B.; Xavier, P. (1995), "Provably good approximation algorithms for optimal kinodynamic planning for Cartesian robots and open chain manipulators" (PDF), Algorithmica, 14 (56): 480–530, doi:10.1007/BF01586637
  3. ^ Donald, B.; Xavier, P. (1995), "Provably good approximation algorithms for optimal kinodynamic planning: Robots with decoupled dynamics bounds" (PDF), Algorithmica, 14 (56): 443–479, doi:10.1007/BF01586636