Soutenance mémoire
Télécharger le fichier pdf d’un mémoire de fin d’études
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.
Mise en correspondance
Pour une meilleure correction de la position du robot et la carte, un amer devrait être observé plusieurs fois au cours de la navigation du robot. Il est donc nécessaire de mettre en correspondance, après chaque extraction, les amers détectés avec ceux déjà existants dans la carte. Cette opération est possible en associant un descripteur unique à chaque amer détecté. Un descripteur peut être assimilé à une carte d’identité permettant d’identifier l’amer lors de la navigation. Dans le SLAM visuel, la manière la plus intuitive est d’utiliser le voisinage du point d’intérêt comme descripteur [Davison, 2003]. D’autres types de descripteurs sont plus complexes. Ils sont également calculés en utilisant le voisinage du point d’intérêt (BRIEF, ORB, BRISK, FRICK). Une distance de similarité est ensuite calculée entre l’amer détecté et ceux déjà dans la carte. L’amer est associé à l’amer offrant la meilleure similarité et dépassant un certain seuil.
Correction
La phase de correction est le coeur du processus de SLAM. Elle corrige la position du robot et la carte en fusionnant les mesures des amers et du déplacement. Pour les méthodes probabilistes, on trouve essentiellement trois méthodes : l’EKF-SLAM, le FastSLAM et le SLAM par optimisation de graphe. L’EKF-SLAM se base sur un filtre de Kalman Étendu. Le FastSLAM s’appuie, à son tour, sur un filtre particulaire. Le SLAM par optimisation de graphe ou GraphSLAM utilise une représentation graphique du problème de SLAM. D’autre part, il existe l’approche ensembliste. Celle-ci utilise l’analyse par intervalle dans un objectif de garantir les résultats de localisation et de cartographie contrairement aux approches Bayésiennes où la position du robot (ou la carte) est donné avec une incertitude (probabilité).
Méthode de SLAM
EKF-SLAM
La première application du Filtre de Kalman Étendu (EKF) pour la localisation et cartographie simultanée a été introduite dans les travaux de [Smith and Cheeseman, 1986, Smith et al., 1990]. L’EKF a été donc la première approche à utiliser pour résoudre le problème de SLAM. Plusieurs travaux ont succédé pour améliorer le SLAM [Castellanos et al., 1999, Dissanayake et al., 2001, Durrant-Whyte and Bailey, 2006, Bailey and Durrant-Whyte, 2006, Durrant-Whyte et al., 2003]. L’EKF est une extension du filtre de Kalman qui prend en compte les systèmes non linéaires. En effet, les modèles de mouvement et d’observation sont, en général, non linéaires. L’EKF-SLAM est une approche Bayésienne récursive qui nécessite plusieurs hypothèses :
— La trajectoire du robot forment une chaîne de Markov de premier ordre. La position courante du robot xt ne dépend que de la position précédente et de la commande ut .
— Les observations des amers sont indépendantes entre elles.
— L’observation d’un amer à l’instant t ne dépend que de la position du robot à cet instant.
— Les mesures capteurs sont affectées d’un bruit blanc Gaussien.
Sous ces hypothèses, la formulation Bayésienne de l’EKF-SLAM est donnée par : p(xt ;mjz1:t ;u1:t) = h p(zt jxt ;m) p(xt jxt?1;ut) p(xt?1;mjz1:t?1;u1:t?1;x0) dxt?1 (1.2) , où h est une constante de normalisation.
Principe
Le principe de cette méthode consiste en la représentation de la position du robot et des amers par
un vecteur d’état X. Les mesures étant affectées d’un bruit Gaussien, le vecteur d’état est donc une
variable normale aléatoire. Par conséquent, on associe au vecteur d’état une matrice de variancescovariances P caractérisant les incertitudes sur les positions et les corrélations entre les variables du vecteur d’état. Les moyennes de cette matrice représentent la position du robot et celles des amers.
Avec :
x : la position courante du robot
Pi j : la covariance entre les variables i et j. Cette matrice est une approximation Gaussienne résultant de la linéarisation autour d’un point (état du système) supposé proche de la solution réelle. Au fur à mesure que le robot se déplace, le filtre de Kalman met à jour le vecteur d’état et la matrice de variances-covariances.
Dans la pratique, l’estimation de l’état du système s’effectue en deux temps :
— Prédiction : Dans cette phase, le modèle d’évolution prédit la position courante à partir de la position précédente et les données proprioceptives.
— Correction : La position prédite du robot et la carte sont corrigées en utilisant les observations d’amers.
Avantages et inconvénients
Dans l’approche EKF-SLAM, les déterminants de chaque sous-matrice de la matrice de variances covariances décroissent à chaque observation. L’incertitude sur la position du robot et les amers a
donc tendance à diminuer avec le temps.
Cependant, l’inconvénient principal de l’EKF-SLAM reste sa complexité de calcul. La première hypothèse Markovienne, pour laquelle on ne prend en compte dans l’estimation que la dernière position du robot, implique que les amers deviennent corrélés entre eux. La matrice de variances-covariances devient de plus en plus dense. Cela requiert un stockage mémoire et un calcul quadratiques en nombre d’amers. Cette complexité restreint l’utilisation de cette approche qu’à des zones relativement petites ou incluant quelques centaines d’amers [Thrun et al., 2004]. De nombreux travaux ont été effectués pour atténuer cette complexité en appliquant l’EKF-SLAM sur plusieurs sous-cartes [Bosse et al., 2003, Paz et al., 2007].
D’autre part, l’EKF-SLAM souffre du problème de consistance. Celle-ci peut être vue comme la qualité de l’incertitude fournie par le filtre par rapport à l’erreur réelle. L’inconsistance provient de la linéarisation approximative autour d’un état estimé plutôt que l’état réel [Julier and Uhlmann, 2001, Bailey et al., 2006, Huang and Dissanayake, 2007]. Pour améliorer la consistance, une variante de l’EKF appelée UKF (Unscented Kalman Filter) a été proposée [Wan and Van Der Merwe, 2000]. Celle-ci évite la linéarisation des modèles non linéaires pour améliorer la consistance.
Fast-SLAM
La forte complexité algorithmique de l’EKF-SLAM a poussé la communauté scientifique à chercher d’autres alternatives. Le FastSLAM [Montemerlo et al., 2002] utilise un filtre particulaire à la place du filtre de Kalman. Le filtre particulaire consiste à échantillonner la densité à posteriori de la trajectoire en un ensemble de particules. Chaque particule de la trajectoire est associée à un ensemble d’amers.
Principe
Dans la pratique, le principe du FastSLAM consiste à générer stochastiquement plusieurs hypothèses (particules) pour la trajectoire. Pour chaque particule, les amers peuvent être estimés indépendamment les uns des autres. On associe alors à chaque amer un filtre de Kalman étendu (EKF). Celui-ci permet d’estimer les paramètres de l’amer correspondant en utilisant les mesures d’observation. Globalement, les étapes à suivre dans le FastSLAM sont les suivantes :
— Échantillonnage : Génération de N particules. Le nombre de particules est à fixer de telle manière à réduire le temps de calcul, mais également à éviter l’épuisement des particules. Ce dernier peut conduire à une divergence dans la localisation.
— Pondération : Chaque particule est pondérée en fonction de sa vraisemblance avec les mesures.
— Ré-échantillonnage : Les particules sont ré-échantillonnées une seconde fois en fonction de leurs poids pour en éliminer les moins probables.
— Estimation de la carte : Pour chaque particule, on estime la carte correspondante.
Avantages et inconvénients
Par le biais d’un filtre particulaire, le FastSLAM réduit la complexité algorithmique par rapport à l’EKF-SLAM. Le fait d’appliquer un filtre de Kalman par amer donne une complexité de O(NM), où N et M sont respectivement le nombre de particules et d’amers.
Cependant, cette approche souffre également du problème de consistance. La convergence du filtre particulaire dépend du nombre de particules générées. Si les mesures proprioceptives sont très bruitées, la plupart des particules sont éliminées lors de la phase de ré-échantillonnage. Cela peut conduire à une pauvre représentation en termes de particules et pose, donc, à un problème de consistance pour les particules restantes [Bailey et al., 2006, Zhang et al., 2009]. Notons que le FastSLAM 2.0 [Montemerlo et al., 2003] améliore le FastSLAM original en prenant en compte les mesures les plus récentes lors de la phase de ré-échantillonnage. De cette façon, le FastSLAM donne de meilleures performances en convergence tout en gardant le même nombre de particules.
GraphSLAM
Le GraphSLAM a été introduit pour la première fois par Lu et Milios en 1997 [Lu and Milios, 1997]. Cette approche constitue depuis une dizaine d’années un axe de recherche très actif au sein de la communauté de robotique. L’estimation de l’état du système est formulée par un problème d’optimisation.
Ce dernier fait appel à plusieurs techniques issues essentiellement de l’algèbre linéaire et de la théorie du graphe. Le GraphSLAM ou SLAM basé optimisation de graphe modélise le problème de SLAM à l’aide d’un graphe. Comme l’illustre la figure 1.2, la trajectoire et la carte des amers sont représentées par des noeuds. Associées à un bruit Gaussien, les mesures capteurs donnent des contraintes spatiales entre les noeuds. Ces contraintes spatiales sont modélisées par des arêtes. On distingue deux types d’arêtes : arêtes de mouvement et arêtes d’observation. Une arête de mouvement relie deux noeuds robot (pose) consécutifs. Une arête d’observation provient d’une observation d’un amer. Un amer est relié à une pose (noeud robot) s’il a été observé depuis celle-ci.
FIGURE 1.2 – Illustration du GraphSLAM.
Le GraphSLAM est une approche de lissage qui consiste, contrairement à l’EKF-SLAM, à réestimer, en plus de la position courante, toute la trajectoire depuis l’état initial en prenant en compte tout l’historique des mesures. De même que les autres approches Bayésiennes, le GraphSLAM suppose que les bruits sont Gaussiens. Le GraphSLAM estime la densité p(x1:t ;mjz1:t ;u1:t ;x0). A la différence du filtre particulaire qui génère plusieurs hypothèses de trajectoire, le GraphSLAM modélise toutes les contraintes spatiales entre les noeuds. Dans la pratique, le GraphSLAM est divisé en deux parties (Fig. 1.3) : Front-end (partie en-amont) et Back-end (partie en-aval).
FIGURE 1.3 – Composantes du GraphSLAM : construction de graphe (Front-end) et optimisation de graphe (Back-end).
Front-end
Il s’agit principalement dans cette partie de traiter les données brutes des capteurs proprioceptifs et
extéroceptifs afin de construire le graphe. A chaque nouvelle mesure proprioceptive ou extéroceptive, le graphe est augmenté en insérant de nouveaux noeuds et arêtes. Une mesure proprioceptive résulte en l’ajout d’une pose (noeud robot) associée à une arrête de mouvement. Les mesures extéroceptives sont traitées pour en extraire des amers. Une observation d’un amer met à jour le graphe en ajoutant une arête d’observation et éventuellement l’amer en question s’il n’est pas encore dans le graphe. Par ailleurs, cette partie est aussi en charge de l’identification de fermetures de boucles. Une fermeture de boucle implique que le robot repasse par une zone déjà visitée. Elle permet ainsi d’augmenter la précision de localisation et de cartographie.
Back-end
Une fois le graphe construit, l’état du système peut être estimé via une optimisation globale du graphe. Celle-ci consiste à trouver une configuration (trajectoire et carte) qui correspond le mieux aux contraintes introduites par les arêtes. Ce problème d’optimisation peut être formulé, dans la pratique, par un un problème de moindres carrés ou NLS (Nonlinear Least Squares). Ce dernier est souvent résolu par une méthode itérative (Gauss-Newton, Levenberg-Marquadt, Dog-Leg,…).
Ce travail de thèse se focalise sur l’optimisation de graphe. Il s’agit d’étudier et de réduire la complexité de l’optimisation de graphe indépendamment de la première partie (Front-end).
Avantages et inconvénients
Les approches de lissage comme le GraphSLAM, réestiment à chaque optimisation de graphe tout
l’état du système. Celui-ci est raffiné à chaque nouvelle optimisation de graphe. La linéarisation est de même effectuée en utilisant la dernière estimée de l’état du système. Contrairement aux approches de filtrage, cela permet d’éviter la propagation des erreurs de linéarisation, et donc évite l’inconsistance des résultats.
La résolution du NLS associé au GraphSLAM finit par la résolution d’un système linéaire par blocs. Chaque bloc correspond à un élément dans le graphe (noeud, arête). De plus, ce système est, par construction, symétrique défini positif et souvent creux étant donné qu’en général les graphes obtenus sont épars. En termes de calcul, cela a l’avantage de permettre l’utilisation de méthodes éparses telles que Cholesky. Celle-ci réduit considérablement le temps de calcul. En termes de stockage mémoire et de consistance, le GraphSLAM s’avère plus adapté que l’EKF-SLAM et le FastSLAM pour le SLAM à grande-échelle.
|
Table des matières
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 noeuds
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
5 Étude et implantation sur architectures hétérogènes à base de FPGA
5.1 Introduction
5.2 Architecture et optimisation de ressources
5.2.1 SLAM 2D
5.2.2 Calcul analytique des Jacobiennes
5.2.3 Unification des calculs
5.2.4 Incrémentalité
5.2.5 Calcul trigonométrique sur CPU
5.2.6 Calcul flottant
5.2.7 Modèle d’implantation HPS-FPGA
5.3 Approche OpenCL
5.3.1 Mémoire partagée
5.3.2 Ressources FPGA
5.3.3 Évaluation temporelle
5.4 Approche LegUp
5.4.1 Architecture
5.4.2 Évaluation temporelle
5.5 Conclusion
A Formulation probabiliste du GraphSLAM
B Présentation de la méthode de Cholesky
B.1 Renumérotation
B.2 Factorisation symbolique
B.3 Factorisation numérique
B.4 Résolution
C Validation fonctionnelle
Télécharger le rapport complet
