On the complexity of kinodynamic planning
The following problem, is considered: given a robot system, find a minimal-time trajectory from a start position and velocity to a goal position and velocity, while avoiding obstacles and respecting dynamic constraints on velocity and acceleration. The simplified case of a point mass under Newtonian mechanics together with velocity and acceleration bounds is considered. The point must be flown from a start to a goal, amid 2-D or 3-D polyhedral obstacles. While exact solutions to this problem are not known, the first provably good approximation algorithm is given and shown to run in polynomial time.
Canny, J; Reif, J; Donald, B; Xavier, P
Start / End Page
International Standard Serial Number (ISSN)