Skip to main content


eCommons@Cornell >
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
Reif, John
Xavier, Patrick G.
Keywords: computer science
technical report
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

Files in This Item:

File Description SizeFormat
88-929.pdf2.03 MBAdobe PDFView/Open
88-929.ps410.05 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us