Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. On the Complexity of Kinodynamic Planning

On the Complexity of Kinodynamic Planning

File(s)
88-929.ps (410.05 KB)
88-929.pdf (1.98 MB)
Permanent Link(s)
https://hdl.handle.net/1813/6769
Collections
Computer Science Technical Reports
Author
Canny, John
Donald, Bruce Randall
Reif, John
Xavier, Patrick G.
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.

Date Issued
1988-08
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR88-929
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance