SLAM par optimisation de graphe

SLAM par optimisation de graphe 

Le terme SLAM (Simultaneous Localization and Mapping) est apparu dans les travaux de [Leonard and Durrant-Whyte, 1991]. Le processus de localisation et cartographie simultanées consiste à reconstruire la carte de l’environnement exploré tout en localisant, en même temps, le robot sur celle-ci. Initialement, le robot n’a aucune information à priori sur l’environnement et sa position.

Plusieurs approches ont été proposées dans la littérature pour résoudre le problème de SLAM. Cellesci peuvent être classifiée, dans un premier lieu, en approches probabilistes et ensemblistes. L’approche dominante est l’approche probabiliste. Elle cherche à estimer, en général, la densité à posteriori de la carte et la position du robot. Par ailleurs, on peut diviser encore les approches de SLAM en approches de filtrage et approches de lissage (ou approches d’optimisation). Les approches de filtrage corrigent la position courante et la carte. Dans cette catégorie, on trouve principalement l’EKF-SLAM (Extended Kalman Filter for SLAM) [Smith and Cheeseman, 1986, Smith et al., 1990, Dissanayake et al., 2001] et le FastSLAM (Filtre particulaire) [Montemerlo et al., 2002]. Les approches de lissage permettent de corriger la carte des amers et toute la trajectoire depuis l’état initial. Le SLAM par optimisation de graphe [Lu and Milios, 1997] est une méthode de lissage. Ce travail de thèse s’intéresse particulièrement à cette dernière méthode pour ses avantages par rapport à l’EKF-SLAM et le FastSLAM. Dans ce manuscrit de thèse, nous utilisons l’appellation GraphSLAM pour désigner le SLAM par optimisation de graphe. Le terme GraphSLAM [Thrun and Montemerlo, 2006, Grisetti et al., 2010] est le plus populaire, au sein de la communauté scientifique, pour faire référence aux méthodes de SLAM basées sur l’optimisation de graphe.

Nous allons présenter, dans un premier temps, ces approches en expliquant leurs principes, et en mettant en évidence les avantages et les inconvénients de chacune d’entre elles. Nous donnons ensuite une description détaillée du GraphSLAM. Nous étudierons, ensuite, les différentes approches suivies pour réduire la complexité de calcul du GraphSLAM.

Processus de SLAM

Dans la pratique, on peut découper le processus de SLAM en quatre étapes :
— Extractions des amers
— Estimation des mesures
— Mise en correspondance
— Correction .

Extraction des amers

Cette étape consiste en l’extraction des amers après acquisition des données par un ou plusieurs capteurs extéroceptifs. Les amers sont des éléments particuliers de l’environnement identifiables sans ambiguïté par le robot. Un amer est, en général, un point d’intérêt de l’environnement. Il peut aussi avoir d’autres formes géométriques (rectangle, segments, voire des objets [Salas-Moreno et al., 2013]). Différents types de capteurs peuvent être utilisés pour la détection des amers. Selon le type du capteur utilisé, on distingue, en général, trois catégories : SLAM basé Laser [Hahnel et al., 2003, Holz and Behnke, 2016], SLAM basé SONAR (SOund Navigation And Ranging) [Kleeman, 2003, Jaulin, 2006, Sliwka et al., 2011] et SLAM basé vision. Des critères comme la précision, le type de la carte à reconstruire ainsi que la nature de l’environnement influencent le choix des capteurs.

Dans le SLAM basé Laser, la perception de l’environnement est, souvent, assurée par des télémètres Laser. Ceux-ci se distinguent par une grande vitesse d’acquisition couplée à une haute précision. Cela a fait des télémètres Laser un choix incontournable dans les premiers systèmes de SLAM. Le SLAM visuel [DeSouza and Kak, 2002] utilise une ou plusieurs caméras comme capteurs extéroceptifs. Une image constitue une source très riche en informations en comparaison avec les capteurs Laser. Les caméras sont également adaptées aux systèmes embarquées : elles sont souvent légères, bascoût et moins consommatrices en énergie que les capteurs Laser. Les amers sont extraits suite à la détection de points d’intérêt dans les images acquises. Pour ce faire, il existe plusieurs algorithmes de détection et de description : Harris [Harris and Stephens, 1988], SIFT [Lowe, 1999], SURF [Bay et al., 2008], FAST [Rosten et al., 2010], BRIEF [Calonder et al., 2010], ORB [Rublee et al., 2011], BRISK [Leutenegger et al., 2011], FRICK [Alahi et al., 2012]. Finalement, pour faire face au bruit et à l’insuffisance d’informations, on peut combiner plusieurs types de capteurs. Cela donne lieu à un SLAM hybride [Biber et al., 2004, Fu et al., 2007, Gallegos et al., 2010, Shen et al., 2011, Oh et al., 2015, Karakaya et al., 2015].

