On computability of fine motion plans
- 7 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 177-182 vol.1
- https://doi.org/10.1109/robot.1989.99986
Abstract
It is shown that fine motion plans in the LMT framework developed by T. Lozano-Perez, M. Mason and R. Taylor (1984) are computable, and an algorithm for computing them by reducing fine motion planing to an algebraic decision problem is presented. Fine-motion planning involves planning a successful motion of a robot at the fine scale of assembly operations, where control and sensor uncertainty are significant. It is shown that, as long as the envelope of trajectories generated by the control system can be described algebraically, there is an effective procedure for deciding if a successful n-step plan exists. The proposed method makes use of recognizable sets as subgoals for multistep planning. These sets are finitely parameterizable, and it is shown that they are the only sets that need be considered as subgoals. Unfortunately, if the full generality of the LMT framework is used, finding a fine-motion plan can take time double exponential in the number of plant steps.Keywords
This publication has 9 references indexed in Scilit:
- Automatic planning of fine motions: Correctness and completenessPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Complexity of deciding Tarski algebraJournal of Symbolic Computation, 1988
- The complexity of planar compliant motion planning under uncertaintyPublished by Association for Computing Machinery (ACM) ,1988
- Some algebraic and geometric computations in PSPACEPublished by Association for Computing Machinery (ACM) ,1988
- New lower bound techniques for robot motion planning problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1987
- Using Backprojections for Fine Motion Planning with UncertaintyThe International Journal of Robotics Research, 1986
- An exploration of sensorless manipulationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1986
- Automatic Synthesis of Fine-Motion Strategies for RobotsThe International Journal of Robotics Research, 1984
- A Decision Method for Elementary Algebra and GeometryPublished by University of California Press ,1951