Modélisation d’environnements pour la navigation : des cartes spatiales aux modèles sémantiques

Modèles spatiaux 

La navigation est la tâche la plus fondamentale que doit réaliser un robot mobile autonome. Elle peut recouvrir des réalités très diverses selon le contexte dans lequel évolue le robot. Ici, naviguer s’entend au sens le plus large, c’est à dire réaliser un ensemble de tâches qui permettent, à partir d’une positon donnée, d’atteindre une position quelconque, dans un environnement arbitrairement grand et dans lequel évoluent d’autres agents intelligents, biologiques ou artificiels. Pour naviguer efficacement, le robot doit être capable, d’une part, de se localiser dans son environnement et d’autre part, de planifier sa trajectoire vers une position cible en tenant compte des contraintes de l’environnement. A défaut de disposer d’un moyen de localisation externe, la navigation demande donc que le robot possède une représentation interne de son environnement. La construction automatique de ce modèle est ardue pour au moins trois raisons :
– La dimensionnalité du problème : les environnements explorés peuvent être arbitrairement grands et les données acquises représenter un volume d’information conséquent. Se pose donc la question de savoir comment représenter l’environnement de manière compacte.
– L’environnement est intrinsèquement dynamique : le modèle ne peut donc pas être statique. Comment capturer la dynamique de la scène dans la représentation?
– Le robot n’observe pas les objets directement, ses capteurs ne fournissent que la mesure de certaines grandeurs physiques. Faut-il représenter les données ou une interprétation des données ?

Depuis le début de la robotique mobile, le problème de l’acquisition automatique d’un modèle de l’environnement par un robot a occupé une part significative des recherches. Selon le contexte opérationnel, la nature de l’environnement et des capteurs disponibles, de nombreuses représentations différentes ont été proposées, chacune conduisant à des stratégies de navigation, de localisation et de planification de trajectoire différentes. Il existe un très grand nombre de facteurs permettant de classer les différents modèles de carte proposés, entre ceux développés pour l’intérieur ou pour l’extérieur, ceux acquis avec des lasers ou des caméras ou encore en fonction du type de plateforme utilisée (UAV,UGV…). Dans ce chapitre les principaux modèles sont présentés de façon à souligner le fil conducteur ayant guidé les recherches en cartographie jusqu’à aujourd’hui, dans le but de mettre en perspective la démarche globale et d’identifier les objectifs actuels.

Cartes métriques

La première classe de modèles a avoir émergé regroupe les cartes métriques. Elles représentent l’environnement par sa géométrie avec un point de vue géocentré, c’est à dire que l’ensemble des données est repositionné par rapport à un même référentiel global, souvent le point de départ du robot. Il s’agit sans doute de la représentation la plus intuitive de l’espace. Une très grande variété de représentations métriques ont été proposées que l’on peut regrouper en deux familles : les méthodes qui représentent l’espace lui même, le plus souvent par une discrétisation de celui-ci, les grilles d’occupation ; les méthodes représentant les objets dans l’espace, le plus souvent sous forme de nuages de points ou de primitives géométriques.

Grilles d’occupation

Grille 2D L’un des premier modèle d’environnement est la grille d’occupation, proposée dans [Elfes 1987, Elfes 1989]. Comme pour beaucoup d’algorithmes de cartographie, les grilles d’occupations reposent sur le filtrage bayésien. L’espace est représenté par une grille 2D dont chaque cellule possède une probabilité d’occupation dépendant des observations et qui peut être mise à jour au fur et à mesure de l’exploration. Du fait de sa relative simplicité et de sa robustesse, ce modèle été très largement utilisé, notamment avec des lasers et des sonars [Burgard 1999]. Cependant, l’impossibilité de modéliser la hauteur des obstacles le rend aussi difficilement exploitable par d’autres robots que celui ayant acquis le modèle : en plaçant le capteur à deux hauteurs différentes, la carte obtenue n’est pas nécessairement la même.

Cartes d’élévation Pour corriger ce problème, une première extension des grilles d’occupation 2D a été envisagée dans le cas où certaines hypothèses peuvent être faites sur l’environnement [Herbert 1989]. La carte résultante est une représentation 2.5D de l’environnement, c’est à dire une grille dans laquelle chaque cellule, au lieux de coder la probabilité d’occupation, mesure la hauteur du terrain. Ce type de carte a été utilisée avec succès dans le cas de robot navigant en extérieur [Hadsell 2009]. Le modèle de la carte d’élévation nécessite, dans sa version de base, de faire l’hypothèse assez restrictive que l’environnement peut être modélisé par une seule surface continue. Cependant d’autres possibilités ont été explorées en relâchant l’hypothèse d’une surface unique comme dans [Pfaff 2007] où plusieurs surfaces sont admises ou dans [Dryanovski 2010] qui stocke pour chaque cellule une liste des voxels occupés et libres dans une grille d’occupation multivolume. D’autres représentations ont été proposées en s’appuyant sur l’hypothèse manhattan-world, c’est à dire un monde où les structures sont purement verticales. Ce modèle a été utilisé pour reconstruire une scène en 3D dans [Furukawa 2009].

Extension 3D Le succès des grilles d’occupation 2D a conduit à étendre le formalisme à la 3D [Moravec 1994]. Les cases 2D sont remplacées par des voxels de taille homogène dans tout l’espace. Tout comme dans le cas 2D, la taille du maillage doit être défini au préalable de façon à ce que la grille soit au moins aussi grande que l’espace à explorer. Dans le cas d’environnement de grande dimension et lorsqu’une précision locale importante est requise, la taille du modèle devient vite très importante tout comme dans le cas de points 3D. Une approche plus sophistiquée à base d’octree a été utilisée avec OctoMap [Hornung 2013] pour résoudre ce problème, l’idée ayant été initialement proposée dans [Meagher 1982]. Au lieu d’utiliser un maillage homogène de l’espace, la grille d’occupation est remplacée par un octree. Ceci présente plusieurs avantages. Premièrement le modèle global est beaucoup plus compacte qu’avec une grille régulière puisque les vaste zones vides de la carte peuvent être encodée dans un petit nombre de cases tandis que les zones occupées bénéficient d’un découpage plus fin. Deuxièmement l’accès aux données est beaucoup plus rapide qu’avec une grille régulière du fait de la structure hiérarchique des octrees et de l’existence d’algorithmes de recherche puissants. Enfin, avec un octree la taille de l’environnement n’a pas besoin d’être connue initialement et peut être ajustée au fur et à mesure de l’accumulation des mesures en ajoutant une branche à la structure.

En dépit d’évolutions fructueuses des modèles basés sur une discrétisation de l’espace, de nombreux inconvénients demeurent qui rendent peu envisageable leur utilisation à grande échelle dans des cas réels. En premier lieu, les grilles d’occupation n’offrent aucun moyen de prendre en compte l’incertitude sur la pose ou les mesures, supposant un algorithme de localisation parfait et des capteurs d’une extrême précision, ce qui n’est généralement pas le cas dans la pratique. Dans le cas de grand environnements, la localisation est sujette à une dérive qui rend ces modèles difficilement utilisables. Ensuite, ces représentations utilisent comme unité de base des éléments d’espace discrétisés qui les rendent inutilisables à grandes échelles. Le compromis nécessaire quant à la taille des cellules et de l’espace modélisé conduit soit à des discontinuités du modèle local qui rendent l’analyse de la géométrie délicate, soit à un modèle trop lourd. Enfin et dans une moindre mesure, une hypothèse de départ de toutes ces représentations est l’indépendance statistique des cases de la grille, qui n’est, la plupart du temps, pas vraie.

Représentations basées mesures

La deuxième famille de modèle ne représente plus l’espace lui même mais les objets  qu’il contient, soit en représentant directement les mesures dans l’espace euclidien, soit en représentant leur interprétation.

