Kalman Filter

Es gibt viele verschiedene Artikel zum Kalman-Filter, aber es ist schwierig, den zu finden, der eine Erklärung enthält, aus der alle Filterformeln stammen. Ich denke, dass diese Wissenschaft ohne Verständnis davon völlig unverständlich wird. In diesem Artikel werde ich versuchen, alles auf einfache Weise zu erklären.

Der Kalman-Filter ist ein sehr leistungsfähiges Werkzeug zum Filtern verschiedener Arten von Daten. Die Hauptidee dahinter ist, dass man Informationen über den physischen Prozess verwenden sollte. Wenn Sie beispielsweise Daten vom Tachometer eines Autos filtern, haben Sie aufgrund seiner Trägheit das Recht, eine große Geschwindigkeitsabweichung als Messfehler zu behandeln. Der Kalman-Filter ist auch deshalb interessant, weil er in gewisser Weise der beste Filter ist. Wir werden genau diskutieren, was es bedeutet. Am Ende des Artikels werde ich zeigen, wie es möglich ist, die Formeln zu vereinfachen.

Vorbereitungen

Lassen Sie uns zunächst einige Definitionen und Fakten aus der Wahrscheinlichkeitstheorie auswendig lernen.

Zufällige Variable

Wenn man sagt, dass es eine Zufallsvariable gibt $$$\ xi$ bedeutet dies, dass zufällige Werte angenommen werden können. Unterschiedliche Werte haben unterschiedliche Wahrscheinlichkeiten. Wenn zum Beispiel jemand einen Würfel fallen lässt, ist der Wertesatz diskret $$$\ {1,2,3,4,5,6 \}$ . Wenn Sie sich mit einer Geschwindigkeit bewegen, mit der sich Partikel bewegen, sollten Sie natürlich mit einem kontinuierlichen Satz von Werten arbeiten. Werte, die nach jedem Experiment (Messung) herauskommen, würden wir mit bezeichnen $$$x_1, x_2, ...$ , aber manchmal verwenden wir den gleichen Buchstaben wie für eine Zufallsvariable $$$\ xi$ . Bei einem kontinuierlichen Satz von Werten wird eine Zufallsvariable durch ihre Wahrscheinlichkeitsdichtefunktion charakterisiert $$$\ rho (x)$ . Diese Funktion zeigt eine Wahrscheinlichkeit, dass die Zufallsvariable in eine kleine Nachbarschaft fällt $$$dx$ des Punktes $$$x$ . Wie wir auf dem Bild sehen können, entspricht diese Wahrscheinlichkeit der Fläche des schraffierten Rechtecks ​​unter dem Diagramm $$$\ rho (x) dx$ .

Sehr oft in unserem Leben haben Zufallsvariablen die Gauß-Verteilung, wenn die Wahrscheinlichkeitsdichte ist $$$\ rho (x) \ sim e ^ {- \ frac {(x- \ mu) ^ 2} {2 \ sigma ^ 2}}$ .

