KINODYNAMIC MOTION PLANNING

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