On the general motion planning problem with two degrees of freedom

ABSTRACT

We show that, under reasonable assumptions, any collision-avoiding motion planning problem for a moving system with two degrees of freedom can be solved in time &Ogr;(&lgr;s(n) log2n), where n is the number of collision constraints imposed on the system, s is a fixed parameter depending e.g. on the maximum algebraic degree of these constraints, and &lgr;s(n) is the (almost linear) maximum length of (n,s) Davenport Schinzel sequences. This follows from an upper bound of &Ogr;(&lgr;s(n)) that we establish for the combinatorial complexity of a single connected component of the space of all free placements of the moving system. Although our study is motivated by motion planning, it is actually a study of topological, combinatorial, and algorithmic issues involving a single face in an arrangement of curves. Our results thus extend beyond the area of motion planning, and have applications in many other areas.

REFERENCES

• ASS: P. Agarwal, M. Sharir and P. Shor, Sharp upper and lower bounds for the length of general Davenport Schinzel sequences, Tech. Rept. 332, Comp. Scienc~ Dept., Courant Institute, 1987.
• AS: B. Aronov , M. Sharir, Triangles in space or building (and analyzing) castles in the Air, Proceedings of the fourth annual symposium on Computational geometry, p.381-391, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73432]
• At: M. Atallah, Dynamic computational geometry, Proc. 24th IEEE Syrup. on Foundations of Computer Science, 1983, pp. 92-99. Also in Comp. Math. with Appls. 11 (1985) pp. 1171-1181.
• BO: J.L. Bently and T. Ottmann, Algorithm for reporting and counting geometric intersections, IEEE Tras. on Computers, Vol C-28 (1979), pp. 643-647.
• CG: Bernard Chazelle , Leonidas J. Guibas, Visibility and intersectin problems in plane geometry, Proceedings of the first annual symposium on Computational geometry, p.135-146, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323252]
• CEGSW: K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir and E. Welzl, in preparation.
• DSST: J R Driscoll , N Sarnak , D D Sleator , R E Tarjan, Making data structures persistent, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.109-121, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12142]
• EG: H Edelsbrunner , L J Guibas, Topologically sweeping an arrangement, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.389-403, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12171]
• EGPPSS: Herbert Edelsbrunner , Leonidas J. Guibas , János Pach , Richard Pollack , Raimund Seidel , Micha Sharir, Arrangements of Curves in the Plane - Topology, Combinatorics, and Algorithms, Proceedings of the 15th International Colloquium on Automata, Languages and Programming, p.214-229, July 11-15, 1988
• EGHPPSSS: H. Edelsbrunner , L. J. Guibas , J. Hershberger , J. Pach , R. Pollack, On arrangements of Jordan arcs with three intersections per pair, Proceedings of the fourth annual symposium on Computational geometry, p.258-265, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73420]
• EGS: H. Edelsbrunner , L. J. Guibas , M. Sharir, The complexity of many faces in arrangements of lines of segments, Proceedings of the fourth annual symposium on Computational geometry, p.44-55, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73399]
• ES: H. Edelsbrunner and M. Sharir, The maximum number of ways to stab n disjoint convex sets in the plane is 2n-2, Tech. Rept. 281, Comp. Sci. Dept., Courant Institute, New York 1987 (to appear in Discrete Comput. Geom.)
• FWY: S. Fortune, G. Wilfong and C. Yap, Coordinated motion of two robot arms, Proc. IEEE Conf. on Robotics and Automation. pp. 1216-1223, 1986.
• GHLST: L. Guibas, J. Hershberger, D. Leven, M. Sharir and R. Tarjan, Linear time algorithms for visibility and shortest path problems in triangulated simple polygons, Algorithmica 2 (1987) pp. 209-233.
• HS: S Hart , M Sharir, Nonlinearity of Daveport:80Schinzel sequences and of generalized path compression schemes, Combinatorica, v.6 n.2, p.151-177, 1986 [doi>10.1007/BF02579170]
• KS: K. Kedem , M. Sharir, An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles, Proceedings of the first annual symposium on Computational geometry, p.75-80, June 05-07, 1985, Baltimore, Maryland, United States [doi>10.1145/323233.323244]
• KS2: K. Kedem , M. Sharir, Planning algorithm for a convex polygonal object in two-dimensional polygonal space, Discrete & Computational Geometry, v.5 n.1, p.43-75, Jan. 1990 [doi>10.1007/BF02187779]
• KLPS: Klara Kedem , Ron Livne , János Pach , Micha Sharir, On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles, Discrete & Computational Geometry, v.1 n.1, p.59-71, 1986 [doi>10.1007/BF02187683]
• LS1: Daniel Leven , Micha Sharir, An efficient and simple motion planning algorithm for a ladder amidst polygonal barriers, Journal of Algorithms, v.8 n.2, p.192-215, June 1987 [doi>10.1016/0196-6774(87)90038-1]
• LS2: D. Leven and M. Sharir, Planning a purely translational motion of a convex object in two-dimensional space using generalized Voronoi diagrams, Discrete Comput. Geom. 2 (1987) pp. 9-31.
• LW: 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]
• OSY1: C. O'Dunlaing, M. Sharir and C. Yap, Generalized Voronoi diagrams for a ladder: I. Topological considerations, Comm. Pure Appl. Math. 39 (1986) pp. 423-483.
• OSY2: C. O'Dunlaing, M. Sharir and C. Yap, Generalized Voronoi diagrams for a ladder: i1. Efficient construction of the diagram, Algorithmica 2 (1987) pp. 29-57.
• OY: C. O'Dunlaing and C. Yap, A 'retraction' method for planning the motion of a disc, J. of Algorithms 6 (1985) pp. 104-111.
• PS: J. Pach and M. Sharir, The upper envelope of piecewise linear functions and the region enclosed by comvex plates: combinatorial analysis, Tech. Rept. 279, Comp. Sci. Dept., Courant Institute, March 1987 (to appear in Discrete Comp ut. Geom.)
• PSS: R. Pollack , M. Sharir , S. Sifrony, Separating two simple polygons by a sequence of translations, Discrete & Computational Geometry, v.3 n.2, p.123-136, Jan, 1988 [doi>10.1007/BF02187902]
• SS1: J.T. Schwartz and M. Sharir, On the piano movers' problem: 1. The case of a rigid polygonal body moving amidst polygonal barriers, Comm. Pure Appl. Math. 36 (1983) pp. 345-398.
• SS2: J.T. Schwartz and M. Sharir, On the piano movers' problem: iI. General techniques for calculating topological properties of real algebraic manifolds, Advances Appl. Math. 4 (1983) pp. 298-351.
• SS3: 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, Int. J. Robotics Research, 2 (1983) (3) pp. 46-75.
• SS4: J.T. Schwartz and M. Sharir, On the piano movers' problem: V. The case of a rod moving in 3-D space amidst polyhedral obstacles, Comm. Pure Appl. Math. 37 (1984) pp. 815-848.
• SS5: J.T. Schwartz and M. Sharir, On the two-dimensional Davenport Schinzel problem, Tech. Rept. 193 (revised), Comp. Sci. Dept., Courant institute, New York 1987.
• SA: M. Sharir and E. Ariel-Sheffi, On the piano movers' problem: IV. Various decomposable two-dimensional motion planning problems, Comm. Pure Appl. Math. 37 (1984) pp. 479-493.
• Sh1: M. Sharir, Almost linear upper bounds on the length of general Davenport-Schinzel sequences, Combinatorica, v.7 n.1, p.131-143, Jan. 1987 [doi>10.1007/BF02579209]
• Sh2: M. Sharir, Almost linear upper bounds on the length of general Davenport-Schinzel sequences, Combinatorica, v.7 n.1, p.131-143, Jan. 1987 [doi>10.1007/BF02579209]
• SSi: M. Sharir , S. Sifrony, Coordinated motion planning for two independent robots, Proceedings of the fourth annual symposium on Computational geometry, p.319-328, June 06-08, 1988, Urbana-Champaign, Illinois, United States [doi>10.1145/73393.73426]
• Sho: P. Shor, in preparation.
• Si: S. Sifrony, Ph.D. Dissertation, in progress.
• SiS: S. Sifrony and M. Sharir, A new efficient motionplanning algorithm for a rod in 2-D polygonal space, Algorithmica 2 (1987) pp. 367-402. }
• WS: Ady Wiernik , Micha Sharir, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, Discrete & Computational Geometry, v.3 n.1, p.15-47, Jan., 1988 [doi>10.1007/BF02187894]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.10 Vision and Scene Understanding
            Subjects: Motion

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

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

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems; Graph algorithms

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION
  I.5 PATTERN RECOGNITION
      I.5.4 Applications
          Subjects: Computer vision

General Terms:
Algorithms, Design, Measurement, Performance, Theory