On the Relationship between Classical Grid Search and Probabilistic Roadmaps

TLDR

We present and analyze a spectrum of planners to explore the relationship between classical grid search and probabilistic roadmaps (PRMs). We develop deterministic PRM variants that use low‑discrepancy and low‑dispersion samples, including lattices, and extend classical grid search with subsampling for collision detection and a dispersion‑optimal Sukharev grid to form a lattice‑based roadmap. Experimental and theoretical results show that these deterministic variants outperform the original multiple‑query and lazy PRMs, with some grid‑search variants matching performance, and that they are resolution complete with superior asymptotic convergence, indicating that randomization in the original PRM offers no advantage.

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