Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Robot motion planning and the single cell problem in arrangements

  • Published:
Journal of Intelligent and Robotic Systems Aims and scope Submit manuscript

Abstract

Robot motion planning has become a central topic in robotics and has been studied using a variety of techniques. One approach, followed mainly in computational geometry, aims to develop combinatorial, nonheuristic solutions to motion-planning problems. This direction is strongly related to the study of arrangements of algebraic curves and surfaces in low-dimensional Euclidean space. More specifically, the motion-planning problem can be reduced to the problem of efficiently constructing a single cell in an arrangement of curves or surfaces. We present the basic terminology and the underlying ideas of the approach. We describe past work and then survey a series of recent results in exact motion planning with three degrees of freedom and the related issues of the complexity and construction of a single cell in certain arrangements of surface patches in three-dimensional space.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Agarwal, P.K. and Aronov, B.: Counting facets and incidences,Discrete Comput. Geom. 7 (1992), 359–369.

    Google Scholar 

  2. Agarwal, P.K., Sharir, M. and Shor, P.W.: Sharp upper and lower bounds on the length of general Davenport—Schinzel sequences,J. Combin. Theory A 52 (1989), 228–274.

    Google Scholar 

  3. Alevizos, P., Boissonnat, J.-D., and Preparata, F.: An optimal algorithm for the boundary of a cell in a union of rays,Algorithmica 5 (1990), 573–590.

    Google Scholar 

  4. Aronov, B., Matoušek, J., and Sharir, M.: On the sum of squares of cell complexities in hyperplane arrangements,J. Combin. Theory Ser. A 65 (1994), 311–321.

    Google Scholar 

  5. Aronov, B. and Ó'Dúnlaing, C.: Analysis of the motion-planning problem for a simple two-link planar arm, Technical Report 314, Courant Institute of Mathematical Sciences, 1987.

  6. Aronov, B., Pellegrini, M., and Sharir, M.: On the zone of a surface in a hyperplane arrangement,Discrete Comput. Geom. 9 (1993), 177–188.

    Google Scholar 

  7. Aronov, B. and Sharir, M.: Triangles in space, or building (and analyzing) castles in the air,Combinatorica 10 (1990), 137–173.

    Google Scholar 

  8. Aronov, B. and Sharir, M.: Castles in the air revisited,Proc. 8th Symp. Comput. Geom. 1992, pp. 146–156.

  9. Aurenhammer, F.: Power diagrams: Properties, algorithms and applications,SIAM J. Comput. 16 (1987), 78–96.

    Google Scholar 

  10. Canny, J.: The complexity of robot motion planning, PhD dissertation, Computer Science Department, MIT, 1987.

  11. Chazelle, B., Edelsbrunner, H., Guibas, L.J., Sharir, M., and Snoeyink, J.: Computing a face in an arrangement of line segments and related problems,SIAM J. Computing 22 (1993), 1286–1302.

    Google Scholar 

  12. Chazelle, B., Guibas, L.J., and Lee, D.T.: The power of geometric duality,BIT 25 (1985), 76–90.

    Google Scholar 

  13. Clarkson, K.L.: Computing a single face in arrangements of segments,Unpublished, 1990.

  14. Clarkson, K.L. and Shor, P.W.: Applications of random sampling in computational geometry, II,Discrete Comput. Geom. 4 (1989), 387–421.

    Google Scholar 

  15. De Berg, M., Van Kreveld, M., and Snoeyink, J.: Point location in zones ofk-flats in arrangements,Proc. 3rd Canadian Conf. Comput. Geom., Vancouver, 1991, pp. 228–232.

  16. Edelsbrunner, H.:Algorithms in Combinatorial Geometry, Springer-Verlag, Heidelberg, 1987.

    Google Scholar 

  17. Edelsbrunner, H., Guibas, L.J., Pach, J., Pollack, R., Seidel, R., and Sharir, M.: Arrangements of curves in the plane — topology, combinatorics, and algorithms,Theoret. Comput. Sci. 92 (1992), 319–336.

    Google Scholar 

  18. Edelsbrunner, H., Guibas, L.J., and Sharir, M.: The complexity and construction of many faces in arrangements of lines and of segments,Discrete Comput. Geom. 5 (1990), 161–196.

    Google Scholar 

  19. Edelsbrunner, H., O'Rourke, J., and Seidel, R.: Constructing arrangements of lines and hyperplanes with applications,SIAM J. Comput. 15 (1986), 341–363.

    Google Scholar 

  20. Edelsbrunner, H., Seidel, R., and Sharir, M.: On the zone theorem for hyperplane arrangements,SIAM J. Comput. 22 (1993), 418–429.

    Google Scholar 

  21. Guibas, L. and Sharir, M.: Combinatorics and algorithms of arrangements, in J. Pach (ed.),New Trends in Discrete and Computational Geometry, Springer-Verlag, 1993, pp. 9–36.

  22. Guibas, L., Sharir, M., and Sifrony, S.: On the general motion planning problem with two degrees of freedom,Discrete Comput. Geom. 4 (1989), 491–521.

    Google Scholar 

  23. Halperin, D.: On the complexity of a single cell in certain arrangements of surfaces related to motion planning,Discrete Comput. Geom. 11 (1994), 1–33.

    Google Scholar 

  24. Halperin, D.: Algorithmic motion planning via arrangements of curves and of surfaces, PhD thesis, Tel-Aviv University, 1992.

  25. Halperin, D., Overmars, M.H., and Sharir, M.: Efficient motion planning for an L-shaped object,SIAM J. Comput. 21 (1992), 1–23.

    Google Scholar 

  26. Halperin, D. and Sharir, M.: On disjoint concave chains in arrangements of (pseudo) lines,Inform. Process. Lett. 40 (1991), 189–192.

    Google Scholar 

  27. Halperin, D. and Sharir, M.: Improved combinatorial bounds and efficient techniques for certain motion planning problems with three degrees of freedom,Comput. Geom. Theory Appl. 1 (1992), 269–303.

    Google Scholar 

  28. Halperin, D. and Sharir, M.: Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment, inProc. 34th Annual Symp. on Foundations of Computer Science (FOCS), Palo Alto, 1993, pp. 382–391.

  29. Halperin, D. and Sharir, M.: Almost tight upper bounds for the single cell and zone problems in three dimensions, inProc. 10th ACM Symp. Computational Geometry, Stony Brook, 1994, pp. 11–20.

  30. Hart, S. and Sharir, M.: Nonlinearity of Davenport—Schinzel sequences and of generalized pathcompression schemes,Combinatorica 2 (1986), 151–177.

    Google Scholar 

  31. Hershberger, J.: Finding the upper envelope ofn line segments in O(n logn) time,Inform. Process. Lett. 33 (1989), 169–174.

    Google Scholar 

  32. Kedem, K., Livne, R., Pach, J., and Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles,Discrete Comput. Geom. 1 (1986), 59–71.

    Google Scholar 

  33. Kedem, K. and Sharir, M.: An efficient motion planning algorithm for a convex polygonal object in two-dimensional polygonal space,Discrete Comput. Geom. 5 (1990), 43–75.

    Google Scholar 

  34. Latombe, J.-C.:Robot Motion Planning, Kluwer Acad. Publ., Boston, 1991.

    Google Scholar 

  35. Leven, D. and Sharir, M.: An efficient and simple motion planning algorithm for a ladder moving in two-dimensional space amidst polygonal barriers,J. Algorithms 8 (1987), 192–215.

    Google Scholar 

  36. Pach, J. and Sharir, M.: The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis,Discrete Comput. Geom. 4 (1989), 291–309.

    Google Scholar 

  37. Pollack, R., Sharir, M., and Sifrony, S.: Separating two simple polygons by a sequence of translations,Discrete Comput. Geom. 3 (1988), 123–136.

    Google Scholar 

  38. Preparata, F.P. and Shamos, M.I.:Computational Geometry — An Introduction, Springer-Verlag, New York, 1985.

    Google Scholar 

  39. Schwartz, J.T. and Sharir, M.: On the two-dimensional Davenport—Schinzel problem,J. Symbol. Comput. 10 (1990), 371–393.

    Google Scholar 

  40. Sharir, M.: Davenport—Schinzel sequences and their geometric applications, in R.A. Earnshaw (ed.),Theoretical Foundations of Computer Graphics and CAD, Springer-Verlag, Berlin, 1988, pp. 253–278.

    Google Scholar 

  41. Sharir, M.: Algorithmic motion planning in robotics,Computer 22 (1989), 9–20.

    Google Scholar 

  42. Wiernik, A. and Sharir, M.: Planar realizations of nonlinear Davenport—Schinzel sequences by segments,Discrete Comput. Geom. 3 (1988), 15–47.

    Google Scholar 

  43. Yap, C.-K.: Algorithmic motion planning, in J.T. Schwartz and C.-K. Yap (eds),Advances in Robotics, Vol. I: Algorithmic and Geometric Aspects of Robotics, Lawrence Erlbaum Associates, New Jersey, 1987, pp. 95–143.

    Google Scholar 

Download references

Author information

Author notes

  1. Dan Halperin

    Present address: Robotics Laboratory, Department of Computer Science, Stanford University, California, USA

Authors and Affiliations

  1. Department of Computer Science, Tel-Aviv University, Israel

    Dan Halperin

Authors
  1. Dan Halperin
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Halperin, D. Robot motion planning and the single cell problem in arrangements. J Intell Robot Syst 11, 45–65 (1994). https://doi.org/10.1007/BF01258293

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01258293

Key words

Search

Navigation