Robotique mobile

À ce stade, il convient de préciser la notion de position que nous emploierons. En effet, la position d'un robot est définie à la fois par son emplacement spatial, estimé par rapport à un point de référence et par sa direction, estimée par rapport à une direction de référence. Ces deux quantités sont couplées, mais ont des statuts qui peuvent être distincts en pratique.

Lors du mouvement, la direction du robot influence la manière dont varie sa position, mais peut parfois être contrôlée indépendamment. Dans le cas de plates-formes holonomes, ce découplage permet notamment de simplifier le processus de planification en ne tenant pas compte de la direction du robot, laquelle peut être contrôlée sans influencer la position. La variable importante est alors la position du robot, la direction devant être estimée pour pouvoir agir, mais non pour planifier.

Cette indépendance relative au niveau de la planification peut conduire à des systèmes d'estimation de la position et de la direction séparés. Cette séparation est supportée par le fait que la direction d'un robot peut être mesurée par des capteurs indépendamment de l'estimation de sa position. Il est par exemple possible d'utiliser une boussole qui mesure la direction par rapport à la direction du pôle magnétique, ou un gyroscope qui mesure la direction par rapport à une direction arbitraire fixe.

Le choix de représenter et d'estimer de manière séparée la position et la direction n'interdit toutefois pas des interactions entre ces informations. L'estimation de la position utilisera évidemment celle de la direction pour pouvoir intégrer de nouvelles données lors du mouvement du robot. L'estimation de la direction pourra également dépendre de la position par un système de recalage qui utilisera la perception d'un point de référence connu depuis une position connue pour estimer la direction.

Ceci dit, la majorité des systèmes métriques (voir section III.B.2Cartes métriques) vont néanmoins estimer la position et la direction ensemble, soit en 2D (trois degrés de liberté), soit en 3D (six DDL).

Il convient également de préciser les types d'environnements que nous considérons ici. En effet, les robots sont amenés à se déplacer dans une grande variété d'environnements qui peuvent être regroupés en deux grandes catégories : les environnements statiques et les environnements dynamiques. Les environnements statiques sont des environnements qui ne subissent pas de modification au cours du temps. Cette stabilité concerne à la fois leur structure spatiale et leur apparence pour les capteurs du robot. Cela exclut la majorité des environnements dans lesquels les humains évoluent quotidiennement. Les environnements dynamiques, pour leur part, présentent des caractéristiques qui évoluent au cours du temps. La plupart des environnements courants appartiennent évidemment à la seconde catégorie. Par exemple, un environnement de bureau est dynamique, du fait des personnes qui y travaillent, des chaises qui y sont déplacées ou des portes qui y sont ouvertes ou fermées.

Il est, de plus, possible de distinguer deux catégories d'éléments dynamiques. La première catégorie regroupe les éléments variables qui ne caractérisent pas l'environnement. De tels éléments peuvent être considérés comme du bruit qui n'a pas d'intérêt dans la modélisation de l'environnement pour la planification. C'est, par exemple, le cas des personnes évoluant dans un bureau, ou des chaises déplacées. Ces environnements peuvent être considérés comme constitués d'une partie statique sur laquelle se superposent différentes sources de bruit. La partie statique est la partie la plus importante à modéliser pour parvenir à une navigation efficace. Deux effets du bruit doivent toutefois être pris en compte. Il faut premièrement veiller à ce qu'il n'empêche pas la réalisation de commandes issues de la planification. Cela est en général réalisé par le système de contrôle (dans le cadre d'une architecture hybride, voir section I.A.2.cContrôleurs hybrides), séparé du système de navigation, qui réalise l'interface avec la partie physique du robot. De plus, il faut prendre en compte ce bruit au niveau de la cartographie et de la localisation afin qu'il ne nuise pas à la modélisation de la seule partie statique de l'environnement et ne conduise pas à une mauvaise estimation de la position. Les méthodes de navigation actuelles (présentées dans ce cours) sont plus ou moins robustes face à ces bruits, mais cette robustesse reste généralement limitée, surtout pour la partie cartographie. Il commence cependant à apparaître des méthodes prenant explicitement en compte ces éléments dynamiques, qui permettent d'envisager d'utiliser des robots dans des environnements assez fortement bruités (par exemple [143]).

La seconde catégorie d'éléments dynamiques regroupe les éléments variables qui caractérisent l'environnement et peuvent avoir un intérêt pour la planification. C'est, par exemple, le cas des portes qui modifient la structure spatiale de l'environnement et peuvent entraîner des modifications de trajectoires en fonction de leur état. Ils doivent donc être enregistrés dans la carte si l'on veut pouvoir les prendre en compte.

La plupart des systèmes de navigation robotiques s'intéressent aux environnements appartenant à l'une des deux premières catégories. Les environnements sont donc supposés être soit statiques, soit entachés d'un bruit qui n'influence pas la planification. Ces systèmes s'intéressent donc à modéliser la partie statique des environnements qui va être utile pour la localisation et la planification. Il faut toutefois noter que ces systèmes, qui ne modélisent pas les éléments dynamiques de la seconde catégorie, sont néanmoins capables d'évoluer dans des environnements qui contiennent de tels éléments. Pour ce faire, ces systèmes sont en général capables de vérifier que la trajectoire planifiée est correctement exécutée. En cas de problème d'exécution, un chemin alternatif ne passant pas par la zone qui ne peut être atteinte est alors recherché. Cette méthode, qui ne modélise pas explicitement les portes, par exemple, est néanmoins capable de provoquer des détours si une porte fermée bloque un chemin.

Les cartes topologiques permettent de représenter l'environnement du robot sous forme de graphe. Les nœuds du graphe correspondent à des lieux, c'est-à-dire des positions que le robot peut atteindre. Les arêtes liant les nœuds marquent la possibilité pour le robot de passer directement d'un lieu à un autre et mémorisent en général la manière de réaliser ce passage.

La détection et la mémorisation des lieux reposent en général sur deux procédures qui utilisent les perceptions. La première permet simplement de comparer deux perceptions et donc de reconnaître un lieu de la carte ou de détecter un lieu nouveau. La seconde procédure permet de mémoriser un nouveau lieu ou d'adapter la définition d'un lieu lors des passages successifs du robot en ce lieu. Comme nous l'avons déjà mentionné, la reconnaissance d'un lieu est soumise aux problèmes de la variabilité perceptuelle et du perceptual aliasing. En conséquence, la première procédure peut donner des résultats erronés. Par exemple, un lieu déjà visité peut ne pas être reconnu, ou un lieu nouveau peut être confondu avec un lieu déjà mémorisé. Pour résoudre ces problèmes, la reconnaissance des lieux fera donc appel aux données proprioceptives en plus des perceptions. De nombreuses méthodes, dont les plus importantes seront décrites dans la suite du cours, ont été mises en œuvre dans ce but.

Les données mémorisées dans les arêtes du graphe sur les relations de voisinage entre lieux proviennent, pour leur part (en général), des données proprioceptives. Cela est caractéristique des cartes topologiques, dans lesquelles les perceptions ne sont en général pas utilisées pour estimer les positions relatives des lieux visités, mais seulement pour reconnaître un lieu. Ces données peuvent être des informations sur les positions relatives des nœuds, ou des informations sur les actions à effectuer pour parcourir cette arête.

Un avantage important des cartes topologiques est qu'elles ne requièrent pas de modèle métrique des capteurs pour fusionner les données proprioceptives et les perceptions au sein d'une représentation unifiée de l'environnement. Cela est avantageux pour deux raisons. D'une part, ces modèles métriques peuvent, comme nous l'avons vu, être difficiles à obtenir ou s'avérer peu fiables. Se passer de modèle métrique permet par exemple d'utiliser simplement des images panoramiques pour la reconnaissance de lieux. D'autre part, le fait de ne pas fusionner les deux sources d'informations permet de séparer les influences des erreurs correspondantes. En effet, l'estimation de la position d'objets, lorsque l'on utilise un modèle métrique, dépend à la fois des valeurs mesurées par les capteurs et de la position du robot. Une erreur sur la position d'un objet peut donc provenir des deux sources. Déterminer la contribution de chacune des sources peut être difficile. Dans les cartes topologiques, au contraire, le bruit sur les mesures des capteurs influe principalement sur la reconnaissance des lieux, tandis que le bruit sur les données proprioceptives influe principalement sur la position associée à chaque lieu.

La mémorisation de l'environnement sous forme d'un ensemble de lieux distincts autorise en général une définition des lieux plus directement reliée aux capacités perceptives du robot. En effet, comme les perceptions ne sont pas transformées dans un repère métrique, il n'y a pas de limitation au type de capteurs utilisables (cf. la section I.B.2Informations extéroceptives). Cette utilisation directe des perceptions permet un meilleur ancrage dans l'environnement, c'est-à-dire une meilleure mise en relation du robot avec son environnement. Puisque la carte est très proche des données brutes perçues par le robot, il est en général assez simple de comparer et de mémoriser des lieux de l'environnement.

Cette proximité avec les données brutes conduit en général la représentation topologique à utiliser beaucoup moins de concepts de haut niveau que les représentations métriques. La carte topologique reste ainsi proche des possibilités du robot, en mémorisant ses perceptions et ses déplacements possibles, indépendamment de concepts de plus haut niveau tels que des objets ou des obstacles.

La discrétisation de l'environnement correspondant au choix des lieux représentés dans la carte est un autre point fort des cartes topologiques. Cette discrétisation est en effet très utile pour la planification des mouvements du robot, qui se réduit alors à la recherche de chemin dans un graphe. Cette recherche est, en termes de complexité algorithmique, beaucoup plus simple que la recherche d'un chemin dans un espace continu à deux dimensions. Cet avantage est encore plus important lorsque les lieux représentés dans la carte correspondent à des structures humaines telles que les portes, les couloirs ou les pièces. La discrétisation permet alors de décrire et de résoudre les problèmes de manière naturelle pour les humains, par exemple en donnant l'ordre d'aller au bureau B744, plutôt que de dire d'aller à la position définie par les coordonnées x=354,y=285.

Comme nous l'avons déjà mentionné, l'utilisation directe des perceptions sans modèle métrique empêche d'estimer ces données pour des positions non visitées. En conséquence, les cartes topologiques nécessitent en général une exploration très complète de l'environnement pour le représenter avec précision. En particulier, tous les lieux intéressants que l'on souhaite trouver dans la carte devront être visités au moins une fois au cours de la construction de la carte, parce qu'ils ne peuvent pas être perçus à distance. Dans le cas où les lieux représentés sont des structures d'assez haut niveau (comme des couloirs ou des pièces), cela n'est pas gênant, car ces lieux sont peu nombreux et une exploration exhaustive est donc relativement rapide. En revanche, dans les cartes topologiques représentant des lieux avec une assez grande densité spatiale, cela peut être un inconvénient, car l'exploration complète de l'environnement demandera un temps important.

La reconnaissance des lieux de l'environnement peut également être difficile dans le cas de capteurs très bruités, ou d'environnements très dynamiques. Elle est, de plus, très sensible au problème de perceptual aliasing. Ces difficultés conduisent à des problèmes de fausse reconnaissance, c'est-à-dire à la reconnaissance d'un lieu donné alors que le robot se trouve dans un autre lieu. À leur tour, ces fausses reconnaissances conduisent à une mauvaise topologie de la carte et à des liens qui relient des nœuds de la carte qui ne sont pas physiquement reliés dans l'environnement. Ces difficultés rendent problématique la construction de cartes topologiques dans des environnements de grande taille, car la carte résultante risque d'être incohérente. Il devient alors très difficile d'estimer correctement la position du robot au sein de cette carte et de lui ajouter de nouvelles informations sans erreurs.

Comme nous l'avons vu, la représentation de l'environnement peut être assez proche des données brutes des capteurs du robot, ce qui peut être un avantage du point de vue de l'autonomie du robot. Toutefois, cette représentation centrée sur l'individu peut poser des problèmes pour la réutilisation de la carte. En effet, le manque de représentation de l'environnement indépendante de l'individu et l'absence de modèle métrique des capteurs ne permettront pas d'adapter la carte à un robot avec des capteurs légèrement différents. En effet, si l'on dispose d'un tel modèle, l'adaptation se fait simplement au niveau du modèle de capteur, sans modification de la carte elle-même. Cela est plus difficile avec une carte topologique, au sein de laquelle il est quasiment impossible de changer les données recueillies par un capteur pour les transformer en données telles qu'un autre capteur aurait pu les acquérir. De plus, cette représentation centrée sur un individu est moins naturelle pour un opérateur humain, plus habitué aux représentations objectives du type plan d'architecte, ce qui peut être gênant lorsque l'on souhaite une interaction forte entre un opérateur et le robot.

IV-B-1-d-i. Définition des nœuds▲

IV-B-1-d-ii. Définition des arêtes▲

Dans une carte métrique, l'environnement est représenté par un ensemble d'objets auxquels sont associées des positions dans un espace métrique, généralement en deux dimensions. Cet espace est, la plupart du temps, celui dans lequel s'exprime la position du robot estimée par les données proprioceptives. Les perceptions permettent, en utilisant un modèle métrique des capteurs, de détecter ces objets et d'estimer leur position par rapport au robot. La position de ces objets dans l'environnement est alors calculée en utilisant la position estimée du robot. La fusion des deux sources d'informations au sein d'un même cadre de représentation est caractéristique des cartes métriques.