Cartes de points La première manière de représenter le contenu de l’espace consiste simplement à représenter les mesures des capteurs sous forme d’un ensemble de points épars, notamment les amers utilisés pour la navigation. Dans MonoSlam [Davidson 2007] ce type de carte est construit à partir d’un système de vision monoculaire. Des points d’intérêt sont extraits des images et leurs positions sont estimées et mémorisées pour former un embryon de modèle d’environnement. Une forme un peu plus évoluée de représentation consiste à construire une carte dense de points, en 2D ou en 3D [Lu 1997, Thrun 2000, Cole 2006]. Ce type de modèle offre une représentation plus réaliste visuellement que les cartes éparses puisque la densité des points permet de simuler la continuité des surfaces. Cependant, l’accumulation des mesures conduit à une redondance de l’information dans les zones où elles se superposent et en fait des modèles gourmands en mémoire. De plus, ce type de modèle n’enregistre que la position des points mesurés à un instant donné, sans estimer ni l’espace libre ni les zones non explorées. Il est alors impossible de mettre à jour cette carte en retirant des mesures qui pourraient être erronées. En outre, sans information sur l’orientation des normales, rien dans le modèle ne permet de faire la différence entre la face observée d’un objet et la partie cachée. Il n’y a donc aucun moyen de savoir si une surface est observable depuis un point de vue quelconque. Ces limitations rendent ces représentations adaptées uniquement pour la modélisation des scènes statiques et observées avec des capteurs de grande précision.

Carte de primitives géométriques L’idée de remplacer les mesures par des primitives géométriques a été introduite très tôt [Chatila 1985] où un ensemble de lignes continues est utilisé, se rapprochant davantage de la réalité que les nuages de points. En plus d’offrir un modèle plus compact, la représentation est aussi plus précise car les primitives sont estimées à partir de nombreuses mesures dont l’erreur individuelle est ainsi atténuée. Ce type de carte permet une interprétation à plus haut niveau de la scène utile pour la navigation. Dans le même esprit mais en 3D cette fois [Martin 2002] propose d’extraire les plans de l’environnement et d’approximer les zones non planes par des polygones. L’algorithme EM est utilisé pour estimer les zones planes et reconstruire en ligne une carte à l’aspect réaliste. Dans [Biber 2003] est introduit une nouvelle représentation, la Normal Distribution Transform ou NDT. Au lieu de d’utiliser les points d’un nuage, cette représentation est basée sur un ensemble de distributions normales qui encodent la probabilité de trouver une surface à une certaine position. En plus d’offrir une représentation lisse, cette modélisation est aussi beaucoup plus compacte qu’un nuage de point équivalent. Elle a été étendu au cas 3D dans [Magnusson 2007].

Dans le même esprit, une modélisation à base de surfaces planes a été proposée dans [Habbeck 2007] où la forme des objets est approximée par croissance de région en utilisant un ensemble de disques plans nommés Surfels. Ces Surfels sont des entités ayant comme caractéristique une position, une orientation,une taille et potentiellement une couleur. Cette représentation associée à un algorithme de SLAM a été utilisée dans [Peter 2010] pour la reconstruction en temps réel d’environnement intérieur. Bien que plus précises que les représentations utilisant une discrétisation de l’espace car modélisant des surfaces, ces méthodes présentent tout de même l’inconvénient de ne pas faire la différence entre espace libre et inconnu. Une représentation alternative permettant de modéliser à la fois l’espace occupé, vide ou inconnu et permettant de caractériser la surface a été introduite dans [Curless 1996]. Les objets sont modélisés par une fonction, la signed distance function, ou SDF, qui s’annule au niveau de leur surface, est positive lorsque l’espace est libre et négative lorsqu’il est inconnu. Une représentation similaire a été utilisée KinectFusion [Newcombe 2011].

Table des matières

Introduction
I Modélisation d’environnements pour la navigation : des cartes spatiales aux modèles sémantiques
1 Modèles spatiaux
1.1 Introduction
1.2 Cartes métriques
1.2.1 Grilles d’occupation
1.2.2 Représentations basées mesures
1.3 Carte topologique
1.4 Les cartes hybrides et hiérarchiques
1.4.1 Cartes par superposition
1.4.2 Carte Pyramidale
1.4.3 Assemblage de cartes locales
1.5 Limites des représentations spatiales
2 Modèles sémantiques
2.1 Approche moderne de la cartographie
2.1.1 Modèles de cartes sémantiques
2.1.2 Synergie des cartes sémantiques
2.2 Limites des représentations actuelles
II Cartographie Hybride Métrique-Topologique-Sémantique
3 Le modèle des sphères ego-centrées
3.1 Introduction
3.2 Synthèse de nouvelle vue
3.3 Construction d’images sphériques
3.3.1 Systèmes multicameras multibaseline
3.3.1.1 Calibration
3.3.1.2 Matching et triangulation sphérique
3.4 Odométrie visuelle
3.5 Limites de la représentation RGBD
4 Extraction d’information sémantique
4.1 Introduction
4.2 Pipeline visuel utilisé
4.2.1 Architecture globale
4.2.2 Calcul des descripteurs
4.2.3 Classification
4.2.3.1 Forêts d’arbres de décision
4.2.3.2 Champ Conditionnel Aléatoire
4.3 Consistance spatio-temporelle
4.4 Résultats de la labelisation
4.4.1 Bases de données
4.4.2 Mesures
4.4.3 Mise en oeuvre
4.4.4 Labelisation unitaire
4.4.5 Consistance temporelle
4.5 Limites des mesures de performances des algorithmes de classification
4.6 Conclusion
5 Construction de la couche sémantique
5.1 Introduction
5.2 Graphe Sémantique
5.2.1 Caractéristiques des Graphes Sémantiques
5.3 Architecture de la carte
5.4 Détection d’erreur dans un graphe sémantique
5.4.1 Résultats
5.4.2 Conslusion
6 Mise à jour de la représentation
6.1 Introduction
6.2 Principe
6.3 Mise à jour par l’observation
6.4 Généralisation
6.5 Expériences
6.5.1 Méthode
6.5.2 Résultats et analyse
7 Extrapolation de Cartes d’Environnements Dynamiques
7.1 Introduction
7.2 Approche
7.3 Modèle
7.3.1 Extrapolation basée objet statique
7.3.2 Extrapolation basée objet quasi-statique
7.3.3 Extrapolation basée objets dynamiques
7.4 Expériences
7.4.1 Extrapolation de graphe
7.4.2 Extrapolation d’espace libre
7.5 Conclusion
III Navigation Sémantique
8 Localisation Sémantique
8.1 Introduction
8.2 Localisation dans un graphe de sphères
8.2.1 Comparaison de graphes sémantiques
8.2.2 Accélération du processus
8.2.3 Requête de haut niveau
8.3 Résultats
8.3.1 Scénario 1 : récupération d’images
8.3.2 Scénario 2 : Robustesse au changement de point de vue
8.3.3 Scénario 3 : Localisation après mise à jour
8.3.4 Scénario 4 : Localisation sous contrainte
8.3.5 Scénario 5 : Requêtes complexes
8.4 Conclusion
9 Planification de chemin basée sémantique
9.1 Introduction
9.2 Contraintes sémantiques
9.3 Caractériser un chemin
9.3.1 Langage pour la description de chemin
9.3.2 Compression de la description
9.4 Résultats
9.4.1 Planification de trajectoire
9.4.1.1 Environnement virtuel
9.4.1.2 Environnement réel
9.4.2 Description de chemin
9.4.2.1 Environnement virtuel
9.4.2.2 Environnement réel
9.5 Conclusion
IV Conclusion

Lire le rapport complet