Show simple item record

dc.contributor.authorNatarajan, B. K.en_US
dc.date.accessioned2007-04-23T17:13:05Z
dc.date.available2007-04-23T17:13:05Z
dc.date.issued1986-02en_US
dc.identifier.citationhttp://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR86-734en_US
dc.identifier.urihttps://hdl.handle.net/1813/6574
dc.description.abstractWe 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.en_US
dc.format.extent2041548 bytes
dc.format.extent547006 bytes
dc.format.mimetypeapplication/pdf
dc.format.mimetypeapplication/postscript
dc.language.isoen_USen_US
dc.publisherCornell Universityen_US
dc.subjectcomputer scienceen_US
dc.subjecttechnical reporten_US
dc.titleThe Complexity of Fine Motion Planningen_US
dc.typetechnical reporten_US


Files in this item

Thumbnail
Thumbnail

This item appears in the following Collection(s)

Show simple item record

Statistics