Path Finding - PascalBauer/Notre-bon-plaisir-Pascal-Bauer GitHub Wiki
Explication de l'algorithme de RRT
Pour trouver le chemin que doit parcourir le robot en évitant les obstacles de sa position à un point d’arrivée sélectionné par un clic sur le « mapping » établi, nous avons choisi l’approche RRT (Rapidly-exploring Random Tree). Cette approche a l’avantage de pouvoir être utilisée pour de l’exploration et de fonctionner même si la carte n’est pas complète, alors que le « mapping » est en cours.L’approche RRT laisse la possibilité de l’implémentation du comportement exploratoire.
L’algorithme est le suivant :
- On part d’un point d’origine
- On prend un point aléatoirement sur l’espace libre de la carte
- On se déplace de Δ𝑞 dans la direction de ce point aléatoire à partir du point le plus proche si et seulement si le segment [point obtenu-point le plus proche] est dans l’espace libre . On ajoute le point obtenu à la forêt du point le plus proche dans le graphe.
- On exécute l’algorithme pendant un certain nombre d’itérations que l’on peut choisir comme le nombre de points que l’on veut au final dans notre graphe. Une difficulté de l’algorithme est de trouver dans le graphe le point le plus proche du point « aléatoire ». Pour trouver un tel point, nous avons parcouru le graphe (arbre général) de manière récursive tout en gardant en mémoire le point le plus proche trouvé à l’appel 𝑛 au fil des appels récursifs.
On obtient un graphe comme celui-ci :
Afin d'obtenir le chemin partant de l’origine et allant au point de destination, on prend le point du graphe le plus proche de cette destination : la remontée du graphe jusqu’à l’origine nous donne alors le chemin le plus court pour aller de l’origine à la destination. Il ne nous reste alors en termes de planification plus qu’à prendre en compte la largeur du robot, puis lisser la trajectoire.
Avantages
- simple et rapide
- adapté aux espaces à grande dimension
Inconvénients
- Le nombre de points choisis.
- petites dimensions
État de l'art
Algorithmes existants
Domaines d'applications, avantages et inconvénients de chaque algorithme: Liens
- Algorithme de Dijkstra: http://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra#Avantages_et_inconv.C3.A9nient;performance dans le cas où à partir d'une source unique on veut atteindre de nombreuses destinations. Appliqué par exemple lorsque l'on veut connaitre l'itinéraire d'un lieu vers un autre (il peut y'avaoir plusiseurs chemins).
- Algorithme de Ford-Bellman: http://fr.wikipedia.org/wiki/Algorithme_de_Bellman-Ford; pratique dont le cadre ou dans le graphe il y'a des poids négatifs.
- A*: http://fr.wikipedia.org/wiki/Algorithme_A*; Adapté aux espaces de configuration continues (environnement fermé, map connue à l'avance) ainsi que dans le cadre où on recherche une performance en terme de longueur du chemin ou de précision; cependant avec les grandes dimensions l'algorithme devient très lent ainsi il faut opter pour les algorithmes probabilistes complets comme RRT, Bi-RRT,...
- D*: http://en.wikipedia.org/wiki/D*; adapté aux situations où le graphe change au cours du temps.