Particle Filter

Aussi appelé: sequential Monte Carlo, SMC, bootstrap filter
Catégorie: State estimation & navigation › Localisation
Mots-clés: state-estimation, localization, bayesian-filtering, probabilistic-robotics, monte-carlo

Méthode d'estimation d'état qui représente une croyance par un ensemble d'échantillons pondérés, les déplace avec un modèle de mouvement, les pondère par la vraisemblance du capteur et les rééchantillonne.

Définition

Un filtre particulaire (particle filter) est un estimateur bayésien récursif qui représente la distribution de probabilité sur l'état d'un système par un ensemble d'échantillons, appelés particules, chacun portant un poids. L'approche est aussi connue sous le nom de Monte Carlo séquentiel (sequential Monte Carlo) ; sa forme largement citée, le filtre bootstrap, a été publiée par Gordon, Salmond et Smith en 1993. En robotique, elle est devenue standard grâce à la localisation de Monte Carlo (Monte Carlo localization), développée par Dellaert, Fox, Burgard et Thrun, et elle est traitée en profondeur dans Probabilistic Robotics.

Chaque mise à jour comporte trois étapes. À l'étape de prédiction, chaque particule est déplacée selon le modèle de mouvement, avec un bruit ajouté pour refléter l'incertitude de l'odométrie ou de la commande. À l'étape de mise à jour, chaque particule est pondérée selon la concordance entre la dernière mesure du capteur et l'état qu'elle représente. À l'étape de rééchantillonnage, un nouvel ensemble de particules est tiré proportionnellement aux poids, de sorte que les hypothèses probables sont dupliquées et que les improbables disparaissent. L'estimation peut être lue sur la moyenne pondérée, la meilleure particule ou un groupe de particules.

Contrairement au filtre de Kalman et à ses extensions, un filtre particulaire ne suppose pas que la croyance est gaussienne. Il peut maintenir plusieurs hypothèses distinctes à la fois, comme un robot qui pourrait se trouver dans l'un de deux couloirs identiques, ou un objet tenu en main qui pourrait être dans plusieurs poses compatibles avec les contacts ressentis jusqu'ici. Le prix est calculatoire : le nombre de particules nécessaires croît rapidement avec la dimension de l'état, et si trop peu de particules tombent près de l'état vrai, le filtre peut s'effondrer sur une mauvaise réponse. Les filtres pratiques utilisent donc un rééchantillonnage à faible variance, ne rééchantillonnent que lorsque la taille effective de l'échantillon baisse, adaptent le nombre de particules et injectent des particules aléatoires pour se remettre des échecs.

Pourquoi c'est important

De nombreux problèmes d'estimation en robotique sont non linéaires et ambigus, avec des croyances qui ont plusieurs pics plutôt qu'un seul. Le filtre particulaire les traite directement, c'est pourquoi il est à la base de la localisation 2D standard des robots mobiles et constitue un outil courant pour estimer la pose d'objets à partir du contact et du toucher.

Applications principales

Localisation de robots mobiles par rapport à une carte connue (localisation de Monte Carlo)
Estimation de la pose d'un objet dans la main à partir de la proprioception et du contact tactile
Suivi de personnes et d'objets dans des scènes encombrées ou avec occultations
SLAM avec des filtres particulaires Rao–Blackwellisés comme FastSLAM et GMapping
Localisation globale et récupération quand un robot est déplacé à son insu

En pratique

Un robot d'entrepôt qui utilise la pile de navigation ROS se localise généralement avec AMCL, un paquet de localisation de Monte Carlo adaptative. Au démarrage, l'opérateur donne une pose initiale approximative, et quelques milliers de particules sont réparties autour. Pendant que le robot roule, l'odométrie des roues déplace les particules et chaque scan LiDAR les repondère par rapport à la carte d'occupation stockée ; le nuage se resserre autour de la pose vraie en quelques mètres de déplacement. Les ingénieurs règlent les paramètres de bruit d'odométrie pour qu'ils correspondent à la transmission réelle, fixent les nombres minimal et maximal de particules et surveillent le nuage de particules dans RViz : un nuage qui se scinde en deux groupes dans une allée répétitive indique que le filtre suit deux hypothèses et a besoin d'un élément distinctif pour les départager.

Idées reçues

Plus de particules règlent toujours les problèmes de précision — le besoin en particules croît rapidement avec la dimension de l'état, si bien que les problèmes en grande dimension exigent de meilleures distributions de proposition ou une structure, pas seulement plus d'échantillons
Un filtre particulaire n'est qu'un filtre de Kalman plus lent — il représente des croyances non gaussiennes et multimodales que les filtres de type Kalman ne peuvent pas représenter
Rééchantillonner à chaque étape est toujours préférable — rééchantillonner trop souvent détruit la diversité ; de nombreux filtres ne rééchantillonnent que lorsque la taille effective de l'échantillon passe sous un seuil
Le filtre se remet toujours d'une estimation erronée — une fois que les particules se sont effondrées loin de l'état vrai, elles ne peuvent pas revenir à moins d'injecter des particules aléatoires

Qui devrait le savoir

Ingénieurs en localisation et navigation de robots mobiles
Développeurs en estimation d'état et en SLAM
Chercheurs en manipulation qui estiment la pose d'objets par le toucher
Étudiants en robotique qui étudient la robotique probabiliste

Technologies associées

Localisation de Monte Carlo (Monte Carlo Localization, AMCL)
Filtre de Kalman (Kalman Filter)
FastSLAM
Échantillonnage préférentiel (Importance Sampling)
Carte en grille d'occupation (Occupancy Grid Map)

Termes associés

Projets associés

Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
Nav2: ROS 2 navigation stack with path planning and obstacle avoidance for mobile robots
GTSAM: Factor-graph optimization library powering many modern SLAM backends
OpenVINS: The reference open platform for visual-inertial state estimation research
AprilTag: The standard visual fiducial marker system for robot localization and pose estimation
GLIM: GPU-accelerated 3D lidar SLAM framework for any range sensor, from AIST

Vidéos

Understanding the Particle Filter | | Autonomous Navigation, Part 2: MATLAB
Particle Filter - 5 Minutes with Cyrill: Cyrill Stachniss

Wikipédia

Filtre particulaire