Les objets mémorisés dans la carte peuvent être très divers et seront détaillés dans la suite de cette section. Dans certaines implantations, ces objets correspondent aux obstacles que le robot pourra rencontrer dans son environnement. La carte de l'environnement correspond alors directement à l'espace libre, c'est-à-dire à l'espace dans lequel le robot peut se déplacer.

L'avantage principal des cartes métriques est de permettre de représenter l'ensemble de l'environnement, et non un petit sous-ensemble de lieux comme le font les cartes topologiques. Cette représentation complète permet ainsi d'estimer avec précision et de manière continue la position du robot sur l'ensemble de son environnement. De plus, cette représentation complète ne se limite pas aux positions physiquement explorées, mais s'étend à toutes les zones que le robot a pu percevoir depuis les lieux qu'il a visités. Cette propriété peut permettre la construction d'une carte plus exhaustive de l'environnement en un temps plus court.

Un autre avantage des cartes métriques est lié au fait que la position du robot est définie de manière non ambiguë par ses coordonnées au sein de l'espace dans lequel la carte est représentée. Il s'ensuit une utilisation simple et directe de toutes les informations métriques fournies par les données proprioceptives ou les perceptions. Cela est un avantage par rapport aux cartes topologiques où les positions possibles du robot sont limitées aux nœuds présents dans la carte et sont donc relativement imprécises. Une telle représentation, dans laquelle chaque nœud peut couvrir une zone étendue de l'environnement, rend plus difficile l'utilisation des données métriques, car la position relative de deux zones est moins bien définie.

La représentation de l'environnement indépendante de l'individu utilisée dans les cartes métriques apporte un certain nombre d'avantages supplémentaires. Comme nous l'avons mentionné à propos des cartes topologiques, une telle représentation permet une réutilisation plus facile d'une carte sur des robots différents, équipés de capteurs différents, l'essentiel de l'adaptation se déroulant au niveau des modèles métriques des capteurs. Ce type de représentation est aussi facilement interprétable par un humain, ce qui peut être important dans le cas où il doit intervenir dans les déplacements du robot.

Cette représentation peut de plus utiliser des concepts de plus haut niveau, tels que des objets, des obstacles ou des murs. Cela permet un apport de connaissance plus facile de la part des humains, par exemple pour imposer que les murs détectés soient perpendiculaires ou parallèles.

Lors de l'utilisation de cartes métriques, les données proprioceptives ont en général une importance supérieure à celle qu'elles ont dans l'utilisation d'une carte topologique. Par conséquent, une odométrie plus fiable peut être requise. Le niveau de fiabilité nécessaire peut être atteint en imposant des limitations sur l'environnement du robot. Par exemple, il est possible d'imposer que tous les couloirs soient orthogonaux, afin de pouvoir corriger efficacement la dérive de l'estimation de la position.

Comme nous l'avons mentionné dans la section I.B.2Informations extéroceptives, un modèle métrique des capteurs peut être difficile à obtenir. Les problèmes liés au bruit des capteurs et à la difficulté de modéliser de manière fiable leur relation avec l'environnement constituent donc un point faible des cartes métriques.

Enfin, le calcul de chemin au sein des cartes métriques peut être plus complexe, car la planification se déroule dans un espace continu et non dans un espace préalablement discrétisé, comme c'est le cas pour les cartes topologiques. De nombreuses méthodes recourent d'ailleurs à l'extraction d'une carte topologique depuis la carte métrique pour réaliser cette opération de planification [87].

Deux méthodes principales sont utilisées pour mémoriser des informations sous forme de carte métrique. La première méthode consiste à extraire explicitement des objets des perceptions et à les enregistrer dans la carte avec leur position estimée. Les objets peuvent être de types très variés et se situer à différents niveaux d'abstraction. La seconde méthode s'attache à représenter directement l'espace libre accessible au robot et les zones d'obstacles qu'il ne peut pas franchir, sans avoir recours à l'identification d'objets individuels.

IV-B-2-d-i. Représentation d'objets▲

IV-B-2-d-ii. Représentation de l'espace libre▲

Dans le cas des cartes topologiques, estimer la position à partir des seules perceptions est extrêmement simple. En effet, parmi tous les lieux représentés dans la carte, la position du robot est celle d'un des nœuds qui correspond le mieux aux perceptions courantes. La recherche de ces nœuds passe donc par la comparaison des perceptions du robot avec les perceptions mémorisées dans chacun des nœuds de la carte. Les nœuds qui sont identiques ou suffisamment similaires sont alors reconnus comme positions possibles du robot.

En l'absence de perceptual aliasing, tous les nœuds de la carte correspondent à des situations différentes. Cette étape est alors suffisante pour la localisation complète du robot, car le nœud reconnu est unique. Différents systèmes perceptifs ont été utilisés pour implanter de tels modèles. Certains auteurs utilisent des images panoramiques de l'environnement pour définir les nœuds de la carte [80, 51]. D'autres modèles utilisent les directions ou les distances d'amers ponctuels tous discernables, soit en simulation [25, 93, 139, 124], soit sur des robots réels [9, 54].

L'utilisation d'images panoramiques permet par exemple de réaliser un système de localisation à partir d'une méthode d'indexation d'images [128]. Il suffit en effet d'avoir une base de données indexant les images des différents nœuds de la carte, puis, pour se localiser, de rechercher dans cette base l'image la plus proche de l'image courante. Cette image nous donnera le nœud correspondant à la position courante. L'indexation peut par exemple utiliser une analyse en composantes principales(9) qui va déterminer une base sur laquelle il sera possible de projeter chaque image. Les coordonnées de chaque image dans cette base fournissent ainsi une représentation de faible dimension de chaque nœud de la carte. Pour la localisation, il suffit de projeter l'image courante sur la base et de chercher l'image ayant les coordonnées les plus proches.

Lorsqu'une position dans un espace métrique est associée à chacun des nœuds de la carte, la localisation permet en outre de déterminer la position métrique du robot. Cette position peut simplement être la position du nœud reconnu, mais il est souvent possible d'obtenir une précision supplémentaire. En effet, au lieu de tenir simplement compte du nœud le plus conforme aux perceptions courantes, il est possible de tenir compte de chacun des nœuds, selon son degré de similarité avec ces perceptions. La méthode mise en œuvre dans de tels modèles pour réaliser cette estimation de position s'appelle dans la terminologie des neurosciences le codage par population de vecteurs [56]. Cette méthode consiste à estimer la position du robot par la moyenne des positions des différents nœuds, pondérées par le degré de similarité de chaque nœud avec les perceptions du robot. Cette méthode donne une estimation précise de la position du robot, mais suppose une relative continuité de l'environnement. Elle suppose en effet que des lieux similaires seront proches les uns des autres pour que la moyenne des positions ait un sens. Les perceptions doivent donc varier de manière relativement continue avec la position.

Lorsque les modèles permettent la gestion du perceptual aliasing (par une des méthodes décrites dans les paragraphes suivants), les lieux peuvent également être définis par des images panoramiques de leur environnement [6, 40, 66, 141, 113, 142], ou par la configuration des positions d'amers distants [12, 137]. Mais, puisque le perceptual aliasing sera géré par ailleurs, des définitions plus simples des nœuds peuvent également être adoptées, au prix d'une moins grande discrimination. Certains modèles utilisent ainsi les valeurs brutes de capteurs de distance [105, 98, 82, 69, 66, 108], ou la configuration des murs autour du robot afin de détecter des angles de couloirs ou des embranchements [83, 33, 125, 27, 106, 127, 130].

Dans le cas des cartes métriques, diverses méthodes d'estimation de la position existent. Lorsque les perceptions sont constituées d'amers ponctuels, une méthode de triangulation peut être utilisée [14, 59, 93, 96]. Cette méthode repose sur la mesure de la direction et de la distance d'amers ponctuels connus. La perception de trois amers de ce type permet en effet de définir la position du robot de manière unique. Un simple calcul mathématique permet donc d'estimer cette position à partir des positions des amers. Ce calcul peut également être approché par des réseaux de neurones, [111], ou par des méthodes heuristiques qui permettent une meilleure résistance au bruit [144]. Lorsque cette méthode est utilisée avec des cartes ne comportant pas de perceptual aliasing, chaque amer est unique et cette méthode permet d'estimer directement de manière non ambiguë la position du robot. En cas de perceptual aliasing, certains amers ne peuvent être distingués et il faut tenir compte de l'estimation précédente de la position afin de pouvoir identifier correctement les différents amers et estimer correctement la position.

Certains types d'objets fournissent plus d'informations que des amers ponctuels, sans toutefois permettre une estimation non ambiguë de la position. Par exemple, c'est le cas des murs dont la perception fournit une information sur la distance du robot à ce mur, mais pas sur sa position le long de ce mur (cf. Figure 10.1). Certains modèles utilisent de tels types d'objets, qui permettent d'affiner une estimation précédente de la position, mais pas d'estimer directement cette position [28, 73, 117].

Lorsque les objets mémorisés dans la carte ont une certaine étendue spatiale en deux dimensions, il est par contre possible d'utiliser la perception d'un seul objet afin d'estimer directement la position du robot. Les amers utilisés peuvent alors être des objets tridimensionnels détectés par une caméra [126], les angles des obstacles détectés par un télémètre laser [7, 18, 57, 73] ou un capteur à ultrason [92, 117], des segments détectés en utilisant une caméra [8] ou un télémètre laser [28, 31, 103].

D'autres modèles enfin n'estiment pas directement la position du robot au vu des perceptions, mais reposent sur la comparaison d'une carte métrique locale avec la carte métrique globale (cf. Figure 10.2). La carte métrique locale est construite soit à partir des seules perceptions courantes, soit à partir des données proprioceptives et des perceptions recueillies sur un court laps de temps. Le problème est alors de trouver la portion de carte globale qui correspond le mieux à la carte locale. Cette méthode est très souvent utilisée avec les grilles d'occupation [107, 119, 122, 131], ainsi qu'avec des données brutes de télémètres laser [94, 65, 41]. Le polygone de visibilité, qui entoure la zone d'espace libre visible depuis la position courante du robot peut aussi être utilisé [62, 75]. Comme nous le verrons dans la section suivante, ces méthodes sont souvent utilisées sur un espace de recherche restreint par une estimation initiale de la position. Elles peuvent cependant être utilisées pour la localisation globale [107, 62, 75].

Dans cette section, nous allons détailler une méthode de corrélation de cartes qui permet de chercher, pour deux cartes de dimensions réduites, la transformation (translation+rotation) qui permet la meilleure superposition. Cette transformation permet alors de corriger l'estimation de position du robot. Cette méthode peut être utilisée avec différents types de cartes, dont les grilles d'occupation, mais donne des résultats particulièrement efficaces avec des données issues d'un télémètre laser (Figure 10.3).

Il existe de nombreuses méthodes de mise en correspondance de scans lasers, telle que la méthode Iterated Closest Point (ICP) [95] ou des méthodes basées sur l'approche RANdom SAmple Consensus (RANSAC) [76] que nous ne présenterons pas toutes ici. La méthode que nous avons choisi de présenter [116] est une méthode simple qui est relativement robuste et résistante au bruit. Elle est basée sur les histogrammes des directions des tangentes au scan laser.

La première étape consiste à calculer pour chaque point du scan la droite tangente en utilisant la méthode des moindres carrés. On cherche pour cela la droite qui fournit la plus faible erreur quadratique sur un ensemble comprenant quelques points avant et quelques points après le point courant (Figure 10.4).

On construit ensuite l'histogramme des directions de ces tangentes, après avoir filtré les points pour lesquels la qualité de l'approximation des tangentes est trop faible. Cet histogramme contient alors des pics lorsque des ensembles de points correspondent à un mur rectiligne de l'environnement. Après avoir construit ces histogrammes de direction pour les deux scans, on cherche le décalage de ces histogrammes qui fournit la meilleure corrélation. Dans l'hypothèse où les deux scans ont été perçus en des points de l'environnement assez proches et représentent donc à peu près la même zone, ce décalage correspond à la rotation qui aligne les deux scans (Figure 10.5 gauche).

Une fois la direction recalée, pour corriger la translation, on projette les points selon la direction principale des tangentes. On construit ensuite l'histogramme du nombre de points projetés sur la perpendiculaire à cette direction et, en cherchant le maximum de corrélation entre les histogrammes correspondant aux deux scans, on corrige le décalage en translation selon cette direction (Figure 10.5 droite). On recommence ensuite cette procédure dans la direction perpendiculaire.

Cette méthode fonctionne bien dès qu'il y a des structures rectilignes dans l'environnement qui conduisent à des histogrammes contenant des pics pour lesquels le recalage par corrélation fonctionne bien. Il faut toutefois prendre un certain nombre de précautions qui ne sont pas détaillées ici, notamment faire un filtrage intelligent des scans afin de ne garder que les points qui ne correspondent ni à du bruit ni à des éléments dynamiques. Il faut également veiller à ne réaliser ce recalage que pour des scans qui ont été perçus à des positions effectivement proches, sous peine de recueillir des résultats très fantaisistes. Pour s'assurer de ce point, il est possible de vérifier la qualité de la corrélation des histogrammes afin de vérifier a posteriori que les deux scans représentaient des portions similaires de l'environnement.

