Retraction: A new approach to motion-planning

ABSTRACT

The two-dimensional Movers' Problem may be stated as follows: Given a set of polygonal obstacles in the plane, and a two-dimensional robot system B, determine whether one can move B from a given placement to another without touching any obstacle, and plan such a motion when one exists. Efficient algorithms are presented for the two special cases in which B is either a disc or a straightline segment, running respectively in time 0(n log n) and 0(n2 log n). To solve the problem for a disc one uses the planar Voronoi diagram determined by the obstacles; in the case of a line-segment one generalizes the notion of Voronoi diagram to the 3-dimensional configuration space of the moving segment.

REFERENCES

• 1: John E. Hopcroft , Deborah A. Joseph , Sue H. Whitesides, On the Movement of Robot Arms in Two Dimensional Bounded Regions, Cornell University, Ithaca, NY, 1982
• 2: Tomás Lozano-Pérez , Michael A. Wesley, An algorithm for planning collision-free paths among polyhedral obstacles, Communications of the ACM, v.22 n.10, p.560-570, Oct. 1979 [doi>10.1145/359156.359164]
• 3: J. Reif, "Complexity of the mover's problem and generalizations," Proc. 20th Symp. on the Foundations of Computer Science (1979), pp. 421-427.
• 4: J.T. Schwartz and M. Sharir, "On the piano movers' problem: I. The special case of a rigid polygonal body moving amidst polygonal barriers," to appear in Comm. Pure Appl. Math.
• 5: J.T. Schwartz and M. Sharir, "On the piano movers' problem: II. General techniques for computing topological properties of real algebraic manifolds," to appear in Adv. Appl. Math.
• 6: J.T. Schwartz and M. Sharir, "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., Courant Institute, N.Y.U., 1983.
• 7: D.E. Willard, "A new time complexity for orthogonal range-queries," Proc. 20th Allerton Conf. on Comm. Control and Comput. (1982).
• 8: C.K. Yap, "Motion coordination for two discs," Tech. Rept., Courant Institute, N.Y.U., Jan. 1983.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms