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. The Complexity of Fine Motion Planning

The Complexity of Fine Motion Planning

File(s)
86-734.pdf (1.95 MB)
86-734.ps (534.19 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6574
Collections
Computer Science Technical Reports
Author
Natarajan, B. K.
Abstract

We study the complexity of fine motion planning for robots with position measurement and damping. A reduction from fine motion planning with position measurement only to the "classical piano mover's problem" is developed, thereby showing it to be feasible in polynomial time. We then show that deciding the existence of fine motion plans for robots with damping in three dimensional scenes is PSPACE-hard and, with a view to finding the cause for the jump in the complexity, we identify a restricted subclass of the PSPACE-hard problem that is PSPACE-complete. Finally, we show how to restrict this subclass to permit polynomial time algorithms for the problems in it.

Date Issued
1986-02
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-734
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

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