L'hypothèse d'un environnement sans perceptual aliasing est relativement forte, car beaucoup de capteurs en robotique sont limités et bruités. De plus, les environnements intérieurs, de type bureaux, peuvent être très réguliers et présenter de nombreuses zones apparemment similaires pour le robot. Toutefois, les environnements courants contiennent souvent suffisamment d'informations accessibles à des capteurs précis et efficaces. Un être humain, par exemple, n'a aucun mal à se repérer dans un immeuble de bureaux, en lisant les numéros écrits sur les portes (trouver son chemin jusqu'à la sortie est un autre problème !). Il est donc théoriquement possible de concevoir des systèmes suffisamment discriminants pour être capables de se repérer grâce aux seules perceptions et une carte précise. Il est de plus possible d'aménager l'environnement afin de simplifier la tâche de perception pour le robot (comme le montre l'exemple des numéros de porte). Cette solution nuit toutefois à l'autonomie du robot puisqu'il est alors limité aux environnements bien définis qui ont été préparés à l'avance. Le rejet de cette dernière solution et la difficulté de réaliser des capteurs suffisamment discriminants conduisent donc la plupart des systèmes de navigation robotique à prendre en compte le perceptual aliasing et à utiliser les données proprioceptives pour déterminer leur position de manière unique. Nous allons décrire les différentes méthodes qui peuvent être utilisées dans la suite de ce chapitre.

Dans une carte topologique, sélectionner le nœud correct parmi les nœuds correspondant aux perceptions peut reposer simplement sur l'adjacence avec le nœud précédent. Dans ce cas, le nœud sélectionné est celui qui est connecté au nœud représentant la position précédente. Cette information est toutefois rarement suffisante et les relations métriques mémorisées dans les arêtes entre nœuds sont souvent utilisées en complément. Le nœud sélectionné est donc celui dont la position relative par rapport au nœud précédent correspond le mieux aux données proprioceptives [82, 83, 33, 105]. Lorsqu'une position métrique est associée à chaque nœud, c'est le nœud dont la position est la plus proche de la position estimée par l'odométrie qui est sélectionné [12, 84, 145].

Certains modèles fonctionnent dans le sens opposé. Au lieu d'utiliser les données proprioceptives pour sélectionner un nœud parmi les nœuds possibles, ils utilisent ces données pour restreindre l'ensemble des nœuds possibles et utilisent ensuite les perceptions pour sélectionner le nœud correct parmi ceux-ci. Les perceptions sont, par exemple, utilisées pour choisir un nœud parmi tous les nœuds adjacents au nœud précédent [141], ou parmi les nœuds suffisamment proches de la position estimée par l'odométrie [142].

Enfin, certains modèles intègrent les deux étapes en une seule en calculant la probabilité que chaque nœud représente la position courante. Cette probabilité intègre, d'une part, la similarité du nœud avec les perceptions courantes, et d'autre part sa proximité avec la position estimée par l'odométrie. Le nœud ayant la plus forte probabilité peut alors être reconnu [98], ou la position peut être estimée par codage par population de vecteurs en utilisant les probabilités calculées [6, 137].

Dans une carte métrique, l'estimation initiale de la position est utilisée pour restreindre l'espace de recherche de la position correspondant aux perceptions. Dans le cas où la carte contient des objets, une estimation de la position permet de simplifier le problème de l'appariement entre les objets perçus et ceux de la carte. En effet, dans le cas où les senseurs sont soumis à un fort perceptual aliasing, de nombreux objets identiques, situés à des positions différentes, sont présents dans la carte. Lorsque le robot perçoit un objet, déterminer quel objet a été perçu exige d'examiner un grand nombre de possibilités. L'estimation de la position du robot permet donc d'estimer la position des objets perçus et donc de déterminer à quels objets de la carte ils correspondent. Ce choix se fait en général en appariant simplement chaque objet perçu à l'objet mémorisé identique le plus proche [8, 28, 31, 39, 57, 92, 103, 129, 144]. Une fois l'appariement effectué, les objets sont identifiés sans ambiguïté et permettent donc d'estimer la position de manière unique.

Lorsque la position est déterminée par la mise en correspondance d'une carte locale et d'une carte globale, la position estimée est utilisée pour restreindre la recherche de la position donnant la meilleure correspondance entre les deux cartes [119, 122, 131, 147]. La recherche du maximum de correspondance est simplement effectuée sur une zone limitée autour de la position estimée précédemment. La zone étant de faible étendue, le problème de perceptual aliasing se pose moins et la recherche conduit en général à une position unique.

Lorsque la position correspondant aux perceptions a été identifiée de manière unique, elle peut être considérée directement comme la nouvelle estimation de la position du robot [147, 57, 144]. Cependant la plupart des modèles considèrent que cette estimation est entachée d'erreur, de la même manière que l'estimation initiale provenant de l'odométrie. La nouvelle position du robot est donc en général une combinaison de ces deux positions. La plupart des modèles [8, 129, 103, 31, 92, 119, 14, 18, 94, 28] utilisent un filtre de Kalman [99] pour réaliser cette combinaison. Ce filtre permet de calculer une estimation optimale de la position du robot, connaissant les deux positions et leur covariance respective. Il constitue une méthode classique de localisation et est décrit en détail dans la section III.C.3.cFiltrage de Kalman pour la localisation. D'autres méthodes sont également utilisables pour combiner ces deux informations, par exemple la minimisation d'une fonction de coût reliée à ces deux positions [131], ou l'utilisation de la méthode des moindres carrés récursifs [16].

IV-C-3-c-i. Principe▲

IV-C-3-c-ii. Application dans le cas d'une seule variable▲

IV-C-3-c-iii. Filtre de Kalman étendu▲

IV-C-3-c-iv. Application à la localisation sans perceptual aliasing▲

IV-C-3-c-v. Application à la localisation avec perceptual aliasing▲

IV-C-3-c-vi. Filtre de Kalman sans parfum (unscented)▲

La limitation principale de toutes ces méthodes de suivi de position est qu'elles ne garantissent une bonne estimation de la position que localement, autour de l'estimation initiale de la position. En pratique, si cette estimation initiale est trop éloignée de la position réelle, ces modèles ne pourront pas estimer correctement la position du robot (cf. Figure 10.10). Ces modèles ne garantissent donc pas que la position calculée soit la position de la carte qui corresponde globalement le mieux aux données recueillies par le robot et donc la position réelle la plus probable.

Ce problème prend toute son importance lorsque l'estimation de la position est perturbée à la suite d'informations proprioceptives ou de perceptions erronées. En effet, de telles informations erronées peuvent faire diverger l'estimation de la position de telle manière que le système soit par la suite incapable de retrouver une estimation correcte de la position.

La position correcte du robot pourra cependant être retrouvée par l'une des méthodes de localisation globale décrites dans la section précédente. Cette position pourra ensuite être utilisée comme nouvelle position initiale dans le processus de suivi de position. Toutefois, il est également possible d'utiliser une des méthodes de localisation globale décrites dans la fin de ce chapitre qui permettent de ne plus dépendre d'une estimation initiale correcte de la position. Cette seconde solution, qui ne requiert pas l'utilisation séparée de deux méthodes de localisation sera en général plus robuste, mais parfois moins précise.

Ce suivi de plusieurs hypothèses peut être réalisé de manière explicite, en gérant une liste des hypothèses en question. Lorsque des données proprioceptives sont disponibles, chaque hypothèse est simplement mise à jour de manière à refléter le déplacement du robot (cf. Figure 10.11c). Lorsque de nouvelles perceptions sont disponibles, l'ensemble des positions de la carte susceptibles de correspondre à ces perceptions est déterminé. Cet ensemble est ensuite comparé à l'ensemble des hypothèses. Si une hypothèse correspond à une position perçue, cette hypothèse est alors mise à jour en utilisant les perceptions par une méthode similaire à celle permettant le suivi de position, par exemple un filtre de Kalman. Les positions perçues qui ne correspondent à aucune hypothèse sont utilisées pour créer de nouvelles hypothèses associées à la position correspondante. La crédibilité de chacune des hypothèses est ensuite évaluée, généralement en fonction de la proximité de l'hypothèse avec une position correspondant aux perceptions du robot (cf. Figure 10.11d). Ainsi, une hypothèse verra sa crédibilité augmenter si elle est proche d'une des positions correspondant aux perceptions du robot, elle la verra diminuer dans le cas contraire. De nouvelles hypothèses peuvent également être ajoutées pour les positions correspondant aux perceptions qui ne correspondent à aucune hypothèse existante.

De tels modèles ont été implémentés en utilisant des cartes topologiques [37] où les différentes hypothèses correspondent à différents nœuds de la carte. Il existe également des modèles de ce type utilisant des cartes métriques [110, 73]. Ces derniers modèles utilisent en général plusieurs filtres de Kalman en parallèle et permettent de résoudre en grande partie les problèmes de divergence du filtre de Kalman employé seul. Cette technique est connue sous le nom de multi hypothesis tracking (MHT) [73].

Les méthodes de localisation multihypothèses peuvent être vues dans un cadre plus large, celui du filtrage bayésien. Cette méthode de filtrage permet d'intégrer de manière similaire les deux types d'informations (odométrie et perceptions), mais ne gère en général pas explicitement les hypothèses de position. Les différentes hypothèses sont ici remplacées par une distribution de probabilités de présence du robot sur l'ensemble des positions possibles de la carte. Cette représentation permet donc de considérer chacune des positions au sein de la carte comme une position possible du robot dont il faut évaluer la probabilité. Nous présentons d'abord le cadre général qui permet la gestion de cette distribution de probabilités, avant de voir comment il peut être utilisé en pratique dans des cas discrets ou continus.

Le filtrage bayésien regroupe un ensemble de méthodes d'estimation d'état utilisant les probabilités et plus particulièrement la loi de Bayes :

kitxmlcodelatexdvp\begin{equation} P(X|Y)=\frac{P(Y|X)P(X)}{P(Y)}\quad(10.22) \end{equation}finkitxmlcodelatexdvp

Dans le cadre de la localisation en robotique mobile, kitxmlcodeinlinelatexdvpXfinkitxmlcodeinlinelatexdvp est en général la position et kitxmlcodeinlinelatexdvpYfinkitxmlcodeinlinelatexdvp une perception de l'environnement. Cette loi nous permet donc d'estimer la probabilité kitxmlcodeinlinelatexdvpP(X|Y)finkitxmlcodeinlinelatexdvp des positions, connaissant une perception, c'est-à-dire précisément ce que nous cherchons à calculer pour localiser un robot. Pour ce calcul, nous aurons besoin de kitxmlcodeinlinelatexdvpP(Y|X)finkitxmlcodeinlinelatexdvp, la probabilité d'une perception connaissant la position, qui peut être calculée grâce à la carte de l'environnement et au modèle du capteur utilisé. Nous aurons également besoin d'une estimation des probabilités des positions kitxmlcodeinlinelatexdvpP(X)finkitxmlcodeinlinelatexdvp avant cette perception, ainsi que de la probabilité globale kitxmlcodeinlinelatexdvpP(Y)finkitxmlcodeinlinelatexdvp de cette perception. Dans un filtre bayésien, cette formule est utilisée de manière récursive et kitxmlcodeinlinelatexdvpP(X)finkitxmlcodeinlinelatexdvp est donc simplement l'estimation précédente de la probabilité des positions. Quant à kitxmlcodeinlinelatexdvpP(Y)finkitxmlcodeinlinelatexdvp, il peut être remplacé par un artifice de calcul lors de l'utilisation de la formule. En effet, par la loi des probabilités marginales :

kitxmlcodelatexdvp\begin{eqnarray*} P(Y) = \sum_XP(Y|X)P(X) \end{eqnarray*}finkitxmlcodelatexdvp

ce qui permet d'utiliser la loi de Bayes pour calculer les probabilités kitxmlcodeinlinelatexdvpP(X|Y)finkitxmlcodeinlinelatexdvp de la manière suivante :

kitxmlcodelatexdvp\begin{eqnarray*} \forall X, temp_{X|Y} & = & P(Y|X)P(X) \\ P(Y) & = & \sum_Xtemp_{X|Y} \\ \forall X, P(X|Y) & = & \frac{temp_{X|Y}}{P(Y)} \end{eqnarray*}finkitxmlcodelatexdvp

Dans cette équation, le terme kitxmlcodeinlinelatexdvpP(X)finkitxmlcodeinlinelatexdvp est la probabilité a priori (prior en anglais), kitxmlcodeinlinelatexdvpP(X|Y)finkitxmlcodeinlinelatexdvp est la probabilité a posteriori (posterior en anglais). La puissance de cette équation réside dans le fait qu'elle permet de transposer une quantité simple à évaluer, kitxmlcodeinlinelatexdvpP(Y|X)finkitxmlcodeinlinelatexdvp, en une quantité plus difficile à estimer et qui nous intéresse, kitxmlcodeinlinelatexdvpP(X|Y)finkitxmlcodeinlinelatexdvp. La vraisemblance kitxmlcodeinlinelatexdvpP(Y|X)finkitxmlcodeinlinelatexdvp est simple à évaluer, car elle est le produit d'un raisonnement causal : connaissant une carte, un modèle de capteur et une position, on peut facilement prévoir les mesures que devraient renvoyer ce capteur. kitxmlcodeinlinelatexdvpP(X|Y)finkitxmlcodeinlinelatexdvp, pour sa part, est le fruit d'un raisonnement de diagnostic et il est difficile à évaluer, car une perception kitxmlcodeinlinelatexdvpYfinkitxmlcodeinlinelatexdvp ne permet pas de définir simplement une position, mais peut correspondre à plusieurs, notamment dans le cas du perceptual aliasing(11).

