Les voitures autonomes et la localisation
Dans une voiture autonome, les GPS (Global Positioning System) permettent par trilatération de situer notre position.
Dans ces mesures, il peut y avoir une erreur allant de 1 à 10 mètres. Cette erreur est trop importante et peut potentiellement être fatale pour les passagers ou l’environnement du véhicule autonome. Nous incluons donc une étape appelée localisation.
La localisation est l’implémentation d’algorithmes pour estimer où est notre véhicule avec une erreur de moins de 10 cm.
Cet article fait suite aux articles l’IA…Et le véhicule fut autonome et La fusion de capteurs.
La localisation est une étape implémentée dans la majorité des robots et véhicules pour se localiser avec une marge d’erreur faible. Si nous voulons prendre des décisions comme dépasser un véhicule ou simplement définir un itinéraire, nous devons savoir ce qu’il y a autour de nous (fusion de capteurs) et où nous sommes (localisation). Ce n’est qu’avec ces informations que nous pourrons définir une trajectoire.
Comment se localiser précisément ?
Il existe beaucoup de techniques différentes pour aider un véhicule autonome à se localiser.
- Odométrie — La première technique, l’odométrie, utilise une position de départ et un calcul du déplacement des roues estimer une position à un instant t. Cette technique est généralement très peu précise et entraîne une accumulation d’erreurs due aux imprécisions de mesures, au glissement des roues, ...
- Filtre de Kalman — L’article précédent évoquait cette technique pour estimer l’état des véhicules autour de nous. Nous pouvons également implémenter cela pour définir l’état de notre propre véhicule.
- Filtre Particulaire — Les filtres bayésiens peuvent également avoir une variante appelée filtres particulaires. Cette technique compare les observations de nos capteurs avec la carte de l’environnement. Nous créons ensuite des particules autour des zones où les observations sont semblables à la carte.
- SLAM — Une technique très populaire si nous souhaitons également estimer la carte existe. On parle de SLAM (Simultaneous Localization And Mapping). Dans cette technique, nous estimons notre position mais également la position de points de repères. Un feu tricolore peut être un point de repère.
Capteurs
- Inertial Measurement Unit (IMU) ou centrale inertielle est un capteur capable de définir les déplacement du véhicule selon les axe yaw, pitch, roll. Ce capteur calcule les accélérations selon les axes X, Y, Z, l’orientation , l’inclinaison, et l’altitude.
- Global Positioning System (GPS) ou NAVSTAR sont le système américain pour le positionnement. En Europe, on parle de Galileo; en Russie, de GLONASS. Le terme GNSS (Global Navigation Satellite System) est un système de positionnement par satellites très fréquents aujourd’hui qui peut utiliser plusieurs de ces sous-systèmes pour augmenter la précision.
Termes
Nous introduirons plusieurs termes dans cet article :
- L’observation — Une observation peut être une mesure, une image, un angle…
- Le contrôle — Il s’agit ici de nos déplacements incluant nos vitesses et nos angles yaw, pitch, roll récupérés par l’IMU.
- La position du véhicule — Ce vecteur inclue les coordonnées (x,y) et l’orientation θ.
- La carte — Il s’agit ici de nos points de repères, routes… Il existe plusieurs cartes et des entreprises comme Here Technologies produisent des HD Maps, des cartes précises centimètre par centimètre. Ces cartes sont produites selon l’environnement où la voiture autonome pourra conduire.
Les filtres de Kalman
Expliqué dans l’article précédent, un filtre de Kalman peut estimer l’état d’un véhicule. Pour rappel, il s’agit de l’implémentation d’un filtre bayésien, avec une phase de prédiction et une phase de mise à jour / correction.
Notre première estimation est une repartition equitable sur toute la zone.
Nous avons ensuite une mesure nous indiquant que nous sommes situés près d’une porte. Notre distribution se modifie alors pour donner une probabilité plus forte aux zones situées près d’une porte.
Nous réalisons ensuite un déplacement, nos probabilités se décalent avec des incertitudes plus importantes.
Nous réalisons une nouvelle mesure, nous indiquant que nous sommes à nouveau près d’une porte.
La seule possibilité est donc d’être sur la porte du milieu.
Dans cet exemple d’un filtre de Kalman, nous avons pu nous localiser à l’aide de quelques mesures et d’une comparaison avec la carte. Il est essentiel de connaître la carte (incluant l’information seule la 1e porte a une porte adjacente) pour réaliser des déductions sur la localisation. Cette technique permet de ne pas utiliser de position initiale, ce qui est préférable à la technique utilisant l’odométrie.
Les filtres particulaires
Un filtre particulaire est une autre implémentation d’un filtre bayésien.
Dans un filtre particulaire, nous créons des particules dans toute la zone définie par le GPS et nous assignons à chaque particule un poids.
Le poids d’une particule représente la probabilité que notre véhicule soit à l’endroit de la particule.
A la différence du filtre de Kalman, nous n’avons pas de probabilité continue mais des valeurs discretes ayant chacune une probabilité ou poids.
Algorithme
L’implémentation de l’algorithme se fait selon le schéma suivant. Nous distinguons quatre étapes (Initialisation, Prédiction, Mise à jour, Echantillonage) se réalisant à l’aide de plusieurs données (GPS, données IMU, vitesses, mesures des points de repères).
- Initialisation — Nous utilisons une estimation initiale provenant du GPS et ajoutons du bruit (du à l’imprecision des capteurs) pour initialiser un nombre choisi de particules. Chaque particule a une position (x,y) et une orientation θ.
Cela nous donne une répartition des particules dans toute la zone GPS avec des poids égaux. - Prédiction — Une fois nos particules initialisées, nous réalisons une première prédiction prenant en compte notre vitesse et nos rotations. Dans toutes les prédictions, c’est nos déplacements qui seront pris en compte. Nous utilisons des équations décrivant x, y, θ (orientation) pour décrire le déplacement d’un véhicule.
- Mise à jour — Dans notre phase de correction, nous réalisons premièrement une correspondance entre nos mesures n et la carte m.
Nous utilisons les données de la fusion de capteurs pour déterminer objets environnants et mettons ensuite à jour nos poids avec l’équation suivante :
Dans cette équation, pour chaque particule :
- σx et σy sont nos incertitudes
- x et y sont les observations des points de repères
- μx et μy sont les vraies coordonnées des points de repères provenant de la carte.
Dans le cas où l’erreur est forte, le terme exponentiel vaut 0, le poids de notre particule est donc 0 également. Dans le cas où elle est très faible, le poids de la particule est 1 normalisé par le terme 2π.σx.σy.
- Echantillonage — Enfin, nous avons une dernière étape où nous sélectionnons les particules avec les poids les plus élevés et détruisons les moins probables.
Plus le poids est important, plus la particule a de chance de survivre.
Le cycle se repète ensuite avec les particules les plus probables, nous prenons en compte nos déplacements depuis le dernier calcul et réalisons une prédiction puis une correction selon nos observations.
Les filtres particulaires sont efficaces et permettent de localiser très précisément un véhicule. Pour chaque particule, nous comparons les mesures faites par la particule avec les mesures faites par le véhicule et calculons une probabilité ou poids. Ce calcul peut rendre le filtre lent si nous avons beaucoup de particules. Elle nécessite également d’avoir la carte de l’environnement où nous conduisons en permanence.
Résultat
Mes projets avec Udacity m’ont permis d’apprendre à implémenter un filtre particulaire en C++. Comme dans l’algorithme décrit plus tôt, nous implémentons la localisation en définissant 100 particules et en assignant un poids à chaque particule grâce aux mesures faites par nos capteurs.
Dans la vidéo suivante, nous pouvons voir :
- Un laser vert représentant les mesures provenant du véhicule.
- Un laser bleu représentant les mesures provenant de la particule la plus proche (cercle bleu).
- Une particule localisant le véhicule (cercle bleu).
- Les cercles noirs sont nos points de repères (feux tricolores, panneaux, buissons, …) provenant de la carte.
SLAM (Simultaneous Localization And Mapping)
Une autre méthode très populaire est appelée SLAM, cette technique permet d’estimer la carte (les coordonnées des points de repères) en plus d’estimer les coordonnées de notre véhicule.
Pour fonctionner, nous pouvons avec les Lidar trouver les murs, les trottoirs et ainsi construire une carte. Les algorithmes de SLAM ont besoin de savoir reconnaître les points de repères pour ensuite les positionner et ajouter des éléments à la carte.
Conclusion
La localisation est un sujet essentiel pour n’importe quel robot ou véhicule autonome. Si nous pouvons localiser notre véhicule très précisément, nous pouvons conduire de façon autonome. Ce sujet évolue en permanence, les capteurs deviennent de plus en plus précis et les algorithmes de plus en plus performants. Les techniques de SLAM sont très populaires pour la navigation en extérieur comme en intérieur où les GPS sont peu efficaces. La cartographie a également un rôle très important puisque sans carte, nous ne pouvons nous localiser.
Aujourd’hui, les recherches explorent la localisation à l’aide d’algorithmes de Deep Learning et de caméras.
Maintenant que nous sommes localisés et connaissons notre environnement, nous pouvons discuter des algorithmes de création de trajectoires et de prises de décisions !
Jeremy Cohen.
La suite sur la navigation autonome, le contrôle et l’intégration finale
