Advanced Search

Journal Navigation

Journal Home

Subscriptions

Archive

Contact Us

Table of Contents

Sign In to gain access to subscriptions and/or personal tools.
The International Journal of Robotics Research
This Article
Right arrow Full Text (PDF)
Right arrow References
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Right arrow Citation Map
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to Saved Citations
Right arrow Download to citation manager
Right arrowRequest Permissions
Right arrow Request Reprints
Right arrow Add to My Marked Citations
Citing Articles
Right arrow Citing Articles via HighWire
Right arrow Citing Articles via Google Scholar
Right arrow Citing Articles via Scopus
Google Scholar
Right arrow Articles by Barraquand, J.
Right arrow Articles by Raghavan, P.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Complore   Add to Connotea   Add to Del.icio.us   Add to Digg   Add to Reddit   Add to Technorati   Add to Twitter  
What's this?

A Random Sampling Scheme for Path Planning

Jérôme Barraquand

Salomon Brothers Int. Ltd. Victoria Plaza 111 Buckingham Palace Road London SWIW 0SB, UK

Lydia Kavraki

Department of Computer Science Rice University Houston, TX 77005-1892

Jean-Claude Latombe

Department of Computer Science Stanford University Stanford, CA 94305, USA

Rajeev Motwani

Department of Computer Science Stanford University Stanford, CA 94305, USA

Tsai-Yen Li

Department of Computer Science National Chengchi University Wenshan, Taipei, Taiwan

Prabhakar Raghavan

IBM Almaden Research Center San Jose, CA 95120, USA

Several randomized path planners have been proposed dur ing the last few years. Their attractiveness stems from their applicability to virtually any type of robots, and their empir ically observed success. In this article, we attempt to present a unifying view of these planners and to theoretically explain their success. First, we introduce a general planning scheme that consists of randomly sampling the robot 's configuration space. We then describe two previously developed planners as instances of planners based on this scheme, but applying very different sampling strategies. These planners are probabilis tically complete: if a path exists, they will find one with high probability, if we let them run long enough. Next, for one of the planners, we analyze the relation between the probability of failure and the running time. Under assumptions characteriz ing the "goodness" of the robot's free space, we show that the

The International Journal of Robotics Research, Vol. 16, No. 6, 759-774 (1997)
DOI: 10.1177/027836499701600604
Add to CiteULike CiteULike   Add to Complore Complore   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us   Add to Digg Digg   Add to Reddit Reddit   Add to Technorati Technorati   Add to Twitter Twitter    What's this?


This article has been cited by other articles:


Home page
 The International Journal of Robotics ResearchHome page
C. Sultan, S. Seereram, and R. K. Mehra
Deep Space Formation Flying Spacecraft Path Planning
The International Journal of Robotics Research, April 1, 2007; 26(4): 405 - 430.
[Abstract] [PDF]

Home page
 The International Journal of Robotics ResearchHome page
G. Varadhan, S. Krishnan, T. V.N. Sriram, and D. Manocha
A Simple Algorithm for Complete Motion Planning of Translating Polyhedral Robots
The International Journal of Robotics Research, November 1, 2006; 25(11): 1049 - 1070.
[Abstract] [PDF]

Home page
 The International Journal of Robotics ResearchHome page
J. P. van den Berg and M. H. Overmars
Using Workspace Information as a Guide to Non-uniform Sampling in Probabilistic Roadmap Planners
The International Journal of Robotics Research, December 1, 2005; 24(12): 1055 - 1071.
[Abstract] [PDF]

Home page
 The International Journal of Robotics ResearchHome page
D. Hsu, R. Kindel, J.-C. Latombe, and S. Rock
Randomized Kinodynamic Motion Planning with Moving Obstacles
The International Journal of Robotics Research, March 1, 2002; 21(3): 233 - 255.
[Abstract] [PDF]

Home page
 The International Journal of Robotics ResearchHome page
G. Sanchez and J.-C. Latombe
On Delaying Collision Checking in PRM Planning: Application to Multi-Robot Coordination
The International Journal of Robotics Research, January 1, 2002; 21(1): 5 - 26.
[Abstract] [PDF]