Estimation des mesures 

Dans cette étape, on effectue une première estimation de la position courante du robot et la carte en utilisant, respectivement, le modèle d’observation et le modèle de mouvement. Ceux-ci sont des modèles mathématiques dépendant des capteurs utilisés. Pour l’odométrie, la position courante du robot est obtenue par intégration successive des données odométriques. Dans le SLAM 3D où les amers résident dans un plan 3D, l’initialisation de la profondeur d’un amer constitue un grand défi particulièrement dans le SLAM monoculaire [DeSouza and Kak, 2002, Davison, 2003, Celik et al., 2008, Hwang and Song, 2011, Scaramuzza, 2011, Choi et al., 2011, Nourani-Vatani and Borges, 2011]. Celui-ci utilise une seule caméra. Celle-ci étant un capteur projectif, la profondeur ne peut être obtenue que si l’amer a été observé depuis, au moins, deux positions différentes. [Davison, 2003] a introduit l’initialisation retardée des amers. L’initialisation est raffinée en traquant le point sur plusieurs images. Un point 2D n’est considéré comme un amer 3D que si son initialisation est assez bonne. L’introduction de l’initialisation non retardée [Sola et al., 2005] et puis la paramétrisation par inverse de profondeur (inverse depth parametrisation) [Civera et al., 2006] ont beaucoup contribué à la résolution du problème d’initialisation d’amers pour le SLAM monoculaire. [Davison et al., 2007] ont proposé un nouvel algorithme de SLAM appelé MonoSLAM. Celui-ci permet d’estimer la trajectoire 3D d’une caméra sans utiliser de capteurs proprioceptifs. La profondeur est obtenue suite au mouvement de la caméra. D’autres travaux [Klein and Murray, 2007, Kitt et al., 2010, Geiger et al., 2011, Ventura et al., 2014] utilisent la technique de triangulation, entre images consécutives, pour initialiser les amers.

Dans le SLAM monoculaire, la trajectoire et la carte de l’environnement sont données à un facteur d’échelle près. Celui-ci résulte des projections des points 3D de l’environnement sur un plan 2D de la caméra. Un point 2D sur l’image peut correspondre à un nombre infini de points constituant une droite. Pour pallier à ce problème, plusieurs techniques ont été proposée dans la littérature. [Royer et al., 2005] utilisent un GPS différentiel pour corriger le facteur d’échelle. [Kitt et al., 2010, Geiger et al., 2011] s’appuient sur la détection d’un certain nombre de points sur le sol afin de corriger le facteur d’échelle. Similairement, [de la Escalera et al., 2016] détectent et traquent des points statiques sur le sol pour calculer le mouvement relatif entre les images.

Dans le même contexte et pour simplifier l’initialisation des amers 3D, un système stéréo peut être utilisé [Agrawal et al., 2005, Carrasco et al., 2016, Herath et al., 2007, Lemaire et al., 2007, Moreno et al., 2015, Zhang et al., 2015, Takezawa et al., 2004]. Les caméras stéréoscopiques fournissent la profondeur ou la distance aux objets dans l’environnement. Cela facilite l’initialisation des amers. Par ailleurs, l’émergence de la nouvelle génération des caméras RGB-D (La Kinect, Primesense Carmine, Asus Xtion) a aussi contribué à l’évolution rapide du SLAM 3D [Henry et al., 2010, Engelhard et al., 2011, Endres et al., 2012, Engel et al., 2014, Melbouci et al., 2015]. Ces caméras utilisent des projections infrarouges pour calculer la profondeur.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