Wir können sehen, dass die Glockenform funktioniert $$$\ rho (x)$ ist am Punkt zentriert $$$\ mu$ und seine charakteristische Breite ist ungefähr $$$\ sigma$ .
Da es sich um die Gaußsche Verteilung handelt, wäre es eine Sünde, nicht zu erwähnen, woher sie kommt. Sowie die Nummer $$$e$ und $$$\ pi$ sind fest in der Mathematik verankert und können an den unerwartetsten Stellen gefunden werden, so dass die Gaußsche Verteilung tiefe Wurzeln in der Wahrscheinlichkeitstheorie hat. Die folgende bemerkenswerte Aussage erklärt teilweise das Vorhandensein der Gauß-Verteilung in vielen Prozessen:
Lassen Sie eine Zufallsvariable $$$\ xi$ hat eine willkürliche Verteilung (tatsächlich gibt es einige Einschränkungen für die Willkür, aber sie sind überhaupt nicht einschränkend). Lassen Sie uns durchführen $$$n$ experimentiert und berechnet eine Summe $$$\ xi_1 + ... + \ xi_n$ von gefallenen Werten. Lassen Sie uns viele Experimente machen. Es ist klar, dass wir jedes Mal einen anderen Wert der Summe erhalten. Mit anderen Worten, diese Summe ist eine Zufallsvariable mit einem eigenen Verteilungsgesetz. Es stellt sich heraus, dass für ausreichend groß $$$n$ Das Verteilungsgesetz dieser Summe tendiert zu einer Gaußschen Verteilung (übrigens wächst die charakteristische Breite einer Glocke wie $$$\ sqrt n$ . Lesen Sie mehr in der Wikipedia: Zentraler Grenzwertsatz . Im wirklichen Leben gibt es viele Werte, die eine Summe einer großen Anzahl unabhängiger und identisch verteilter Zufallsvariablen sind. Diese Werte haben also eine Gauß-Verteilung.

Bedeutungswert

Per Definition ist ein Mittelwert einer Zufallsvariablen ein Wert, den wir in einer Grenze erhalten, wenn wir mehr und mehr Experimente durchführen und einen Mittelwert gefallener Werte berechnen. Ein Mittelwert wird auf verschiedene Arten bezeichnet: Mathematiker bezeichnen mit $$$E \ xi$ (Erwartung), Physiker bezeichnen es mit $$$\ overline {\ xi}$ oder $$$<\ xi>$ . Wir werden es so bezeichnen wie Mathematiker.

Zum Beispiel ein Mittelwert der Gaußschen Verteilung $$$\ rho (x) \ sim e ^ {- \ frac {(x- \ mu) ^ 2} {2 \ sigma ^ 2}}$ ist gleich $$$\ mu$ .

Varianz

Bei der Gaußschen Verteilung sehen wir deutlich, dass die Zufallsvariable dazu neigt, in einen bestimmten Bereich ihres Mittelwerts zu fallen $$$\ mu$ . Lassen Sie uns die Gaußsche Verteilung noch einmal genießen:

Auf dem Bild kann man sehen, dass eine charakteristische Breite eines Bereichs, in dem die Werte meistens fallen, ist $$$\ sigma$ . Wie können wir diese Breite für eine beliebige Zufallsvariable schätzen? Wir können einen Graphen seiner Wahrscheinlichkeitsdichtefunktion zeichnen und nur den charakteristischen Bereich visuell bewerten. Es wäre jedoch besser, einen genauen algebraischen Weg für diese Bewertung zu wählen. Wir können eine mittlere Abweichungslänge vom Mittelwert finden: $$$E | \ xi-E \ xi |$ . Dieser Wert ist eine gute Schätzung einer charakteristischen Abweichung von $$$\ xi$ . Wir wissen jedoch sehr gut, wie problematisch es ist, Absolutwerte in Formeln zu verwenden, weshalb diese Formel in der Praxis selten verwendet wird.

Ein einfacherer Ansatz (aus Sicht der Berechnung einfach) ist die Berechnung $$$E (\ xi-E \ xi) ^ 2$ .

Dieser Wert wird als Varianz bezeichnet und mit bezeichnet $$$\ sigma_ \ xi ^ 2$ . Die quadratische Wurzel der Varianz ist eine gute Schätzung der charakteristischen Abweichung der Zufallsvariablen. Es wird die Standardabweichung genannt.

Zum Beispiel kann man das für die Gaußsche Verteilung berechnen $$$\ rho (x) \ sim e ^ {- \ frac {(x- \ mu) ^ 2} {2 \ sigma ^ 2}}$ die Varianz ist gleich $$$\ sigma ^ 2$ somit ist die Standardabweichung $$$\ sigma$ . Dieses Ergebnis entspricht wirklich unserer geometrischen Intuition. Tatsächlich ist hier ein kleiner Betrug versteckt. Tatsächlich sehen Sie in einer Definition der Gauß-Verteilung die Zahl $$$2$ in einem Nenner des Ausdrucks $$$- \ frac {(x- \ mu) ^ 2} {2 \ sigma ^ 2}$ . Das hier $$$2$ steht dort zweckmäßig für die Standardabweichung $$$\ sigma_ \ xi$ genau gleich sein $$$\ sigma$ . Die Formel der Gauß-Verteilung ist also so geschrieben, dass man bedenkt, dass man ihre Standardabweichung berechnen würde.

Unabhängige Zufallsvariablen

Zufällige Variablen können voneinander abhängen oder nicht. Stellen Sie sich vor, Sie werfen eine Nadel auf den Boden und messen die Koordinaten ihrer beiden Enden. Diese beiden Koordinaten sind Zufallsvariablen, aber sie hängen voneinander ab, da ein Abstand zwischen ihnen immer gleich der Länge der Nadel sein sollte. Zufallsvariablen sind unabhängig voneinander, wenn die fallenden Ergebnisse der ersten nicht von den Ergebnissen der zweiten abhängen. Für zwei unabhängige Variablen $$$\ xi_1$ und $$$\ xi_2$ Der Mittelwert ihres Produkts ist gleich dem Produkt ihres Mittelwerts: $$$E (\ xi_1 \ cdot \ xi_2) = E \ xi_1 \ cdot \ xi_2$

Kalman-Filter

Problemm Aussage

Bezeichne mit $$$x_k$ Ein Wert, den wir messen und dann filtern wollen. Dies kann eine Koordinate, Geschwindigkeit, Beschleunigung, Luftfeuchtigkeit, Temperatur, Druck usw. Sein

Beginnen wir mit einem einfachen Beispiel, das uns zur Formulierung des allgemeinen Problems führt. Stellen Sie sich vor, Sie haben ein Spielzeugauto mit Funksteuerung, das nur vorwärts und rückwärts fahren kann. In Kenntnis seiner Masse, Form und anderer Parameter des Systems haben wir berechnet, wie sich ein steuernder Joystick auf die Geschwindigkeit eines Autos auswirkt $$$v_k$ .


Die Koordinate des Autos würde nach folgender Formel

$$

$$x_ {k + 1} = x_k + v_kdt$$

Im wirklichen Leben können wir nicht, wir können keine genaue Formel für die Koordinate haben, da einige kleine Störungen auf das Auto wirken, wie Wind, Unebenheiten, Steine ​​auf der Straße, so dass die tatsächliche Geschwindigkeit des Autos von der berechneten abweicht . Also fügen wir eine Zufallsvariable hinzu $$$\ xi_k$ auf der rechten Seite der letzten Gleichung:

$$

$$x_ {k + 1} = x_k + v_kdt + \ xi_k$$

Wir haben auch einen GPS-Sensor am Auto, der versucht, die Koordinate des Autos zu messen $$$x_k$ . Natürlich gibt es einen Fehler bei dieser Messung, bei der es sich um eine Zufallsvariable handelt $$$\ eta_k$ . Vom Sensor würden wir also falsche Daten erhalten:

$$

$$z_k = x_k + \ eta_k$$

Unser Ziel ist es, eine gute Schätzung für die wahre Koordinate zu finden $$$x_k$ , die Daten eines falschen Sensors kennen $$$z_k$ . Diese gute Schätzung werden wir mit bezeichnen $$$x ^ {opt}$ .
Im Allgemeinen die Koordinate $$$x_k$ may steht für einen beliebigen Wert (Temperatur, Luftfeuchtigkeit, ...) und das Kontrollelement, mit dem wir bezeichnen würden $$$u_k$ (im Beispiel mit einem Auto $$$u_k = v_k \ cdot dt$ ) Die Gleichungen für die Koordinaten- und Sensormessungen wären wie folgt:

(1)

Lassen Sie uns diskutieren, was wir in diesen Gleichungen wissen.

• $$$u_k$ ist ein bekannter Wert, der eine Entwicklung des Systems steuert. Wir kennen es aus dem Modell des Systems.
• Die Zufallsvariable $$$\ xi$ repräsentiert den Fehler im Modell des Systems und der Zufallsvariablen $$$\ eta$ ist ein Sensorfehler. Ihre Verteilungsgesetze hängen nicht von der Zeit ab (vom Iterationsindex $$$k$ )
• Die Fehlermittel sind gleich Null: $$$E \ eta_k = E \ xi_k = 0$ .
• Wir kennen möglicherweise kein Verteilungsgesetz der Zufallsvariablen, aber wir kennen ihre Varianzen $$$\ sigma_ \ xi$ und $$$\ sigma_ \ eta$ . Beachten Sie, dass die Abweichungen nicht von der Zeit abhängen $$$k$ ) da die entsprechenden Vertriebsgesetze auch nicht.
• Wir nehmen an, dass alle zufälligen Fehler unabhängig voneinander sind: der Fehler zu der Zeit $$$k$ hängt nicht vom jeweiligen Fehler ab $$$k ’$ .

