- Comme les mesures de position et de vitesse dans le monde réel fluctuent toujours, on peut comprendre le filtre de Kalman comme une méthode qui combine plusieurs sources d’information imparfaites pour produire une estimation d’état plus fiable
- Dans l’exemple de la position d’un bateau, le modèle d’une vitesse moteur de 10 m/s se trompe à cause du vent et des vagues, et des capteurs comme le GPS ne sont pas toujours précis non plus à cause du bruit ou des perturbations
- Le code d’exemple montre l’intuition du filtre de Kalman en faisant produire à 1000 passagers une estimation basée sur la vitesse et une mesure de capteur, puis en combinant les deux par moyenne pondérée
- La fiabilité des sources d’information est calculée à partir de la variance des mesures, et on utilise
1/variance pour moins faire confiance à ce qui varie beaucoup et davantage à ce qui reste cohérent
- Quand le capteur fonctionne normalement, on suit davantage sa valeur, et dans les phases instables comme
t=3 et t=6, son influence diminue automatiquement afin de conserver une estimation plus stable
Situations où un filtre de Kalman est nécessaire
- On peut voir le filtre de Kalman comme un entonnoir qui compresse plusieurs sources d’information bruitées en une seule valeur statistique plus précise
- D’un point de vue mathématique, cela implique de l’algèbre linéaire, des probabilités et du calcul différentiel, mais ici l’accent est mis sur l’intuition plutôt que sur la théorie complète
- Supposons qu’un bateau parte du port en
x=0, se déplace en une dimension, et que son moteur fournisse une vitesse constante de 10 m/s
- Dans un monde idéal, sa position au bout de 2 secondes serait
2 * 10 = 20m, mais dans le monde réel, le moteur, le vent et les vagues empêchent la vitesse et la position de rester parfaitement exactes
- On ne peut donc pas être certain de la position réelle du bateau avec la seule formule de position
Les capteurs ne sont pas parfaits non plus
- Avec un capteur comme le GPS, on peut mesurer directement la position à un instant donné, mais les mesures du capteur ne sont pas toujours exactes non plus
- À 3 secondes, le GPS peut fournir une valeur proche de la position réelle, comme 29.998 m ou 30.002 m, mais dans de très rares cas il peut aussi renvoyer une valeur très éloignée, comme 100 m
- Dans une zone sans couverture satellite, le capteur GPS peut pratiquement cesser de fonctionner
- Si le capteur ne tombait jamais hors ligne et pouvait mesurer n’importe quelle valeur avec une précision arbitraire, il n’y aurait pas besoin de filtre de Kalman
- Le filtre de Kalman permet d’estimer plus précisément la position en combinant plusieurs sources d’information comme l’estimation fondée sur la vitesse, l’estimation GPS, le radar ou le sonar
Estimation de position vue dans le code
- L’exemple suppose qu’il y a 1000 passagers sur le bateau et que chacun possède son propre appareil GPS
- Chaque passager commence par estimer la nouvelle position en ajoutant à la position précédente la vitesse et les variations des facteurs extérieurs
from random import gauss
def new_position(last):
velocity = 10
wind = gauss(0, 2)
wave = gauss(0, 0.1)
return last + velocity + wind + wave
gauss produit des valeurs aléatoires positives ou négatives, et son second paramètre représente l’ampleur de la variation- Comme on ne peut pas mesurer directement l’effet du vent et des vagues, l’exemple modélise le bruit avec des nombres aléatoires de moyenne 0 et d’écart-type
2 et 0.1
- Dans une deuxième étape, le capteur renvoie une mesure en ajoutant un bruit de capteur à la position réelle
def sensor(t):
if t == 3:
# oops, passing through a thunderstorm. GPS fluctuating!
sensor_noise = gauss(5, 10)
elif t == 6:
# uh-oh, satellite unavailable!
sensor_noise = gauss(-5, 10)
else:
sensor_noise = gauss(0, 1)
return true_position[t] + sensor_noise
- À
t=3, on modélise un GPS perturbé par un orage, et à t=6, une situation où le satellite n’est pas disponible
- Même au même instant, les mesures de capteur diffèrent d’un passager à l’autre
Trajectoire réelle et moyenne simple
- La position réelle du bateau est donnée par la liste suivante
true_position = [0, 9, 19.2, 28, 38.1, 48.5, 57.2, 66.2, 77.5, 85, 95.2]
- Le bateau part du port en
x=0, se trouve à 9 m après 1 seconde, à 19.2 m après 2 secondes, puis se déplace ensuite selon les valeurs de la liste
- L’objectif des passagers est de prédire aussi précisément que possible la position à chaque seconde à partir de mesures bruitées et peu fiables
- Si, à
t=1, l’estimation fondée sur la vitesse d’un passager vaut 9.37 et que la mesure du capteur vaut 8.98, leur moyenne simple est 9.17
- Si la position réelle est de 9 m, cette moyenne simple est moins erronée que l’estimation fondée sur la vitesse, mais pire que cette mesure de capteur précise
Moyenne pondérée et fiabilité
- Une meilleure méthode que la moyenne simple consiste à utiliser une moyenne pondérée
def combine(A, B, trustA, trustB):
total_trust = trustA + trustB
return (A * trustA + B * trustB) / total_trust
combine(9.37, 8.98, 10, 1) donne un résultat proche de 9.37, soit 9.33, parce qu’on fait davantage confiance à l’estimation fondée sur la vitessecombine(9.37, 8.98, 1, 10) donne 9.01, donc une valeur plus proche de 8.98, parce qu’on fait davantage confiance à la mesure du capteur- Cette moyenne pondérée fondée sur la confiance est l’intuition centrale du filtre de Kalman et le cœur de sa capacité à combiner des données
- Le choix de la source à laquelle faire le plus confiance se fait à partir de la variance
- On fait moins confiance à une source dont les conclusions fluctuent fortement
- On fait davantage confiance à une source dont les conclusions sont cohérentes
- Si, parmi 10 stations de radio, 4 annoncent de la pluie et 6 du beau temps, alors que parmi 10 sites web, 9 annoncent de la pluie, les sites web ont une variance plus faible et sont donc plus fiables
Étape de mise à jour
- La mise à jour complète consiste à produire, pour chaque passager, une estimation fondée sur la vitesse et une mesure de capteur, puis à calculer la confiance à accorder à chacun des deux ensembles de mesures à partir de leur variance
from statistics import variance
def update(t, last):
velocity_updates = []
sensor_updates = []
for p in range(1000):
velocity_updates.append(new_position(last[p]))
sensor_updates.append(sensor(t))
fluctuation_velocity = variance(velocity_updates)
fluctuation_sensor = variance(sensor_updates)
trust_velocity = 1 / fluctuation_velocity
trust_sensor = 1 / fluctuation_sensor
combined = []
for p in range(1000):
combined.append(combine(
A=velocity_updates[p],
B=sensor_updates[p],
trustA=trust_velocity,
trustB=trust_sensor
))
return sensor_updates, velocity_updates, combined
- Plus la variance augmente, plus la confiance diminue, d’où l’usage de
1/variance
- Chaque passager met à jour sa propre position individuellement
- Une fois toutes les mises à jour de position des passagers terminées, on peut déduire l’estimation de la position réelle du bateau à partir de la moyenne des positions des passagers
Comment lire les résultats
- La fonction
update_plot stocke, pour construire le graphique, la position réelle, l’estimation par capteur, l’estimation par vitesse et l’estimation combinée à chaque instant
- La boucle principale continue à mettre à jour l’estimation de position à chaque instant à partir de la meilleure estimation courante détenue par les passagers
- Sur le graphique, l’envelope autour des lignes représente l’incertitude, et plus elle est large, plus l’incertitude sur cette valeur est élevée
- Dans l’intervalle
t=0.75 à t=1, lorsque le capteur fonctionne normalement, l’estimation de position combinée est meilleure qu’une estimation fondée uniquement sur la vitesse, mais peut être moins bonne qu’une estimation fondée uniquement sur le capteur
- Dans l’intervalle
t=2 à t=4, lorsque le capteur tombe en panne, l’estimation combinée donne de meilleurs résultats qu’une estimation reposant uniquement sur les mesures défaillantes du capteur
- Dans l’intervalle
t=4 à t=5, lorsque le capteur se rétablit, le filtre de Kalman recommence à privilégier davantage le capteur
Annexe : gauss et variance
- Les fonctions de
normal distribution function gauss(0, 0.1) et gauss(0, 2) génèrent le plus souvent des valeurs aléatoires proches de 0
- Le second paramètre, l’écart-type, contrôle l’ampleur des fluctuations des mesures
gauss(0, 0.1) a de fortes chances de produire de petites valeurs proches de 0, comme 0.06, -0.07 ou 0.02gauss(0, 2) a de fortes chances de produire des valeurs plus dispersées, comme 1.05, -1.06, 1.29 ou -1.72
- Le code d’exemple suppose que le vent varie davantage, tandis que les vagues varient moins
- La variance est une mesure de la cohérence : une forte cohérence implique une faible variance, et une faible cohérence une forte variance
- Une distribution d’écart-type 2 a une variance de 4, tandis qu’une distribution d’écart-type 0.1 a une variance de 0.01
1 commentaires
Avis de Hacker News
L’article était intéressant à lire, mais l’implémentation est incorrecte. La plus grosse erreur est qu’elle ne propage pas l’incertitude dans le temps, ce qui sous-estime l’erreur
Cela se voit aussi sur les graphiques : les intervalles d’erreur devraient contenir l’état réel la plupart du temps, mais ce n’est pas le cas dans les résultats
Les passagers ne sont pas censés ajouter du bruit à l’estimation ; du point de vue d’un passager, étant donné l’état à l’instant k, l’espérance de l’état à l’instant k+1 est simplement
position_k+1 = position_k + velocity * Delta_t. La dynamique réelle contient du bruit, et le filtre en tient compte en l’ajoutant à la covariance estiméeSi le code ne casse pas immédiatement, c’est parce qu’avec 1 000 passagers il tire de nombreux échantillons de dynamique et calcule numériquement la variance des résultats, ce qui est assez différent de ce qu’on fait habituellement en pratique
Par ailleurs, l’idée que le GPS est influencé par la météo est une idée reçue courante, mais ce n’est pas le cas en réalité. Et la définition de cohérence utilisée dans l’article n’est pas standard non plus. En théorie de l’estimation, dire qu’un estimateur est cohérent signifie que, à mesure que la quantité de données augmente, l’estimation converge vers la vraie valeur
C’est bien d’avoir vulgarisé le sujet pour le grand public, mais quelques malentendus semblent poser problème. Je suis doctorant en théorie de l’estimation, donc je peux aider en donnant plus de détails
C’était au point de me demander pourquoi on n’enseigne pas le Kalman Filter aussi simplement dans les cours universitaires de traitement du signal. Les concepts mathématiques doivent évidemment être enseignés mathématiquement, mais pour les personnes qui manquent de prérequis, cela entraîne une perte d’information
J’ai autrefois enseigné la transformée en cosinus discrète et la transformée en ondelettes en partant des images ; donner d’abord l’intuition, plutôt que la rigueur, a toujours mieux fonctionné que l’ordre inverse
Il peut y avoir plusieurs raisons pour lesquelles les professeurs ne donnent pas d’abord l’intuition. Le professeur peut avoir une expertise plus profonde dans les nombres et les manipulations d’équations que dans l’intuition ; les compétences pédagogiques peuvent être peu récompensées, si bien que le temps nécessaire pour expliquer intuitivement est consacré à des dossiers de financement ou à l’encadrement de doctorants ; et, une fois les mathématiques comprises, l’explication intuitive peut sembler être le « chemin difficile », au point que le cerveau refuse de revenir en arrière
Je pense que la troisième raison est particulièrement importante. Cela dépasse l’enseignement des mathématiques : c’est aussi la différence entre expertise et compétence pédagogique. Pour apprendre un drive au golf, il vaut peut-être mieux apprendre auprès de quelqu’un qui a commencé à 100 yards et a fini par atteindre régulièrement 300 yards, plutôt qu’auprès de celui qui frappe le plus loin
Comme avertissement général pour ceux qui veulent implémenter un Kalman Filter, il vaut la peine de lire les premières pages de https://www.stat.berkeley.edu/~brill/Stat248/kalmanfiltering... sur la façon de gérer l’instabilité numérique
En pratique, je n’ai pas souvent vu d’artefacts numériques visibles en procédant ainsi, mais c’est une solution assez séduisante
En complément de cet article, si vous voulez une introduction plus rigoureuse et mathématique à la famille des Kalman Filter, je recommande vivement ce livre : https://github.com/rlabbe/Kalman-and-Bayesian-Filters-in-Pyt...
Comme il a été écrit par un ingénieur logiciel qui a dû implémenter des Kalman Filter dans le cadre de son travail, la façon dont les concepts sont motivés et transmis peut bien convenir à ce public. Il est rédigé sous forme de notebooks Jupyter interactifs, ce qui permet de cloner le dépôt et de suivre en exécutant soi-même les exemples
Il commence par un filtre simple, ajoute la règle de Bayes puis étend le tout aux distributions de probabilité, en améliorant progressivement l’approche ; il offre donc une rampe d’accès en douceur vers le Kalman Filter
Il manque un aspect. Quand on prend une moyenne pondérée de la prédiction et de la mesure, les poids du Kalman Filter peuvent varier au fil du temps. Sinon, je pense qu’on l’appellerait autrement
L’exemple d’une valeur qui varie lentement, mesurée par un seul capteur, est bon. Par exemple, pour une jauge de carburant, il est préférable de supposer qu’elle ne change pas à l’échelle de la seconde, mais la mesure peut contenir du bruit, comme le ballottement du carburant dans le réservoir
Dans ce cas, le Kalman Filter ressemble à un filtre passe-bas du premier ordre avec un gain qui décroît exponentiellement. La fréquence de coupure change, ce qui permet de trouver rapidement le niveau de départ en quelques secondes, puis d’ignorer le bruit avec une fréquence de coupure très basse, par exemple 0,01 Hz
C’est un bon article sur un outil important
Si je comprends bien, le filtre de Kalman linéaire est la solution optimale pour les problèmes linéaires, et il est relativement facile à comprendre et à implémenter. Mais la plupart des applications que j’ai vues étaient non linéaires
Le filtre de Kalman étendu et le filtre de Kalman unscented sont beaucoup plus difficiles à comprendre et à implémenter, et les ressources comme les bibliothèques sont moins nombreuses et moins utiles
Par exemple, en travaillant sur un dispositif AHRS/GNSS CAN pour petit UAV, les filtres de Kalman étendus que j’ai vus dans PX4 ou Ardupilot étaient très complexes, avec beaucoup de paramètres. Partir des principes de base des quaternions et corriger progressivement la solution gyroscopique vers le « haut » de l’accéléromètre et vers le vecteur d’inclinaison du magnétomètre était donc plus simple
Si la norme de l’accélération diffère beaucoup de 1G, ou si le vecteur de champ magnétique diffère beaucoup de l’intensité du champ magnétique terrestre local, on réduit le poids de la mise à jour de ce capteur, ou on la saute, et on laisse le gyroscope continuer tel quel. L’EKF est probablement la bonne réponse, mais j’ai renoncé à le mettre sous une forme facile à comprendre, à construire, à régler et à diagnostiquer
Cela dit, avec les quadrirotors, la grosse difficulté est la rotation. Le modèle linéaire du filtre de Kalman suppose que tout se trouve dans un espace euclidien, alors que les rotations vivent sur une variété. Dans le cas des quaternions, cette variété est l’ensemble des quaternions unitaires
Si l’on applique naïvement un EKF pour estimer un quaternion, il cesse d’être un quaternion unitaire et l’estimation se dégrade. Il existe des méthodes bien connues pour gérer cette contrainte de variété, mais les équations que j’ai traduites en code faisaient partie des plus laides que j’aie vues
Comme exemple simple, on peut imaginer un état
(x, y)qui, à cause des lois de la physique, doit toujours rester sur le cercle unité. La vraie dynamiquef(x, y)produit un nouveau point sur le cercle, mais la dynamique approchée obtenue par linéarisation ne garantit pas de rester sur le cercle unité, ce qui peut mener à des états non physiques ou à une estimation d’état EKF incorrecteParmi les options à regarder, il y a ForneyLab.jl, Infer.net, Gen.jl et Pyro
Mais il existe beaucoup de façons d’utiliser un filtre de Kalman, et selon le point de départ, traiter correctement les transformations non linéaires peut devenir extrêmement fastidieux
Je suis myope et astigmate, et si je ferme un œil en regardant quelque chose comme une horloge murale, je constate que chaque œil produit une image déformée différemment. Les deux yeux sont légèrement différents
Pourtant, quand je regarde l’horloge avec les deux yeux, l’image est beaucoup plus nette, meilleure qu’avec un seul œil. Le scénario de l’article où 1 000 passagers d’un bateau rapportent chacun leurs coordonnées GPS m’a fait penser à ce phénomène
Le cerveau doit lui aussi utiliser largement des algorithmes intelligents du genre filtre de Kalman
Est-ce correct de comprendre le filtre de Kalman comme une méthode qui estime, à partir d’observations bruitées, une valeur meilleure qu’une simple moyenne ?
Par exemple, si l’on mesure quelque chose 3 fois et que l’on obtient 7, 8, 9, on supposerait que la vraie valeur est 8 ; le filtre de Kalman donnerait-il une autre estimation ?
Le filtre de Kalman est traditionnellement utilisé pour estimer des choses qui évoluent dans le temps. Pensez à une personne dans une vidéo, ou à une sorte de marche aléatoire
Si l’on suppose qu’il existe, entre deux instants ou mesures consécutifs, des relations comme la vitesse et la direction actuelle, on peut combiner les informations du modèle de mouvement avec celles du modèle de mesure bruité pour mieux estimer la position, la valeur, voire tout l’historique du déplacement
Si le modèle de mouvement est significativement faux, l’estimation ne s’améliore pas. Beaucoup d’extensions ultérieures se concentrent sur l’intégration de modèles de mouvement plus sophistiqués, comme le patinage des roues en robotique
Par exemple, si l’on mesure une constante, on peut prendre comme modèle de base une constante avec une incertitude initiale, par exemple une distribution gaussienne avec un écart-type, ainsi que des mesures ayant elles aussi un bruit gaussien et un écart-type. On peut ajuster l’incertitude initiale autour de la constante à estimer et l’incertitude des mesures
Dans cet exemple, le filtre de Kalman ne se comporte pas comme une moyenne. Si les mesures sont bonnes, c’est-à-dire peu incertaines, il converge rapidement ; si elles sont mauvaises, l’estimation fluctue et met plus longtemps à converger
Et il n’est pas vrai que le filtre de Kalman ne s’utilise que pour des objets en mouvement. Il est aussi toujours utilisé pour l’estimation de constantes ; il est simplement plus connu pour les objets en mouvement
Le filtre de Kalman traite les cas où les échantillons sont corrélés à cause d’une certaine dynamique linéaire. Les mesures n’ont pas besoin d’être l’objet d’intérêt lui-même ; elles peuvent aussi être une fonction linéaire de cet objet, additionnée d’un bruit gaussien
Ainsi, le fait d’avoir vu 7 à la première mesure modifie la probabilité de voir 8 à la deuxième. Si l’on se contente de faire la moyenne des échantillons comme ci-dessus, en général, on ne converge pas vers la vraie valeur moyenne
Dans votre exemple, ce qu’il produira dépend du modèle exact. Même dans le scénario le plus simple imaginable, comme en bayésien, il faut préciser avec quelle valeur attendue on commence
Si l’on encode cette description sous forme de modèle gaussien linéaire, on obtient un filtre de Kalman
Un court texte qui m’a aussi apporté un déclic en comprenant le Kalman Filter est une note de John D. Cook : https://www.johndcook.com/blog/applied-kalman-filtering/
Alors que la modélisation traditionnelle des systèmes, fondée sur le calcul différentiel et intégral et les équations différentielles, considère qu’il n’y a pas d’incertitude dans les données et que tout est contenu dans le modèle du système, les estimateurs pilotés par les données partent du principe que « tout est dans les données » et ignorent complètement le modèle du processus physique qui génère ces données.
La beauté du Kalman Filter tient au fait qu’il combine ces deux approches.
Il existe aussi un autre article avec de bonnes visualisations : https://www.bzarg.com/p/how-a-kalman-filter-works-in-picture...
Cet article est déjà passé trois fois sur HN.