Path planning in expansive configuration spaces 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 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 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. |