Nous venons de voir comment la loi de Bayes permet de mettre à jour une probabilité de position en fonction d'une perception. Pour la localisation d'un robot mobile, il faut également pouvoir intégrer l'effet d'un déplacement sur une distribution de probabilités. Cela se fait aussi très simplement grâce à l'équation suivante (loi des probabilités marginales) :

kitxmlcodelatexdvp\begin{equation} P(X|U) = \sum_{X'}P(X|U,X')P(X')\quad(10.23) \end{equation}finkitxmlcodelatexdvp

Dans cette équation, kitxmlcodeinlinelatexdvpP(X|U,X')finkitxmlcodeinlinelatexdvp est un modèle du déplacement du robot, qui donne la probabilité d'une position kitxmlcodeinlinelatexdvpXfinkitxmlcodeinlinelatexdvp si le robot exécute l'action kitxmlcodeinlinelatexdvpUfinkitxmlcodeinlinelatexdvp dans la position kitxmlcodeinlinelatexdvpX'finkitxmlcodeinlinelatexdvp. Ce modèle ne dépend que du robot et correspond souvent au modèle d'odométrie que nous avons vu au début du cours. Comme précédemment, la probabilité a priori, kitxmlcodeinlinelatexdvpP(X')finkitxmlcodeinlinelatexdvp, est le fruit d'une estimation à l'étape précédente.

Pour localiser un robot, nous cherchons évidemment à estimer la position à partir de nombreux déplacements et de nombreuses observations : kitxmlcodeinlinelatexdvpP(x_t|u_1,y_2,...,u_{t-1},x_{t-1})finkitxmlcodeinlinelatexdvp. Pour pouvoir réaliser les calculs de manière récursive, l'hypothèse de Markov est utilisée : on suppose que les perceptions ne dépendent que de l'état courant et que la position après un déplacement ne dépend que de la position précédente. Ceci est illustré par le réseau bayésien de la Figure 10.12 qui montre les dépendances entre variables et correspond aux simplifications suivantes :

kitxmlcodelatexdvp\begin{eqnarray*} P(y_t|x_t,u_1,y_2,...,u_{t-1}) & = & P(y_t|x_t)\\ P(x_t|u_1,y_2,...,u_{t-1},x_{t-1}) & = & P(x_t|u_{t-1},x_{t-1}) \end{eqnarray*}finkitxmlcodelatexdvp

Partant de ces différents éléments, le filtrage bayésien permet donc d'estimer de manière récursive l'état d'un système à partir d'une estimation de son évolution et de mesures sur cet état. Pour pouvoir appliquer ce filtrage, nous avons besoin des éléments suivants, qui sont tous connus ou qui peuvent être définis grâce aux modèles du robot, des capteurs et de l'environnement :

• un modèle d'observation (de capteur) kitxmlcodeinlinelatexdvpP(y|x)finkitxmlcodeinlinelatexdvp qui donne, pour une position kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp donnée, la probabilité de la mesure kitxmlcodeinlinelatexdvpyfinkitxmlcodeinlinelatexdvp ;
• un modèle d'évolution (d'action) kitxmlcodeinlinelatexdvpP(x|u,x')finkitxmlcodeinlinelatexdvp qui donne la probabilité que le robot arrive en kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp s'il exécute l'action kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp en kitxmlcodeinlinelatexdvpx'finkitxmlcodeinlinelatexdvp ;
• une suite d'actions et de perceptions kitxmlcodeinlinelatexdvp{u_1,y_2,...,u_{t-1},y_t} ;finkitxmlcodeinlinelatexdvp ;
• une estimation initiale de la position kitxmlcodeinlinelatexdvpP_0(x)finkitxmlcodeinlinelatexdvp, qui peut, par exemple, être uniforme dans le cas de la localisation globale ou qui peut être une répartition gaussienne si nous connaissons la position initiale du robot.

Le filtre permet d'estimer la position en fonction des données mesurées : kitxmlcodeinlinelatexdvpP(x_t|u_1,y_2,...,u_{t-1},y_t)finkitxmlcodeinlinelatexdvp, ce que nous noterons par la suite (en version continue) kitxmlcodeinlinelatexdvpBel(x_t)finkitxmlcodeinlinelatexdvp (de l'anglais Belief State). L'équation de mise à jour récursive permet alors d'estimer kitxmlcodeinlinelatexdvpBel(x_t)finkitxmlcodeinlinelatexdvp en fonction de kitxmlcodeinlinelatexdvpBel(x_{t-1})finkitxmlcodeinlinelatexdvp. Cette équation se dérive de la manière suivante, en utilisant les lois présentées ci-dessus :

kitxmlcodelatexdvp\begin{eqnarray*} Bel(x_t) & = & P(x_t|u_1,y_2,...,u_{t-1},y_t)\\ (Bayes) & = &\eta P(y_t|x_t,u_1,y_2,...,u_{t-1})P(x_t|u_1,y_2,...,u_{t-1})\\ (Markov) & = & \eta P(y_t|x_t)P(x_t|u_1,y_2,...,u_{t-1})\\ (prob totales) & = & \eta P(y_t|x_t) \int P(x_t|u_1,y_2,...,u_{t-1},x_{t-1})P(x_{t-1}|u_1,y_2,...,u_{t-1})dx_{t-1}\\ (Markov) & = & \eta P(y_t|x_t)\int P(x_t|u_{t-1},x_{t-1})P(x_{t-1}|u_1,y_2,...,u_{t-1})dx_{t-1}\\ & = & \eta P(y_t|x_t)\int P(x_t|u_{t-1},x_{t-1})Bel(x_{t-1})dx_{t-1} \end{eqnarray*}finkitxmlcodelatexdvp

Pour résumer, l'estimation de l'état par un filtre bayésien correspond à l'utilisation de l'équation de mise à jour suivante, pour une perception kitxmlcodeinlinelatexdvpy_tfinkitxmlcodeinlinelatexdvp et un déplacement kitxmlcodeinlinelatexdvpu_{t-1}finkitxmlcodeinlinelatexdvp:

kitxmlcodelatexdvpBel(x_t) = \eta P(y_t|x_t)\int P(x_t|u_{t-1},x_{t-1})Bel(x_{t-1})dx_{t-1}\quad(10.24)finkitxmlcodelatexdvp

Le filtrage bayésien regroupe en fait un grand nombre d'approches connues sous des noms différents qui se différentient par la manière dont la distribution de probabilités kitxmlcodeinlinelatexdvpBel(x_t)finkitxmlcodeinlinelatexdvp est représentée (Figure 10.13). Le filtre de Kalman est par exemple une implantation de ce filtre avec des distributions de probabilités gaussiennes et des modèles linéaires. Le filtre de Kalman multihypothèse correspond à une représentation sous forme de somme de gaussiennes. Nous allons voir dans la fin de ce chapitre deux autres méthodes qui utilisent soit une représentation discrète soit une représentation sous forme d'un ensemble d'échantillons. Dans ce dernier cas, le filtre s'appelle le filtre particulaire.

Représenter la position du robot par une telle distribution de probabilités permet d'intégrer la totalité des informations recueillies au cours du temps. Elle est mise à jour, d'une part à chaque déplacement du robot, et donc à chaque nouvelle donnée proprioceptive, et d'autre part à chaque nouvelle perception. De manière imagée, les données proprioceptives permettent de déplacer les probabilités d'une position à une autre pour refléter le déplacement du robot. Les perceptions permettent de moduler la probabilité de chaque position. Ainsi, les positions pour lesquelles les perceptions prévues à l'aide de la carte sont similaires aux données perçues voient leur probabilité augmenter, tandis que les autres voient leur probabilité diminuer.

Lorsqu'on utilise une telle distribution de probabilités, la position du robot calculée est en général donnée par l'hypothèse ayant la plus forte probabilité [66, 69, 125, 127, 24, 49]. Cependant d'autres estimations telles que la moyenne des positions pondérées par leur probabilité peuvent être utilisées [27], ou des versions intermédiaires telles que la moyenne des kitxmlcodeinlinelatexdvpxfinkitxmlcodeinlinelatexdvp % des meilleures positions.

La distribution de probabilités obtenue dépend faiblement des conditions initiales et peut donc être initialisée à une distribution uniforme lorsqu’ aucune information n'est disponible sur la position du robot. La position sera alors retrouvée, même si le robot est soumis à un très fort perceptual aliasing, assurant ainsi la localisation globale du robot dans tous les environnements. Ces méthodes sont extrêmement robustes en pratique et mettent en œuvre un système de localisation complètement autonome, ne dépendant d'aucune intervention extérieure [133].

Ces qualités reposent toutefois de manière importante sur le fait que la carte de l'environnement est complète. En effet, les systèmes de suivi de plusieurs hypothèses nécessitent une estimation correcte des probabilités des différentes positions possibles. Or une carte partielle de l'environnement rend difficile une telle estimation à partir des perceptions. Pour cette raison, ces systèmes sont en général utilisés pour la localisation sur des cartes construites dans une phase préalable.

Pour appliquer le filtrage bayésien que nous avons présenté dans le cas continu, il faut choisir une manière de représenter les distributions de probabilités. Une première approche consiste à discrétiser l'environnement et à donner à chaque position discrète une probabilité approximant la valeur de la distribution continue. Cette approche, également nommée Histogram Filter (je ne connais pas la bonne traduction française…), a été utilisée à la fois avec des cartes topologiques où les nœuds sont utilisés comme positions possibles, [27, 66, 69, 79, 106, 108, 125, 127, 130] et avec des cartes métriques, pour lesquelles il est possible de discrétiser l'ensemble des positions, à la manière des grilles d'occupation [24, 49, 133].

Quelle que soit la discrétisation choisie, l'algorithme reste le même. Il s'agit d'évaluer la probabilité kitxmlcodeinlinelatexdvpBel(x_i)finkitxmlcodeinlinelatexdvp que le robot soit situé sur l'état kitxmlcodeinlinelatexdvpx_ifinkitxmlcodeinlinelatexdvp de la carte. Ceci est fait par deux procédures différentes selon que l'on cherche à intégrer une perception ou des données proprioceptives. Pour une perception, on utilisera la procédure de l'algorithme 10.1. Les probabilités kitxmlcodeinlinelatexdvpP(y|x_i)finkitxmlcodeinlinelatexdvp proviennent soit d'un modèle de capteur métrique pour les grilles d'occupation, soit d'un modèle comparant une perception avec les données mémorisées dans les nœuds pour la carte topologique. Pour un déplacement on utilisera l'algorithme 10.2. La Figure 10.14, tirée de [48] montre un exemple d'évolution de la probabilité de position d'un robot.

L'implantation naïve de cet algorithme conduit à une mise à jour quadratique en fonction du nombre d'états (O(kitxmlcodeinlinelatexdvpN^2finkitxmlcodeinlinelatexdvp)), ce qui peut être rapidement lourd à calculer. Cependant, le modèle probabiliste de déplacement kitxmlcodeinlinelatexdvpP(x|u,x')finkitxmlcodeinlinelatexdvp est en général nul dès que l'on s'éloigne de la position spécifiée par la commande kitxmlcodeinlinelatexdvpufinkitxmlcodeinlinelatexdvp depuis l'état kitxmlcodeinlinelatexdvpx'finkitxmlcodeinlinelatexdvp. Si l'on note kitxmlcodeinlinelatexdvppfinkitxmlcodeinlinelatexdvp le nombre d'états pour lequel le modèle est non nul, on peut facilement écrire un algorithme en O(np), qui est donc linéaire en le nombre d'états de la carte.

Il est également possible d'utiliser une autre méthode pour représenter une distribution de probabilités continue sur l'espace de la carte [46] sans discrétisation de la carte. Cette méthode, le filtrage particulaire est l'une des plus efficaces pour la localisation.

Pour représenter la distribution de probabilités kitxmlcodeinlinelatexdvpBel(x)finkitxmlcodeinlinelatexdvp, cette méthode utilise un échantillonnage en un ensemble de particules qui permet d'approcher la distribution. En effet, considérons que la position du robot est la position moyenne définie par la distribution de probabilités kitxmlcodeinlinelatexdvpBel(x)finkitxmlcodeinlinelatexdvp :

kitxmlcodelatexdvpPosition = \int_x x.Bel(x) dxfinkitxmlcodelatexdvp

Supposons par ailleurs que l'on soit capable de générer un ensemble de kitxmlcodeinlinelatexdvpNfinkitxmlcodeinlinelatexdvp échantillons de position kitxmlcodeinlinelatexdvp\theta_ifinkitxmlcodeinlinelatexdvp, que nous appellerons particules, selon la distribution de probabilités kitxmlcodeinlinelatexdvpBel(x)finkitxmlcodeinlinelatexdvp (Figure 10.15 gauche). On peut alors approcher la position par :

kitxmlcodelatexdvpPosition \approx \frac{1}{N} \sum_i \theta_ifinkitxmlcodelatexdvp

C'est cet ensemble de particules qui va permettre de représenter la distribution de probabilités de positions du robot. Tout le problème revient alors à être capable de générer récursivement un ensemble de particules réparties selon la loi kitxmlcodeinlinelatexdvpBel(x)finkitxmlcodeinlinelatexdvp.

Dans notre cas, il est évidemment impossible a priori de générer de tels échantillons, car kitxmlcodeinlinelatexdvpBel(x)finkitxmlcodeinlinelatexdvp est une distribution inconnue que nous cherchons à évaluer. Pour pouvoir néanmoins approcher cette fonction, nous allons introduire une fonction auxiliaire kitxmlcodeinlinelatexdvp\pi(x)finkitxmlcodeinlinelatexdvp, appelée fonction d'importance selon laquelle nous allons tirer nos particules. En effet, avec de telles particules, réparties selon une loi kitxmlcodeinlinelatexdvp\pi(x)finkitxmlcodeinlinelatexdvp, il est également possible d'approcher kitxmlcodeinlinelatexdvpBel(x)finkitxmlcodeinlinelatexdvp. Pour cela, nous commençons par écrire :

kitxmlcodelatexdvpBel(x) = \frac{Bel(x)}{\pi(x)} \pi(x) = w(x) \pi(x)finkitxmlcodelatexdvp

avec

kitxmlcodelatexdvpw(x) = \frac{Bel(x)}{\pi(x)}finkitxmlcodelatexdvp

et donc, si nous générons les échantillons aléatoires kitxmlcodeinlinelatexdvp\theta_ifinkitxmlcodeinlinelatexdvp selon la fonction d'importance kitxmlcodeinlinelatexdvp\pifinkitxmlcodeinlinelatexdvp (connue, car nous l'avons choisie), nous pouvons estimer la position par :

