Probabilistic Analysis of RRT Trees

MaRDI QIDQ6339944zbMATH OpenFDO

Authors Konrad Anand, Luc Devroye

Publication date 3 May 2020

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 $Thetaleft(frac1epsilo{n}^{d}logleft(frac1epsilonight)ight)$. Also, the time it takes for the tree to reach a region of positive probability is $Oleft(epsilo{n}^{-frac32}ight)$. 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(sqrtn)$ and the expected height of the tree is bounded above by $(e+o(1))logn$.

This page was built for publication: Probabilistic Analysis of RRT Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6339944)