- Der Kalman-Filter ist ein Algorithmus, der in Systemen mit Messrauschen und unbekannten externen Einflüssen den aktuellen Zustand schätzt und die Zukunft vorhersagt; er wird in Bereichen wie Tracking, Navigation, Robotik und Regelungstechnik eingesetzt
- Ein eindimensionales Radar-Beispiel misst die Entfernung (r) und die Geschwindigkeit (v) eines Flugzeugs und behandelt Zustand und Unsicherheit gemeinsam über den Zustandsvektor (\boldsymbol{x}=[r, v]^T) und die Kovarianzmatrizen (\boldsymbol{P}, \boldsymbol{R}, \boldsymbol{Q})
- Die Anfangsmesswerte sind eine Entfernung von 10.000 m und eine Geschwindigkeit von 200 m/s; bei einem Abtastintervall von 5 Sekunden und einem Modell konstanter Geschwindigkeit ergibt sich als nächste Positionsvorhersage 11.000 m
- In der Vorhersagephase wird der Zustand mit der Zustandsübergangsmatrix (\boldsymbol{F}) fortgeschrieben, und die Kovarianz wird mit (\boldsymbol{F}\boldsymbol{P}\boldsymbol{F}^T+\boldsymbol{Q}) berechnet, wodurch berücksichtigt wird, dass Geschwindigkeitsunsicherheit und Prozessrauschen die Positionsunsicherheit erhöhen
- In der Update-Phase wird eine neue Messung weder ungeprüft übernommen noch verworfen; stattdessen werden Vorhersage und Messung über den Kalman Gain gewichtet kombiniert, um die Schätzunsicherheit zu senken. Danach wiederholt der Filter Vorhersage und Update
Welches Problem der Kalman-Filter behandelt
- Der Kalman-Filter ist ein Algorithmus, der in Systemen mit Unsicherheit Zustandsschätzung und Zukunftsvorhersage durchführt
- Er behandelt Situationen, in denen Messrauschen vorliegt oder unbekannte externe Faktoren das System beeinflussen
- Er wird als zentrales Werkzeug in den Bereichen Objektverfolgung, Navigation, Robotik und Regelungstechnik eingesetzt
- Bei der Schätzung der Trajektorie einer Computermaus kann er Handzittern und Rauschen reduzieren und so eine stabilere Bewegungsbahn erzeugen
- In der Finanzmarktanalyse wird er genutzt, um aus verrauschten Marktdaten Aktientrends zu erkennen; in der Meteorologie kommt er bei Wettervorhersagen zum Einsatz
- Dieses Tutorial baut Intuition über numerische Beispiele auf, statt zuerst komplexe Mathematik in den Vordergrund zu stellen
- Es enthält auch ein Beispiel dafür, wie ein falsch ausgelegter Kalman-Filter ein Objekt nicht korrekt verfolgen kann
- Ziel ist ein Niveau, auf dem man die Konzepte und die Mathematik versteht und selbst einen Filter entwerfen und implementieren kann
Lernpfad
- Der angebotene Lernpfad ist in drei Stufen gegliedert
- Einseitige Übersicht: erklärt die Kernkonzepte und wesentlichen Gleichungen ohne Herleitung und setzt Grundkenntnisse in Statistik und linearer Algebra voraus
- Kostenloses webbasiertes Tutorial mit Beispielen: Das tutorial baut anhand numerischer Beispiele Intuition auf und behandelt Schritt für Schritt auch die Herleitung der Kalman-Filter-Gleichungen
- Buch: Kalman Filter from the Ground Up enthält 14 vollständig gelöste numerische Beispiele, Leistungsdiagramme und Tabellen, Extended Kalman Filter und Unscented Kalman Filter, Sensorfusion sowie Implementierungsrichtlinien
Warum Vorhersage beim Radar-Tracking nötig ist
- Damit ein Radar ein Flugzeug verfolgen kann, muss es einen schmalen Strahl wiederholt auf die Zielrichtung ausrichten; daher muss es die zukünftige Position vorhersagen, zu der der nächste Strahl gesendet wird
- Scheitert die Vorhersage, zeigt der Strahl in die falsche Richtung und die Verfolgung kann verloren gehen
- Es ist ein dynamisches Modell nötig, das beschreibt, wie sich das Flugzeug im Zeitverlauf bewegt
- Im vereinfachten eindimensionalen Beispiel wird nur die geradlinige Bewegung betrachtet, bei der sich das Flugzeug auf das Radar zu oder von ihm weg bewegt
- Der Zustand wird als Entfernung (r) vom Radar definiert
- Das Radar berechnet die Entfernung (r) aus der Sende- und Empfangszeit eines Pulses und der Lichtgeschwindigkeit
- Über den Doppler-Effekt kann auch die Geschwindigkeit (v) gemessen werden
- Angenommen wird, dass bei (t_0) eine Entfernung von 10.000 m und eine Geschwindigkeit von 200 m/s mit sehr hoher Genauigkeit und Präzision gemessen wurden
- Das Abtastintervall beträgt (\Delta t=5s)
- Im Modell konstanter Geschwindigkeit ist die zurückgelegte Strecke (\Delta r=v\cdot\Delta t)
- Die vorhergesagte Position ist (10,000+200\cdot5=11,000m)
Messrauschen und Prozessrauschen
- Reale Radarmessungen sind nicht perfekt; selbst wenn mehrere Radare dasselbe Flugzeug im selben Moment messen, liefern sie leicht unterschiedliche Ergebnisse
- Solche Schwankungen entstehen durch Messrauschen
- Man muss nicht nur den Schätzwert berechnen, sondern auch, wie vertrauenswürdig diese Schätzung ist
- Auch das dynamische Modell beschreibt die reale Bewegung nicht vollständig
- Selbst wenn man annimmt, dass sich ein Flugzeug mit konstanter Geschwindigkeit bewegt, können externe Faktoren wie Wind die tatsächliche Bewegung verändern
- Solche unvorhersagbaren Einflüsse werden als Prozessrauschen behandelt
- Der Kalman-Filter liefert gemeinsam die aktuelle Zustandsschätzung, die Vorhersage des zukünftigen Zustands und die jeweilige Unsicherheit
- Er wird als optimaler Algorithmus vorgestellt, der die Unsicherheit der Zustandsschätzung minimiert
Zustandsdarstellung und Initialisierung im Radar-Beispiel
- Der Systemzustand im Beispiel ist ein Vektor, der die Entfernung (r) und die Geschwindigkeit (v) des Flugzeugs enthält
[ \boldsymbol{x}=\left[\begin{matrix}r\v\\end{matrix}\right] ]
- Vektoren werden mit fetten Kleinbuchstaben, Matrizen mit fetten Großbuchstaben notiert
- Der Kalman-Filter wird mit der ersten Messung initialisiert
- Bei (t_0) lauten die Messwerte: Entfernung 10.000 m, Geschwindigkeit 200 m/s
- Der Messvektor ist wie folgt
[ \boldsymbol{z}_0=\left[\begin{matrix}10{,}000\200\\end{matrix}\right] ]
- Messwerte sind nicht der exakte Systemzustand, sondern verrauschte Zufallsvariablen
- Die Standardabweichung der Entfernungsmessung beträgt (4m)
- Die Standardabweichung der Geschwindigkeitsmessung beträgt (0.5m/s)
- Da die Varianz das Quadrat der Standardabweichung ist, lautet die Messkovarianzmatrix (\boldsymbol{R}_0) wie folgt
[ \boldsymbol{R}_0=\left[\begin{matrix}16&0\0&0.25\\end{matrix}\right] ]
- In diesem Beispiel wird angenommen, dass die Messfehler von Entfernung und Geschwindigkeit nicht miteinander zusammenhängen; daher werden die Nicht-Diagonalelemente der Kovarianzmatrix auf 0 gesetzt
- Zum Initialisierungszeitpunkt liegt nur eine einzelne Messung vor, daher kann der Messwert als anfängliche Zustandsschätzung verwendet werden
[ \boldsymbol{\hat{x}}_{0,0}=\boldsymbol{z}_0=\left[\begin{matrix}10{,}000\200\\end{matrix}\right] ]
- Dieses Vorgehen ist nur in der Initialisierungsphase möglich
Vorhersagephase: Fortschreibung von Zustand und Kovarianz
- Um den nächsten Zustand vorherzusagen, wird ein dynamisches Modell mit konstanter Geschwindigkeit verwendet
[ v_1=v_0=v ]
[ r_1=r_0+v_0\Delta t ]
- Die Zustandsvorhersage in Matrixform lautet wie folgt
[ {\hat{\boldsymbol{x}}}{1,0}=\boldsymbol{F}{\hat{\boldsymbol{x}}}{0,0} ]
- (\boldsymbol{F}) ist die Zustandsübergangsmatrix; bei (\Delta t=5s) ergibt sich folgendes Vorhersageergebnis
[ {\hat{\boldsymbol{x}}}_{1,0}
\left[\begin{matrix}1&5\0&1\\end{matrix}\right] \left[\begin{matrix}10,000\200\\end{matrix}\right]
\left[\begin{matrix}11,000\200\\end{matrix}\right] ]
- Die allgemeine Zustandsextrapolation, also die Vorhersagegleichung, lautet
[ {\hat{\boldsymbol{x}}}{n+1,n}=\boldsymbol{F}{\hat{\boldsymbol{x}}}{n,n}+\boldsymbol{G}\boldsymbol{u}_n ]
- (\boldsymbol{u}_n) ist die Eingangsvariable
- (\boldsymbol{G}) ist die Eingangsübergangsmatrix
- Im Beispiel gibt es keinen Eingang, daher gilt (\boldsymbol{u}_n=0)
- Die Kovarianz wird nicht einfach als (\boldsymbol{F}\boldsymbol{P}) berechnet
- Denn Kovarianz enthält quadratische Terme von Varianz und Kovarianz
- Ohne Prozessrauschen lautet die Kovarianz-Extrapolationsgleichung wie folgt
[ \boldsymbol{P}{n+1,n}=\boldsymbol{F}\boldsymbol{P}{n,n}\boldsymbol{F}^T ]
- Wird im Beispiel die anfängliche Kovarianz (\boldsymbol{P}_{0,0}) fortgeschrieben, ergibt sich folgendes Ergebnis
[ \boldsymbol{P}_{1,0}
\left[\begin{matrix}22.25&1.25\1.25&0.25\\end{matrix}\right] ]
- Die Geschwindigkeitsvarianz bleibt bei (0.25m^2/s^2)
- Die Entfernungsvarianz steigt von (16m^2) auf (22.25m^2)
- Die Geschwindigkeitsunsicherheit überträgt sich im Lauf der Zeit auf die Entfernungsunsicherheit
Berücksichtigung von Prozessrauschen
- Allein mit der Annahme konstanter Geschwindigkeit lässt sich die tatsächliche Bewegung eines Flugzeugs nur schwer vollständig beschreiben
- Unbekannte externe Faktoren wie Wind können die Geschwindigkeit beeinflussen
- Solche unvorhersagbaren Einflüsse werden als Prozessrauschen (\boldsymbol{Q}) dargestellt
- Die Kovarianz-Vorhersagegleichung mit Prozessrauschen lautet wie folgt
[ \boldsymbol{P}{n+1,n}=\boldsymbol{F}\boldsymbol{P}{n,n}\boldsymbol{F}^T+\boldsymbol{Q} ]
- Im Beispiel wird für die zufällige Beschleunigung eine Standardabweichung von (\sigma_a=0.2m/s^2) angenommen
- Die Varianz beträgt (\sigma_a^2=0.04m^2/s^4)
- Bei (\Delta t=5s) lautet die Prozessrauschmatrix wie folgt
[ \boldsymbol{Q}
\left[\begin{matrix}6.25&2.5\2.5&1\\end{matrix}\right] ]
- Die Vorhersagekovarianz nach Hinzufügen des Prozessrauschens lautet
[ \boldsymbol{P}_{1,0}
\left[\begin{matrix}28.5&3.75\3.75&1.25\\end{matrix}\right] ]
Update-Phase: Kombination von Messung und Vorhersage
- Bei (t_1) lautet der zweite Messwert wie folgt
[ \boldsymbol{z}_1= \left[\begin{matrix}11{,}020\202\\end{matrix}\right] ]
- Diese Messung hat wegen einer starken Rauschspitze ein niedrigeres Signal-Rausch-Verhältnis als die erste Messung und eine größere Unsicherheit
- Die Standardabweichung der Entfernungsmessung beträgt (6m)
- Die Standardabweichung der Geschwindigkeitsmessung beträgt (1.5m/s)
- Die Messkovarianzmatrix lautet wie folgt
[ \boldsymbol{R}_1=\left[\begin{matrix}36&0\0&2.25\\end{matrix}\right] ]
- Bei (t_1) stehen sowohl der im vorherigen Schritt berechnete vorhergesagte Zustand als auch die neue Messung zur Verfügung
- Die Diagonalelemente der Vorhersagekovarianz (\boldsymbol{P}_{1,0}) sind (28.5), (1.25)
- Die Diagonalelemente der Messkovarianz (\boldsymbol{R}_1) sind (36), (2.25)
- In diesem Fall ist die Vorhersageunsicherheit kleiner als die Messunsicherheit
- Der Kalman-Filter übernimmt die neue Messung weder einfach unverändert noch hält er ausschließlich an der Vorhersage fest
- Er kombiniert Vorhersage und Messung als gewichteten Mittelwert
- Der Seite mit der geringeren Unsicherheit wird ein größeres Gewicht gegeben
- Die eindimensionale Form der Kombination lautet wie folgt
[ \hat{x}{1,1}=K_1z_1+(1-K_1)\hat{x}{1,0} ]
- (K_1) ist der Kalman Gain und bestimmt, wie stark Messung und Vorhersage gewichtet werden
- Solange die Modellannahmen zutreffen, minimiert er die Unsicherheit der aktualisierten Schätzung
Zustandsupdate und Innovation
- Die Gleichung für das Zustandsupdate in Matrixform lautet wie folgt
[ \hat{\boldsymbol{x}}_{1,1}
\hat{\boldsymbol{x}}_{1,0} + \boldsymbol{K}_1(\boldsymbol{z}1-\hat{\boldsymbol{x}}{1,0}) ]
- Im Allgemeinen müssen Messwert und Systemzustand nicht dieselbe physikalische Größe darstellen
- Ein digitales Thermometer misst ein elektrisches Signal, während der Systemzustand die Temperatur sein kann
- In diesem Fall ist eine Beobachtungsmatrix (\boldsymbol{H}) nötig, die den vorhergesagten Zustand in die Messdomäne transformiert
- Die allgemeine Gleichung für das Zustandsupdate lautet
[ \hat{\boldsymbol{x}}_{1,1}
\hat{\boldsymbol{x}}_{1,0} + \boldsymbol{K}_1(\boldsymbol{z}1-\boldsymbol{H}\hat{\boldsymbol{x}}{1,0}) ]
- (\boldsymbol{z}1-\boldsymbol{H}\hat{\boldsymbol{x}}{1,0}) ist die Innovation oder das Residuum und stellt die neue Information dar
- Im Beispiel sind Zustand und Messung jeweils Entfernung und Geschwindigkeit, daher ist (\boldsymbol{H}) die Einheitsmatrix
Berechnung des Kalman Gain
- Der eindimensionale Kalman Gain lautet
[ K_n=\frac{p_{n,n-1}}{p_{n,n-1}+r_n} ]
- (p_{n,n-1}) ist die Varianz des vorhergesagten Zustands
- (r_n) ist die Messvarianz
- Beim multivariaten Kalman-Filter wird der Kalman Gain zu einer Matrix und lautet wie folgt
[ \boldsymbol{K}n= \boldsymbol{P}{n,n-1}\boldsymbol{H}^T \left( \boldsymbol{H}\boldsymbol{P}_{n,n-1}\boldsymbol{H}^T+\boldsymbol{R}_n \right)^{-1} ]
- Der im Beispiel berechnete Kalman Gain bei (t_1) lautet
[ \boldsymbol{K}_1= \left[\begin{matrix}0.4048&0.6377\0.0399&0.3144\\end{matrix}\right] ]
- Die Matrixinverse kann in MATLAB mit
inv(A)oder in Python mitnumpy.linalg.inv(A)berechnet werden- In realen Implementierungen ist es in der Regel besser, statt einer expliziten Inversen ein lineares Gleichungssystem direkt zu lösen, etwa mit
A\bin MATLAB odernumpy.linalg.solve(A, b)in Python
- In realen Implementierungen ist es in der Regel besser, statt einer expliziten Inversen ein lineares Gleichungssystem direkt zu lösen, etwa mit
Update-Ergebnis und Verringerung der Kovarianz
- Im Beispiel lautet die Innovation wie folgt
[ \boldsymbol{z}1-\hat{\boldsymbol{x}}{1,0}
\left[\begin{matrix}20\2\\end{matrix}\right] ]
- Die nach Anwendung des Kalman Gain erhaltene Korrektur lautet
[ \boldsymbol{K}_1 \left[\begin{matrix}20\2\\end{matrix}\right]
\left[\begin{matrix}9.37\1.43\\end{matrix}\right] ]
- Die aktualisierte Zustandsschätzung lautet wie folgt
[ \hat{\boldsymbol{x}}_{1,1}
\left[\begin{matrix}11{,}009.37\201.43\\end{matrix}\right] ]
- Für das multivariate Kovarianzupdate wird häufig die Joseph-Form verwendet
[ \boldsymbol{P}_{n,n}
(\boldsymbol{I}-\boldsymbol{K}n\boldsymbol{H}) \boldsymbol{P}{n,n-1} (\boldsymbol{I}-\boldsymbol{K}_n\boldsymbol{H})^T + \boldsymbol{K}_n\boldsymbol{R}_n\boldsymbol{K}_n^T ]
- In der Literatur erscheint häufig auch die vereinfachte Form
[ \boldsymbol{P}_{n,n}
(\boldsymbol{I}-\boldsymbol{K}n\boldsymbol{H}) \boldsymbol{P}{n,n-1} ]
- Bei exakter Arithmetik liefern beide Formen dasselbe Ergebnis
- In Computerimplementierungen ist die Joseph-Form in der Regel numerisch stabiler
- Im Beispiel wird das vereinfachte Kovarianzupdate verwendet, woraus sich folgendes Ergebnis ergibt
[ \boldsymbol{P}_{1,1}
\left[\begin{matrix}14.57&1.43\1.43&0.71\\end{matrix}\right] ]
- Die Unsicherheit der aktualisierten Schätzung ist geringer als die Vorhersageunsicherheit und die Messunsicherheit
- Die Diagonalelemente der Vorhersagekovarianz sind (28.5), (1.25)
- Die Diagonalelemente der Messkovarianz sind (36), (2.25)
- Die Diagonalelemente der Update-Kovarianz sind (14.57), (0.71)
- Theoretisch reduziert neue Information die Schätzunsicherheit, selbst wenn sie selbst eine große Unsicherheit aufweist
- In realen Systemen kann es Fälle geben, in denen schwer vertrauenswürdige Messungen verworfen werden müssen
Nächste Vorhersage und Wiederholungsschleife
- Die Vorhersagephase von Iteration 1 wird auf die gleiche Weise durchgeführt wie in Iteration 0
- Allerdings sind der Startpunkt nun das aktualisierte (\hat{\boldsymbol{x}}{1,1}) und (\boldsymbol{P}{1,1})
- Die Zustandsvorhersage lautet wie folgt
[ \hat{\boldsymbol{x}}_{2,1}
\boldsymbol{F}\hat{\boldsymbol{x}}_{1,1}
\left[\begin{matrix}12,016.5\201.43\\end{matrix}\right] ]
- Die Kovarianzvorhersage lautet wie folgt
[ \boldsymbol{P}_{2,1}
\boldsymbol{F}\boldsymbol{P}_{1,1}\boldsymbol{F}^\top+\boldsymbol{Q}
\left[\begin{matrix}52.86&7.47\7.47&1.71\\end{matrix}\right] ]
- Wenn ohne neue Messung Zeit vergeht, steigen beide Varianzen wieder an
- Die Geschwindigkeitsunsicherheit erhöht die Entfernungsunsicherheit zusätzlich, sodass die Entfernungsvarianz schneller zunimmt
- Der Kalman-Filter funktioniert so, dass er zu Beginn einmal initialisiert wird und anschließend fortlaufend Vorhersage und Update wiederholt
- Die Vorhersage schreibt die aktuelle Schätzung und Kovarianz mit dem Zustandsübergangsmodell zum nächsten Zeitpunkt fort
- Das Update kombiniert eine neue Messung und die Vorhersage mithilfe des Kalman Gain und aktualisiert so den aktuellen Zustand und die Unsicherheit
1 Kommentare
Meinungen auf Hacker News
Jedes Mal, wenn ich ein „Tutorial für Einsteiger“ sehe, habe ich Hoffnungen, bin aber meistens enttäuscht, und diesmal war es keine Ausnahme.
Am Anfang ist es gut, aber dann wird fast immer irgendein Konzept oder zentraler Begriff übersprungen, ohne ihn ausreichend zu erklären. Hier bin ich bei der Stelle ausgestiegen: „Zufallsvariablen werden durch Wahrscheinlichkeitsdichtefunktionen beschrieben, und Wahrscheinlichkeitsdichtefunktionen werden durch Momente charakterisiert. Die Momente von Wahrscheinlichkeitswerten sind die Erwartungswerte von Potenzen der Zufallsvariablen.“
Ich weiß nicht, ob damit der Erwartungswert des Exponenten eines Wahrscheinlichkeitswerts gemeint ist, der Erwartungswert irgendeiner Potenz eines Wahrscheinlichkeitswerts, oder warum ausgerechnet eine Potenz etwas Besonderes sein soll und nicht einfach der Wahrscheinlichkeitswert selbst. Es ist frustrierend, weil es sich so anfühlt, als würden die Autoren mitten im Gedankengang plötzlich aufgeben, es einfach zu erklären, oder als hätten sie die zugrunde liegenden Konzepte selbst nie richtig verstanden und könnten sie deshalb anderen nicht erklären. Bei Udemy kann man dem Dozenten wenigstens Fragen stellen, aber bei Buchautoren gibt es keinen Weg, eine Antwort zu bekommen.
Wenn ein Autor auch nur eine Erklärung nicht ausreichend liefert, bricht das Ganze zusammen; eine Feedback-Schleife hilft enorm. Wenn es keine gibt, muss man am Ende selbst die Verantwortung übernehmen und unbekannte Wörter und Formulierungen nachschlagen. Man sucht Ausdrücke, die man nicht ausreichend versteht, etwa „Zufallsvariable“ oder „Wahrscheinlichkeitsdichtefunktion“, und ergänzt sie mit Wikipedia, ChatGPT, Lehrbüchern, Videos usw. Dieser Prozess ist rekursiv, sodass wieder unbekannte Konzepte auftauchen, aber man arbeitet sich einfach weiter nach unten. Der Wert eines Tutors liegt auch darin, diese Tiefensuche gut zu begleiten. In einem neuen Fachgebiet ist es normal, dass man mehr Zeit damit verbringt, Hintergrundwissen aufzufüllen, als den eigentlichen Text zu lesen; beim nächsten ähnlichen Thema geht es dann schneller.
Es ist fast merkwürdig, dass ich ein so grundlegendes Konzept trotz Bachelor- und Graduiertenstudium nicht verinnerlicht habe.
Deshalb vergisst man die Dinge, die man selbst für selbstverständlich hält. Bei den Videos von 3blue1brown empfinde ich ein ähnliches Problem. Die Videos sind hübsch, aber daraus entsteht kein Verständnis; Leute, die es schon wissen, nicken, weil sie ein vertrautes Konzept sauber dargestellt sehen, aber für jemanden wie mich wirken die Voraussetzungen viel zu zahlreich.
Um den Kalman-Filter zu verstehen, muss man zunächst die Grundlagen der Wahrscheinlichkeit und die Bedeutung der Gauß-Verteilung kennen. Die mathematische Herleitung nimmt an, dass alle relevanten Wahrscheinlichkeitsverteilungen Gauß-Verteilungen sind, und eine Gauß-Verteilung ist eindeutig bestimmt, wenn man ihr erstes und zweites Moment kennt. Letztlich lässt sich die Einführung der Momente nicht vermeiden, und danach folgt ziemlich harte Mathematik. Der Kalman-Filter ist kein einfaches Thema; Rudolf Kalman sagte in einem Interview, dass die Mondlandung der USA ohne seinen Filter nicht möglich gewesen wäre.
Man kann mit einem einfachen univariaten Fall beginnen, ihn anpassen und verallgemeinern; deshalb habe ich das immer für eine gute Methode gehalten, den Kalman-Filter zu lehren.
Vor einigen Jahren habe ich eine kurze Vorlesungsreihe von Kalman gehört, und er betonte sehr nachdrücklich die Tugend, direkt mit Beobachtungsdaten zu arbeiten.
Er war der Ansicht, dass Verzerrungen entstehen, wenn man zuerst ein Modell annimmt und es dann an die Daten anpasst, und nannte als gutes Beispiel für dieses Prinzip Newtons Principia. Seine Erklärung war, dass Newton nicht nach einem Modell suchte, um Keplers Gesetze zu erklären, sondern mithilfe vor allem geometrischer Argumente aus Keplers Gesetzen das Gravitationsgesetz des inversen Quadrats herleitete. Er war ein ausgezeichneter Redner und hatte starke Meinungen; natürlich erklärte er auch die Idee des Kalman-Filters, aber da ich sie in meiner Arbeit nicht direkt einsetzen musste, habe ich die Details schon vor langer Zeit vergessen.
Ich habe tatsächlich mit Wissenschaftlern und Ingenieuren gearbeitet, die sehr komplexe und weithin bekannte Systeme ausgerollt haben, und solche Leute sind trendigen Algorithmen gegenüber meist skeptisch und beginnen normalerweise bei den ersten Prinzipien. In 90 % der Fälle reichte ein einfacher, gewöhnlicher linearer Kalman-Filter aus, manchmal sogar ohne Bewegungsmodell.
Kürzlich bat mich ein Freund, für ein Nebenprojekt eine Kalman-Filter-Implementierung zu bauen. Ich habe mehrere Materialien und diese Website gelesen, weiß aber immer noch nicht, wie ich es umsetzen soll.
Für mich wirkt alles wie „zeichne den Rest der Eule“. Ich wünschte, es gäbe Material, das es so erklärt, wie ein Programmierer es tun würde, also zum Beispiel mit Array-Iteration statt Sigma-Notation. Soweit ich es verstanden habe, wirkt ein Kalman-Filter wie ein gleitender Mittelwert von Position, Geschwindigkeit und vielleicht Beschleunigung, und diese drei Werte werden wohl genutzt, um den „tatsächlichen Wert“ zu schätzen statt des Werts, den der Sensor liefert.
Allerdings muss man zuerst die Mathematik aufschreiben, die die Dynamik beschreibt. Ein Kalman-Filter ist im Grunde die Anwendung des Satzes von Bayes auf eine bestimmte Systemdynamik: wiederholt wird angewendet, wie man bei einem Messwert die aktuelle Zustandsschätzung aktualisiert und wie die Systemdynamik nach dieser Messung bis zur nächsten Messung die Unsicherheit beeinflusst. Man braucht zuerst ein Dynamikmodell, das beschreibt, wie sich das verfolgte Objekt über die Zeit verändert. Ohne das ist es unvermeidlich, dass die Implementierung verwirrend wird. Wenn man zuerst etwas über Bayes-Filter oder Partikelfilter liest, hilft das, das Konzept auch ohne Matrizen zu verstehen. Die Aussage, man könne Softwareentwickler sein, ohne Mathematik zu können, frustriert mich immer wieder: Für das Erstellen von Webseiten mag das stimmen, aber je mehr Mathematik man kennt, desto größer ist der Bereich an Problemen, die man modellieren und lösen kann.
Wichtig ist, dass man auf Grundlage dieses Zustands schätzt und nach Erhalt einer Messung beide Informationen nutzt, um den nächsten Zustand iterativ anzupassen. Wenn man die Formeln verstanden hat, ist das eigentliche Programmieren ziemlich einfach. Dieses Material könnte hilfreich sein: http://bilgin.esme.org/BitsAndBytes/KalmanFilterforDummies
Externe Steuerung und Prozessrauschen können hinzukommen, und der interne Zustand wird als Vektor von Werten dargestellt. Außerdem braucht man ein lineares Modell dafür, wie der interne Zustand in Beobachtungen transformiert wird, sowie Beobachtungsrauschen.
x ist der Modellzustand, F ist das lineare Zustandsübergangsmodell
x(t+1) = F x(t), Q ist die Kovarianzmatrix des Prozessrauschens, sodass tatsächlichx(t+1) = F x(t) + N(0,Q)gilt, H ist das lineare Beobachtungsmodell, R ist die Kovarianzmatrix des Beobachtungsrauschens, und u sowie B sind ein optionaler externer Steuervektor und die Art, wie er wirkt.N(0,Q)ist eine Normalverteilung mit Mittelwert 0 und Kovarianz Q.Bei einem bewegten Objekt könnte der Modellzustand zum Beispiel aus Position x und Geschwindigkeit v bestehen. Mit Radar oder Ähnlichem beobachtet man normalerweise nur die Position und kann die aktuelle Geschwindigkeit nicht beobachten, daher extrahiert das Beobachtungsmodell nur die Position. Bevor man einen Kalman-Filter einsetzt, braucht man zuerst eine solche „Eule“, und je nach Prozess muss man sie selbst festlegen. Der Kalman-Filter sagt einem, wie man den tatsächlichen Zustandsvektor zu jedem Zeitpunkt optimal schätzt, wenn sowohl das Zustandsübergangsmodell als auch die Beobachtungen Rauschen enthalten. Viele Tutorials vermischen die Teile des gewählten Prozessmodells mit den Teilen des Kalman-Filters, was verwirrend ist; und in zu kleinen Beispielen wie einem eindimensionalen konstanten Modell verschwindet das Dynamikmodell in den Gleichungen, was die Verwirrung eher vergrößert.
Die ersten Kapitel behandeln Kalman-Filter und Informationsfilter sehr gut.
Wenn man weiß, dass Sensormessungen verrauscht sind, mittelt man mehrere Samples, um eine Schätzung zu erhalten, die näher am tatsächlichen Wert liegt; wenn man das Ausmaß des Sensorrauschens kennt, bekommt man auch ein Gefühl dafür, über wie viele Samples man mitteln sollte. Hier kann man sich vorstellen, dass alle Sensorwerte oder abgeleiteten Werte als Gauß-Verteilungen geschätzt werden, die durch Mittelwert und Varianz parametrisiert sind.
In einem physikalischen System mit Beschleunigung, Geschwindigkeit und Position gilt: Wenn zum Zeitpunkt t die Position p und die Geschwindigkeit v ist, dann ist die Position bei t+dt ungefähr
p+(v*dt). Mit einer Beschleunigungsschätzung kann man auch die Geschwindigkeit aktualisieren, und wenn es sich um ein gesteuertes System handelt, kann man mit der befohlenen Kraft auch das Beschleunigungsmodell aktualisieren. Da die Anfangsschätzung jedoch unsicher ist, wächst die Unsicherheit immer weiter, wenn man nur dieses Prozessmodell fortschreibt, bis es schließlich nutzlos wird.Der Kalman-Filter ist eine Methode, Sensorinformationen und Prozessmodell zu kombinieren, um die interessierenden Größen besser zu schätzen, als es mit nur einem von beiden möglich wäre. In jedem Zeitschritt sagt man auf Basis der vorherigen Zustandsschätzung mit dem Prozessmodell den Zustand voraus und aktualisiert mit der aktuellen Sensormessung Mittelwert und Unsicherheit. Beim grundlegenden Kalman-Filter nimmt man an, dass das Prozessmodell linear ist und alle Schätzungen einfache Gauß-Verteilungen sind; dann legt ein multiplikativer Faktor namens Kalman-Gain fest, wie stark man Modell bzw. Sensor vertraut.
Eine weitere Playlist mit einem Schritt-für-Schritt-Video-Tutorial zum Kalman-Filter: https://www.youtube.com/watch?v=CaCcOwJPytQ&list=PLX2gX-ftPV...
Sobald man die Intuition dafür hat, ist der Kalman-Filter wirklich interessant; Partikelfilter sind ebenfalls spannend zu behandeln und zu visualisieren.
Ich besitze dieses Buch und habe es bei realen Problemen recht erfolgreich eingesetzt.
Auch nach mehrmaligem Lesen gibt es ein paar Stellen, denen man nur schwer folgen kann, aber insgesamt ist es ziemlich gut.
Dazu noch ein guter Artikel: Is the Kalman filter a low-pass filter? Sometimes!
https://jbconsulting.substack.com/p/is-the-kalman-filter-jus...
Ich habe ihn verwendet, um das Zittern virtueller Kamerabewegungen in einem Video zu reduzieren, das in Echtzeit um Gesichter herum zuschneidet. Dabei habe ich den Stream erkannter Gesichtspositionen an einen Kalman-Filter-Worker geschickt und einen stabilen Stream von Kamerapositionen zurückbekommen.
Wenn Rechenressourcen knapp sind, ist der Kalman-Filter hervorragend, aber persönlich bevorzuge ich neuere und fortgeschrittenere Modelle wie Partikelfilter.
Der Vorteil von Partikelfiltern ist, dass sie komplexe Situationen mit nichtlinearer Physik und nicht-gaußschen Verteilungen handhaben können. Beim GPS eines Fahrzeugs kann man zum Beispiel auf Basis der jüngsten Abbiegehistorie mithilfe einer Straßenkarte unmögliche Positionen ausschließen. Ein Gauß-Filter kann so etwas nicht und erzeugt am Ende nur einen unscharfen Klumpen, der mehrere Häuserblocks abdeckt.
Außerdem würde mich interessieren, ob es neben Partikelfiltern noch neuere oder fortgeschrittenere Modelle gibt, die man für Offline-Verarbeitung empfehlen kann.
2007 war ich bei einem Werbetechnologie-Unternehmen, und der CEO sowie das Forschungsteam waren regelrecht auf Kalman-Filter fixiert, um Werbekampagnen in den Netzwerken von Google und MSN zu optimieren.
Soweit ich mich erinnere, funktionierte das bis zu einem gewissen Grad, aber heute kann ich die Patentanmeldung nicht mehr finden, und Zeta und Walmart haben die Technologie gekauft.
Erklärungen zu Kalman-Filtern fangen fast immer ungefähr so an: „Als intuitives Beispiel stellen wir uns einen Thermostat vor. Verstanden? Gut! Um es jetzt noch intuitiver zu machen, schauen wir uns fortgeschrittene lineare Algebra an.“
Ich frage mich, ob jemand schon einmal eine Erklärung zu Kalman-Filtern gesehen hat, die nicht direkt in die Mathematik springt.
Wenn du mit geschlossenen Augen auf eine Wand zugehst, wirst du mit der Zeit immer unsicherer über deine eigene Position; sobald deine Finger die Wand berühren, steigt deine Sicherheit über die Position plötzlich stark an. Der erste Teil ist der Vorhersageschritt, der zweite das Mess-Update. Lineare Algebra ist nur die Methode, mit der man diese Gewichte in linearen dynamischen Systemen mit gaußschem Rauschen berechnet.
Kalman-Filter treffen statistische Annahmen wie Normalverteilungen, daher sollte man zumindest Statistik sowie Mittelwert- und Kovarianzmatrizen kennen. Wenn das passt, sollte man bis vor Abschnitt 4 von https://sites.ualberta.ca/~dwiens/stat679/meinhold&singpurwa... folgen können. Ab Abschnitt 4 werden die für die tatsächliche Implementierung nötigen mathematischen Rechnungen durchgezogen; viel zusätzliches Verständnis bringt das nicht.
Alles zuerst eindimensional zu behandeln und danach auf mehrdimensionale Probleme zu erweitern, hilft definitiv, das Konzept zu fassen. Die Playlist scheint hier zu sein: https://youtube.com/playlist?list=PLAwxTw4SYaPkCSYXw6-a_aAoX...
Der Teil zu Kalman-Filtern beginnt beim Video „Tracking Intro - Artificial Intelligence for Robotics“. Der kostenlose Kurs scheint auch hier zu sein, aber für den Zugriff braucht man wohl einen Login: https://www.udacity.com/course/intro-to-artificial-intellige...
Ich kenne mich mit Kalman nicht gut aus und habe die Einführungsartikel auf dieser Website gelesen, aber es hat bei mir nicht richtig Klick gemacht.
Als ich über die Beispielgrafiken nachdachte, wirkte es für mich eher wie ein exponentieller gleitender Durchschnitt, der deutlich leichter zu verstehen ist. Als ich bei Google nach Vergleichen suchte, hieß es auf Stats Stack Exchange, dass EMA bei „Random Walk + Rauschen“ genauso gut sei wie Kalman; und eine Arbeit von Joseph J. LaViola von der Brown University aus dem Jahr 2003 zeigte offenbar, dass ein Algorithmus zur doppelten exponentiellen Glättung bei gleicher Qualität wie Kalman und erweiterter Kalman-Filter 135-mal schneller und einfacher ist.
Da doppelte exponentielle Glättung viel leichter zu verstehen ist als Kalman, werde ich — vorausgesetzt, LaViolas Arbeit stimmt — keine weitere Mühe darauf verwenden, Kalman zu verstehen.