On the ”Piano Movers” problem. I: The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers. (English) Zbl 0554.51007

Schwartz, Jacob T.; Sharir, Micha

Commun. Pure Appl. Math. 36, 345-398 (1983).

We present an algorithm that solves a two-dimensional case of the following problem which arises in robotics: Given a body B, and a region bounded by a collection of ”walls”, either find a continuous motion connecting two given positions and orientations of B during which B avoids collision with the walls, or else establish that no such motion exists. The algorithm is polynomial in the number of walls ( O(n\({}^ 5)\) if n is the number of walls), but for typical wall configurations can run more efficiently. It is somewhat related to a technique outlined by J. Reif.

MSC:

51H99	Topological geometry
51N99	Analytic and descriptive geometry

Keywords:

algorithm; robotics; continuous motion; wall configurations

References:

[1]	Ignat’yev , M. B. Kulakov , F. M. Pokrovskiy , A. M. Robot manipulator control algorithms 1973
[2]	Lockwood, Book of Curves (1961) · doi:10.1017/CBO9780511569340
[3]	Lozano-Perez, An algorithm for planning collision-free paths among polyhedral obstacles, Comm. ACM 22 pp 560– (1979) · doi:10.1145/359156.359164
[4]	Reif , J. Complexity of the mover’s problem and generalizations, Proc. 20th Symp. on the Foundations of Computer Science 1979 421 427 · doi:10.1109/SFCS.1979.10
[5]	Schwartz, Differential Geometry and Topology (1968)
[6]	Schwartz , J. T. Sharir , M. On the piano movers’ problem, I. The case of a two-dimensional rigid polygonal body moving amidst polygonal barriers 1981 · Zbl 0554.51007
[7]	Tarski, A Decision Method for Elementary Algebra and Geometry (1951) · Zbl 0044.25102
[8]	Udupa , S. Collision detection and avoidance in computer-controlled manipulators 1977