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

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.

### 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 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.