On the relationship between classical grid search and probabilistic roadmaps

Steven M. LaValle, Michael S. Branicky, Stephen R. Lindemann

Research output: Contribution to journalArticle

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 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, lazyPRM. 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.

Original languageEnglish (US)
Pages (from-to)673-692
Number of pages20
JournalInternational Journal of Robotics Research
Volume23
Issue number7-8
DOIs
StatePublished - Jul 1 2004

Keywords

  • Algorithms
  • Discrepancy
  • Motion planning
  • Path planning
  • Probabilistic roadmaps
  • Quasi-Monte Carlo
  • Sampling-based motion planning

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Mechanical Engineering
  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Applied Mathematics

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