Archives 2007 2006 2005 2004 2003 2002 2001 2000 1999 En guise d'introduction

17 juin 2002, par Jean-Paul Baquiast

Simultaneous Location and Mapping - Positionnement et cartographie simultanés
NB : on dit aussi CML, Concurrent Mapping and Localization

Comment un robot peut-il se déplacer seul dans un environnement inconnu (non cartographié) en étant toujours certain de sa position ? Le problème est crucial pour la réalisation de robots pleinement autonomes, c'est-à-dire ne disposant pas d'aides extérieures : des cartes déjà élaborées, un positionnement certain (notamment par GPS - Global Positioning System) ou, à défaut, une commande à distance assurée par un humain ? On conçoit qu'il n'est pas question d'envisager l'utilisation de robots n'ayant pas cette faculté quand il s'agira d'explorer des lieux non cartographiés (un immeuble détruit par un séisme, la planète Mars) et où le GPS n'est pas accessible (l'intérieur d'un immeuble ne permettant pas la visibilité des satellites du GPS ou… à nouveau la planète Mars).

Du temps des Vikings et des grandes migrations maoris

Le problème n'est pas nouveau. Il s'est posé aux hommes dès les premiers temps de la navigation maritime. Prenons le cas d'un explorateur marin primitif souhaitant se lancer à la découverte de terres inconnues, en évitant de se perdre complètement dans la mer des ténèbres. De quels instruments dispose-t-il? Il connaît depuis la nuit des temps le loch ou autres techniques archaïques de même nature qui lui donnent approximativement la distance parcourue. Il utilise aussi le repérage sur les étoiles ou sur les vents réguliers pour obtenir le cap suivi. Par contre la sonde mesurant la profondeur n'a pas d'intérêt pour lui hors des plate-formes continentales. Rappelons que la boussole n'a été inventée que tardivement dans l'histoire de la navigation. Elle permet de repérer le cap suivi par rapport au Nord magnétique, mais elle n'est pas utilisable dans des environnements planétaires ne disposant pas de champs magnétiques analogues au nôtre.

Dès les origines, l'art du marin ne disposant pas de méthodes sophistiquées de navigation consiste à naviguer à l'estime (dead reckoning) en corrigeant du mieux possible les innombrables erreurs provenant de l'imprécision du suivi de la route.

Mais l'estime n'a de véritable intérêt que si le marin dispose d'une carte où reporter sa position estimée. Or, par définition, l'explorateur d'un océan inconnu n'a pas de carte. Il lui faut donc en construire une, pour son usage propre et celui de ses successeurs. La méthode traditionnelle consistait à naviguer droit devant soi jusqu'à rencontrer une terre, dont on reportait sur un parchemin la position estimée en cap et en distance (tant de jours de mer ou de milles nautiques dans telle direction). A partir de l'acquisition de ce premier point, on pouvait répéter l'opération pour dessiner les contours du territoire découvert. On pouvait aussi, à partir du port de départ, procéder à des explorations identiques dans d'autres directions, afin d'élargir le champ des terres nouvelles recherchées. Les anciennes cartes comportaient donc des vecteurs qui donnaient aux pilotes l'information approximative que naviguant dans telles directions pendant tel nombre de jours, ils rencontreraient telles terres, iles ou caps de préférence. Avant ces cartes, qui sont apparues semble-t-il au 12e ou 13e siècle, les routes se transmettaient par tradition orale au sein de la corporation très valorisée des maîtres-pilotes océaniques.

L'invention de la boussole puis de la navigation astronomique (repérage précis sur les astres) a permis de préciser simultanément le point et les cartes obtenues grâce à lui, mais n'a en rien dispensé le navigateur de tenir une estime correcte afin de se situer sur ces cartes. Mais tout ceci est dorénavant considéré comme inutile par les marins des pavillons de complaisance, qui se fient entièrement à l'actuel GPS américain, en attendant le futur Galiléo européen (sauf à se trouver en perdition en cas de panne de l'électronique). Le navigateur dispose en effet maintenant à la fois de cartes où les côtes sont identifiés par leurs relèvements GPS et de leur position en temps réel à la dizaine de mètres près.

