DocumentCode :
2529878
Title :
A Voronoi method for the piano-movers problem
Author :
Canny, John
Author_Institution :
MIT AI Lab Cambridge, Mass
Volume :
2
fYear :
1985
fDate :
31107
Firstpage :
530
Lastpage :
535
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Robotics and Automation. Proceedings. 1985 IEEE International Conference on
Type :
conf
DOI :
10.1109/ROBOT.1985.1087297
Filename :
1087297
Link To Document :
بازگشت