Étude, Implémentation et Comparaison d’Algorithmes de Planification

IMT Atlantique
Sheng SHEN
7 Mars 2019

Encadrants techniques:
Alexandre MANOURY
Mai NGUYEN

Ce rapport de wiki présente notre approche pour le problème de la planification robotique des mouvements dans l’environnement réel. Sur la base d'environnement continu, l’algorithme de planification de chemin proposés sont l’algorithme RRT (Rapidly-exploring random tree). Après avoir calculé le chemin, nous faisons ensuite une comparaison pour récupérer le chemin réel. Pour améliorer l’algorithme RRT, nous nous intéresse aux implémentations massivement parallèles d'algorithmes de planification de mouvement de robot basés. Nous avons utilisé parallèle RRT pour accélérer la vitesse et l'efficacité de recherche. Nos résultats expérimentaux indiquent une accélération significative par rapport aux implémentations de processeurs CPU, conduisant à la planification optimale du mouvement dans l'environnement continu de grandes dimensions.

Mots clés : RRT, parallèle RRT, CUDA, CPU

Dans le cadre de travaux de thèse en appentissage automatique appliqué à la robotique, des algorithmes d’apprentissage ont été développés pour permettre à un robot mobile d’apprendre à se déplacer et à interagir avec son environnement. Ces algorithmes lui permettent de réaliser des tâches complexes et notamment de planifier et d’enchaîner des séquences d’actions (par exemple éviter des obstacles ou utiliser des outils). Nous aimerions pouvoir comparer nos algorithmes à des approches plus classiques permettent également de répondre à ces problématiques de planification et de réalisation de tâches complexes nécessitant des successions d’actions. Ainsi, une comparaison dans différents environnement de tests entre ces deux familles d’algorithmes permettrait une meilleure compréhension de leurs atouts et limites respectives ainsi que de guider le développement de nos algorithmes.

L’objectif de ce projet est d’étudier et de réimplémenter en Python des algorithmes de planification classiques (A*, RRT…), fonctionnant dans des environnements discrets ou non, et de les comparer ensuite à des algorithmes déjà existants. Afin de pouvoir appliquer des programmes de machine learning dans un environnement de simulation de robot, il nous faut comprendre et adapter ces algorithmes de “path finding” à cet environnement. Il nous faudra notamment comparer leurs performances par rapport à certains critères, notamment la prise en compte ou non des degrés de mouvement du robot, la rapidité d'exécution et le fonctionnement en environnement continu ou discret. Il nous faudra donc adapter certaines solutions afin de rendre exploitable nos algorithmes.

Il existe un certain nombre des algorithmes déjà implémentés, par nos tuteurs ainsi que par d’autres chercheurs, qui gèrent la planification de robot dans des univers et des contextes particuliers. Voici une description des plus classiques d’entre eux :

Source :
Noreen, I., Khan, A., & Habib, Z. (2016). A comparison of RRT, RRT* and RRT*-smart path planning algorithms. International Journal of Computer Science and Network Security (IJCSNS), 16(10), 20.

Pour implémenter les algorithmes dans notre environnement, nous devons créer un environnement. De plus, pour comparer avec des algorithmes d’apprentissage dans l'environnement de notre vie réelle, nous nous sommes intéressants à l'environnement continu. Pour créer notre environnement, nous utilisons pymunk et pygame. Les deux librairies de python facilitent le développement de jeux vidéo temps réel. Dans ce programme, la taille de la carte que nous avons conçue est ajustable. Nous pouvons ajuster la taille de la carte en fonction de la taille de la carte d'entrée. Pour assurer que le labyrinthe a un point de départ et un point d'arrivée uniques, nous spécifions deux cercles, dont l'un représente le point de départ sur le coin inférieur gauche pour et le point d'arrivée est sur le coin supérieur droit. À part des positions de départ et d'arrivée, les frontières sont entourées de “murs” et la carte présentes des obstacles de formes différentes. Les détails de la configuration d’environnement continue sont les suivants :

- Point de départ : (400, 100), le point jaune dans le coin inférieur gauche
- Point d'arrivée : (200, 450), le point jaune dans le coin supérieur droit
- Longueur * largeur : 500 * 500, les quatre regtancles jaunes

Source :
Pymunk [en ligne]. Disponible sur : http://www.pymunk.org/en/latest/
Pygame [en ligne]. Disponible sur : https://fr.wikipedia.org/wiki/Pygame

