Robotic motion planning requires configuration space exploration. In high-dimensional configuration spaces, a complete exploration is computationally intractable. To devise practical motion planning algorithms in such high-dimensional spaces, computational resources have to be expended in proportion to the local complexity of a configuration space region. We propose a novel motion planning approach that addresses this problem by building an incremental, approximate model of configuration space. The information contained in this model is used to direct computational resources to difficult regions. This effectively addresses the narrow passage problem by adapting the sampling density to the complexity of that region. Each sample of configuration space is guaranteed to maximally improve the accuracy of the model, given the available information. Experimental results indicate that this approach to motion planning results in a significant decrease in the computational time necessary for successful motion planning.
Available at: http://works.bepress.com/oliver_brock/3/