Incrementally Reducing Dispersion by Increasing Voronoi Bias in RRTs

We discuss theoretical and practical issues related to using Rapidly-Exploring Random Trees (RRTs) to incrementally reduce dispersion in the configuration space. The original RRT planners use randomization to create Voronoi bias, which causes the search trees to rapidly explore the state space. We introduce RRT-like planners based on exact Voronoi diagram computation, as well as sampling-based algorithms which approximate their behavior. We give experimental results illustrating how the new algorithms explore the configuration space and how they compare with existing RRT algorithms.