---

École thématique : Filtrage particulaire

---

Objectifs :

En toute généralité, le filtrage consiste à estimer de façon récursive un état caché (par exemple, la position et l'attitude d'un mobile) au vu d'observations bruitées. Compte tenu que l'état caché évolue en principe au cours du temps, il est nécessaire d'introduire un modèle a priori de déplacement du mobile, et de considérer le problème d'estimation dans un cadre bayésien. Le domaine d'application principal est la localisation, la navigation et la poursuite de mobiles, dans le domaine militaire, mais aussi en robotique mobile, en vision par ordinateur, en communications sans-fil (GSM en extérieur, WiFi en indoor), où il s'agit de combiner : un modèle a priori de déplacement du mobile, des mesures issues de capteurs, et éventuellement une base de mesures de références, disponibles par exemples sous la forme d'une carte numérique (modèle numérique de terrain, carte de couverture, etc.).

Dans le cas particulier des systèmes linéaires gaussiens, le problème de filtrage possède une solution explicite, appelée filtre de Kalman. Dans le cas des systèmes non-linéaires avec des bruits non nécessairement gaussiens, ou dans le cas plus général des modèles de Markov cachés, des méthodes de simulation Monte Carlo très efficaces sont apparues récemment, sous le nom de filtres particulaires. De manière intuitive, chaque particule représente ici un état caché possible, explore l'espace d'état en suivant le modèle a priori de déplacement, et est répliquée ou au contraire éliminée à la génération suivante au vu de sa cohérence avec l'observation courante, quantifiée par la fonction de vraisemblance. Ce mécanisme de mutation / sélection a pour effet de concentrer automatiquement les particules (i.e. la puissance de calcul disponible) dans les régions d'intérêt de l'espace d'état.

Plus généralement, les algorithmes particulaires permettent d'approcher des distributions de Feynman-Kac (ou distributions de Boltzmann-Gibbs trajectorielles) au moyen de la distribution de probabilité empirique pondérée associée à un système de particules en interaction, avec des applications qui vont bien au-delà du filtrage : simulation d'évènements rares, méthodes MCMC en interaction, simulation moléculaire, etc.

Cette école thématique est constituée d'un mini-cours et de présentations invitées. L'objectif du mini-cours est

• d'introduire la problématique du filtrage bayésien,
• de présenter différents algorithmes particulaires,
• de les illustrer à partir d'exemples issus du domaine navigation (hors conception des lois de commande), localisation et poursuite,
• de les mettre en œuvre dans le cadre de travaux pratiques en MATLAB,
• et d'énoncer quelques résultats de convergence en utilisant le cadre général de l'approximation particulaire des distributions de Boltzmann-Gibbs.

Il reprend en partie le contenu d'un cours de 3ème année donné à l'ENSTA ParisTech (École Nationale Supérieure de Techniques Avancées) depuis plusieurs années.

Contenu du mini-cours :

1. Objectif : estimation d'un état caché au vu d'observations bruitées
   
   • introduction nécessaire d'un modèle a priori, cadre bayésien
     
   • estimateur MMSE = moyenne conditionnelle, loi conditionnelle (aka. filtre bayésien dans le cas dynamique)
     
   • solution exacte et algorithme récursif dans le cas des systèmes linéaires gaussiens (filtre de Kalman)
   Systèmes non-linéaires / non-gaussiens
   • interprétation comme modèle de propagation des estimateurs et des incertitudes associées
     
   • filtres particulaires SIS et SIR (avec / sans redistribution) : états cachés proposés (aka. particules) et poids associés
     
   Exemples : illustration de modélisation a priori et de comportement des algorithmes
   • navigation par corrélation de terrain (recalage altimétrique)
   • suivi visuel par histogramme de couleur
   • suivi d'une cible furtive (track-before-detect)
   • navigation en environnement intérieur
   slides