Beachten Sie, dass ein Filtrationsproblem kein Glättungsproblem ist. Unser Ziel ist es nicht, die Daten eines Sensors zu glätten, sondern nur den Wert zu erhalten, der so nah wie möglich an der realen Koordinate liegt $$$x_k$ .

Kalman-Algorithmus

Wir würden eine Induktion verwenden. Stellen Sie sich das beim Schritt vor $$$k$ Wir haben den Wert des gefilterten Sensors bereits gefunden $$$x ^ {opt}$ Dies ist eine gute Schätzung der realen Koordinate $$$x_k$ . Denken Sie daran, dass wir die Gleichung kennen, die die reale Koordinate steuert:

$$

$$x_ {k + 1} = x_k + u_k + \ xi_k$$

Bevor wir den Wert des Sensors erhalten, können wir daher angeben, dass er den Wert anzeigt, der nahe daran liegt $$$x ^ {opt} + u_k$ . Leider können wir bisher nichts genaueres sagen. Aber beim Schritt $$$k + 1$ Wir hätten einen ungenauen Messwert vom Sensor $$$z_ {k + 1}$ .
Die Idee von Kalman ist die folgende. Um die beste Schätzung der realen Koordinate zu erhalten $$$x_ {k + 1}$ Wir sollten eine goldene Mitte zwischen dem Ablesen des nicht präzisen Sensors erhalten $$$z_ {k + 1}$ und $$$x ^ {opt} + u_k$ - unsere Vorhersage, was wir auf dem Sensor erwartet haben. Wir werden ein Gewicht geben $$$K$ auf den Wert des Sensors und $$$(1-K)$ auf den vorhergesagten Wert:

