Differences
This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
pathplanning [2019/03/11 17:37] sshen [Amélioration d’algorithme RRT] |
pathplanning [2019/04/25 14:08] (current) |
||
|---|---|---|---|
| Line 36: | Line 36: | ||
| 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. | 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 : \\ | 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 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\\ | - Point d'arrivée : (200, 450), le point jaune dans le coin supérieur droit\\ | ||
| Line 53: | Line 54: | ||
| Ici nous présentons trois exemples. | Ici nous présentons trois exemples. | ||
| \\ | \\ | ||
| - | {{ :rrt1.png?!1000 }} | + | {{ :undefined:inkedrrt1_li.png?1000 }} |
| - | \\ | + | |
| + | 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 cercles noirs et les rectangles noirs sont les obstacles;\\ | ||
| Les points bleus sont un chemin le plus proche;\\ | Les points bleus sont un chemin le plus proche;\\ | ||
| Les traits rouges sont l'arbre épandu. | Les traits rouges sont l'arbre épandu. | ||
| \\ | \\ | ||
| - | Source:\\ | ||
| - | Real-time obstacle avoidance for manipulators and mobile robots [en ligne]. Disponible sur : https://ieeexplore.ieee.org/document/1087247 | ||
| + | \\ | ||
| + | Source:\\ | ||
| + | Khatib, Oussama. "Real-time obstacle avoidance for manipulators and mobile robots." Autonomous robot vehicles. Springer, New York, NY, 1986. 396-404. | ||
| ==== Amélioration d’algorithme RRT==== | ==== Amélioration d’algorithme RRT==== | ||
| 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. | 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. | ||
| Line 69: | Line 72: | ||
| 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. | 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. | ||
| \\ | \\ | ||
| - | {{ :rrt2.png?1000 }} | + | {{ ::inkedrrt2_li.png?1000 }} |
| + | |||
| + | 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:\\ | Source:\\ | ||
| Line 80: | Line 88: | ||
| 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. | 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. | ||
| \\ | \\ | ||
| - | {{ :rrt3.png?1000 }} | + | {{ :inkedrrt3_li.png?1000 }} |
| + | 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.\\ | ||
| \\ | \\ | ||
| Line 96: | Line 108: | ||
| 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. | 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 :\\ | ||
| | ^ Longueur de noeud_liste ^ Longueur de chemin ^Temps (s)^ | | ^ Longueur de noeud_liste ^ Longueur de chemin ^Temps (s)^ | ||
| ^ RRT | 919 | 110 |9,56 | | ^ RRT | 919 | 110 |9,56 | | ||
| Line 120: | Line 133: | ||
| 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. | 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. | ||
| - | ===== Conclusion de Projet===== | + | ===== Descriptif des fichiers/code===== |
| - | Ce projet a été très enrichissant pour moi car il m’a permis de découvrir dans les détails de secteur du planification de chemin et il m’a permis de participer concrètement à ses enjeux au travers de mes missions variées comme celle de l’implémentation d’algorithmes différents que j’ai particulièrement apprécié. Ce projet m’a aussi permis d’appliquer mes compétences apprises en majeure Système d’Information, et j’ai aussi eu l’occasion de me former sur de nombreuses technologies que je n’avais pas eu l’occasion d’étudier à l’école (par exemple, C et CUDA). | + | ==== Installation de projet==== |
| + | 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 \\ | ||
| - | J'ai beaucoup amélioré mes propres compétences de programmation (Python). J'ai également utilisé beaucoup d'algorithmes avancés pour compléter ce projet. En plus, comme on a souvent besoin de communiquer avec mes collègues et présenter notre projet, mon niveau de français a également été grandement amélioré. | + | \\ |
| - | + | {{ ::jupyter.png?800 }} | |
| - | Je suis très satisfait d’avoir eu l’occasion de participer à ce projet. Fort de cette expérience, je peux m’orienter vers les métiers d’ingénieur en développement informatique qui me conviennent mieux. | + | \\ |
| + | 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). | 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). | ||