Probabilistic Analysis of RRT Trees
Konrad Anand, Luc Devroye · arXiv (Cornell University) · 2020
Cette thèse présente l'analyse de les propriétés et le temps d'exécution de l'algorithme Rapidly-exploring Random Tree (\textsc{rrt}). C'est montrer que la temps pour le \textsc{rrt} avec largeur de pas $\epsilon$ à devenir proche à toutes les pointes dans le cube unité de dimension $d$ est bondée en haut et dessus par un constant multiple de un sur epsilon à la d multiplié par le log de l'inverse de epsilon.. Aussi, le temps ça prends à arriver a un région de probabilité positive est moins qu'un constant multiple de epsilon à la moins 3/2. Finalement, un relation avec l'Arbre des plus proches voisins (\textsc{nnt}) est montré. Cet relation montre que la longueur du trajet totale Euclidien après $n$ pas est moins qu'un constant multiple de la racine carrée de n, et l'espérance mathématique de l'hauteur est bondé par e log n plus un terme d'ordre inférieur