Title :
A Voronoi method for the piano-movers problem
Author_Institution :
MIT AI Lab Cambridge, Mass
Abstract :
We describe work in progress toward a polynomial-time algorithm for the classical movers´ problem With 6 degrees of freedom. Rotations are represented as a certain 3-dimensional subset of the space of quaternions. This representation gives rise to algebraic constraints on the allowable configurations of the moving object. We define a generalized Voronoi diagram in the configuration space and show that a subset of the diagram, consisting of zero and one dimensional manifolds, can be constructed in polynomial time, and paths found along it. While this subset of the diagram is not always sufficient for path planning, the triangulation of 1- dimensional manifolds can be used as the basis of a complete path planning algorithm by adding other 1-manifolds.
Keywords :
Artificial intelligence; Orbital robotics; Path planning; Polynomials; Quaternions; Robotics and automation; Robots;
Conference_Titel :
Robotics and Automation. Proceedings. 1985 IEEE International Conference on
DOI :
10.1109/ROBOT.1985.1087297