On the Piano Movers' Problem: III. Coordinating the Motion of Several Independent Bodies: The Special Case of Circular Bodies Moving Amidst Polygonal Barriers

Abstract

We present an algorithm that solves the following motion- planning problem that arises in robotics: Given several two-dimensional circular bodies B ₁, B₂, ..., and a region bounded by a collection of "walls, " either find a continuous motion connecting two given configurations of these bodies during which they avoid collision with the walls and with each other, or else establish that no such motion exists. This paper continues other studies by the authors on motion- planning algorithms for other kinds of moving objects. The algorithms presented are polynomial in the number of walls for each fixed number of moving circles (for two moving circles the algorithm is shown to run in time O(n³) if n is the number of walls), but with exponents increasing with the number of moving circles.

Get full access to this article

View all access options for this article.

References

Hopcroft, J.E. , Joseph, D.A. , and Whitesides, S.H. 1982 (Mar.). On the movement of robot arms in 2-dimensional bounded regions. Tech. Rept. TR 82-486. Ithaca, N.Y.: Cornell University Computer Science Department .

Ignat'yev, M.B. , Kulakov, F.M. , and Pokrovskiy, A.M. 1973. Robot manipulator control algorithms. Rept. No. JPRS 59717 National Technical Information Service. Springfield, Va.

Lockwood, E.H. , and Prag, A. 1961. Book of curves. Cambridge, England: Cambridge University Press.

Lozano-Perez, T. , and Wesley, M. 1979. An algorithm for planning collision-free pathes among polyhedral obstacles. Commun. ACM 22:560-570.

Moravec, H.P. 1980 (Sept.). Obstacle avoidance and navigation in the real world by a seeing robot rover. Ph.D. diss., Stanford University. Rept. No. AIM-340. Stanford, Calif.: Stanford University Artificial Intelligence Laboratory.

Reif, J. 1979. Complexity of the mover's problem and generalizations. Proc. 20th IEEE Symp. Found. Comput. Sci. New York: IEEE, pp. 241-247.

Schwartz, J.T. 1968. Differential geometry and topology. New York: Gordon and Breach.

Schwartz, J.T. , and Sharir, M. 1982 (Sept.). On the piano movers' problem: III. Coordinating the motion of several independent bodies: The special case of circular bodies moving amidst polygonal barriers. Tech. Rept. No. 52. New York: Courant Institute Computer Science Department, New York University.

Schwartz, J.T. , and Sharir, M. 1983a. On the piano movers' problem: I. The special case of a rigid polygonal body moving amidst polygonal barriers. Commun. Pure Appl. Math. 36:345-398.

10.

Schwartz, J.T. , and Sharir, M. 1983b. On the piano movers' problem: II. General techniques for computing topological properties of real algebraic manifolds. Adv. Appl. Math., in press.

11.

Udupa, S. 1977. Collision detection and avoidance in computer-controlled manipulators. Ph.D. diss., California Institue of Technology .