v1.13.2 (763)

Cours scientifique - SOD333 : Filtrage bayésien optimal et approximation particulaire

Domaine > Mathématiques et leurs applications.

Descriptif

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. Le domaine d'application principal est la localisation, la navigation et la poursuite de mobiles, dans le domaine militaire ou civil, 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 éventuellemnent 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, optimisation globale, simulation moléculaire, etc.
L'objectif de ce cours est
  1. de présenter différents algorithmes particulaires,
  2. de les mettre en œuvre dans le cadre de travaux pratiques en MATLAB,
  3. et de démontrer quelques résultats de convergence en utilisant le cadre général de l'approximation particulaire des distributions de Feynman-Kac.

Objectifs pédagogiques

Estimer des états cachés lorsqu'on a des observations sur le bruit.
Etre capable d'implémenter des algorithmes particulaires et analyser la convergence de ces algorithmes.

nombre d'heure en présentiel

21

nombre de blocs

6

Volume horaire par type d'activité pédagogique : types d'activité

  • Bloc de 1/2 journée 3h : 4
  • Cours magistral : 6
  • Contrôle Final : 1
  • Travaux dirigés en salle info : 11

Diplôme(s) concerné(s)

Format des notes

Numérique sur 20

Littérale/grade européen

Pour les étudiants du diplôme Diplôme d'Ingénieur de l'Ecole nationale supérieure de techniques avancées

Vos modalités d'acquisition :

 Examen + TP MATLAB

Le rattrapage est autorisé (Max entre les deux notes écrêté à une note seuil)
  • le rattrapage est obligatoire si :
    Note initiale < 6
  • le rattrapage peut être demandé par l'étudiant si :
    6 ≤ note initiale < 10
L'UE est acquise si Note finale >= 10
  • Crédits ECTS acquis : 1.5 ECTS
  • Scientifique acquis : 1.5

Le coefficient de l'UE est : 1.5

La note obtenue rentre dans le calcul de votre GPA.

L'UE est évaluée par les étudiants.

Programme détaillé

1. Bloc de module:
Introduction au filtrage : estimation récursive d'un état caché au vu d'observations, importance du modèle <em>a priori</em>, estimation bayésienne, borne de Cramér-Rao <em>a posteriori</em><br>
Systèmes linéaires gaussiens et conditionnellement linéaires gaussiens : filtre de Kalman<br>
Systèmes non linéaires à bruits non gaussiens : exemples en localisation, navigation et poursuite
<ul>
<li type="disc">recalage altimétrique de navigation inertielle
<li type="disc">suivi visuel par histogramme de couleurs
<li type="disc">poursuite d'une cible furtive (track-before-detect)
<li type="disc">navigation en environnement intérieur
</ul>
2.CM:
Dérivation du filtre bayésien optimal : représentation probabiliste vs. équation récurrente
<ul>
<li type="disc">systèmes non linéaires à bruits non gaussiens
<li type="disc">modèles de Markov cachés
<li type="disc">chaînes de Markov partiellement observées
</ul>
Distribution de Feynman-Kac : représentation probabiliste vs. équation récurrente<br>
Approximation particulaire : algorithme SIS, algorithme SIR, redistribution adaptative
</ul>
3. TD en salle info:
Recalage altimétrique de navigation inertielle
4. Bloc de module:
Méthodes de Monte Carlo : simulation selon une distribution de Gibbs-Boltzmann
<ul>
<li type="disc">acceptation / rejet
<li type="disc">échantillonnage pondéré, changement de probabilité «optimal» (variance nulle)
<li type="disc">simulation séquentielle (contrôle de la taille de l'échantillon)
<li type="disc">réduction de variance par conditionnement (Rao-Blackwell)
</ul>
Méthodes de Monte Carlo : simulation selon un mélange fini
<ul>
<li type="disc">échantillonnage multinomial, algorithme de Malmquist
<li type="disc">stratification et échantillonnage résiduel
<li type="disc">stratification et randomisation
<li type="disc">échantillonnage systématique
<li type="disc">stratification et tirage uniforme sans remise (cas particulier des poids 0/1)
</ul>
5.  CM:
Méthodes de Monte Carlo séquentielles : échantillonnage selon une distribution de Gibbs-Boltzmann
<ul>
<li type="disc">v.a. conditionnées ou contraintes
<li type="disc">pondération «progressive»
<li type="disc">recuit
</ul>
Dynamique markovienne artificielle : algorithme de Metropolis-Hastings, échantillonneur de Gibbs<br>
Méthodes de branchement multi-niveaux : taux de branchement fixe vs. taille d'échantillon fixe, sélection des niveaux (fonction d'importance optimale, seuils)
<ul>
<li type="disc">évaluation d'une probabilité de dépassement de niveau (cas statique)
<li type="disc">optimisation globale
<li type="disc">simulation d'évènements rares (cas dynamique)
</ul>
Exemples en évaluation de risque
<ul>
<li type="disc">collision entre satellite et débris
<li type="disc">conflit ou collision en trafic aérien
</ul>
6. TD en salle info:
Navigation en environnement intérieur
7. CM:
Rappels : inégalité de Marcinkiewicz-Zygmund, théorème central limite «conditionnel»<br>
Théorèmes limites pour les approximations particulaires : convergence dans L<sub>p</sub>, théorème central limite
8. TD en salle info:
Navigation en environnement intérieur (suite)
9. CM:

Théorèmes limites pour les approximations particulaires
10. TD en salle info:
Evaluation du risque de collision






Mots clés

filtrage, système non linéaire à bruits non gaussiens, modèle de Markov caché, estimation bayésienne, méthode de Monte Carlo, système de particules en interaction, localisation, navigation, poursuite, simulation d'évènements rares
Veuillez patienter