RRT木の確率的解析
Probabilistic Analysis of RRT Trees
RRTアルゴリズムが空間全体を覆うまでの時間や領域到達時間を確率的に解析し、最近傍木との関係から経路長と木の高さの上界を示した論文。
著者: Konrad Anand, Luc Devroye
分類: cs.RO, cs.DS, math.PR
原文アブストラクト
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(\frac1{\epsilon^d} \log \left(\frac1\epsilon\right)\right)$. Also, the time it takes for the tree to reach a region of positive probability is $O\left(\epsilon^{-\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$.