INTRODUCTION
1 SLAM par optimisation de graphe
1.1 Introduction
1.2 Processus de SLAM
1.2.1 Extraction des amers
1.2.2 Estimation des mesures
1.2.3 Mise en correspondance
1.2.4 Correction
1.3 Méthode de SLAM
1.3.1 EKF-SLAM
1.3.2 Fast-SLAM
1.3.3 GraphSLAM
1.3.4 SLAM ensembliste
1.3.5 Comparaison
1.4 Présentation du GraphSLAM
1.4.1 Définitions
1.4.2 GraphSLAM comme un problème de moindres carrés
1.4.3 Résolution du problème de moindres carrés
1.4.4 Algorithme GraphSLAM et partitionnement en blocs fonctionnels
1.4.5 Calcul des erreurs
1.4.6 Construction du système linéaire
1.4.7 Marginalisation des amers et complément de Schur
1.4.8 Construction du format CCS
1.4.9 Résolution du système
1.4.10 Calcul des incréments des amers
1.4.11 Mise à jour de l’état du système
1.5 Approches de réduction de la complexité de calcul
1.5.1 Rapidité de convergence
1.5.2 Élagage
1.5.3 Sous-cartographie et fenêtre glissante
1.5.4 Incrémentalité
1.5.5 Méthodes de résolution des NLS
1.5.6 Optimisation logicielle et matérielle
1.5.7 Notre approche
1.6 Conclusion
2 Architectures et outils de synthèse de haut niveau
2.1 Introduction
2.2 Processeurs graphiques
2.2.1 Architecture du Tegra K1
2.2.2 Programmation des processeurs graphiques
2.2.3 Processeurs graphiques pour l’accélération du SLAM
2.3 Architectures reconfigurables
2.3.1 Vers des FPGAs intégrant des processeurs hardcores
2.3.2 Architecture système-sur-puce du Cyclone V
2.3.3 FPGA pour le SLAM
2.4 Flux de conception sur FPGA : Outils de synthèse de haut niveau
2.4.1 Description manuelle
2.4.2 Synthèse de haut niveau
2.4.3 Présentation de LegUp
2.4.4 Approche OpenCL
2.5 Conclusion
3 Représentation mémoire pour le GraphSLAM incrémental
3.1 Introduction
3.2 Représentation mémoire du GraphSLAM
3.3 Structure de données à index (IDS)
3.4 Structure de données compacte et incrémentale
3.4.1 Représentation des éléments du graphe
3.4.2 Connectivité : connexions entre nœuds
3.4.3 Complément de Schur
3.4.4 Système linéaire
3.4.5 Construction incrémentale du graphe
3.5 Évaluations et résultats temporels
3.5.1 Présentation des jeux de données
3.5.2 Modalités d’évaluation
3.5.3 Résultats fonctionnels
3.5.4 Présentation des architectures d’évaluation
3.5.5 Métrique d’évaluation : Temps de Traitement par Élément de graphe (TPE)
3.5.6 Charges temporelles des blocs fonctionnels
3.5.7 Évaluations temporelles sur un PC Intel
3.5.8 Évaluations temporelles sur architectures embarquées
3.5.9 Complément de Schur
3.5.10 Évolution du temps de traitement : TPE
3.6 Conclusion
4 Étude et implantation sur architectures hétérogènes à base de GPU
4.1 Introduction
4.2 Parallélisation de l’algorithme
4.2.1 Calcul des erreurs
4.2.2 Construction du système linéaire
4.2.3 Complément de Schur
4.2.4 Résolution du système linéaire
4.2.5 Calcul des incréments des amers
4.3 Effet de la fonctionnalité zéro-copie
4.4 Adéquation Algorithme-Architecture
4.4.1 Scalabilité
4.4.2 Analyse de l’évolution du temps par arête
4.4.3 Discussion et partitionnement CPU/GPU
4.4.4 Architecture mémoire
4.5 Résultats expérimentaux
4.5.1 Répartition des charges temporelles
4.5.2 Optimisation de graphe en mode batch
4.5.3 Optimisation de graphe en mode incrémental
4.6 Conclusion
CONCLUSION

Lire le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *