Filtre de Kalman

Filtre de Kalman

Type	Algorithme, filtre, estimateur
Nommé en référence à	Rudolf Kalman

modifier - modifier le code - modifier Wikidata

(en) Concept de base du filtre de Kalman.

En statistique et en théorie du contrôle, le filtre de Kalman est un filtre à réponse impulsionnelle infinie qui estime les états d'un système dynamique à partir d'une série de mesures incomplètes ou bruitées. Le filtre a été nommé d'après le mathématicien et informaticien américain d'origine hongroise Rudolf Kálmán.

Exemples d'applications

Le filtre de Kalman est utilisé dans une large gamme de domaines technologiques (radar, vision électronique, communication…). C'est un thème majeur de l'automatique et du traitement du signal. Un exemple d'utilisation peut être la mise à disposition, en continu, d'informations telles que la position ou la vitesse d'un objet à partir d'une série d'observations relatives à sa position, incluant éventuellement des erreurs de mesures.

Par exemple, pour le cas des radars où l'on désire suivre une cible, des données sur sa position, sa vitesse et son accélération sont mesurées à chaque instant mais avec énormément de perturbations dues au bruit ou aux erreurs de mesure. Le filtre de Kalman fait appel à la dynamique de la cible qui définit son évolution dans le temps pour obtenir de meilleures données, éliminant ainsi l'effet du bruit. Ces données peuvent être calculées pour l'instant présent (filtrage), dans le passé (lissage), ou sur un horizon futur (prédiction).

Le filtrage de Kalman est aussi de plus en plus utilisé en dehors du domaine de l'électronique, par exemple en météorologie et en océanographie, pour l'assimilation de données dans un modèle numérique, en finance ou en navigation et il est même utilisé dans l'estimation^[1] des états de trafic routier dans le cas de commande par rampe d'accès où le nombre de boucles magnétiques sur la route est insuffisant.

Paternité

Le filtre de Kalman doit son nom à Rudolf Kalman bien que Thorvald Nicolai Thiele^[2] et Peter Swerling aient développé un algorithme similaire avant lui. La paternité du filtre fait l'objet d'une petite controverse dans la communauté scientifique. Le filtre a été décrit dans diverses publications par Swerling (1958), Kalman (1960)^[3] et Kalman-Bucy (1961)^[4].

Stanley Schmidt est reconnu comme ayant réalisé la première mise en œuvre du filtre. C'était lors d'une visite de Rudolf Kalman au NASA Ames Research Center qu'il vit le potentiel du filtre pour l'estimation de la trajectoire pour le programme Apollo. Ceci conduisit à l'utilisation du filtre dans l'ordinateur de navigation.

Une grande variété de filtres de Kalman a été, depuis, développée à partir de la formulation originale dite filtre de Kalman simple. Schmidt développa le filtre de Kalman étendu, Bierman, Thornton et bien d'autres développèrent toute une gamme de filtres racine carrée. Le filtre le plus utilisé est vraisemblablement la phase-locked loop, largement répandue dans les radios, ordinateurs, équipements de communication, etc.

Le filtre de Kalman en contexte discret

Le filtre de Kalman en contexte discret est un estimateur récursif : pour estimer l'état courant, seules l'estimation de l'état précédent et les mesures actuelles sont nécessaires. En d'autres termes, l'historique des observations et des estimations n'est ainsi pas requis. Le filtre de Kalman suppose que le processus discret réel ${\displaystyle {\textbf {x}}_{k}}$ (où ${\displaystyle k}$ dénote l'indice de temps), suit la loi d'évolution linéaire suivante :

$${\displaystyle {\textbf {x}}_{k}={\textbf {F}}_{k}{\textbf {x}}_{k-1}+{\textbf {B}}_{k}{\textbf {u}}_{k}+{\textbf {w}}_{k}}$$

dans laquelle :

• ${\displaystyle {\textbf {F}}_{k}}$ est la matrice d'évolution, ou matrice de transition, reliant l'état précédent ${\displaystyle k-1}$ à l'état actuel ${\displaystyle k}$ ;
• ${\displaystyle {\textbf {u}}_{k}}$ est la commande en entrée ;
• ${\displaystyle {\textbf {B}}_{k}}$ est la matrice de contrôle de la commande reliant la commande à l'état ${\displaystyle \mathbf {x} _{k}}$ ;
• ${\displaystyle {\textbf {w}}_{k}}$ est le bruit d'évolution, gaussien centré et de matrice de covariance ${\displaystyle {\textbf {Q}}_{k}}$.

À chaque instant ${\displaystyle k}$, le processus est observé par des mesures ${\displaystyle {\textbf {z}}_{k}}$ s'exprimant comme suit :

$${\displaystyle {\textbf {z}}_{k}={\textbf {H}}_{k}{\textbf {x}}_{k}+{\textbf {v}}_{k}}$$dans laquelle :

• ${\displaystyle {\textbf {H}}_{k}}$ est la matrice d'observation ;
• ${\displaystyle {\textbf {v}}_{k}}$ est le bruit de mesure, gaussien centré et de matrice de covariance ${\displaystyle {\textbf {R}}_{k}}$.

Ces deux équations sont appelées les équations d'évolution et d'observation du système.

L'état réel ${\displaystyle {\textbf {x}}_{k}}$ est estimé par 2 variables :

• ${\displaystyle {\hat {\textbf {x}}}_{k|k}}$, l'estimation de l'état à l'instant k ;
• ${\displaystyle {\textbf {P}}_{k|k}}$, la matrice de covariance de l'erreur (une mesure de la précision de l'état estimé).

Les notations ${\displaystyle {\hat {\textbf {x}}}_{m|n}}$ et ${\displaystyle {\textbf {P}}_{m|n}}$ désignent l'estimation et la covariance de l'estimateur obtenues à l'instant ${\displaystyle m}$ à partir des observations jusqu'à l'instant ${\displaystyle n\leq m}$.

Si les bruits d'évolution et de mesure ne sont pas gaussiens, le filtre optimal n'est pas linéaire en général mais, comme on le montre aisément, les formules de récurrence qui suivent, utilisant la matrice de covariance et la moyenne des bruits d'évolution et de mesure, déterminent le meilleur estimateur linéaire possible au sens des moindres carrés^[5]. Néanmoins, si les lois de probabilité de ces bruits sont très éloignées de lois gaussiennes, par exemple des lois de Poisson, le filtre linéaire optimal sera de piètre qualité en comparaison du filtre optimal (au sens des moindres carrés), qui est alors non linéaire^[6].

Le filtre de Kalman est composé de deux phases distinctes : la prédiction et la mise à jour. La phase de prédiction utilise l'état estimé de l'instant précédent pour produire une estimation de l'état courant. Dans l'étape de mise à jour, les observations de l'instant courant sont utilisées pour corriger l'état prédit dans le but d'obtenir une estimation plus précise.

Prédiction

${\displaystyle {\hat {\textbf {x}}}_{k|k-1}={\textbf {F}}_{k}{\hat {\textbf {x}}}_{k-1|k-1}+{\textbf {B}}_{k}{\textbf {u}}_{k}}$ (état prédit)

${\displaystyle {\textbf {P}}_{k|k-1}={\textbf {F}}_{k}{\textbf {P}}_{k-1|k-1}{\textbf {F}}_{k}^{T}+{\textbf {Q}}_{k}}$ (estimation prédite de la covariance)

avec :

• ${\displaystyle {\textbf {F}}_{k}}$ : matrice qui relie l'état précédent ${\displaystyle k-1}$ à l'état actuel ${\displaystyle k}$
• ${\displaystyle {\textbf {u}}_{k}}$ : entrée de commande
• ${\displaystyle {\textbf {B}}_{k}}$ : matrice qui relie l'entrée de commande ${\displaystyle \mathbf {u} _{k}}$ à l'état ${\displaystyle \mathbf {x} _{k}}$
• ${\displaystyle {\textbf {P}}_{k-1|k-1}}$ : matrice de covariance a posteriori estimée à l'état précédent ${\displaystyle k-1}$
• ${\displaystyle {\textbf {Q}}_{k}}$ : matrice de covariance du bruit d'évolution

Mise à jour

${\displaystyle {\tilde {\textbf {y}}}_{k}={\textbf {z}}_{k}-{\textbf {H}}_{k}{\hat {\textbf {x}}}_{k|k-1}}$ (innovation)

${\displaystyle {\textbf {S}}_{k}={\textbf {H}}_{k}{\textbf {P}}_{k|k-1}{\textbf {H}}_{k}^{T}+{\textbf {R}}_{k}}$ (covariance de l'innovation)

${\displaystyle {\textbf {K}}_{k}={\textbf {P}}_{k|k-1}{\textbf {H}}_{k}^{T}{\textbf {S}}_{k}^{-1}}$ (gain de Kalman)

${\displaystyle {\hat {\textbf {x}}}_{k|k}={\hat {\textbf {x}}}_{k|k-1}+{\textbf {K}}_{k}{\tilde {\textbf {y}}}_{k}}$ (état mis à jour)

${\displaystyle {\textbf {P}}_{k|k}=(I-{\textbf {K}}_{k}{\textbf {H}}_{k}){\textbf {P}}_{k|k-1}}$ (covariance mise à jour)

avec :

• ${\displaystyle {\textbf {z}}_{k}}$ : observation ou mesure du processus à l'instant k
• ${\displaystyle {\textbf {H}}_{k}}$ : matrice qui relie l'état ${\displaystyle {\textbf {x}}_{k}}$ à la mesure ${\displaystyle {\textbf {z}}_{k}}$
• ${\displaystyle {\textbf {P}}_{k|k}}$ : matrice d'estimation a posteriori de la covariance de l'erreur
• ${\displaystyle {\textbf {R}}_{k}}$ : matrice de covariance du bruit de mesure
• ${\displaystyle {I}}$ : matrice identité aux dimensions adéquates

Le gain de Kalman est choisi pour minimiser la valeur de la covariance a posteriori de l'estimateur.

Le filtre d'information

Durrant Whyte a bien traité^[Quoi ?] le filtre informationnel et a montré ses avantages par rapport au filtre de Kalman^{[réf. nécessaire]}, il a surtout traité son aspect décentralisé. Dans le cas décentralisé on n'a pas besoin d'une unité centrale de traitement de données, ce qui réduit fortement le temps d'exécution.

Dans le filtre de l'information, la covariance et l'état estimés sont respectivement remplacés par la matrice d'information et le vecteur d'information. Ils sont définis par :

${\displaystyle {\textbf {Y}}_{k|k}\equiv {\textbf {P}}_{k|k}^{-1}}$

${\displaystyle {\hat {\textbf {y}}}_{k|k}\equiv {\textbf {P}}_{k|k}^{-1}{\hat {\textbf {x}}}_{k|k}}$

De même, la covariance et l'état prédits ont les formes d'information équivalentes, définies par :

${\displaystyle {\textbf {Y}}_{k|k-1}={\textbf {P}}_{k|k-1}^{-1}}$

${\displaystyle {\hat {\textbf {y}}}_{k|k-1}={\textbf {P}}_{k|k-1}^{-1}{\hat {\textbf {x}}}_{k|k-1}}$

La covariance et le vecteur de mesure sont définis par :

${\displaystyle {\textbf {I}}_{k}={\textbf {H}}_{k}^{T}{\textbf {R}}_{k}^{-1}{\textbf {H}}_{k}}$

${\displaystyle {\textbf {i}}_{k}={\textbf {H}}_{k}^{T}{\textbf {R}}_{k}^{-1}{\textbf {z}}_{k}}$

La mise à jour de l'information devient maintenant une somme triviale :

${\displaystyle {\textbf {Y}}_{k|k}={\textbf {Y}}_{k|k-1}+{\textbf {I}}_{k}}$

${\displaystyle {\hat {\textbf {y}}}_{k|k}={\hat {\textbf {y}}}_{k|k-1}+{\textbf {i}}_{k}}$

L'avantage principal du filtre de l'information est que N mesures peuvent être filtrées à chaque instant simplement en additionnant leurs matrices et vecteurs de l'information si la matrice R est une matrice diagonale.

${\displaystyle {\textbf {Y}}_{k|k}={\textbf {Y}}_{k|k-1}+\sum _{j=1}^{N}{\textbf {I}}_{k,j}}$

${\displaystyle {\hat {\textbf {y}}}_{k|k}={\hat {\textbf {y}}}_{k|k-1}+\sum _{j=1}^{N}{\textbf {i}}_{k,j}}$

Pour prédire le filtre d'information, la matrice et le vecteur d'information peuvent être convertis de nouveau à leurs équivalents de l'espace d'état ou, alternativement, la prédiction de l'espace d'information peut être utilisée.

${\displaystyle {\textbf {M}}_{k}=[{\textbf {F}}_{k}^{-1}]^{\text{T}}{\textbf {Y}}_{k-1\mid k-1}{\textbf {F}}_{k}^{-1}}$

${\displaystyle {\textbf {C}}_{k}={\textbf {M}}_{k}[{\textbf {M}}_{k}+{\textbf {Q}}_{k}^{-1}]^{-1}}$

${\displaystyle {\textbf {L}}_{k}=I-{\textbf {C}}_{k}}$

${\displaystyle {\textbf {Y}}_{k|k-1}={\textbf {L}}_{k}{\textbf {M}}_{k}{\textbf {L}}_{k}^{T}+{\textbf {C}}_{k}{\textbf {Q}}_{k}^{-1}{\textbf {C}}_{k}^{T}}$

${\displaystyle {\hat {\textbf {y}}}_{k|k-1}={\textbf {L}}_{k}[{\textbf {F}}_{k}^{-1}]^{T}{\hat {\textbf {y}}}_{k|k}}$

Noter également que F et Q doivent être inversibles.

L'avantage principal du filtre informationnel apparait dans son étape de correction qui est beaucoup plus simple que celle du filtre de Kalman. Ceci apporte de nombreux avantages au problème de diagnostic et surtout dans le cas de détection de plusieurs défauts simultanés.

Les filtres non linéaires

Le filtre de Kalman est limité aux systèmes linéaires. Cependant, la plupart des systèmes physiques sont non linéaires. Le filtre n'est donc optimal que sur une petite plage linéaire osculatrice des phénomènes réels pris en compte par la linéarisation de l'équation physique. La non-linéarité peut être associée au modèle du processus, au modèle d'observation ou bien aux deux.

Filtre de Kalman étendu

Dans le filtre de Kalman étendu (FKE), les modèles d'évolution et d'observation n'ont pas besoin d'être des fonctions linéaires de l'état mais peuvent à la place être des fonctions différentiables.

${\displaystyle {\textbf {x}}_{k}=f({\textbf {x}}_{k-1},{\textbf {u}}_{k},{\textbf {w}}_{k})}$

${\displaystyle {\textbf {z}}_{k}=h({\textbf {x}}_{k},{\textbf {v}}_{k})}$

La fonction f peut être utilisée pour calculer l'état prédit à partir de l'état estimé précédent et, semblablement, la fonction h peut être employée pour calculer l'observation prédite de l'état prédit. Cependant, f et h ne peuvent pas être appliqués directement au calcul de la covariance : une matrice des dérivées partielles, la Jacobienne, est calculée.

À chaque instant, la Jacobienne est évaluée avec les états estimés courants. Ces matrices peuvent être employées dans les équations du filtre de Kalman. Ce processus linéarise essentiellement la fonction non linéaire autour de l'estimation courante.

Ceci donne les équations du filtre de Kalman étendu suivantes :

Prédiction

${\displaystyle {\hat {\textbf {x}}}_{k|k-1}=f({\hat {\textbf {x}}}_{k-1|k-1},{\textbf {u}}_{k},0)}$

${\displaystyle {\textbf {P}}_{k|k-1}={\textbf {F}}_{k}{\textbf {P}}_{k-1|k-1}{\textbf {F}}_{k}^{T}+{\textbf {Q}}_{k}}$

Mise à jour

${\displaystyle {\tilde {\textbf {y}}}_{k}={\textbf {z}}_{k}-h({\hat {\textbf {x}}}_{k|k-1},0)}$

${\displaystyle {\textbf {S}}_{k}={\textbf {H}}_{k}{\textbf {P}}_{k|k-1}{\textbf {H}}_{k}^{T}+{\textbf {R}}_{k}}$

${\displaystyle {\textbf {K}}_{k}={\textbf {P}}_{k|k-1}{\textbf {H}}_{k}^{T}{\textbf {S}}_{k}^{-1}}$

${\displaystyle {\hat {\textbf {x}}}_{k|k}={\hat {\textbf {x}}}_{k|k-1}+{\textbf {K}}_{k}{\tilde {\textbf {y}}}_{k}}$

${\displaystyle {\textbf {P}}_{k|k}=(I-{\textbf {K}}_{k}{\textbf {H}}_{k}){\textbf {P}}_{k|k-1}}$

où les matrices de transition et d'observation sont définies comme étant les jacobiennes suivantes :

${\displaystyle {\textbf {F}}_{k}=\left.{\frac {\partial f}{\partial {\textbf {x}}}}\right\vert _{{\hat {\textbf {x}}}_{k-1|k-1},{\textbf {u}}_{k}}}$

${\displaystyle {\textbf {H}}_{k}=\left.{\frac {\partial h}{\partial {\textbf {x}}}}\right\vert _{{\hat {\textbf {x}}}_{k|k-1}}}$

Remarque : la convergence de ce filtre n'est aucunement assurée car il s'agit d'une convergence locale. En fait, il existe de nombreux exemples pour lesquels la convergence du filtre dépend de l'initialisation de l'état à l'instant initial.

Filtre de Kalman sans parfum

Le filtre de Kalman sans parfum (Unscented Kalman filter, UKF)^[7], procède à une approximation de la densité a posteriori par une gaussienne comme dans le filtre de Kalman étendu. Mais plutôt que de faire une approximation des fonctions non linéaires du modèle d'évolution et du modèle de mesure, il réalise une approximation de la densité de probabilité par un ensemble de points pondérés convenablement choisis de façon déterministe. Ces points sont transformés par les fonctions non linéaires d'évolution et de mesure afin d'obtenir une nouvelle densité de probabilité. Cette approximation est appelée la transformée sans parfum (Unscented Transform).

Les modèles d'évolution et de mesure sont les mêmes que celles du filtre de Kalman étendu.

L'algorithme du filtre de Kalman sans parfum est le suivant :

Calcul des points d'approximation

${\displaystyle s_{k-1}^{a}=[{\hat {x}}_{k-1}^{a}\qquad ({\hat {x}}_{k-1}^{a}\dots {\hat {x}}_{k-1}^{a})+{\sqrt {(n+\lambda )P_{k-1}^{a}}}\qquad ({\hat {x}}_{k-1}^{a}\dots {\hat {x}}_{t-1}^{a})-{\sqrt {(n+\lambda )P_{k-1}^{a}}}]}$

avec :

${\displaystyle {\hat {x}}_{k-1}^{a}=[{\hat {x}}_{k-1|k-1}^{T}\quad 0_{dim(w_{k}-1)}^{T}]}$

et

${\displaystyle P_{k-1}^{a}={\begin{pmatrix}P_{k-1|k-1}&0\\0&Q_{k-1}\end{pmatrix}}}$

Calcul des poids associés

Ceci est réalisé par l'usage de la transformée sans parfum.

Prédiction

${\displaystyle s_{k|k-1}^{x}=f_{k-1}(s_{k-1}^{x},s_{k-1}^{w})}$

${\displaystyle {\hat {x}}_{k|k-1}=\sum \limits _{i=0}^{2n}W_{i}s_{k|k-1}^{x}}$

${\displaystyle P_{k|k-1}=\sum \limits _{i=0}^{2n}W_{i}(s_{k|k-1}^{x}-{\hat {x}}_{k|k-1})(s_{k|k-1}^{x}-{\hat {x}}_{k|k-1})^{T}+Q_{k}}$

${\displaystyle \mathrm {Z} _{i,k|k-1}^{x}=h_{t}(s_{k|k-1}^{x})}$

${\displaystyle {\hat {z}}_{k|k-1}=\sum \limits _{i=0}^{2n}W_{i}\mathrm {Z} _{i,k|k-1}^{x}}$

Estimation

${\displaystyle S_{k}=P_{\nu _{k}\nu _{k}}=R_{k}+\sum \limits _{i=0}^{2n}W_{i}(\mathrm {Z} _{i,k|k-1}^{x}-{\hat {z}}_{k|k-1})(\mathrm {Z} _{i,k|k-1}^{x}-{\hat {z}}_{k|k-1})^{T}}$

${\displaystyle K_{k}=P_{x_{k}z_{k}}S_{k}^{-1}=\sum \limits _{i=0}^{2n}W_{i}(s_{j}-{\hat {x}}_{k|k-1})(\mathrm {Z} _{i,k|k-1}^{x}-{\hat {z}}_{k|k-1})^{T}S_{k}^{-1}}$

${\displaystyle {\hat {x}}_{k|k}={\hat {x}}_{k|k-1}+K_{k}(z_{k}-{\hat {z}}_{k|k-1})}$

${\displaystyle P_{k|k}=P_{k|k-1}-K_{k}S_{k}K_{k}}$

Le filtre de Kalman sans parfum fournit une alternative intéressante au filtre de Kalman étendu et donne dans plusieurs cas de meilleurs résultats que ce dernier, pour une complexité équivalente^[8]. Cependant, ce filtre montre ses limites dans le cas de systèmes fortement non linéaires et/ou non gaussiens^[9],[10].

Applications

• Pilote automatique
• Centrale inertielle
• Systèmes de localisation dynamique
• Cartographie et localisation simultanées (SLAM)
• Système de positionnement par satellites
• Assimilation de données

Voir aussi

• Filtre particulaire
• Théorème de Masreliez
• Algorithme des moindres carrés récursifs
• Réseau bayésien dynamique (une généralisation)

Références

Notes

1. www.springerlink.com/index/M87W5148L57H0L46.pdf
2. Steffen L. Lauritzen, Thiele: Pioneer in Statistics, Oxford University Press, 2002. (ISBN 0-19-850972-3).
3. Kalman, R. E. "A New Approach to Linear Filtering and Prediction Problems," Transactions of the ASME - Journal of Basic Engineering Vol. 82: p. 35-45 (1960)
4. Kalman, R. E., Bucy R. S., "New Results in Linear Filtering and Prediction Theory", Transactions of the ASME - Journal of Basic Engineering Vol. 83: p. 95-107 (1961).
5. (en-US) Jeffrey Uhlmann et Simon J. Julier, « Gaussianity and the Kalman Filter: A Simple Yet Complicated Relationship », Journal de Ciencia e Ingeniería, vol. 14, n^o 1,‎ 30 juin 2022, p. 21–26 (ISSN 2539-066X et 2145-2628, DOI 10.46571/jci.2022.1.2, lire en ligne, consulté le 6 juin 2023)
6. (en-US) Oleg V. Makhnin, « Filtering and parameter estimation for a jump stochastic process with discrete observations », The Electronic Communications in Probability, vol. 13,‎ 2008, p. 210-224 (ISSN 2539-066X et 2145-2628, DOI 10.1214/ECP.v13-1363, lire en ligne)
7. Simon J. Julier et Jeffrey K. Uhlmann, « New extension of the Kalman filter to nonlinear systems », Signal Processing, Sensor Fusion, and Target Recognition VI, SPIE, vol. 3068,‎ 28 juillet 1997, p. 182–193 (DOI 10.1117/12.280797, lire en ligne, consulté le 6 février 2022)
8. Simon S. Haykin, Kalman filtering and neural networks, Wiley, 2001 (ISBN 0-471-46421-X, 978-0-471-46421-1 et 0-471-22154-6, OCLC 52366672, lire en ligne)
9. S.J. Julier, « The scaled unscented transformation », Proceedings of the 2002 American Control Conference (IEEE Cat. No.CH37301), vol. 6,‎ mai 2002, p. 4555–4559 vol.6 (DOI 10.1109/ACC.2002.1025369, lire en ligne, consulté le 6 février 2022)
10. Cindy CAPPELLE, « Localisation de véhicules et détection d'obstacles Apport d'un modèle virtuel 3D urbain », Thèse de doctorat Université de Lille,‎ 2008