2. Quelques modèles a priori
   • systèmes non-linéaires / non-gaussiens : cas particulier de modèle de Markov caché
     
   • modèles de Markov cachés généraux : permet d'inclure des modes / régimes markoviens
     
   • chaînes de Markov partiellement observées (bruit d'observation additif) : permet d'inclure des bruits corrélés
     
   • idem (bruit d'observation non-additif, sans vraisemblance, etc.) : solution approchée de type ABC (approximate Bayesian computation)
   Équation pour le filtre bayésien
   • loi conditionnelle jointe des états cachés
   • loi conditionnelle marginale de l'état caché courant : équation récurrente
   Méthodes de Monte Carlo
   • échantillonnage pondéré (importance sampling) : algorithme SIS, forme récursive, changement de distribution d'importance
   • redistribution : algorithme SIR, redistribution adaptative, directement à partir de l'équation récurrente
   Résultats d'approximation (en fonction de la taille de l'échantillon)
   • estimation d'erreur, théorème central limite
   Quelques extensions des approximations particulaires
   • choix de la distribution d'importance
   • particules auxiliaires
   • marginalisation
   • régularisation
   • maintien de modes multiples
   • MCMC (Markov chain Monte Carlo) et dynamique markovienne artificielle
   • correction / pondération progressive
   • contrôle / adaptation du nombre de particules
   • échantillonnage séquentiel (contrôle de la taille de l'échantillon)
   • ABC (approximate Bayesian computation)
   slides

Programmation des présentations invitées :

• jeudi 2 février
  • à 14:00, Patrick Pérez (Technicolor) : Filtrage particulaire pour le suivi visuel, slides
  • à 15:00, Anne Cuzol (université de Bretagne Sud et INRIA) : Filtrage pour l'estimation de mouvement fluide, slides
  
  
• jeudi 9 février
  • à 14:00, Céline Teulière (IRISA et INRIA) : Filtrage particulaire dans la vision robotique : application à la commande d'un mini-drone, slides
  • à 15:00, Christian Musso (ONERA) : Gestion des modes multiples par clustering et approximation de Laplace en filtrage particulaire, slides

Références bibliographiques :

ouvrages de référence

• Nathalie Bartoli et Pierre Del Moral, Simulation et Algorithmes Stochastiques, Cépaduès, Toulouse, 2001.
• Olivier Cappé, Éric Moulines and Tobias Ryden, Inference in Hidden Markov Models, Springer Series in Statistics, Springer, New York, 2005.
• Pierre Del Moral, Feynman-Kac Formulae. Genealogical and Interacting Particle Systems with Applications, Probability and its Applications, Springer, New York, 2004.
• Arnaud Doucet, Nando de Freitas and Neil Gordon, editors, Sequential Monte Carlo Methods in Practice, Statistics for Engineering and Information Science, Springer, New York, 2001.

polycopié téléchargeable (format PDF)

• François Le Gland, Filtrage bayésien et approximation particulaire, cours de 3ème année à l'ENSTA ParisTech (École Nationale Supérieure de Techniques Avancées), version du 13 septembre 2011 + site du cours.

articles téléchargeables (format PDF)

• Neil J. Gordon, David J. Salmond and Adrian F. M. Smith, Novel approach to nonlinear / non-Gaussian Bayesian state estimation, IEE Proceedings, Part F, Radar, Sonar and Navigation, 140, 2, 107-113, April 1993.
• Petr Tichavsky, Carlos H. Muravchik and Arye Nehorai, Posterior Cramér-Rao bounds for discrete-time nonlinear filtering, IEEE Transactions on Signal Processing, SP-46, 5, 1386-1396, May 1998.
• Arnaud Doucet, Simon J. Godsill and Christophe Andrieu, On sequential Monte Carlo sampling methods for Bayesian filtering, Statistics and Computing, 10, 3, 197-208, July 2000.
• David J. Salmond and H. Birch, A particle filter for track-before-detect, American Control Conference (ACC'01), Arlington, June 2001, 3755-3760, IEEE-CSS, 2001.
• Sanjeev M. Arulampalam, Simon Maskell, Neil J. Gordon and Tim C. Clapp, A tutorial on particle filters for online nonlinear / non-Gaussian Bayesian tracking, IEEE Transactions on Signal Processing, SP-50, 2 (special issue on Monte Carlo Methods for Statistical Signal Processing), 174-188, February 2002.
• Fredrik Gustafsson, Fredrik Gunnarsson, Niclas Bergman, Urban Forssell, Jonas Jansson, Rickard Karlsson and Per-Johan Nordlund, Particle filters for positioning, navigation, and tracking, IEEE Transactions on Signal Processing, SP-50, 2 (special issue on Monte Carlo Methods for Statistical Signal Processing), 425-437, February 2002.
• Patrick Pérez, Carine Hue, Jako Vermaak and Marc Gangnet, Color-based probabilistic tracking, European Conference on Computer Vision (ECCV'02), Copenhagen, June 2002, Lecture Notes in Computer Science 2350, 661-675, Springer, Berlin, 2002.
• Dieter Fox, Jeffery Hightower, Lin Liao, Dirk Schulz and Gaetano Borriello, Bayesian filtering for location estimation, IEEE Pervasive Computing, 2, 3, 24-33, July / September 2003.
• Thomas Schön, Fredrik Gustafsson and Per-Johan Nordlund, Marginalized particle filters for mixed linear / nonlinear state-space models, IEEE Transactions on Signal Processing, SP-53, 7, 2279-2289, July 2005.
• Olivier Cappé, Simon J. Godsill and Éric Moulines, An overview of existing methods and recent advances in sequential Monte Carlo, Proceedings of the IEEE, 95, 5, 899-924, May 2007.
• Fredrik Gustafsson, Particle filter theory and practice with positioning applications, IEEE Aerospace and Electronic Systems Magazine, 25, 7 (part 2), 51-82, July 2010.

Retour à la page de François Le Gland