College of Engineering >
Computer Science >
Computer Science Technical Reports >
Please use this identifier to cite or link to this item:
|Title: ||On the Complexity of Kinodynamic Planning|
|Authors: ||Canny, John|
Donald, Bruce Randall
Xavier, Patrick G.
|Keywords: ||computer science|
|Issue Date: ||Aug-1988|
|Publisher: ||Cornell University|
|Abstract: ||In robotics, kinodynamic planning attempts to solve a motion problem subject to simultaneous kinematic and dynamic constraints. We consider the following problem: 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. 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. While exact solutions to this problem are not known, we provide the first provably good approximation algorithm, and show that it runs in polynomial time.|
|Appears in Collections:||Computer Science Technical Reports|
Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.