Deformable Rapidly-Exploring Random Trees

In this paper, using the Hypercube Diagonal Experiment we first investigate the convergence rates of sampling-based path-planning algorithms in terms of the dimensionnality of the search space. We show that the probability of sampling a point that improves the solution decreases exponentially with the dimension of the problem. We then analyze how the samples can be repositioned in the search space in order to minimize the approximation error. Finally, we present the DRRT (Deformable Rapidly Exploring Random Tree) algorithm that utilizes optimization of sample location in the framework of RRT algorithms to improve convergence. It is shown that the DRRT algorithm significantly outperforms all current sampling-based algorithms in terms of convergence.