Search Space Design

Path planning in expansive configuration spaces
David Hsu, Jean-Claude Latombe and Rajeev Motwani  (ICRA 1997)

Available from:

We introduce the notion of expansiveness to characterize a family of robot configuration spaces whose connectivity can be effectively captured by a roadmap of randomly-sampled milestones. The analysis of expansive configuration spaces has inspired us to develop a new randomized planning algorithm. This algorithm tries to sample only the portion of the configuration space that is relevant to the current query, avoiding the cost of precomputing a roadmap for the entire configuration space. Thus, it is well-suited for problems where a single query is submitted for a given environment. The algorithm has been implemented and successfully applied to complex assembly maintainability problems from the automotive industry.

On the relationship between classical grid search and probabilistic roadmaps
S. M. LaValle, M. S. Branicky, and S. R. Lindemann  (IJRR '04)

Available from:

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.

Steps toward derandomizing RRTs
S. R. Lindemann and S. M. LaValle  (IWRMC '04)
Available from:

We present two motion planning algorithms, based on the Rapidly Exploring Random Tree (RRT) family of algorithms. These algorithms represent the first work in the direction of derandomizing RRTs; this is a very challenging problem due to the way randomization is used in RRTs. In RRTs, randomization is used to create Voronoi bias, which causes the search trees to rapidly explore the state space. Our algorithms take steps to increase the Voronoi bias and to retain this property without the use of randomization. Studying these and related algorithms will improve our understanding of how efficient exploration can be accomplished, and will hopefully lead to improved planners. We give experimental results that illustrate how the new algorithms explore the state space and how they compare with existing RRT algorithms.