Titre: Algorithmes SLAM (Simultaneous Localization et Mapping): Vers une Implémentation Embarquée
Auteurs: M. ABOUZAHIR MOHAMED
Ecole/Université: Université Paris Sud
Résumé: La navigation autonome est un axe de recherche principal dans le domaine de la robotique mobile. Dans ce contexte, le robot doit disposer des algorithmes qui lui permettent d’évoluer de manière autonome dans des environnements complexes et inconnus. Les algorithmes de SLAM (Simultaneous Localization et Mapping) permettent à un robot de cartographier son environnement tout en se localisant dans l’espace. Les algorithmes SLAM sont de plus en plus performants, mais aucune implémentation matérielle ou architecturale complète n’a eu lieu.
Une telle implantation d’architecture doit prendre en considération la consommation d’énergie, l’embarquabilité et la puissance de calcul. Ce travail scientifique vise à évaluer des systèmes SLAM embarqués. La méthodologie adoptera une approche A3 (Adéquation Algorithme Architecture) pour améliorer l’efficacité de l’implantation des algorithmes. Le système SLAM embarqué doit disposer d’une architecture électronique et logicielle permettant d’assurer la production d’information pertinentes à partir de données capteurs, tout en assurant la localisation de l’embarquant dans son environnement. Les premiers travaux de cette thèse ont consisté à explorer les différentes approches algorithmiques permettant la résolution du problème de SLAM. Cette étude, nous a permet d’évaluer quatre algorithmes de différente nature: FastSLAM2.0, ORB SLAM, RatSLAM et le SLAM linéaire.
Ces algorithmes ont été ensuite évalués sur plusieurs architectures pour l’embarqué afin d’étudier leur portabilité sur des systèmes de faible consommation énergétique et de ressources limitées. Après avoir analysé profondément les évaluations temporelles de chaque algorithme, le FastSLAM2.0 est finalement choisi, pour un compromis temps d’exécution-consistance de résultat de localisation, comme candidat pour une étude plus approfondie sur une architecture hétérogène embarquée.
La seconde partie de cette thèse est consacré à l’étude d’un système embarqué implémentant le FastSLAM2.0 monoculaire dédié aux environnements larges. Une réécriture algorithmique du FastSLAM2.0 a été nécessaire afin de l’adapter au mieux aux contraintes imposées par les environnements de grande échelle. Dans une démarche A3, le FastSLAM2.0 a été implanté sur une architecture hétérogène CPU-GPU. Grâce à un partitionnement efficace, un facteur d’accélération global de l’ordre de 22 a été obtenu sur une architecture récente dédiée pour l’embarqué. Une deuxième instance matérielle basée sur une architecture programmable FG est proposée. Les gains obtenus sont conséquent, même par rapport aux GPU haut-de-gamme qui disposent actuellement d’un grand nombre de ceours. Le système résultant peut cartographier des environnements larges tout en garantissant le compromis entre la consistance des résultats de localisation et le temps réel. Ces travaux de thèse ont permis de mettre en avant l’intérêt des architectures hétérogènes parallèles (multicoeurs-GPU) pour le portage des algorithmes SLAM. Les architectures hétérogènes à base du FPGA peuvent particulièrement devenir des candidats potentiels pour porter des algorithmes complexes traitant des données massives.
Extrait du sommaire:
1 Algorithmes SLAM et architectures dédiées : état de l’art 7
1.1 Localisation et cartographie simultanées 8
1.2 Nécessité du SLAM pour la navigation autonome 9
1.3 Le problème SLAM est-il résolu ? 10
1.4 Formalisation d’un système de SLAM moderne 11
1.4.1 Phase d’acquisition des données capteurs 12
1.4.2 Phase de prétraitement : 12
1.4.3 Coeur SLAM 17
1.5 Résolution du SLAM 19
1.5.1 L’approche probabiliste 19
1.5.2 Approche de structuration à partir du mouvement 20
1.5.3 Approche bio-inspirée 21
1.6 Architectures de calcul embarqué pour le SLAM 21
1.7 Synthèse 22
1.8 Conclusion 23
2 Méthodologie d’évaluation et de conception 27
2.1 Introduction 28
2.2 Adéquation Algorithme Architecture : Application au SLAM 28
2.2.1 Modèle et spécifications algorithmiques 29
2.2.2 Factorisation algorithmique 30
2.2.3 Modèle Architecturale 31
2.2.4 Modèle d’implémentation 32
2.2.5 Transformation de graphe et adéquation 33
2.3 Outils de Prototypage et méthodologie d’évaluation 33
2.3.1 Outils de simulation 33
2.3.2 Données Expérimentales 35
2.3.3 Validation Hardware In the Loop 37
2.3.4 Critères d’évaluation 39
2.3.5 Évaluation des temps d’exécution 40
2.4 Outils de développement et de conception 41
2.4.1 Optimisation logicielle sur architectures multicoeurs 41
2.4.2 Calcul sur GPU 41
2.4.3 Outils de synthèse et de conception sur FPGA 43
2.5 Bilan 44
3 Étude algorithmique et choix des architectures 46
3.1 Introduction 48
3.2 Prétraitement des données capteurs 48
3.2.1 Extraction des amers 48
3.2.2 Appariement des amers 49
3.2.3 Étape d’initialisation 49
3.3 Algorithme FastSLAM2.0 50
3.3.1 Approche de l’indépendance conditionnelle 50
3.3.2 Structure de données 50
3.3.3 Échantillonnage des particules 50
3.3.4 Mise à jour de la position des particules 51
3.3.5 Estimation des amers 51
3.3.6 Gestion de la carte et représentation par arbre binaire 51
3.3.7 Rééchantillonnage 52
3.4 Algorithme ORB SLAM 52
3.4.1 Présentation du système 52
3.4.2 Tâche de suivi 54
3.4.3 Cartographie locale 55
3.4.4 Fermeture de boucle 56
3.5 Algorithme Bio-inspiré : RatSLAM 56
3.5.1 L’architecture du RatSLAM 57
3.5.2 La dynamique du RatSLAM 58
3.6 Le SLAM Linéaire 61
3.6.1 Structure des cartes locales 61
3.6.2 Principe de fusion de deux cartes locales 61
3.6.3 Fusion d’une séquence de cartes locales 62
3.7 Évaluation de l’aspect fonctionnel des algorithmes 64
3.8 Découpage en blocs fonctionnels 65
3.9 Choix des architectures et évaluation temporelle 68
3.9.1 Choix des architectures 68
3.9.2 Évaluation des temps d’exécution 70
3.10 Comparaison des performances 74
3.11 Bilan 78
4 FastSLAM2.0 : Vers une implantation embarquée 81
4.1 Introduction 82
4.2 Définition du problème 82
4.3 Analyses des dépendances de l’algorithme 84
4.4 Implémentation sur une architecture multi-coeurs homogène 86
4.4.1 Temps d’exécution global 86
4.4.2 Optimisation parallèle 88
4.4.3 Évaluation des résultats de l’optimisation parallèle 90
4.4.4 Analyses des résultats 91
4.4.5 Évaluation des résultats de cartographie et de localisation 92
4.5 Le FastSLAM2.0 monoculaire à grande échelle 94
4.5.1 Convergence du FastSLAM2.0 94
4.5.2 Convergence de l’incertitude des particules 95
4.5.3 Gestion de rééchantillonnage 96
4.5.4 Évaluation des Résultats de cartographie et de localisation 96
4.6 Implémentation sur une architecture massivement parallèle 97
4.6.1 Choix d’une architecture adaptée 97
4.6.2 Adéquation algorithme architecture 99
4.6.3 Résultats expérimentaux 118
4.7 Accélération matérielle sur une architecture programmable 128
4.7.1 Modèle d’implémentation 128
4.7.2 Conception de haut-niveau par OpenCL 129
4.7.3 Spécifications matérielle 131
4.7.4 Techniques et stratégies d’optimisation 133
4.8 Résultat expérimentaux et comparaison de performance 134
4.9 Bilan 137
5 Conclusion Générale 140
5.1 Conclusion et résumé des contributions 140
5.2 Perspectives 141
6 Références 143
7 Annexes 155
7.1 Annexe A 155
7.1.1 Codeur Optique 155
7.1.2 Télémètre Laser 155
7.2 Annexe B 156
7.2.1 Exemple de factorisation algorithmique 156
7.2.2 Exemple de modélisation architecturale 158
7.2.3 Formalisme mathématique du graphe 159
7.2.4 Formalisation mathématique de la distribution 160
7.2.5 Formalisme mathématique de l’ordonnancement 161
7.3 Annexe C 162
7.3.1 Détection à partir d’un flux Laser 162
7.3.2 Détection des amers par FAST 162
7.3.3 Appariement des amers 163
7.3.4 Initialisation des amers 166
7.3.5 Représentation en arbre binaire 167
7.3.6 Méthode linéaire pour la fusion de deux cartes locales 168
7.3.7 Recherche active des amers dans le système ORB SLAM 171
7.4 Annexe D 172
7.4.1 Intégration de bruit dans la trajectoire odométrique 172
7.4.2 Calcule de la nouvelle distribution probabiliste 172
7.4.3 Estimation et correction des amers 173
7.4.4 Rééchantillonnage 176
7.4.5 Implémentation OpenGL 176
7.4.6 Résultats de comparaison entre l’implémentation OpenCL et OpenGL 179
Télécharger le fichier PDF: Algorithmes SLAM (Simultaneous Localization et Mapping): Vers une Implémentation Embarquée