$$

$$x ^ {opt} _ {k + 1} = K \ cdot z_ {k + 1} + (1-K) \ cdot (x_k ^ {opt} + u_k)$$

Der Koeffizient $$$K$ wird als Kalman-Koeffizient bezeichnet. Es hängt vom Iterationsindex ab, und genau genommen sollten wir lieber schreiben $$$K_ {k + 1}$ . Aber um Formeln in einer schönen Form zu halten, würden wir den Index von weglassen $$$K$ .
Wir sollten den Kalman-Koeffizienten so wählen, wie es die geschätzte Koordinate ist $$$x ^ {opt} _ {k + 1}$ wäre so nah wie möglich an der realen Koordinate $$$x_ {k + 1}$ .
Wenn wir zum Beispiel wissen, dass unser Sensor sehr hochpräzise ist, würden wir auf seine Anzeige vertrauen und ihm ein großes Gewicht geben ( $$$K$ ist nah an eins). Wenn der Sensor umgekehrt überhaupt nicht präzise ist, würden wir uns auf unseren theoretisch vorhergesagten Wert verlassen $$$x ^ {opt} _k + u_k$ .
Im Allgemeinen sollten wir den Fehler unserer Schätzung minimieren:

$$

$$e_ {k + 1} = x_ {k + 1} -x ^ {opt} _ {k + 1}$$

Wir verwenden die Gleichungen (1) (die sich auf einem blauen Rahmen befinden), um die Gleichung für den Fehler neu zu schreiben:

$$

$$e_ {k + 1} = (1-K) (e_k + \ xi_k) - K \ eta_ {k + 1}$$

Nun ist es an der Zeit zu diskutieren, was bedeutet der Ausdruck "um den Fehler zu minimieren"? Wir wissen, dass der Fehler eine Zufallsvariable ist, daher nimmt er jedes Mal andere Werte an. Eigentlich gibt es keine eindeutige Antwort auf diese Frage. Ähnlich war es bei der Varianz einer Zufallsvariablen, als wir versuchten, die charakteristische Breite ihrer Wahrscheinlichkeitsdichtefunktion abzuschätzen. Wir würden also ein einfaches Kriterium wählen. Wir würden einen Mittelwert des Quadrats minimieren:

