Probabilistic Analysis of RRT Trees

Abstract

This thesis presents analysis of the properties and run-time of the Rapidly-exploring Random Tree (RRT) algorithm. It is shown that the time for the RRT with stepsize $\epsilon$ to grow close to every point in the $d$-dimensional unit cube is $\Theta \left(\frac{1}{{\epsilon }^d}\log \left(\frac{1}{\epsilon }\right)\right)$. Also, the time it takes for the tree to reach a region of positive probability is $O\left({\epsilon }^{-\frac{3}{2}}\right)$. Finally, a relationship is shown to the Nearest Neighbour Tree (NNT). This relationship shows that the total Euclidean path length after $n$ steps is $O(\sqrt{n})$ and the expected height of the tree is bounded above by $(e+o(1))\log n$.

29 pages, 10 figures, submitted to The International Journal of Robotics Research