kitxmlcodelatexdvpPosition = \int_x x.Bel(x) dx = \int_x x. w(x) \pi(x) \approx \frac{1}{N} \sum_i w(\theta_i) \theta_ifinkitxmlcodelatexdvp

Ainsi la distribution kitxmlcodeinlinelatexdvpBel(x)finkitxmlcodeinlinelatexdvp peut s'approcher sous la forme d'un ensemble de particules tirées selon une loi kitxmlcodeinlinelatexdvp\pi(x)finkitxmlcodeinlinelatexdvp, chaque particule ayant un poids associé kitxmlcodeinlinelatexdvpw(x)finkitxmlcodeinlinelatexdvp (Figure 10.15 droite). La difficulté d'échantillonner selon kitxmlcodeinlinelatexdvpBel(x)finkitxmlcodeinlinelatexdvp reste cachée dans la difficulté de calculer le poids de chaque particule kitxmlcodeinlinelatexdvpw(x)finkitxmlcodeinlinelatexdvp, mais grâce à un choix judicieux de kitxmlcodeinlinelatexdvp\pi(x)finkitxmlcodeinlinelatexdvp nous pouvons arriver à rendre ce calcul possible en utilisant l'équation de mise à jour du filtrage bayésien.

En effet, dans le cas qui nous intéresse :

kitxmlcodelatexdvp\begin{equation} Bel(x_t) = \eta P(y_t|x_t)\int P(x_t|u_{t-1},x_{t-1})Bel(x_{t-1})dx_{t-1}\quad(10.25) \end{equation}finkitxmlcodelatexdvp

en choisissant (intelligemment) kitxmlcodeinlinelatexdvp\pi(x) =\int P(x|u_{t-1},x_{t-1})Bel(x_{t-1})dx_{t-1}finkitxmlcodeinlinelatexdvp, nous obtenons:

kitxmlcodelatexdvp\begin{eqnarray*} w(\theta) & = & \frac{Bel_t(\theta)}{\pi(\theta)} \\ & = & \frac{\eta P(y_t|\theta)\int P(\theta|u_{t-1},x_)Bel_{t-1}(x)dx }{\int P(\theta|u_{t-1},x_{t-1})Bel(x_{t-1})dx_{t-1}} \\ & = &\eta P(y_t|\theta) \end{eqnarray*}finkitxmlcodelatexdvp

Cette valeur est simple à calculer, car elle ne dépend que de la carte et du modèle de capteurs pour la position d'un échantillon kitxmlcodeinlinelatexdvp\thetafinkitxmlcodeinlinelatexdvp.

Le problème du calcul des poids est donc réglé avec ce choix de kitxmlcodeinlinelatexdvp\pi(x) =\int P(x|u_{t-1},x_{t-1})Bel(x_{t-1})dx_{t-1}finkitxmlcodeinlinelatexdvp. Reste à voir comment il est possible d'échantillonner des particules selon cette loi. Comme nous utilisons une méthode récursive, kitxmlcodeinlinelatexdvpBel(x_{t-1})finkitxmlcodeinlinelatexdvp est approchée sous la forme d'un ensemble de particules kitxmlcodeinlinelatexdvp\theta_{t-1}finkitxmlcodeinlinelatexdvp, chacune associée à un poids kitxmlcodeinlinelatexdvpw_{t-1}finkitxmlcodeinlinelatexdvp. À partir de ces particules, l'échantillonnage selon kitxmlcodeinlinelatexdvp\pi(x)finkitxmlcodeinlinelatexdvp, se déroule en deux étapes : une mise à jour selon le modèle d'évolution kitxmlcodeinlinelatexdvpP(x|u_{t-1},x_{t-1})finkitxmlcodeinlinelatexdvp, puis un rééchantillonnage des particules pour correspondre à la loi kitxmlcodeinlinelatexdvp\pi(x)finkitxmlcodeinlinelatexdvp.

Pour la première étape, les particules sont mises à jour à partir du modèle de déplacement en tirant de manière aléatoire, pour chaque particule kitxmlcodeinlinelatexdvp\theta_ifinkitxmlcodeinlinelatexdvp, une particule kitxmlcodeinlinelatexdvp\delta_ifinkitxmlcodeinlinelatexdvp selon la loi kitxmlcodeinlinelatexdvpP(x|u_{t-1},\delta_i)finkitxmlcodeinlinelatexdvp. L'ensemble des kitxmlcodeinlinelatexdvp\delta_ifinkitxmlcodeinlinelatexdvp représente alors la distribution kitxmlcodeinlinelatexdvp\int P(x|u_{t-1},x_{t-1})Bel(x_{t-1})dx_{t-1}finkitxmlcodeinlinelatexdvp, mais la fonction d'importance selon laquelle ils sont répartis n'est pas celle que nous voulons (Figure 10.16).

La seconde étape a pour but d'obtenir un échantillonnage selon la fonction d'importance kitxmlcodeinlinelatexdvp\int P(x|u_{t-1},x_{t-1})Bel(x_{t-1})dx_{t-1}finkitxmlcodeinlinelatexdvp. Pour cela, il faut rééchantillonner, ce qui peut se faire selon une méthode appelée Stochastic universal sampling [11]. Cette méthode consiste à choisir kitxmlcodeinlinelatexdvpNfinkitxmlcodeinlinelatexdvp particules kitxmlcodeinlinelatexdvp\delta_ifinkitxmlcodeinlinelatexdvp selon des points équirépartis sur un cercle sur lequel sont disposées l'ensemble initial des particules selon des secteurs angulaires de taille proportionnelle à leur poids (Figure 10.17). Cette méthode permet de multiplier les particules qui ont des poids élevés, et de réduire le nombre d'échantillons correspondant aux particules de poids faibles (Figure 10.18).

En résumé, la localisation par filtrage particulaire s'effectue selon l'algorithme 10.3, et est illustrée sur la Figure 10.19. Intuitivement, l'algorithme permet de concentrer les particules dans les zones de plus fortes probabilités, où elles auront des poids plus forts. C'est un algorithme finalement extrêmement simple et particulièrement robuste.

Cette version de base demande cependant un réglage relativement précis des paramètres, notamment des modèles probabilistes de perception et de l'odométrie pour donner des résultats satisfaisants.

Le nombre de particules utiles pour approcher correctement la probabilité de position peut également être relativement délicat à choisir. En effet, s'il y a trop peu de particules, les zones de fortes probabilités risquent de ne pas être bien représentées et le rééchantillonnage ne permettra pas de concentrer les particules autour de la position la plus probable, le filtre ne convergera donc pas. On parle alors de raréfaction des particules.Ce problème est d'autant plus important pour la localisation globale, pour laquelle les particules sont initialisées aléatoirement sur tout l'environnement. S'il n'y a pas initialement de particule proche de la position réelle du robot, le filtre ne pourra pas la découvrir.

Augmenter le nombre de particules permet en général de résoudre le problème, mais augmente proportionnellement le temps de calcul, ce qui est rapidement problématique. Il existe donc de nombreuses variantes et améliorations de la méthode, qui permettent par exemple de sélectionner automatiquement le nombre de particules optimal pour fournir une approximation correcte de la position [50], ou de réaliser des mises à jour partielles pour respecter un temps de calcul limite [85].

Comme nous l'avons expliqué dans le chapitre III.ALocalisation, cartographie et planification la cartographie est indissociable de la localisation, ce qui implique de disposer d'une méthode de localisation robuste pour espérer avoir une carte correcte. Ceci est le principal problème lors de la phase de cartographie, car une localisation correcte repose en général sur une bonne carte de l'environnement.

La tâche de cartographie est donc intrinsèquement plus complexe que celle de localisation. En effet, la localisation revient à rechercher, parmi les positions possibles représentées dans la carte, celle qui correspond le mieux à la position courante du robot. Cette recherche se déroule donc dans un espace fermé, car on postule que la position recherchée se trouve parmi les positions enregistrées dans la carte. Dans le cas de la cartographie, une difficulté importante provient du fait que l'estimation de la position du robot se déroule dans un espace ouvert, puisque le robot peut découvrir des zones encore inconnues. De plus cet espace est de faible dimension pour la localisation (trois en général), tandis que la construction de la carte se déroule dans un espace de beaucoup plus grande dimension. Par exemple, pour une carte de kitxmlcodeinlinelatexdvpNfinkitxmlcodeinlinelatexdvp amers 2D, il y aura kitxmlcodeinlinelatexdvp2Nfinkitxmlcodeinlinelatexdvp paramètres. Or que ce soit pour la cartographie ou la localisation, les données disponibles (odométrie et perceptions) restent les mêmes, et il faudra donc mieux les exploiter pour construire une carte.

L'incomplétude de la carte rend de plus la plupart des méthodes de localisation globale précédemment évoquées difficiles à utiliser, car elles supposent une comparaison des probabilités des différentes hypothèses de position. Or avec une carte en cours de construction, le robot peut se situer dans une zone qui n'est pas encore cartographiée et il sera donc impossible d'évaluer la probabilité de cette position. La plupart des systèmes reposent donc sur une méthode de localisation qui réalise un suivi de position. En effet, si le robot atteint un lieu qui n'est pas représenté dans la carte, il est possible, grâce à ces méthodes locales, de définir sa position par rapport à une position précédente connue au sein de la carte.

L'utilisation de systèmes de localisation effectuant un suivi de position lors de la cartographie pose cependant certains problèmes, car comme nous l'avons vu au chapitre précédent, ces méthodes peuvent diverger et conduire à une estimation erronée de la position sans possibilité de retrouver la position réelle du robot. Ce problème est particulièrement important au cours du processus de cartographie, car les erreurs de localisation conduisent à des mises à jour erronées de la carte, ce qui peut conduire à des erreurs durables dans les futures tentatives de localisation.

Ces erreurs sont cruciales dans les environnements cycliques, c'est-à-dire dans des environnements contenant des boucles dont les différentes parties ne sont pas toutes visibles par les capteurs les unes à partir des autres (cf. Figure 11.1). En effet, dans de tels environnements, les erreurs de cartographie durant le parcours du cycle peuvent empêcher la reconnaissance de la fermeture du cycle et conduire à des cartes à la topologie erronée (cf. Figure 11.2). Il existe d'ailleurs des algorithmes spécialement adaptés à la détection de fermetures de boucle afin de pouvoir corriger ce type d'erreurs [1].

Un autre problème important de la cartographie est le choix de la représentation utilisée pour mémoriser les informations qui serviront par la suite au robot. Nous avons déjà présenté les réponses à ce problème en présentant les diverses structures de cartes, mais il faut garder à l'esprit que le choix de cette structure a une grande influence sur la qualité du processus de cartographie. Le choix de la représentation va déterminer la possibilité de faire ou non des mises à jour globales et efficaces lorsque de nouvelles informations sont disponibles.

On peut distinguer deux grandes catégories de méthodes de cartographie. La cartographie incrémentale [134] constitue une première méthode simple de construction de carte. Elle permet simplement d'ajouter localement de nouvelles informations dans la carte à partir de l'estimation courante de la position du robot. Cependant, si cette estimation se révèle fausse a posteriori, il est impossible de revenir sur les modifications qui ont été effectuées. Cette limitation se révèle problématique dans les environnements contenant des cycles parce que la fermeture d'un tel cycle donne une information importante sur les erreurs des estimations précédentes de la position du robot. Cette information est ignorée par les systèmes de cartographie incrémentale et conduit, dans le cas d'environnements cycliques à des cartes dans lesquelles les erreurs vont se concentrer dans une petite zone (cf. Figure 11.2 et 11.3).

La cartographie incrémentale constitue la méthode de base de nombreux systèmes utilisant des cartes topologiques. Cette méthode est également utilisée pour la création de grilles d'occupation que nous décrirons plus loin.