$$

$$E (e ^ 2_ {k + 1}) \ rightarrow min$$

Schreiben wir den letzten Ausdruck um:

$$

$$E (e ^ 2_ {k + 1}) = (1-K) ^ 2 (E_k ^ 2 + \ sigma ^ 2_ \ xi) + K ^ 2 \ sigma ^ 2_ \ eta$$

Der letzte Ausdruck nimmt seinen Minimalwert an, wenn seine Ableitung Null ist. Also wann:

$$

$$\ displaystyle K_ {k + 1} = \ frac {Ee ^ 2_k + \ sigma ^ 2_ \ xi} {Ee ^ 2_k + \ sigma ^ 2_ \ xi + \ sigma ^ 2_ \ eta}$$

Hier schreiben wir den Kalman-Koeffizienten mit seinem Index, daher betonen wir die Tatsache, dass dies vom Iterationsschritt abhängt. Wir ersetzen den mittleren quadratischen Fehler durch die Gleichung $$$E (e ^ 2_ {k + 1})$ der Kalman-Koeffizient $$$K_ {k + 1}$ die seinen Wert minimieren:

$$

$$\ displaystyle E (e ^ 2_ {k + 1}) = \ frac {\ sigma ^ 2_ \ eta (Ee ^ 2_k + \ sigma ^ 2_ \ xi)} {Ee ^ 2_k + \ sigma ^ 2_ \ xi + \ sigma ^ 2_ \ eta}$$

Also haben wir unser Problem gelöst. Wir haben die iterative Formel zur Berechnung des Kalman-Koeffizienten erhalten.

Beispiel

Auf dem Plot vom Anfang dieses Artikels befinden sich gefilterte Daten des fiktiven GPS-Sensors, die sich auf dem fiktiven Auto befinden und sich mit konstanter Beschleunigung bewegen $$$a$ .

$$

$$x_ {t + 1} = x_t + bei \ cdot dt + \ xi_t$$

Analyse

Wenn man sich anschaut, wie der Kalman-Koeffizient ist $$$K_k$ Änderungen gegenüber der Iteration $$$k$ ist zu sehen, dass es sich auf den bestimmten Wert stabilisiert $$$K_ {stab}$ . Wenn beispielsweise die quadratischen mittleren Fehler des Sensors und des Modells als zehn zu eins zueinander stehen, wäre die Darstellung der Kalman-Koeffizientenabhängigkeit vom Iterationsschritt wie folgt:


Im nächsten Beispiel würden wir diskutieren, wie dies unser Leben vereinfachen kann.

Zweites Beispiel

In der Praxis kommt es vor, dass wir vom physikalischen Modell fast nichts wissen, was wir filtern. Stellen Sie sich vor, Sie haben beschlossen, diese Messungen von Ihrem bevorzugten Beschleunigungsmesser zu filtern. Eigentlich weiß man nicht vorwärts, wie der Beschleunigungsmesser bewegt werden würde. Das einzige, was Sie vielleicht wissen, ist die Varianz des Sensorfehlers $$$\ sigma ^ 2_ \ eta$ . In diesem schwierigen Problem könnten wir alle unbekannten Informationen aus dem physikalischen Modell in die Zufallsvariable einfügen $$$\ xi_k$ ::

$$

$$x_ {k + 1} = x_k + \ xi_k$$

