Motion planning for a steering-constrained robot through moderate obstacles

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Motion planning for a steering-constrained robot through moderate obstacles

Full text

Pdf (1.11 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-seventh annual ACM symposium on Theory of computing table of contents

Las Vegas, Nevada, United States

Pages: 343 - 352

Year of Publication: 1995

ISBN:0-89791-718-9

Authors

Pankaj K. Agarwal	Computer Science Department, Duke University, Box 90129, Durham, NC
Prabhakar Raghavan	IBM T.J. Watson Research Center, Yorktown Heights, NY
Hisao Tamaki	IBM Tokyo Research Laboratory, 1623-14 Shimotsuruma, Yamato-shi, Kanagawa 242, Japan

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 32, Citation Count: 10

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/225058.225158 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	J. Barraquand and J-C. Latombe. Nonholonomic mobile robots and optimal maneuvering. Revue d 'Intelligence Art@ielle, 3:77-103, 1989.
	2	J. Barraquand and J-C. Latombe. Nonholonomic multi-body mobile robots: controllability and motion planning in the presence of obstacles. Algorithmic, 10:12 1-1 55, 1993.
	3	X. Bui, J. Boissonnat, P. Soueres, and J. Leblond. Short-est path synthesis for Dubins non-holonomic robot. Pr-oceedings of the IEEE International Confewzce on Ro-botics and Automation, 1994.
	4	J. Boissonnat, A. C6rezo, and J. Leblond. Shortest paths of bounded curvature in the plane. Proceedings of the IEEE In~ernational Confewnceon Robotics andAutoma-tion, 1992.
	5	L.E. Dubins. On curves of minimal length with a con-straint on average curvature and with prescribed initial and terminal positions and tangents. American Journal of Mathematics, 79:497-5 16, 1957.
	6	S. Fortune and G. Wilfong. Planning constrained motion. In Annals ofA4ath. andArt. Intell., pages 21-82, 1991.
	7	T. Fraichard. Smooth trajectory planning for a car in a structured world. In Proceedings of the IEEE Intern-ational Conference on Robotics and Automation, pages 318-323, 1991.
	8	P. Jacobs and J. Canny. Planning smooth paths for mobile robots. In Proceedings of the IEEE International Con-ference on Robotics and Automation, pages 2-7, 1989.
	9	P. Jacobs, J-P. Laumond, and M. Taix. Efficient motion planners for nonbolonomic mobile robots. In Pwceed-ings of the IEEE/RSJ International Workshop on Intelli-gent Robots and Systems, pages 1229-1235, 1991.
	10	J-C. Latombe. A fast path-planner for a car-like indoor mobile robot. In Pwceedings of the 9th National Con-jxmce on Art@cialIntelligence, pages 65!L665, 1991.
	11	Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
	12	J-P. Laumond and T. Simeon. Motion planning foratwo degrees of freedom mobile robot with towing. Technical Report 89148, LAASKNRS, Toulouse, 1989.
	13	J-P. Laumond, M. Taix, and P. Jacobs. A motion planner for car-like robots based on a global/local approach. In Proceedings of the IEEE/RSJIntemational Workshop on Intelligent Robots and Systems, pages 76>773, 1990.
	14	J-P. Laumond. Finding collision-free smooth trajecto-ries for a non-holonomic mobile robot. In Pwceedings of the International Joint Conference on Artificial Intel-ligence, pages 112(L1 123, 1987.
	15	B. Mirtich and J. Canny. Using skeletons for nonholo-nomic path planning among obstacles. In Proceedings of the IEEE International Confenmce on Robotics and Automa~ion, pages 2533-2540, 1992.
	16	Christos H. Papadimitriou , Mihalis Yannakakis, Shortest paths without a map, Theoretical Computer Science, v.84 n.1, p.127-150, July 22, 1991 [doi>10.1016/0304-3975(91)90263-2]
	17	Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
	18	J.A. Reeds and L.A. Shepp. Optimal paths for a car that goes both forwards and backwards. Pacljic Journal of Mathematics, 145:367-393, 1990.
	19	H. Wang, P. Agarwal and J. Reif. Approximation algo-rithms for shortest paths with bounded curvature in 2 and higher dimensions, manuscript.
	20	G. Wilfong. Motion planning for an autonomous vehi-cle. In Proceedings of the IEEE International Confeirmce on Robotics and Automation, pages 529-533, 1988.
	21	G. Wilfong. Shortest paths for autonomous vehicles. In Proceedings of the IEEE International Confewnce on Robotics and Automation, pages 15-20, 1989.

CITED BY 10

	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
	Jean-Daniel Boissonnat , Sylvain Lazard, A polynomial-time algorithm for computing a shortest path of bounded curvature amidst moderate obstacles (extended abstract), Proceedings of the twelfth annual symposium on Computational geometry, p.242-251, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	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
	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
	Alok Aggarwal , Don Coppersmith , Sanjeev Khanna , Rajeev Motwani , Baruch Schieber, The angular-metric traveling salesman problem, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.221-229, January 05-07, 1997, New Orleans, Louisiana, United States
	Sergey Bereg , David Kirkpatrick, Curvature-bounded traversals of narrow corridors, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	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
	R. Cerulli , P. Festa , G. Raiconi , G. Visciano, The Auction Technique for the Sensor Based Navigation Planning of an Autonomous Mobile Robot, Journal of Intelligent and Robotic Systems, v.21 n.4, p.373-395, April 1998
	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