On the complexity of kinodynamic planning


Journal Article

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.

Duke Authors

Cited Authors

  • Canny, J; Reif, J; Donald, B; Xavier, P

Published Date

  • December 1, 1988

Published In

Start / End Page

  • 306 - 316

International Standard Serial Number (ISSN)

  • 0272-5428

Citation Source

  • Scopus