On the relationship between classical grid search and probabilistic roadmaps

Steven M. LaValle, Michael S. Branicky

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 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 optimal-dispersion 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 PRM and the recent Lazy PRM. This even includes searching using a grid with subsampled collision checking. 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 superior to that obtained by random sampling. Thus, in surprising contrast to recent trends, there is both experimental and theoretical evidence that some forms of grid search are superior to the original PRM.

Original languageEnglish (US)
Title of host publicationAlgorithmic Foundations of Robotics V
Pages59-75
Number of pages17
DOIs
StatePublished - Dec 1 2004
Event5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002 - Nice, France
Duration: Dec 15 2002Dec 17 2002

Publication series

NameSpringer Tracts in Advanced Robotics
Volume7 STAR
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X

Other

Other5th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2002
CountryFrance
CityNice
Period12/15/0212/17/02

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Artificial Intelligence

Fingerprint Dive into the research topics of 'On the relationship between classical grid search and probabilistic roadmaps'. Together they form a unique fingerprint.

  • Cite this

    LaValle, S. M., & Branicky, M. S. (2004). On the relationship between classical grid search and probabilistic roadmaps. In Algorithmic Foundations of Robotics V (pp. 59-75). (Springer Tracts in Advanced Robotics; Vol. 7 STAR). https://doi.org/10.1007/978-3-540-45058-0_5