La seconde catégorie de systèmes de cartographie regroupe les systèmes qui permettent d'intégrer des informations a posteriori sur les positions passées du robot (Figure 11.3). Il faut noter que l'intégration de données a posteriori sur les positions passées est relativement simple dans les cartes topologiques grâce à la séparation des données proprioceptives et des perceptions que cette représentation implique. En effet, des erreurs dans l'estimation de la position du robot n'influent que sur les informations mémorisées dans les liens de la carte, et non sur les perceptions qui sont mémorisées dans les nœuds. Ainsi, revenir sur une modification passée de la carte, lorsque des nouvelles informations sur la position du robot sont disponibles, requiert simplement de modifier les informations mémorisées dans les liens et ne concerne pas les perceptions mémorisées. Dans le cas des cartes métriques, la modification d'une position passée va avoir des répercussions sur les perceptions (via le modèle métrique) et va donc rendre les modifications dues aux retours en arrière assez profondes. Pour permettre de tels retours en arrière, il faut alors utiliser un moyen de mémoriser les perceptions en les reliant à la position depuis laquelle elles ont été perçues. Cela peut se faire en mémorisant les perceptions indépendamment (des scans lasers par exemple), mais n'est pas possible pour certaines représentations (notamment les grilles d'occupation).

Pour construire une carte topologique, nous commençons donc par estimer la position du robot. Dans les cartes topologiques sans perceptual aliasing [124, 25, 93, 51, 146, 55, 10], il suffit de comparer les perceptions courantes avec les données mémorisées dans chacun des nœuds de la carte. Si aucun des nœuds ne correspond suffisamment bien aux données courantes, cela signifie que le lieu n'est pas représenté dans la carte et qu'il devra donc être ajouté. Au contraire, si la similitude des données courantes avec un nœud de la carte est suffisante, ce nœud sera reconnu comme la position courante du robot. Le choix entre ces deux possibilités est le point difficile du processus de cartographie. En effet, dans le cas de la simple localisation, il suffit de trouver le nœud correspondant le mieux à la situation courante pour trouver la position du robot. Dans le cadre de la cartographie, il faut de plus utiliser un seuil pour décider si le lieu le plus similaire est la position courante du robot ou non : si la similitude est supérieure à ce seuil, le nœud est reconnu, sinon un nouveau lieu est créé. Cette utilisation d'un seuil rend le processus de cartographie potentiellement plus instable que la localisation seule.

Lorsque le perceptual aliasing est pris en compte, percevoir un lieu différent de tous les lieux mémorisés dans la carte permet toujours de conclure que ce lieu est nouveau. Mais des perceptions qui correspondent à un lieu déjà mémorisé ne sont pas suffisantes pour déterminer si le lieu est nouveau ou s'il est connu, car un lieu nouveau peut être similaire à un lieu déjà visité. La position précédente du robot doit donc être prise en compte pour déterminer si un lieu est nouveau ou s'il correspond à un nœud mémorisé. Si la position prédite par l'odométrie depuis le lieu précédent ne correspond pas au lieu déjà mémorisé, le lieu est considéré comme nouveau et ajouté à la carte [82, 43, 84, 145, 83, 142, 105, 12]. Certains modèles intègrent directement les informations perceptuelles et la position pour la reconnaissance des nœuds, se ramenant ainsi au cas où il n'y a pas de perceptual aliasing [6, 137, 33, 98].

Une fois le nœud reconnu ou créé, les perceptions sont utilisées pour corriger les données mémorisées dans ce nœud. Cela permet d'avoir une meilleure estimation des perceptions caractérisant le lieu grâce au filtrage du bruit sur ces données. Les données proprioceptives recueillies depuis le nœud précédent sont ensuite utilisées pour créer ou modifier l'arête qui joint le nœud précédent au nœud courant. Ce processus de cartographie est décrit par l'algorithme 11.1

Comme nous l'avons mentionné précédemment, dans le cas où des informations métriques sont mémorisées entre les lieux, la carte obtenue peut alors se révéler incohérente. Dans les méthodes de cartographie incrémentale, la cohérence peut être assurée par l'association d'une position à chacun des nœuds de la carte [6, 137, 33, 98, 84], ou par une adaptation locale des valeurs des liens (Figure 11.3). Dans le cas où ces valeurs seront ensuite simplement utilisées de manière locale(12), sans chercher à estimer les relations métriques entre lieux distants, le maintien de la cohérence peut être simplement négligé [82, 43].

Une première méthode simple de cartographie métrique incrémentale consiste à simplement utiliser une méthode de corrélation de scans lasers ou de cartes locales. Lorsque le robot progresse dans une zone encore non cartographiée, la corrélation est simplement effectuée entre la carte locale courante et la carte locale précédente. La nouvelle carte locale est ensuite ajoutée à la carte de l'environnement à sa position estimée (Figure 11.4).

Lorsque le robot revient ensuite dans une zone déjà cartographiée après avoir parcouru une boucle, la corrélation peut être faite entre la carte locale courante et la portion de la carte globale la plus proche de la position actuelle (et non uniquement avec la carte locale précédente). Ceci permet de réestimer la position du robot dans la portion de carte déjà construite, mais ne corrige pas la carte le long de la boucle. Nous verrons plus loin (section III.D.3.aMéthodes de relaxation) comment étendre ces méthodes pour corriger ces erreurs.

Cette méthode est en général suffisante lorsqu'elle est utilisée avec les données d'un télémètre laser et dans un environnement de taille limitée ne contenant pas de grands cycles. Lors de la fermeture de grands cycles, par contre, elle montre rapidement ses limites, car les erreurs de localisation ne permettent pas de trouver la bonne portion de carte avec laquelle faire la corrélation. La méthode échoue alors, mais il est possible d'ajouter des procédures spécifiques qui font une recherche globale lorsqu'un cycle semble être fermé et permettent de rattraper ces échecs [64].

Une autre méthode de cartographie incrémentale très populaire est la construction de grilles d'occupation. Rappelons que les grilles d'occupation sont une représentation de l'environnement dans laquelle l'espace est discrétisé en cellules régulières et dont chaque cellule a une probabilité associée d'être occupée par un obstacle (Figure 11.5). La construction de grilles d'occupation est l'une des premières méthodes de cartographie à avoir été développée.

Dans les premiers travaux de leurs créateurs, Moravec et Elves [101, 131], la construction de grilles d'occupation supposait la position du robot connue. Dans des développements ultérieurs, toutefois, la grille en cours de construction est utilisée pour estimer la position du robot. On utilise pour cela des techniques de mise en correspondance de grilles similaires à celles présentées dans la section III.C.2.cCorrélation de cartes. Ces méthodes de recalage permettent de limiter la dérive de l'odométrie, mais ne sont en général pas suffisantes pour garantir une cartographie correcte dans les environnements cycliques. Pour résoudre ce problème, il est possible d'utiliser des hypothèses sur l'environnement, afin de permettre le recalage de l'odométrie durant la cartographie. L'hypothèse la plus couramment utilisée suppose que les murs de l'environnement sont rectilignes et orthogonaux [131, 83], ce qui permet de corriger facilement l'estimation de la direction du robot.

Après avoir estimé la position du robot, les valeurs des différentes cellules de la grille d'occupation sont mises à jour en fonction des perceptions. Pour cela, nous disposons d'un modèle des capteurs kitxmlcodeinlinelatexdvpP(occ_i|s)finkitxmlcodeinlinelatexdvp qui, pour une perception kitxmlcodeinlinelatexdvpsfinkitxmlcodeinlinelatexdvp donnée, nous fournit la probabilité d'occupation des cellules dans le champ de vision du capteur en fonction de la valeur renvoyée par le capteur. Ce modèle probabiliste est en général similaire à ceux présentés dans la section I.C.2.a.iiModèle probabiliste pour la distance au capteur et utilise une erreur gaussienne pour l'écart entre la direction de la cellule et la direction du capteur.

Nous cherchons donc à accumuler ces mesures pour estimer la probabilité pour la cellule kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp d'être occupée en fonction de toutes mesures précédentes : kitxmlcodeinlinelatexdvpP(occ_i^T)=P(occ_i|s_1,...,s_T)finkitxmlcodeinlinelatexdvp. Pour cela, nous utilisons, comme souvent, la formule de Bayes pour extraire la probabilité de la dernière mesure en fonction des autres variables :

kitxmlcodelatexdvpP(occ_i^T)=\frac{P(s_T|occ_i,s_1,...,s_{T-1})P(occ_i|s_1,...,s_{T-1})}{P(s_T|s_1,...,s_{T-1})}finkitxmlcodelatexdvp

En faisant l'hypothèse que le monde est statique, qui se traduit par le fait que les mesures sont conditionnellement indépendantes si l'on connaît la valeur de la cellule de la carte, nous pouvons simplifier :

kitxmlcodelatexdvpP(occ_i^T)=\frac{P(s_T|occ_i)P(occ_i^{T-1})}{P(s_T|s_1,...,s_{T-1})}finkitxmlcodelatexdvp

notre modèle de capteur nous donnant kitxmlcodeinlinelatexdvpP(occ_i|s_T)finkitxmlcodeinlinelatexdvp, nous le faisons apparaître en utilisant Bayes une nouvelle fois :

kitxmlcodelatexdvpP(occ_i^T)=\frac{P(occ_i|s_T)P(s_T)}{P(occ_i)}\frac{P(occ_i^{T-1})}{P(s_T|s_1,...,s_{T-1})}finkitxmlcodelatexdvp

Dans cette équation nous ne connaissons pas kitxmlcodeinlinelatexdvpP(s_T)finkitxmlcodeinlinelatexdvp ni kitxmlcodeinlinelatexdvpP(s_T|s_1,...,s_{T-1})finkitxmlcodeinlinelatexdvp. Pour pouvoir estimer kitxmlcodeinlinelatexdvpP(occ_i^T)finkitxmlcodeinlinelatexdvp, nous allons utiliser le fait que la valeur d'occupation est binaire. Nous commençons par calculer la probabilité que la cellule soit vide kitxmlcodeinlinelatexdvpP (\bar{occ}_i^T)finkitxmlcodeinlinelatexdvp, ce qui se fait de la même manière :

kitxmlcodelatexdvpP(\bar{occ}_i^T)=\frac{P(\bar{occ}_i|s_T)P(s_T)}{P(\bar{occ}_i)}\frac{P(\bar{occ}_i^{T-1})}{P(s_T|s_1,...,s_{T-1})}finkitxmlcodelatexdvp

et nous permet en utilisant le rapport des deux valeurs, de se débarrasser des termes gênants.

kitxmlcodelatexdvp\frac{P(occ_i^T)}{P(\bar{occ}_i^T)}=\frac{P(occ_i|s_T)}{P(\bar{occ}_i|s_T)}\frac{P(\bar{occ}_i^{T-1})}{P(occ_i^{T-1})}\frac{P(\bar{occ}_i)}{P(occ_i)}finkitxmlcodelatexdvp

et en utilisant le fait que kitxmlcodeinlinelatexdvpP(\bar{occ}_i)=1-P(occ_i)finkitxmlcodeinlinelatexdvp, nous obtenons :

kitxmlcodelatexdvp\frac{P(occ_i^T)}{1-P(occ_i^T)}=\frac{P(occ_i|s_T)}{1- P(occ_i|s_T)}\frac{1-P(occ_i^{T-1})}{P(occ_i^{T-1})}\frac{1-P(occ_i)}{P(occ_i)}finkitxmlcodelatexdvp

il est alors possible d'extirper kitxmlcodeinlinelatexdvpP(occ_i^T)finkitxmlcodeinlinelatexdvp de cette expression, mais il est plus simple de chercher à estimer directement la valeur kitxmlcodeinlinelatexdvpl_ifinkitxmlcodeinlinelatexdvp définie par :

kitxmlcodelatexdvpl_i^T = log\left(\frac{P(occ_i^T)}{1-P(occ_i^T)}\right)finkitxmlcodelatexdvp

qui se calcule simplement par :

kitxmlcodelatexdvpl_i^T = log\left(\frac{P(occ_i|s_T)}{1- P(occ_i|s_T)}\right)+log\left(\frac{1-P(occ_i)}{P(occ_i)}\right)+l_i^{T-1}\quad(11.1)finkitxmlcodelatexdvp

Ceci nous fournit une règle simple de mise à jour incrémentale des valeurs kitxmlcodeinlinelatexdvpl_i^Tfinkitxmlcodeinlinelatexdvp en fonction des valeurs précédentes et du modèle de capteur. La valeur kitxmlcodeinlinelatexdvpP(occ_i)finkitxmlcodeinlinelatexdvp est une valeur initiale de la probabilité d'occupation. Elle est en général choisie égale à 0,5 mais peut être plus faible ou plus forte si l'on souhaite intégrer un a priori sur le fait que l'environnement contient une densité plus ou moins grande d'obstacles. On retrouve ensuite la probabilité d'occupation par : kitxmlcodeinlinelatexdvpp(occ_i^T) = 1-1/e^{l_i^T}finkitxmlcodeinlinelatexdvp

Il existe également des moyens plus simples de mise à jour des grilles, qui consistent simplement à estimer la probabilité d'occupation d'une cellule en fonction du nombre de perceptions de cette cellule qui ont eu lieu. Ainsi, si on note kitxmlcodeinlinelatexdvpocc(x,y)finkitxmlcodeinlinelatexdvp le nombre de fois où un obstacle a été détecté dans cette cellule et kitxmlcodeinlinelatexdvpvide(x,y)finkitxmlcodeinlinelatexdvp le nombre de fois où cette cellule est apparue vide, car le faisceau du télémètre a traversé cette cellule, on peut simplement estimer la probabilité par :

kitxmlcodelatexdvpP_{occ}(x,y) = \frac{occ(x,y)}{vide(x,y)+occ(x,y)}finkitxmlcodelatexdvp

Une variante encore plus simple pour créer une grille d'occupation est une mise à jour utilisant un simple décompte dans lequel on ajoute une certaine valeur fixe à la probabilité d'occupation d'une cellule si un obstacle y est détecté et on retranche une autre valeur fixe si la cellule a été traversée par le faisceau [78] (voir aussi la section II.B.2Méthode Vector Field Histogram). Cette méthode, nommée « histogrammic in motion mapping (HIMM) » présente cependant l'inconvénient de ne pas converger vers une valeur fixe lorsque le nombre de perceptions d'une cellule tend vers l'infini. Elle est de plus relativement sensible au bruit et suppose des réglages délicats de paramètres pour être adaptée à un robot spécifique.

Pour limiter les erreurs de cartographie dans ce type de méthodes, il est possible d'utiliser une exploration active de l'environnement, plutôt que de passivement mémoriser les données recueillies par le robot. Dans le cadre des cartes topologiques, il est par exemple possible, lorsqu'un nœud a été reconnu, de chercher à atteindre un des nœuds voisins mémorisés dans la carte [82]. Si ce second nœud est correctement détecté, il permet de confirmer la détection du nœud précédent qui est alors mis à jour. D'autres modèles utilisent une exploration active de l'environnement pour diriger le robot vers les zones pour lesquelles l'incertitude de la carte est grande dans le but de la réduire [42]. Enfin certains modèles sont capables de générer des hypothèses sur des portions non visitées de l'environnement qui sont ensuite vérifiées grâce à une procédure qui dirigera le robot dans les zones où de telles hypothèses ont été faites [83]. Des stratégies d'explorations peuvent également être utilisées afin de garantir une exploration rapide et exhaustive de l'environnement [131, 83, 147].

D'une manière générale, de telles procédures permettent donc, d'une part, de limiter les erreurs de cartographie en insistant sur les zones incertaines et en évitant que l'estimation de la position ne devienne trop mauvaise et, d'autre part, de garantir une exploration exhaustive de l'environnement.

Une première méthode pour prendre en compte la nouvelle information de position est de propager l'erreur tout le long du cycle parcouru par le robot. Cette méthode peut s'appliquer à des cartes topologiques ou à des cartes de scans (voir section III.D.2.bCartes métriques : corrélation de scan). Intuitivement, cela correspond à identifier la carte à un réseau de ressorts, dont les positions au repos correspondent aux positions relatives des nœuds (Figure 11.6). L'erreur lors de la fermeture de boucle correspond alors à un déséquilibre dans ce réseau de ressort. Pour obtenir une carte globalement cohérente et qui respecte au mieux les positions relatives des nœuds, il suffit de calculer la position de repos du réseau de ressorts (d’où le terme de méthode de relaxation).

Il existe différents algorithmes de relaxation. Nous présentons ici un algorithme itératif très simple qui donne de bons résultats [35, 2]. Le principe de cet algorithme est de calculer la position de chaque nœud à partir de celle de ses voisins itérativement jusqu'à convergence des positions (Figure 11.7). Ainsi pour chaque nœud kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp, les trois étapes suivantes sont appliquées :

• Estimation de la position du nœud kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp depuis chaque voisin kitxmlcodeinlinelatexdvpjfinkitxmlcodeinlinelatexdvp:
  kitxmlcodeinlinelatexdvp\begin{eqnarray} (x'_{i})_j &= & x_j + d_{ji}\cos(\theta_{ji}+\theta_j)&\quad(11.2)\\ (y'_{i})_j &= & y_j + d_{ji} \sin(\theta_{ji}+\theta_j)&\quad(11.3)\\ (\theta'_{i})_j &= & \theta_j + \varphi_{ji}&\quad(11.4) \end{eqnarray}finkitxmlcodeinlinelatexdvp
  et estimation de la variance du nœud kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp depuis le nœud kitxmlcodeinlinelatexdvpjfinkitxmlcodeinlinelatexdvp:
  kitxmlcodeinlinelatexdvp(v'_{i})_j=v_j+v_{ji}finkitxmlcodeinlinelatexdvp
• Estimation de la variance du nœud kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp par la moyenne harmonique des estimations depuis les voisins :
  kitxmlcodeinlinelatexdvp\begin{eqnarray} v_{i} &= & \frac{n_i}{ \sum_j \frac{1}{(v'_{i})_j}}&\quad(11.5)\\ &&&\quad(11.6) \end{eqnarray}finkitxmlcodeinlinelatexdvp
  où kitxmlcodeinlinelatexdvpn_ifinkitxmlcodeinlinelatexdvp est le nombre de voisins du nœud kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp.
• Estimation de la position du nœud comme la moyenne pondérée des estimations depuis ses voisins :
  kitxmlcodeinlinelatexdvp\begin{eqnarray} x_{i} &= & \frac{1}{n_i} \sum_j \frac{(x'_{i})_jv_i}{(v'_{i})_j}&\quad(11.7) \\ y_{i} &= & \frac{1}{n_i} \sum_j \frac{(y'_{i})_jv_i}{(v'_{i})_j}&\quad(11.8) \\ \theta_{i} &= & \arctan \left( \frac{ \sum_j{\frac{\sin((\theta'_{i})_j)}{(v'_{i})_j}}}{ \sum_j{\frac{\cos((\theta'_{i})_j)}{(v'_{i})_j}}} \right)&\quad(11.9) \\ &&&\quad(11.10) \end{eqnarray}finkitxmlcodeinlinelatexdvp

La Figure 11.8 montre un exemple de l'application de cet algorithme à une carte topométrique. Les nœuds entourés montrent les fermetures de boucle, c'est-à-dire les retours détectés à une position précédente qui sont utilisés pour contraindre le graphe.

Cet algorithme donne de bons résultats, mais peut être assez lent à converger. En effet, si l'on applique la mise à jour à tous les nœuds dans un ordre fixe (l'ordre de création des nœuds par exemple), l'erreur qui est localisée sur une seule arête au départ ne sera propagée que sur un voisin supplémentaire à chaque tour. Pour accélérer la convergence, il est possible de simplement réordonner la mise à jour des nœuds afin que l'erreur se diffuse plus rapidement.

C'est ce que propose par exemple l'algorithme TORO (Tree-based netwORk Optimizer) [61] qui construit un arbre associé au graphe de la carte pour déterminer un ordre optimal de mise à jour. Cet arbre est construit simplement en ajoutant chaque nouveau nœud comme fils du plus ancien de ses voisins (Figure 11.9). La méthode de mise à jour de la position des nœuds est ensuite appliquée dans l'ordre donné par le parcours descendant de l'arbre. Ainsi dans l'exemple de la Figure 11.9, l'erreur(13) initialement concentrée sur l'arête entre les nœuds 1 et 9 sera propagée lors du premier parcours de la carte aux nœuds 9 et 2, puis 3, 4, 7. Avec une mise à jour dans l'ordre de création des nœuds, la propagation aurait simplement été faite aux nœuds 2, 3, 4… La première mise à jour n'aurait donc modifié que la position du nœud 9 et aurait été nulle pour les autres.

Le filtrage de Kalman étendu (section III.C.3.cFiltrage de Kalman pour la localisation) peut aussi être utilisé pour la cartographie. C'est cette méthode qui était à l'origine présentée sous le terme SLAM [129, 91]. Le terme SLAM est depuis devenu plus générique et la cartographie par filtrage de Kalman étendu se retrouve souvent sous le nom « EKF SLAM ».

Le filtrage est ici utilisé non seulement pour estimer la position du robot, mais aussi pour estimer la position des différents éléments enregistrés dans la carte. Cette méthode est en général utilisée avec des cartes représentant l'environnement sous forme d'objets géométriques simples tels que des points ou des segments. Elle va permettre d'utiliser les relations mesurées entre le robot et ces objets pour estimer leurs différentes positions.

Plus généralement, l'idée est donc d'utiliser un filtrage bayésien estimant à la fois les positions du robot (kitxmlcodeinlinelatexdvpx_tfinkitxmlcodeinlinelatexdvp) et des objets de la carte (kitxmlcodeinlinelatexdvpc_tfinkitxmlcodeinlinelatexdvp):

kitxmlcodelatexdvpBel(x_t,c_t) = \eta p(y_t|x_t,c_t) \int \int p(x_t,c_t|x_{t-1},c_{t-1},u_{t-1})Bel(x_{t-1},c_{t-1}) dx_{t-1} dc_{t-1}finkitxmlcodelatexdvp

Cette équation peut être simplifiée en utilisant l'hypothèse de monde statique, qui est utilisée dans la plupart des modèles, et qui entraîne donc que la carte de l'environnement reste la même au cours du temps (kitxmlcodeinlinelatexdvpc_t = c_{t-1}finkitxmlcodeinlinelatexdvp). Il faut bien distinguer cette hypothèse du fait que notre estimation de la probabilité des différentes cartes (kitxmlcodeinlinelatexdvpBel(x_t,c_t)finkitxmlcodeinlinelatexdvp) évolue au cours du temps, et donc que la carte que nous supposons représenter l'environnement (la plus probable en général) change au cours du temps. En utilisant cette hypothèse, l'équation du filtrage devient alors :

kitxmlcodelatexdvpBel(x_t,c_t) = \eta p(y_t|x_t,c_t) \int \int p(x_t|x_{t-1},u_{t-1})Bel(x_{t-1},c_{t-1}) dx_{t-1} dc_{t-1}finkitxmlcodelatexdvp

Comme pour la localisation, ce filtrage peut être implémenté de différentes manières, par exemple en utilisant un filtre de Kalman ou un filtrage particulaire (voir section suivante). Il peut également être utilisé avec différentes formes de cartes, qui rendent son implantation plus ou moins aisée. La technique communément nommée EKF SLAM consiste en l'implantation de ce filtrage sous la forme d'un filtre de Kalman étendu, en utilisant une carte contenant des amers qui peuvent être des points ou des segments. C'est historiquement la première implantation de ce type de cartographie [129].

Détaillons à titre d'exemple une implantation de cette méthode utilisant une carte contenant des amers ponctuels. Dans un état où la carte contient N amers, on utilise un vecteur d'état contenant la position du robot et des différents amers. Le vecteur d'état est donc de dimension 2N+3 :

kitxmlcodelatexdvpBel(x_t,c_t)=\left[ \begin{array}{c} x \\ y \\ \theta\\ x_{a1} \\ y_{a1} \\ \vdots \\ x_{aN} \\ y_{aN} \\ \end{array} \right]finkitxmlcodelatexdvp

La matrice de covariance associée permet de mémoriser les relations qui ont été perçues entre les amers et entre les amers et le robot. C'est l'utilisation de ces covariances lors de la mise à jour qui permettra un retour sur les modifications passées au sens où elle permettra de propager toute nouvelle information de position du robot vers les éléments dont la position relative avec le robot est connue (c.-à-d. les éléments avec lesquels la covariance est non nulle).

Supposons que l'on commande les vitesses de rotation et de translation du robot kitxmlcodeinlinelatexdvpu=(v,\omega)finkitxmlcodeinlinelatexdvp, l'équation d'évolution ne modifiera que la position du robot et sera alors :

kitxmlcodelatexdvpf(X_t,u)=\left[ \begin{array}{c} x+ v.dt.cos(\theta)\\ y+v.dt.sin(\theta)\\ \theta+\omega.dt \\ x_{a1} \\ y_{a1} \\ \vdots \\ x_{aN} \\ y_{aN} \\ \end{array}\right]finkitxmlcodelatexdvp

Ce qui donne la matrice jacobienne :

kitxmlcodelatexdvpA=\left[ \begin{array}{cccccc} 1 & 0 & -sin(\theta) & 0 & \dots & 0\\ 0 & 1 & cos(\theta)& 0 & \dots & 0\\ 0 & 0 & 1 & 0 & \dots & 0 \\ 0 & \dots &\dots &\dots & \dots & 0 \\ \vdots & \vdots &\vdots &\vdots & \vdots & \vdots\\ 0 & \dots &\dots &\dots & \dots & 0\\ \end{array}\right]finkitxmlcodelatexdvp

enfin si l'on suppose que lors de la perception de l'amer kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp, on mesure sa position relative dans le repère lié au robot en coordonnées polaires (kitxmlcodeinlinelatexdvpr_i,\phi_ifinkitxmlcodeinlinelatexdvp), l'équation d'observation sera :

kitxmlcodelatexdvph_i(X_t) = \left[ \begin{array}{c} \sqrt{(x-x_{ai})^2+(y-y_{ai})^2}\\ atan2(\frac{y_{ai}-y}{x_{ai}-x})-\theta \end{array}\right]finkitxmlcodelatexdvp

la matrice jacobienne de l'équation d'observation s'écrira alors :

kitxmlcodelatexdvpH_i=\left[ \begin{array}{ccc} \frac{(x-x_{ai})}{\sqrt{(x-x_{ai})^2+(y-y_{ai})^2}} & \frac{(y-y_{ai})}{\sqrt{(x-x_{ai})^2+(y-y_{ai})^2}} & 0 \\ \frac{(y-y_{ai})}{(x-x_{ai})^2+(y-y_{ai})^2} & - \frac{(x-x_{ai})}{(x-x_{ai})^2+(y-y_{ai})^2} & -1 \end{array} \right]finkitxmlcodelatexdvp

Pour estimer à la fois la position des amers et du robot, il suffira alors de dérouler les équations du filtrage de Kalman étendu :

• Prédiction de l'état :
  kitxmlcodeinlinelatexdvp\begin{equation} X_{t}^* = f(\hat{X}_{t-1},u_t)\quad(11.11) \end{equation}finkitxmlcodeinlinelatexdvp
  et de la covariance:
  kitxmlcodeinlinelatexdvp\begin{equation} P_t^* = A.\hat{P}_{t-1}.A^T+Q\quad(11.12) \end{equation}finkitxmlcodeinlinelatexdvp
• Prédiction de l'observation :
  kitxmlcodeinlinelatexdvp\begin{equation} Y_t^*=h(X_t^*)\quad(11.13) \end{equation}finkitxmlcodeinlinelatexdvp
• Observation : on obtient une mesure kitxmlcodeinlinelatexdvpYfinkitxmlcodeinlinelatexdvp, dont on estime le bruit kitxmlcodeinlinelatexdvpP_Yfinkitxmlcodeinlinelatexdvp grâce au modèle du processus de perception.
• Correction de l'état prédit:
  kitxmlcodeinlinelatexdvp\hat{X}_t = X_t^* + K(Y - Y_t^*)\quad(11.14)finkitxmlcodeinlinelatexdvp kitxmlcodeinlinelatexdvp\hat{P}_t = P_t^* - KHP_t^*\quad(11.15)finkitxmlcodeinlinelatexdvp
  où kitxmlcodeinlinelatexdvpKfinkitxmlcodeinlinelatexdvp est le gain de Kalman:
  kitxmlcodeinlinelatexdvp\begin{equation} K = P_t^* H^T.(H.P_t^*.H^T + P_Y)^{-1}\quad(11.16) \end{equation}finkitxmlcodeinlinelatexdvp

Cette mise à jour suppose que l'amer perçu soit déjà dans la carte et donc dans le vecteur d'état. Si l'amer détecté par le robot n'est pas dans la carte, il est simplement ajouté à la fin du vecteur d'état et toutes les matrices sont agrandies de deux lignes (et éventuellement colonnes) correspondantes.

Il reste un problème important dans la méthode décrite, car elle suppose que l'on soit capable d'identifier les amers, c'est-à-dire de savoir à quel amer kitxmlcodeinlinelatexdvpifinkitxmlcodeinlinelatexdvp correspond un amer perçu. Or, en utilisant de simples points ou segments de droite, cela se révèle difficile à cause du très fort perceptual aliasing. Comme pour la localisation, il y a deux méthodes possibles pour résoudre ce problème. La première est de particulariser chaque amer, par exemple en utilisant une image de l'environnement autour de l'amer afin de pouvoir l'identifier individuellement. Cette méthode est rarement suffisante, car avec l'augmentation de la taille de l'environnement on retombe en général sur le problème de perceptual aliasing. La seconde solution repose sur des amers indistinguables et sélectionne l'amer correct en se basant sur sa position estimée. Pour cela, on estime la position absolue de l'amer perçu à partir de la position estimée du robot, puis on considère qu'il correspond à l'amer de la carte dont la position est la plus proche. Cette mise en correspondance peut également utiliser une distance de Mahalanobis (voir section III.C.3.c.vApplication à la localisation avec perceptual aliasing), ou utiliser des critères supplémentaires qui caractérisent les amers. Si les amers sont des segments, par exemple, on peut chercher le segment le plus proche qui a la même direction que le segment perçu.

L'algorithme 11.2 décrit finalement le processus complet de cette méthode de cartographie. Cette méthode est également illustrée graphiquement dans la Figure 11.10.

La principale faiblesse de cette méthode réside dans la phase d'appariement qui peut entraîner une divergence de l'algorithme en cas d'erreur. En effet, dans ce cas, non seulement la position de l'amer apparié par erreur sera mal estimée, mais cette mauvaise estimation sera propagée aux autres amers, via la matrice des covariances, ainsi qu'à la position du robot. Cette mauvaise estimation de la position du robot produira par la suite de nouvelles erreurs d'appariement qui se succéderont et entraîneront la divergence complète de l'algorithme.

Un autre inconvénient est la complexité des calculs requis, qui augmente en kitxmlcodeinlinelatexdvpO(N^2)finkitxmlcodeinlinelatexdvp avec le nombre d'amers de la carte. Ceci est lié à la taille de la matrice de covariances qui est kitxmlcodeinlinelatexdvpN\times Nfinkitxmlcodeinlinelatexdvp. Or cette matrice mémorise les interrelations entre les positions des amers et du robot et est nécessaire à la bonne estimation de ces positions.

Pour réduire la complexité des calculs, il est cependant possible de réduire la taille de cette matrice en négligeant certaines interrelations entre amers. Ceci peut se faire par exemple en ne mémorisant les covariances qu'au sein de cartes locales, dont l'assemblage couvre l'ensemble de l'environnement. Diverses méthodes existent, utilisant différentes manières de découper la carte globale et de propager les informations entre cartes locales (par exemple [109]).

La méthode d'appariement des amers utilisée dans la méthode du SLAM EKF est à la source de la plupart des problèmes de cette méthode. Elle repose en effet sur l'hypothèse que l'estimation de la position du robot est approximativement correcte pour fournir un appariement correct. On peut donc remarquer que si la position du robot est parfaitement connue, le problème se simplifie énormément, car la mise en correspondance ne pose plus de problème et il reste simplement à estimer correctement la position des amers, ce qui est relativement trivial (sous l'hypothèse de la connaissance de la position du robot).

Cette remarque a inspiré la méthode de cartographie nommée Fast SLAM [100, 70, 60]. Dans cette méthode, on mémorise un grand nombre de trajectoires possibles, dont on évalue la probabilité, et pour ces trajectoires, on construit simplement la carte à partir des perceptions. Cet ensemble de trajectoires correspond en fait à un échantillonnage de la distribution de probabilités sur ces trajectoires au moyen d'un filtre particulaire. Pour la construction de la carte à partir de l'une de ces trajectoires, on utilise le filtrage de Kalman, mais dans des conditions beaucoup plus favorables. En effet, comme la trajectoire est connue, les perceptions successives des différents amers deviennent indépendantes et il n'est plus nécessaire de mémoriser l'ensemble des covariances, mais seulement les variances des amers individuels. On passe ainsi d'une complexité en kitxmlcodeinlinelatexdvpO(N^2)finkitxmlcodeinlinelatexdvp à une complexité en kitxmlcodeinlinelatexdvpO(N)finkitxmlcodeinlinelatexdvp pour la partie filtrage de Kalman. Il faut cependant y ajouter la complexité du filtrage particulaire sur les trajectoires, mais globalement, l'algorithme est plus stable et moins gourmand en calculs que le SLAM original.

Cette méthode de séparation du problème de SLAM et un filtre particulaire pour la partie non gaussienne et en un filtre de Kalman pour une partie du sous-problème est une méthode très générale connue sous le nom de Rao-Blackwellisation du filtre.

La force de ces méthodes est surtout apparente lors de la fermeture de grands cycles. En effet, avant la fermeture, un grand nombre de trajectoires différentes sont mémorisées, ce qui permet d'avoir une forte probabilité que l'une d'elles corresponde à la trajectoire précise du cycle. Après la fermeture du cycle, le rééchantillonnage du filtre particulaire sélectionne naturellement les trajectoires correctes et permet ainsi une cartographie correcte du cycle (Figure 11.11). Ce rééchantillonnage entraîne cependant une forte perte d'informations, puisque la plupart des trajectoires estimées avant la fermeture de boucle sont ignorées (c'est le problème classique de raréfaction des particules des méthodes de filtrage particulaire, voir section III.C.4.dFiltrage particulaire). Cette perte d'informations devient problématique dans des environnements contenant plusieurs cycles, notamment dans le cas de cycles imbriqués.

Une méthode de cartographie très similaire au FastSLAM permet de construire une carte métrique directement à partir des données laser [70]. Elle n'utilise pas de filtre de Kalman, mais repose sur un échantillonnage des trajectoires possibles par un filtre particulaire et sur un algorithme rapide de corrélation de scans pour l'évaluation des probabilités des trajectoires. Cette méthode permet de construire de très grandes cartes contenant plusieurs cycles (Figure 11.12).

Le premier type de plan qui peut être généré contient une suite d'actions à effectuer par le robot, ou une suite de points à atteindre afin de rejoindre le but. Les algorithmes classiques de recherche dans les graphes, tels que l'algorithme de Dijkstra, kitxmlcodeinlinelatexdvpA^\starfinkitxmlcodeinlinelatexdvp, ou l'une de leurs nombreuses variantes, peuvent être utilisés pour calculer ce type de plan [93, 79, 81, 120, 106, 5, 38]. La taille raisonnable des cartes topologiques classiquement utilisées en robotique rend ces algorithmes suffisamment efficaces en pratique. Ce type de plan pose toutefois des problèmes lors de son exécution si le robot ne parvient pas à atteindre l'un des points du chemin calculé, ou s'il s'éloigne de la trajectoire et que sa position correspond à un nœud qui ne fait pas partie du chemin planifié. La solution à ces problèmes est alors de recommencer le processus de planification en prenant en compte la nouvelle position de départ (ce qui peut même se produire indéfiniment en cas de problème). Ce processus de replanification est souvent inutilement coûteux en calculs, car un grand nombre des opérations nécessaires auront déjà été effectuées lors de la planification précédente.

Un second type de plan peut être utilisé, qui associe à chacune des positions possibles du robot au sein de la carte l'action qu'il doit effectuer pour atteindre son but. Ce type de plan est appelé politique (comme pour l'apprentissage par renforcement, section II.CApprentissage par renforcement) ou plan universel [121]. Le résultat est alors une stratégie de déplacement similaire à la stratégie d'action associée à un lieu mentionnée dans la section I.A.1Stratégies de navigation. L'enchaînement de reconnaissances de positions et de réalisations des actions associées à ces positions permet donc de générer une route joignant le but. Ce type de plan présente l'avantage de permettre au robot d'atteindre le but, aussi longtemps qu'il possède une estimation correcte de sa position. En effet, le chemin précis rejoignant le but n'est pas spécifié et le robot peut donc s'écarter du chemin direct entre la position initiale et le but sans entraîner de replanification.

Une politique est plus lourde à calculer que les plans du type précédent, car toutes les positions de la carte doivent être envisagées, sans utiliser les heuristiques des algorithmes précédents qui permettent de restreindre l'exploration de l'espace de recherche. Toutefois, cette augmentation est rapidement compensée si le robot s'écarte du chemin direct vers le but. Dans ce cas, en effet, la planification doit être reprise pour le premier type de plan, alors que c'est inutile pour une politique. Le calcul d'une politique reste donc en général praticable pour les cartes de taille limitée typiques de la robotique mobile.

Pour calculer une telle politique, une simple recherche en largeur dans le graphe en partant du but peut être utilisée. Cette méthode se retrouve sous le nom de breadth first search, spreading activation [98, 10] ou wavefront propagation [104]. Ces deux derniers noms viennent de l'analogie entre l'ordre de parcours du graphe et la manière dont un fluide progresserait s'il s'échappait du but pour se répandre dans le graphe.

Plutôt que d'associer directement une action à chaque état, le calcul d'une politique passe souvent par le calcul d'un potentiel associé à chaque état qui augmente en fonction de la distance nécessaire pour atteindre le but depuis l'état courant. À partir de ce potentiel, il est alors très simple de retrouver les actions à effectuer par une simple descente de gradient.

Pour calculer ce potentiel, des coûts élémentaires sont associés à chaque nœud et à chaque lien entre les nœuds. Les coûts associés aux liens traduisent en général la distance entre nœuds, tandis que les coûts associés aux nœuds permettent de marquer des zones à éviter ou à favoriser pour les trajectoires du robot.

La méthode la plus simple pour calculer le potentiel est l'algorithme de Dijkstra (12.1), qui, partant du but fait à chaque étape la mise à jour du nœud suivant de potentiel le plus faible. Cet algorithme suppose que tous les coûts utilisés sont positifs ou nuls.

Une seconde méthode pour calculer ces potentiels lorsque certains coûts sont négatifs est l'utilisation de l'algorithme de programmation dynamique de Bellman-Ford (12.2), aussi connu sous le nom de value iteration, notamment en apprentissage par renforcement [22, 131, 23]. Une itération de cet algorithme utilise quasiment la même méthode de mise a jour que l'algorithme de Dijkstra, mais sans utiliser le même ordre dans les mises à jour des nœuds. En présence de coûts négatifs, cette itération doit être répétée autant de fois qu'il y a de nœuds pour garantir la convergence. De plus il peut arriver qu'un cycle du graphe ait un poids total négatif, ce qui ne permet pas de trouver de chemin de coût minimal. L'algorithme retourne FAUX dans ce cas.

La Figure 12.5 permet de comparer l'ordre des mises à jour des valeurs de potentiels pour l'algorithme de Dijkstra et pour Value Iteration, qui aboutissent au même résultat.

Si l'on ne souhaite que calculer un chemin, il est par exemple possible d'employer l'algorithme kitxmlcodeinlinelatexdvpA^\starfinkitxmlcodeinlinelatexdvp. Cet algorithme utilise exactement le même mécanisme que l'algorithme de Dijkstra, mais utilise une heuristique pour choisir le nœud suivant à explorer au lieu d'explorer systématiquement les nœuds voisins des nœuds déjà planifiés. Cette heuristique doit fournir une évaluation la plus rapide possible de la distance entre le nœud courant et le but (par exemple simplement la distance euclidienne en supposant qu'il n'y a pas d'obstacle). La mise en place d'une bonne heuristique assure de trouver très rapidement un chemin vers le but, mais ne garantit pas forcément l'optimalité (ce qui n'est souvent pas très important en pratique).