Probabilistic Analysis of RRT Trees
share
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 Θ(1/ϵ^dlog(1/ϵ)). Also, the time it takes for the tree to reach a region of positive probability is O(ϵ^-3/2). 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(√(n)) and the expected height of the tree is bounded above by (e + o(1)) log n.
READ FULL TEXT