Le robot navigateur

De quoi un robot explorateur autonome a-t-il besoin pour acquérir une expérience de la navigation analogue à celle ayant permis les grandes explorations maritimes de l'antiquité ? Il doit simultanément construire la carte du milieu dans lequel il se déplace et se situer avec précision sur cette carte. Sinon il est condamné à errer au hasard, sans pouvoir acquérir ou retransmettre d'informations utiles, ni sur lui ni sur le territoire qu'il explore. La première fonction à acquérir vise à mesurer le chemin parcouru (le loch). C'est relativement facile pour un robot terrestre dont on peut compter les tours de roues (sauf erreurs dues aux patinages et autres incidents de parcours). C'est plus difficile pour les robots se déplaçant en milieu liquide ou aérien, mais il existe des techniques de plus en plus fiables permettant le positionnement par inertie. Des algorithmes de correction de l'estime d'une grande complexité sont cependant nécessaires pour tenir compte des dérives et imprécisions diverses.

La deuxième fonction à acquérir vise à identifier les caractéristiques du milieu afin d'en construire une image en 3 dimensions cohérente. Les robots modernes disposent déjà de systèmes de reconnaissance des formes, volumes et couleurs qui commencent à être utilisables sans intervention correctrice permanente d'un observateur humain. Mais là encore beaucoup de progrès restent à faire dans l'identification des détails et la construction du cadre d'ensemble.

Si cependant les roboticiens peuvent recourir à des méthodes relativement fiables permettant la navigation à l'estime et la cartographie, comment combiner les deux ? C'est là l'objectif de la nouvelle stratégie de recherche dite SLAM, qui fut entreprise au début des années 1990. Il s'agit de reprendre en la transposant la technique du Viking Eric le Rouge décrite ci-dessus. Le robot dans cette technique décrit les objets de son environnement tels qu'il les perçoit par ses capteurs, afin d'en faire  les points remarquables d'une carte. Il utilise ses propres trajectoires estimées comme références en cap et distance à partir de son point de départ, pour positionner ces objets sur ladite carte. Evidemment, comme ce fut d'ailleurs la cas chez les premiers navigateurs dont un grand nombre se perdit en mer suite à l'accumulation des erreurs de détail, il faut que l'informatique du robot lui permette de corriger les différentes informations qu'il capte afin de les rendre cohérentes entre elles (self consistent). Les mesures ne visent évidemment pas à la perfection mais font appel aux probabilités pour donner des résultats acceptables

Les premiers robots explorateurs autonomes

Un article de NewScientist (Unchartered territory, 31 mai 2003, p. 38) expose toute cette problématique et cite les principaux projets concurrents permettant de progresser dans la direction du SLAM. Mentionnons ici, parmi de nombreuses autres références que l'on trouvera sur le web :

les drones australiens de Durrant-Whyte et ses collègues (sur les travaux de ceux-ci, voir http://www.acfr.usyd.edu.au/publications/downloads/2002/... le B21, robot à roues, de John Leonard au MIT (voir John Leonard Home page http://oe.mit.edu/~jleonard/)
- la carte en 3D d'une mine de charbon en Pennsylvanie, réalisée sous la direction de Sebastian Thrun à Carnegie Mellon. Le robot est baptisé Groundhog. (Sur ce projet, voir http://www.cmu.edu/PR/releases03/030530_autonomous.html.
Sur S. Thrun, voir http://www.ri.cmu.edu/people/thrun_sebastian.html)
Voir aussi de Zunino et Christensen http://voronoi.sbp.ri.cmu.edu/papers/00928558.pdf

L'avenir est désormais dégagé et on peut pronostiquer le temps où des flottes de robots pratiquant de façon coopérative le positionnement et la cartographie simultanées exploreront les planètes voisines et nous en fourniront des cartes précises.