论文标题
RRT树的概率分析
Probabilistic Analysis of RRT Trees
论文作者
论文摘要
本文介绍了快速探索随机树（RRT）算法的性质和运行时间的分析。结果表明，在$ d $二维单位立方体中，带有sptepize $ε$的RRT的时间是$θ\ left（\ frac1 {ε^d} \ log \ lod \ left（\frac1ε\ right）\ right）\ right）$。同样，到达积极概率区域所需的时间为$ o \ left（ε^{ - \ frac32} \ right）$。最后，向最近的邻居树（NNT）显示了关系。这种关系表明，$ n $ steps之后的欧几里得路径长度为$ O（\ sqrt n）$，而树的预期高度则以$（e + o（e + o（1））\ log n $限制。
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$.