Les algorithmes de planification de chemin traditionnels incluent la méthode du champ potentiel artificiel, et l’algorithme d’optimisation de la colonie de fourmis. Cependant, ces méthodes doivent modéliser les obstacles dans un certain espace. La complexité de calcul est liée de manière exponentielle au degré de liberté du robot. Elle ne convient pas à la résolution des robots à plusieurs degrés de liberté dans des environnements complexes.
L'algorithme de planification de chemin basé sur RRT peut éviter la modélisation d'espace en détectant par collision les points d'échantillonnage dans l'espace d'état, ce qui peut résoudre efficacement des problèmes d'espaces de grande dimension et de contraintes complexes.
Cet algorithme se caractérise par la possibilité de rechercher rapidement et efficacement dans un espace de grande dimension et de guider la recherche vers une zone vierge via des points d'échantillonnage aléatoires de l'espace d'états, ainsi nous pouvons trouver un chemin de planification allant du point de départ au point cible, ce qui peut résoudre le robot à plusieurs degrés de liberté dans un environnement complexe et dynamique.

Ici nous présentons trois exemples.

Le point rouge est le point de départ et Le point jaune est le point de d’arrivée;
Les cercles noirs et les rectangles noirs sont les obstacles;
Les points bleus sont un chemin le plus proche;
Les traits rouges sont l'arbre épandu.

Source:
Khatib, Oussama. “Real-time obstacle avoidance for manipulators and mobile robots.” Autonomous robot vehicles. Springer, New York, NY, 1986. 396-404.

L’algorithme RRT présente également quelques inconvénients: lorsque l’espace C contient un grand nombre d’obstacles ou de contraintes de canal étroites, la vitesse de convergence de l’algorithme est plus lente. Pour résoudre ce problème, nous avons utilisé parallele-RRT pour accélérer la vitesse de convergence et élever son efficace.

L’algorithme RRT ci-dessus ne recherche que l’arbre aléatoire en expansion rapide à partir du point initial. Si deux arbres poussent étendre simultanément à partir du point initial et du point cible pour rechercher l’espace, l’efficacité est plus supérieure. Esn 2000, les professeurs LaValle et Kuffner de l'Université de Tokyo au Japon ont proposé conjointement un algorithme RRT à double arbre connecté basé sur un solde étendu bidirectionnel, appelé l'algorithme RRT-Connect.

Le point rouge est le point de départ et Le point jaune est le point de d’arrivée;
Les cercles noirs et les rectangles noirs sont les obstacles;
Les points bleus sont un chemin le plus proche;
Les traits bleus sont le premier arbre; Les traits verts sont le deuxième arbre.

Source:
Kuffner, J., and S. LaValle RRT-Connect. “An efficient approach to single-query path planning ieee international conference on robotics and automation.” San Francisco (2000): 473-479.

Pour un environnement statique, la complexité temporelle de la RRT est régie par les opérations de graphe, telles que l’évaluation des voisins les plus proches et la détection de collision. Pour l’évaluation des voisins, chaque fois nous ne générons que un point aléatoire. Pour accélérer la recherche de chemin, nous pouvons générer plusieurs points chaque fois et puis trouver un voisin le plus proche. Dans notre cas, la taille de Batching est 5 points.
De plus, nous devons calculer la distance (cf. euclidienne) entre les deux points. Nous pouvons donc utiliser le modèle CUDA. Les fonctions CUDA C exécutées sur le GPU sont appelées KernelsLa détection de collision avec plusieurs points a également un impact significatif sur la réduction de la durée d’exécution du RRT. Pour réaliser notre Kernels de CUDA, nous avons utilisé C et PyCuda.
Le point rouge est le point de départ et Le point jaune est le point de d’arrivée;
Les cercles noirs et les rectangles noirs sont les obstacles;
Les points bleus sont un chemin le plus proche;
Les traits rouges sont l'arbre épandu.

Source:
Bialkowski, J., Karaman, S., & Frazzoli, E. (2011, September). Massively parallelizing the RRT and the RRT. In 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 3513-3518). IEEE.
Jacobs, Sam Ade, et al. “A scalable distributed RRT for motion planning.” 2013 IEEE International Conference on Robotics and Automation. IEEE, 2013.

Après avoir implémenté l’algorithme RRT, nous pouvons récupérer un chemin idéal, mais dans notre environnement continu, pour chaque position, il existe une vitesse correspondant. Par conséquent, nous devons calculer le chemin réel.