Genau genommen erfüllt diese Art von System nicht die Bedingung, die wir der Zufallsvariablen auferlegt haben $$$\ xi_k$ . Da es die uns unbekannten Informationen der Physik der Bewegung enthält. Wir können nicht sagen, dass die Fehler zu unterschiedlichen Zeitpunkten unabhängig voneinander sind und ihre Mittelwerte gleich Null sind. Mit anderen Worten bedeutet dies, dass für diese Art von Situationen die Kalman-Theorie nicht angewendet wird. Trotzdem können wir versuchen, die Maschinerie der Kalman-Theorie zu nutzen, indem wir nur einige vernünftige Werte für auswählen $$$\ sigma_ \ xi ^ 2$ und $$$\ sigma_ \ eta ^ 2$ um nur eine schöne Grafik des gefilterten Datums zu erhalten.
Aber es gibt einen viel einfacheren Weg. Wir haben das mit zunehmender Stufe gesehen $$$k$ Der Kalman-Koeffizient stabilisiert sich immer auf den bestimmten Wert $$$K_ {stab}$ . Also anstatt die Werte der Koeffizienten zu erraten $$$\ sigma ^ 2_ \ xi$ und $$$\ sigma ^ 2_ \ eta$ und Berechnen des Kalman-Koeffizienten $$$K_k$ Durch schwierige Formeln können wir annehmen, dass dieser Koeffizient konstant ist, und nur diese Konstante auswählen. Diese Annahme würde die Filterergebnisse nicht wesentlich beeinflussen. Erstens ist die Kalman-Maschinerie ohnehin nicht genau auf unser Problem anwendbar, und zweitens stabilisiert sich der Kalman-Koeffizient schnell auf die Konstante. Am Ende wird alles sehr einfach. Wir brauchen fast keine Formel aus der Kalman-Theorie, wir müssen nur einen vernünftigen Wert auswählen $$$K_ {stab}$ und fügen Sie es in die iterative Formel ein

$$

$$x ^ {opt} _ {k + 1} = K_ {stab} \ cdot z_ {k + 1} + (1-K_ {stab}) \ cdot x_k ^ {opt}$$

In der nächsten Grafik sehen Sie die auf zwei verschiedene Arten gefilterten Messungen von einem imaginären Sensor. Die erste Methode ist die ehrliche mit allen Formeln aus der Kalman-Theorie. Die zweite Methode ist die vereinfachte.


Wir sehen, dass es keinen großen Unterschied zwischen zwei dieser Methoden gibt. Am Anfang gibt es eine kleine Abweichung, wenn der Kalman-Koeffizient noch nicht stabilisiert ist.

Diskussion

Wir haben gesehen, dass die Hauptidee des Kalman-Filters darin besteht, den Koeffizienten zu wählen $$$K$ in einer Weise, dass der gefilterte Wert

$$

$$x ^ {opt} _ {k + 1} = Kz_ {k + 1} + (1-K) (x ^ {opt} _k + u_k)$$

im Durchschnitt wäre so nah wie möglich an der realen Koordinate $$$x_ {k + 1}$ . Wir sehen, dass der gefilterte Wert $$$x ^ {opt} _ {k + 1}$ ist eine lineare Funktion aus der Messung des Sensors $$$z_ {k + 1}$ und der vorherige gefilterte Wert $$$x ^ {opt} _k$ . Aber der vorherige gefilterte Wert $$$x ^ {opt} _k$ selbst ist eine lineare Funktion der Sensormessung $$$z_k$ und der vorhergehende gefilterte Wert $$$x ^ {opt} _ {k-1}$ . Und so weiter bis zum Ende der Kette. Der gefilterte Wert hängt also linear von allen vorherigen Sensorwerten ab:

$$

$$x ^ {opt} _ {k + 1} = \ lambda + \ lambda_0z_0 + \ ldots + \ lambda_ {k + 1} z_ {k + 1}$$

Aus diesem Grund wird der Kalman-Filter als linearer Filter bezeichnet. Es kann nachgewiesen werden, dass der Kalman-Filter der beste aller linearen Filter ist. Das Beste in dem Sinne, dass es einen quadratischen Mittelwert des Fehlers minimiert.

Mehrdimensionaler Fall

Es ist möglich, die gesamte Kalman-Theorie auf den mehrdimensionalen Fall zu verallgemeinern. Die dortigen Formeln sehen etwas ausgefeilter aus, aber die Idee ihrer Ableitung bleibt immer noch dieselbe wie in einer Dimension. Zum Beispiel können Sie in diesem schönen Video das Beispiel sehen.

Literatur

Den Originalartikel von Kalman können Sie hier herunterladen:
http://www.cs.unc.edu/~welch/kalman/media/pdf/Kalman1960.pdf