Filtres à particules

Un traitement plus technique de cet article de blog a été initialement publié sur le blog Udacity .

Les robots utilisent un algorithme étonnamment simple mais puissant pour savoir où ils se trouvent sur une carte, un problème appelé localisation par les ingénieurs. L'algorithme connu sous le nom de filtrage de particules a l'air incroyablement cool. La première partie de cet article en deux parties a été publiée ici . Dans ce premier article, nous allons élucider les mathématiques nécessaires pour construire vos propres filtres à particules.

Les voitures autonomes sont conçues pour se comporter comme des conducteurs humains. Un système de voiture autonome typique est composé de six composants. Chacun des six composants résout un problème critique nécessaire à la conduite, autonome ou non. Les composants peuvent être considérés comme exécutant les fonctions qui imitent les conducteurs humains, à savoir :

Localisation : Où sommes-nous ?
Planification d'itinéraire : Comment arriver à destination ?
Perception : Qu'y a-t-il d'autre dans les environs ?
Prédiction : A quoi ressemblera l'environnement un peu plus tard ?
Planning : Quel est le parcours que nous allons suivre dans les prochaines secondes ?
Control : Comment allons-nous suivre le cours que nous voulons ?

La localisation pour les humains a tendance à être très facile. Nous nous rappelons généralement de mémoire où nous nous trouvons dans le monde, souvent aidés par un appareil GPS comme un smartphone qui nous aide à identifier notre emplacement beaucoup plus précisément sur une carte. Nous utilisons également des indices visuels comme les panneaux de navigation, le marquage des voies et notre compréhension des autres véhicules, de la route et des environs pour nous assurer que nous sommes toujours dans la bonne voie, sur la bonne route et que nous nous dirigeons dans la bonne direction.

En matière de localisation, la conduite autonome nécessite également la position et la direction dans laquelle se déplace le véhicule, également appelée cap. Cependant, contrairement aux humains, le niveau de précision requis par les véhicules autonomes est très élevé. Il ne suffit pas de savoir qu'un véhicule se trouve dans la voie de droite et roule parallèlement à la voie. Une grande précision est nécessaire pour la planification. Si la localisation est décalée de plus de quelques centimètres autour de la position ou de plus de quelques degrés autour du cap, le composant de planification peut générer une trajectoire désastreuse entraînant une collision parmi de nombreux autres résultats indésirables.

Comme les humains, les véhicules autonomes obtiennent leur première estimation de position et de cap à partir d'un GPS. Les récepteurs GPS, même les plus petits que l'on trouve sur un smartphone, ont tendance à être assez précis. Cependant, la précision des informations de localisation reçues d'un GPS est insuffisante pour une conduite autonome en toute sécurité. Par exemple, la position signalée peut être décalée d'un mètre à plusieurs mètres ou, dans le pire des cas, encore plus.

La précision fluctue fréquemment et énormément en fonction de facteurs tels que le nombre de satellites visibles pour le récepteur, les réflexions des faisceaux des satellites sur de grands objets comme les bâtiments et l'absorption par les éléments atmosphériques.

Si cela ne suffit pas, la vitesse à laquelle le GPS met à jour les informations de localisation est également assez lente, comprise entre 1 et 10 Hz. Même à 10 Hz, un véhicule se déplaçant à 20 km/h en retard se serait déplacé d'environ un demi-mètre entre deux mises à jour GPS.

Pour atténuer l'incertitude de localisation due au mouvement, les véhicules autonomes utilisent des unités de mesure inertielle (IMU). Les IMU sont rapides et précises et mesurent l'accélération et le taux de virage d'un véhicule. Ces informations peuvent ensuite être utilisées pour connaître la position de la voiture entre deux mises à jour GPS successives. Les IMU ont tendance à accumuler de petites erreurs d'approximation au fil du temps, mais ce n'est pas le problème que nous traitons ici.

