A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles (extended abstract)

Full text

Pdf (1.05 MB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twelfth annual symposium on Computational geometry table of contents

Philadelphia, Pennsylvania, United States

Pages: 242 - 251

Year of Publication: 1996

ISBN:0-89791-804-5

Authors

Jean-Daniel Boissonnat	INRIA, BP 93, 06902 Sophia Antipolis Cedex, France
Sylvain Lazard	INRIA, BP 93, 06902 Sophia Antipolis Cedex, France

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 38, Citation Count: 5

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/237218.237393 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Pankaj K. Agarwal , Prabhakar Raghavan , Hisao Tamaki, Motion planning for a steering-constrained robot through moderate obstacles, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.343-352, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225158]
	2	J. Barraquand and J-C. Latombe. Nonholonomic mobile robots and optimal maneuvering. Revue d'Intelligence artifie~eUe, 3:77-103, 1989.
	3	J. Barraquand and J-C. Latombe. Nonholonomic multibody mobile robots: controllability and motion planning in the presence of obstacles. Algorithmica, 10:121- 155, 1993.
	4	Behnke, Bachmann, and Fladt. Fundamentals of mathematics, Geometry, volume 1. MIT Press, 1986.
	5	J-D. Boissonnat and X-N. Bui. Accessibility region for a car that only moves forwards along optimal paths. Research Report 2181, INRIA, BP93, 06902 Sophia- Antipolis, France, 1994.
	6	J.-D. Boissonnat, A. C~r6zo, and J. Leblond. Shortest paths of bounded curvature in the plane, internat. J. Intell. Syst., 10:1-16, 1994.
	7	X-N. Bui, P. Sou~res, J-D. Boissonnat, and J-P. Laumond. Shortest path synthesis for Dubins nonholonomic robot. In IEEE Int. Conf. on Robotics and Automation, pages 2-7, San Diego, 8-13 Mai 1994.
	8	K. L. Clarkson , P. W. Shor, Applications of random sampling in computational geometry, II, Discrete & Computational Geometry, v.4 n.5, p.387-421, 1989 [doi>10.1007/BF02187740]
	9	D. P. Dobkin and D. L. Souvaine. Computational geometry in a curved world. Algorithmica, 5:421-457, 1990.
	10	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.
	11	Steven Fortune , Gordon Wilfong, Planning constrained motion, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.445-459, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62256]
	12	P. Jacobs and J. Canny. Planning smooth paths for mobile robots. In Proc. IEEE Internat. ,Conf. Robot. Autom., pages 2-7, 1989.
	13	P. Jacobs, J-P. Laumond, and M. Taix. Efficient motion planners for nonholonomic mobile robots. In Proceedings of the IEEE/RSJ International Workshop on Intelligent Robots and Systems, pages 1229-1235, 1991.
	14	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]
	15	J-C. Latombe. A fast path-planner for a car-like indoor mobile robot. In Proceedings of the 9th National Conference on Artificial Intelligence, pages 659-665, 1991.
	16	Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
	17	J-P. Laumond. Finding collision-free smooth trajectories for a non-holonomic mobile robot, in Proceedings of the International Joint Conference on Artificial intelligence, pages 1120-1123, 1987.
	18	J-P. Laumond, M. Taix, P. Jacobs, and R.M. Murray. A motion planner for nonholonomic mobile robots. IEEE Trans. on Robotics and Automation, 1993.
	19	Zexiang Li , J. F. Canny, Nonholonomic Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1992
	20	Y. Nakamura and R. Mukherjee. Nonholonomic path planning and automation. In Proc. IEEE lht. Conf. on Robotics and Automation, pages 1050-1055, 1989.
	21	J. A. Reeds and L. A. Shepp. Optimal paths for a car that goes both forwards and backwards. Pacific Journal of Mathematics, 145(2), 1990.
	22	H. J. Sussmann and G. Tang. Shortest paths for the reeds-shepp car: a worked out example of the use of geometric techniques in nonlinear optimal control. Research Report SYCON-91-10, Rutgers University, New Brunswick, NJ, 1991.
	23	Hongyan Wang , Pankaj K. Agarwal, Approximation algorithms for curvature-constrained shortest paths, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.409-418, January 28-30, 1996, Atlanta, Georgia, United States
	24	G. Wilfong. Motion planning for an autonomous vehicle. In Proc. IEEE Internat. Conf. Robot. Autom., pages 529-533, 1988.
	25	G. Wilfong. Shortest paths for autonomous vehicles, in Proceedings of the IEEE International on Robotics and Automation, pages 15-20, 1989.

CITED BY 5

	Pankaj K. Agarwal , Therese Biedl , Sylvain Lazard , Steve Robbins , Subhash Suri , Sue Whitesides, Curvature-constrained shortest paths in a convex polygon (extended abstract), Proceedings of the fourteenth annual symposium on Computational geometry, p.392-401, June 07-10, 1998, Minneapolis, Minnesota, United States
	Hee-Kap Ahn , Otfried Cheong , Jiří Matoušek , Antoine Vigneron, Reachability by paths of bounded curvature in convex polygons, Proceedings of the sixteenth annual symposium on Computational geometry, p.251-259, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Wilson D. Esquivel , Luciano E. Chiang, Nonholonomic path planning among obstacles subject to curvature restrictions, Robotica, v.20 n.1, p.49-58, January 2002
	Jonathan Backer , David Kirkpatrick, Finding curvature-constrained paths that avoid polygonal obstacles, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea
	Hamidreza Chitsaz , Steven M. Lavalle , Devin J. Balkcom , Matthew T. Mason, Minimum Wheel-Rotation Paths for Differential-Drive Mobile Robots, International Journal of Robotics Research, v.28 n.1, p.66-80, January 2009