Probabilistic Analysis of RRT Trees
This provides theoretical guarantees for RRT, a key algorithm in robotics and motion planning, though it is incremental analysis of existing methods.
The thesis analyzes the Rapidly-exploring Random Tree (RRT) algorithm, showing that the time to cover a d-dimensional unit cube is Θ(1/ε^d log(1/ε)) and the time to reach a positive probability region is O(ε^{-3/2}), with additional bounds on path length and tree height.
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 $ε$ to grow close to every point in the $d$-dimensional unit cube is $Θ\left(\frac1{ε^d} \log \left(\frac1ε\right)\right)$. Also, the time it takes for the tree to reach a region of positive probability is $O\left(ε^{-\frac32}\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$.