Advanced Search

Journal Navigation

Journal Home

Subscriptions

Archive

Contact Us

Table of Contents

CiteULike is a free service for managing and discovering scholarly references - click here to get started.

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
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in Web of Science
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 Web of Science (22)
Right arrow Citing Articles via Google Scholar
Right arrow Citing Articles via Scopus
Google Scholar
Right arrow Articles by LaValle, S. M.
Right arrow Articles by Lindemann, S. R.
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?

On the Relationship between Classical Grid Search and Probabilistic Roadmaps

Steven M. LaValle

Department of Computer Science, University of Illinois, Urbana, IL 61801 USA lavalle{at}cs.uiuc.edu

Michael S. Branicky

Department of Electrical Engineering, and Computer Science, CaseWestern Reserve University, Cleveland, OH 44106 USA

Stephen R. Lindemann

Department of Computer Science, University of Illinois, Urbana, IL 61801 USA

We present, implement, and analyze a spectrum of closely-related planners, designed to gain insight into the relationship between classical grid search and probabilistic roadmaps (PRMs). Building on the quasi-Monte Carlo sampling literature, we have developed deterministic variants of the PRM that use low-discrepancy and low-dispersion samples, including lattices. Classical grid search is extended using subsampling for collision detection and also the dispersion-optimal Sukharev grid, which can be considered as a kind of lattice-based roadmap to complete the spectrum. Our experimental results show that the deterministic variants of the PRM offer performance advantages in comparison to the original, multiple-query PRM and the single-query, lazy PRM. Surprisingly, even some forms of grid search yield performance that is comparable to the original PRM. Our theoretical analysis shows that all of our deterministic PRM variants are resolution complete and achieve the best possible asymptotic convergence rate, which is shown to be superior to that obtained by random sampling. Thus, in surprising contrast to recent trends, there is both experimental and theoretical evidence that the randomization used in the original PRM is not advantageous.

Key Words: motion planning • probabilistic roadmaps • sampling-based motion planning • path planning • quasi-Monte Carlo • discrepancy • algorithms

The International Journal of Robotics Research, Vol. 23, No. 7-8, 673-692 (2004)
DOI: 10.1177/0278364904045481
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
Peng Cheng and V. Kumar
Sampling-based Falsification and Verification of Controllers for Continuous Dynamic Systems
The International Journal of Robotics Research, November 1, 2008; 27(11-12): 1232 - 1245.
[Abstract] [PDF]

Home page
 The International Journal of Robotics ResearchHome page
D. Hsu, J.-C. Latombe, and H. Kurniawati
On the Probabilistic Foundations of Probabilistic Roadmap Planning
The International Journal of Robotics Research, July 1, 2006; 25(7): 627 - 643.
[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
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, 2005; 24(11): 983 - 995.
[Abstract] [PDF]