Le chemin bleu est le chemin réel, et le noir est le chemin idéal. Nous pouvons remarquer que les formes de deux chemins sont presque les mêmes.
Pour comparer les 3 algorithmes de RRT, nous avons calculé la valeur moyenne de 10 fois et les résultats sont dans le tableau suivant :

Nous pouvons constater que l’algorithme RRT-Connect est le mieux algorithme. En effet, l’algorithme RRT-Connect possède une longueur de 438, qui est la moitié de la longueur des algorithmes RRT et Parallèle-RRT. La longueur de chemin est aussi plus courte que les deux autres algorithmes et le temps moyen d’exécution est également moins que les autres algorithmes, parce que les deux arbres s’épanouissent constamment au lieu d’utiliser une extension aléatoire. Cette extension heuristique rend l'extension de l'arborescence plus gourmande et plus efficace. Pour l’algorithme parallèle RRT, même si chaque fois nous avons généré plusieurs points pour rechercher le chemin, le temps d’exécution moyen est moins que l’algorithme RRT. De plus, la longueur de noeud n’a pas augmenté. Il peut aussi améliorer la vitesse de recherche.

Pour ce projet, nous avons rencontré 3 difficultés principalement:

● La configuration de l’environnement du travail: Au début j’ai essayé de mettre en place dans mon ordinateur, mais je me suis rencontré plusieurs problèmes, par exemple, l’installation de libraire et la compréhension d’utiliser l’environement continu. J’ai perdu énormément de temps.

● Pour implémenter l’algorithme RRT, en début je n’ai pas trouvé une bonne solution pour détecter la collision. Sur l’internet, il calcule plutôt la disatance euclienne entre le point généré de manière aléatoire et le centre du cercle, et puis il compare cette distance avec le rayon d’obstacle. En effet, cette méthode ne convient que pour calculer l'obstacle sous forme de cercle. Si les obstacles sont la forme rectangle ou irréguliers, je ne peut plus utiliser cette méthode. Pour résoudre ce problème, j'ai essayé de diviser la distance entre deux points en un grand nombre de petits segments, et puis j’ai pris le point de départ de chaque segment. J’ai calculé ensuite deux nombres entiers près du point de départ (l'un est plus petit que son plus grand entier et l'autre est plus petit que son plus petit entier), pour détecter la présence d'obstacle.

● Quand j’ai en début installé le CUDA, il existe plusieurs bugs. De plus, il doit comprendre comment utiliser le CUDA et les conceptions comme « block size » et « grid ». Il doit aussi étudier comment programmer le Kernel.

Ce rapport technique décrit ses algorithmes d'origine et des variantes d'autres algorithmes RRT. Afin d'optimiser la vitesse de convergence de l'algorithme RRT, un algorithme RRT parallèle est proposé. D’une part, les avantages de l’algorithme RRT sont simples et faciles à mettre en œuvre. Il peut être utilisé dans la planification de chemin de grande dimension et il permet toujours de trouver une solution réalisable. D’autre part, il a aussi des inconvénients: Par exemple, il est difficile à obtenir la solution plus optimale pour l’algorithme RRT. Nous pouvons utiliser l'algorithme RRT* pour l’amélioration. Il existe également un effet de “longue traîne”, tel que le point au début de l'expansion est utile, et le point d'échantillonnage aléatoire suivant ne peut pas être utilisé complètement. Il a perdu plusieurs temps. Nous pouvons utiliser RRT en temps ou RRT dynamique pour optimiser l'algorithme RRT ,etc.

Télécharger le projet:
git clone https://github.com/Pikalchemist/lems
Installer les librairies:
./install-dependencies.sh
sudo python3 -m pip install -e .
Changer la branche:
git checkout sheng
Enter la répertoire ./lems/examples:
cd ./lems/examples
Utiliser Jupyter pour ouvrir mon projet:
jupyter notebook

Il existe plusieurs fichiers, ce que nous utilisons est les fichiers suivants:
rrt.ipynb : l'algorithme RRT
rrt-connect.ipynb : l'algorithme RRT-Connect
p-rrt.ipynb : l'algorithme parallèle RRT
Environnement.ipynb : il permet de créer l'environnement continu ou discret
rrt.py : exemple de pygame RRT

Pour les détails de ce projet, vous pouvez regarder mon rapport technique et les codes sur ce Github (https://github.com/Pikalchemist/lems/tree/sheng).