Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Convex tours of bounded curvature

  • Conference paper
  • First Online:

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 855))

Included in the following conference series:

Abstract

We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon withm vertices, containing an obstacle in a form of a simple polygon withn vertices. We present anO(m+n) time algorithm finding the path, going around the obstacle, whose curvature is the smallest possible.

This work has been supported in part by the ESPRIT Basic Research Actions Nr. 7141 (ALCOM II) and Nr. 6546 (PROMotion), NSERC, FCAR and FODAR.

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

Access this chapter

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. A. Aggarwal, L. J. Guibas, J. Saxe, and P. W. Shor. A linear-time algorithm for computing the Voronoi diagram of a convex polygon.Discrete Comput. Geom., 4:591–604, 1989.

    Article MathSciNet  Google Scholar 

  2. J. Canny, B. R. Donald, J. Reif, and P. Xavier. On the complexity of kinodynamic planning. InProc. 29th Annu. IEEE Sympos. Found. Comput. Sci., pages 306–316, 1988.

    Google Scholar 

  3. L. E. Dubins. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents.Amer. J. Math., 79:497–516, 1957.

    MATH MathSciNet  Google Scholar 

  4. S. Fortune and G. Wilfong. Planning constrained motion. InProc. 20th Annu. ACM Sympos. Theory Comput., pages 445–459, 1988.

    Google Scholar 

  5. P. Jacobs and J. Canny. Planning smooth paths for mobile robots. InProc. IEEE Internat. Conf. Robot. Autom., pages 2–7, 1989.

    Google Scholar 

  6. D. G. Kirkpatrick. Optimal search in planar subdivisions.SIAM J. Comput., 12:28–35, 1983.

    MATH MathSciNet  Google Scholar 

  7. J.-C. Latombe.Robot Motion Planning. Kluwer Academic Publishers, Boston, 1991.

    Google Scholar 

  8. C. Ó'Dúnlaing. Motion-planning with inertial constraints.Algorithmica, 2:431–475, 1987.

    MATH MathSciNet  Google Scholar 

  9. M. H. Overmars. A random approach to motion planning. Report RUU-CS-92-32, Dept. Comput. Sci., Univ. Utrecht, Utrecht, Netherlands, 1992.

    Google Scholar 

  10. F. P. Preparata. The medial axis of a simple polygon. InProc. 6th Internat. Sympos. Math. Found. Comput. Sci., volume 53 ofLecture Notes in Computer Science, pages 443–450. Springer-Verlag, 1977.

    Google Scholar 

  11. J. H. Reif and M. Sharir. Motion planning in the presence of moving obstacles. InProc. 26th Annu. IEEE Sympos. Found. Comput. Sci., pages 144–154, 1985.

    Google Scholar 

  12. J. T. Schwartz and M. Sharir. Algorithmic motion planning in robotics. In J. van Leeuwen, editor,Algorithms and Complexity, volume A ofHandbook of Theoretical Computer Science, pages 391–430. Elsevier, Amsterdam, 1990.

    Google Scholar 

  13. P. Švestka. A probabilistic approach to motion planning for car-like robots. Report RUU-CS-93-18, Dept. Comput. Sci., Univ. Utrecht, Utrecht, Netherlands, 1993.

    Google Scholar 

  14. G. Wilfong. Motion planning for an autonomous vehicle. InProc. IEEE Internat. Conf. Robot. Autom., pages 529–533, 1988.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. INRIA, 2004 Route des Lucioles, B.P.109, 06561, Valbonne cedex, France

    Jean-Daniel Boissonnat & Olivier Devillers

  2. Dép. d'informatique, Université du Québec à Hull, Canada

    Jurek Czyzowicz

  3. Dép. d'informatique et de mathématique, Université du Québec à Chicoutimi, Canada

    Jean-Marc Robert

  4. URA 1376, Lab. I3S, INRIA and CNRS, 250 rue Albert Einstein, 06560, Sophia Antipolis, Valbonne, France

    Mariette Yvinec

Authors
  1. Jean-Daniel Boissonnat

    You can also search for this author inPubMed Google Scholar

  2. Jurek Czyzowicz

    You can also search for this author inPubMed Google Scholar

  3. Olivier Devillers

    You can also search for this author inPubMed Google Scholar

  4. Jean-Marc Robert

    You can also search for this author inPubMed Google Scholar

  5. Mariette Yvinec

    You can also search for this author inPubMed Google Scholar

Editor information

Jan van Leeuwen

Rights and permissions

Copyright information

© 1994 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Boissonnat, JD., Czyzowicz, J., Devillers, O., Robert, JM., Yvinec, M. (1994). Convex tours of bounded curvature. In: van Leeuwen, J. (eds) Algorithms — ESA '94. ESA 1994. Lecture Notes in Computer Science, vol 855. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0049413

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp