Kinodynamic Motion Planning

Authors

Bruce Donald, Patrick Xavier, John Canny, John Reif

Year

1993

Journal Paper

Algorithm

Kinodynamic Motion Planning

Source

Journal of the ACM

Identifiers

DOI 10.1145/174147.174150

Abstract¶

Kinodynamic planning attempts to solve a robot motion problem subject to simultaneous kinematic and dynamics constraints. In the general problem, given a robot system, we must find a minimal-time trajectory that goes from a start position and velocity to a goal position and velocity while avoiding obstacles by a safety margin and respecting constraints on velocity and acceleration. We consider the simplified case of a point mass under Newtonian mechanics, together with velocity and acceleration bounds. The point must be flown from a start to a goal, amidst polyhedral obstacles in 2D or 3D. Although exact solutions to this problem are not known, we provide the first provably good approximation algorithm, and show that it runs in polynomial time.

Summary¶

Formulates kinodynamic motion planning as planning under simultaneous kinematic and dynamic constraints, including velocity, acceleration, obstacle clearance, and minimum-time objectives. The work established the term and problem class, connecting robot motion planning with dynamics-aware trajectory search and computational complexity.