Le principal problème auquel le système de localisation doit faire face est que les mises à jour GPS sont intrinsèquement inexactes. Au lieu de signaler une position exacte, par exemple, le GPS signale une petite zone au sol où un véhicule est susceptible d'être présent lorsque le GPS se met à jour. Nous appelons cette zone un spot GPS.

Le problème d'effectuer une localisation précise se ramène au problème de la réduction de la surface du spot GPS.

L'une des techniques utilisées en robotique pour une localisation précise, à partir d'une moins précise, est connue sous le nom de filtrage de particules . Il est utile lorsque l'environnement comporte un certain nombre de points de repère, c'est-à-dire de grands objets fixes qui ne changent pas fréquemment d'emplacement, d'apparence et de taille. Il peut s'agir de bâtiments, de tours de téléphonie cellulaire, de piliers de pont, de poteaux électriques ou de feux de circulation et de panneaux de signalisation.

Pour comprendre le fonctionnement des filtrages de particules nous utiliserons une analogie. Supposons que vous reveniez fatigué dans une chambre d'hôtel, que vous éteigniez les lumières et que vous vous effondriez sur le lit face contre terre. Vous vous réveillez au milieu de la nuit et vous voulez savoir où vous êtes. Bien sûr, vous vous souvenez de vous être écrasé dans le lit, mais vous voudriez savoir dans quelle direction vous faites face, où se trouvent les interrupteurs et où se trouvent vos pantoufles. Cela demande plus de précision qu'un faible souvenir d'être dans le lit.

Pour s'orienter rapidement, on profite de l'environnement. Vous vous imaginez d'abord à différents endroits sur le lit. Ensuite, vous ressentez les objets «repères» dans les environs en les touchant et en les identifiant. Vous pourriez pousser une bouteille d'eau sur une table à proximité ou vous cogner le pied contre une chaise. Ces observations vous donnent des indices importants sur l'endroit où vous êtes susceptible d'être dans le domaine du lit d'hôtel. Puisque vous vous souvenez où se trouvaient la bouteille, la table et la chaise par rapport au lit, vous pouvez déduire votre position sur le lit avec plus de précision. À chaque nouvelle observation, vous pouvez exclure certains endroits du lit et augmenter vos chances de vous trouver à d'autres endroits.

C'est exactement ainsi que fonctionne le filtrage des particules pour les véhicules autonomes. Armé d'un point GPS initial, le véhicule connaît sa position approximative et son cap sur la carte. Cette position approximative est ensuite divisée en petites cellules imaginaires. Le véhicule sait également quels points de repère se trouvent à proximité de cet emplacement approximatif. Le véhicule mesure ensuite la distance à ces points de repère à l'aide d'un lidar embarqué. Le système de localisation compare ensuite ces mesures à chaque cellule imaginaire. Au fur et à mesure que de plus en plus de points de repère sont sondés, la plupart des cellules sont exclues et seules quelques-unes très probables restent comme emplacements probables.

Le nom de filtrage de particules vient du fait que l'emplacement de chaque cellule imaginaire est représenté par une particule sur la carte et nous excluons les particules en les filtrant en calculant les distances aux points de repère et en supprimant les particules qui ne semblent pas être à la bonne distance de les repères.

L'animation ci-dessous montre l'emplacement initial des particules couvrant une zone importante, qui pourrait être répartie sur plusieurs voies, routes et zones ouvertes. La détection ou le sondage de l'environnement est représenté par des rayons bleus. Le point vert représentant la position la plus probable saute initialement autour de la carte mais s'installe très rapidement car de plus en plus de particules sont exclues en détectant l'environnement.

Le filtrage des particules est un algorithme incroyablement simple qui alimente de nombreux robots et voitures autonomes. Nvidia Drive Labs a publié une courte vidéo sur la façon dont la localisation peut bénéficier de cartes riches, avec une variété de points de repère. Uber ATG a publié un blog sur la façon dont ils améliorent la précision du GPS ici .