- Kalman-Filter
-
Das Kalman-Filter ist ein nach seinem Entdecker Rudolf E. Kálmán benannter Satz von mathematischen Gleichungen. Mithilfe dieses Filters sind bei Vorliegen lediglich fehlerbehafteter Beobachtungen Rückschlüsse auf den Zustand von vielen der Technologien, Wissenschaften und des Managements zugeordneten Systemen möglich. Vereinfacht gesprochen dient das Kalman-Filter zum Entfernen der von den Messgeräten verursachten Störungen. Dabei müssen sowohl die mathematische Struktur des zugrundeliegenden dynamischen Systems als auch die der Messverfälschungen bekannt sein.
Im Rahmen der mathematischen Schätztheorie spricht man auch von einem Bayes'schen Minimum-Varianz-Schätzer für lineare stochastische Systeme in Zustandsraumdarstellung.
Eine Besonderheit des 1960 von Kálmán vorgestellten Filters[1] bildet seine spezielle mathematische Struktur, die den Einsatz in Echtzeitsystemen verschiedenster technischer Bereiche ermöglicht. Dazu zählen u.a. die Auswertung von Radarsignalen zur Positionsverfolgung von sich bewegenden Objekten (Tracking) aber auch der Einsatz in elektronischen Regelkreisen allgegenwärtiger Kommunikationssysteme wie etwa Radio und Computer.
Inhaltsverzeichnis
Historisches
Obgleich die Benennung des Filters nach Rudolf E. Kálmán erfolgte, wurden bereits zuvor nahezu identische Verfahren durch Thorvald N. Thiele[2] und Peter Swerling veröffentlicht. Auch existierten zur selben Zeit bereits allgemeinere, nichtlineare Filter von Ruslan L. Stratonovich,[3][4] die das Kalman-Filter und weitere lineare Filter als Spezialfälle enthalten. Ebenso erwähnenswert sind Vorarbeiten und gemeinsame Publikationen von Kálmán mit Richard S. Bucy, insbesondere für den Fall zeitkontinuierlicher dynamischer Systeme. Daher wird häufig die Bezeichnung Kalman-Bucy-Filter und gelegentlich auch Stratonovich-Kalman-Bucy-Filter in der Fachliteratur benutzt.
Der erste nennenswerte und erfolgreiche Einsatz des Filters erfolgte in Echtzeitnavigations- und Leitsystemen, die im Rahmen des Apollo-Programms der NASA unter Federführung von Stanley F. Schmidt entwickelt wurden.
Mittlerweile existiert eine große Bandbreite von Kalman-Filtern für die unterschiedlichsten Anwendungsgebiete. Neben der ursprünglichen Formulierung sind dies das Erweiterte Kalman-Filter, das Unscented Kalman-Filter,[5][6] das Informationsfilter und eine Vielzahl von numerisch stabilen Varianten wie beispielsweise die sog. Wurzel-Implementierung[7] oder der Bierman-Thornton-UD-Algorithmus.[8] Die meistgenutzte Variante jedoch ist die der Kontrolltheorie entstammende sogenannte Phasenregelungsschleife,[9] ein wesentlicher Bestandteil der meisten modernen Kommunikationsmittel.
Grundlagen
Im Gegensatz zu den klassischen FIR- und IIR-Filtern der Signal- und Zeitreihenanalyse basiert das Kalman-Filter auf einer Zustandsraummodellierung, bei der explizit zwischen der Dynamik des Systemzustands und dem Prozess seiner Messung unterschieden wird.
Zustandsraummodellierung
Als Zustand eines Systems wird dabei häufig der kleinste, das System vollständig beschreibende Satz von Bestimmungsstücken verstanden und im Rahmen der Modellbildung in Form eines mehrdimensionalen Vektors X mit entsprechender Bewegungsgleichung, der sogenannten Zustandsgleichung dargestellt. Diese Gleichung ist häufig eine Differenzengleichung, da in vielen Fällen die Zustände nur zu bestimmten, durch feste Zeitintervalle Δt voneinander getrennten Zeitpunkten tk = t0 + k·Δt mit k als natürlicher Zahl von Interesse sind. Es hat sich eingebürgert, die diskreten Zeitpunkte tk einer einfachen Notation halber in Gleichungen verkürzt als Index k der betreffenden Größe zu notieren, tk-1 als Index k-1 usw. usf. Mit dieser Schreibweise und für den von Kálmán betrachteten Sonderfall einer lediglich linearen Abhängigkeit der Zustände untereinander, vereinfacht sich die Zustandsgleichung zur linearen Differenzengleichung
- .
Die Matrix Fk-1 beschreibt die Übergänge zwischen zeitlich aufeinanderfolgenden Zuständen Xk-1 und Xk. Neben der durch die Übergangsmatrix Fk-1 ausgedrückten eigentlichen Dynamik modelliert die Zustandsgleichung zudem weitere äußere Einflüsse auf das System. Dabei wird zwischen deterministischen, also vollständig bestimmbaren Einflüssen sowie solchen zufälliger Natur unterschieden. Der deterministische Anteil wird durch die wirkende Störung uk-1 und deren Dynamik in Form einer Matrix Bk-1 dargestellt; die zufälligen, nicht erfassbaren Komponenten durch einen Rauschterm, der stochastischen Größe wk-1. Das zeitlich unkorrelierte Rauschen wk-1 folgt dabei einer Normalverteilung mit Mittelwert 0 und Kovarianz Qk-1, in üblicher Kurznotation:
- .
Aufgrund der Unvorhersagbarkeit des Rauschterms enthält auch der Zustandsvektor einen gewissen Anteil an "Zufall" und ist somit selbst eine stochastische Größe, eine Zufallsvariable. Die Menge aller Zustandsvektoren bilden einen speziellen stochastischen Prozess, eine Markow-Kette bzw. ein Markow-Modell erster Ordnung, d.h. der Zustand zu einem Zeitpunkt k hängt lediglich vom unmittelbaren zeitlichen Vorgänger an k-1 ab.
Der Prozess der Beobachtung der wahren Systemzustände Xk, Xk-1, ... muss die Eigenschaften des Beobachters bzw. der Messapparatur widerspiegeln. Dies umfasst modellierbare Verzerrungen und das unvorhersagbare Messrauschen. Für den Fall des Kalman-Filters wird die Verzerrung als linear und das Rauschen als zeitlich unkorreliert und normalverteilt angenommen. Die entsprechende Modellierung des Messprozesses, die Beobachtungsgleichung, lautet
mit der Beobachtungsmatrix Hk und dem Messrauschen
- .
Dynamisches Rauschen w und Messrauschen v sollen zu allen Zeiten voneinander unabhängig sein.
Die Gesamtheit von Zustandsgleichung und Beobachtungsgleichung nennt man Zustandsraummodell[A 1]. Aufgrund des "versteckten" bzw. durch einen zweiten stochastischen Prozess, der Messung, überdeckten Markow-Modells spricht man beim Zustandsraummodell auch häufig von einem Verborgenen Markow-Modell (engl. Hidden Markov Model).
Das Filterproblem
Eine in der Praxis ausgeführte Messung ergibt pro Zeitpunkt häufig lediglich eine einzelne Realisierung zk der normalverteilten Zufallsgröße Zk. Nun stellt sich das inverse Problem, nämlich anhand der Informationen einer Messreihe mit den Werten z1, z2, z3, z4, ... auf die entsprechenden X1, X2, X3, X4 ... rückschließen zu können. Da die gesuchten Zustände aufgrund der Linearität des Modells und der gemachten Voraussetzungen für die Rauschterme w und v für alle Zeiten normalverteilt bleiben und eine Normalverteilung durch ihren Mittelwert und Kovarianz vollständig beschrieben wird, beschränkt sich das Filterproblem auf die Schätzung dieser beiden Bestimmungsstücke. Eine mögliche exakte Lösung dieses inversen Problems ist das zeitdiskrete Kalman-Filter, ein Satz von Gleichungen also, der Schätzungen für den Mittelwert und die Kovarianz des Zustands
anhand der aus der Messreihe zk, zk-1, zk-2 ... z1 extrahierten Informationen liefert.
Häufig stellt sich die Aufgabe, das Filterproblem auch für zeitkontinuierliche Systeme zu lösen. Dabei gehen die Differenzengleichungen des Zustandsraummodells durch eine mathematische Grenzwertbildung in Differentialgleichungen über. Die Gleichungen des zeitkontinuierlichen Kalman-Filters ergeben sich entsprechend aus dem zeitdiskreten Filter durch Anwendung derselben Grenzwertbildung.[10] Aus diesem Grund und im Sinne einer verständlichen Darstellung soll im Folgenden lediglich auf die Gleichungen des zeitdiskreten Filters eingegangen werden.
Gleichungen
Die Schätzung des Zustands sollte möglichst auf der Kenntnis aller früheren Beobachtungen beruhen. Dabei ist ein minimaler Schätzfehler zu fordern, der durch die bereits gemachten Beobachtungen nicht zu verbessern sein soll. Für lange Messreihen wird das entsprechende mathematische Minimierungsproblem schnell unhandlich, da für jede Schätzung die gesamte Messreihe ausgewertet werden muss. Die Idee des Kalman-Filters ist nun, die Schätzung zum Zeitpunkt k als lineare Kombination der vorangegangenen Schätzung mit dem neuen Messwert zk zu formulieren. Dies ist möglich, da die Schätzung zum Zeitpunkt k-1 die Informationen der Messreihe zk-1, zk-2 ... z1 enthält. Diese rekursive Formulierung des Schätzproblems erlaubt eine effiziente rechentechnische Umsetzung.
Das Kalman-Filter verfügt neben seiner handhabbaren rekursiven zudem über eine Prädiktor-Korrektor-Struktur.
Prädiktion
Beim ersten Schritt des Filtervorgangs wird die zeitlich vorangegangene Schätzung der Zustandsdynamik unterworfen um eine Voraussage für den aktuellen Zeitpunkt zu erhalten. Für den Mittelwert ergibt sich
- .
und für die Kovarianz- .
Die Indizierungsschreibweise k|k-1 drückt die Bedingtheit der Schätzungen zu den Zeitpunkten k und k-1 voneinander aus. Das hochgestellte T bezeichnet die Transponierte der entsprechend gekennzeichneten Matrix.
Korrektur
Die Vorhersagen werden schließlich mit den neuen Informationen des aktuellen Messwerts korrigiert und ergeben die gesuchten Schätzungen
sowie
mit den Hilfsgrößen Innovation
Residualkovarianz
und der zugehörigen Kalman-Matrix
- .
Die Hilfsgröße Innovation beschreibt, wie genau der vorhergesagte Mittelwert den aktuellen Messwert mithilfe der Beobachtungsgleichung zu beschreiben in der Lage ist. Für eine schlechte Vorhersage wird die dazugehörige Innovation groß, für eine genaue Vorhersage dagegen klein sein. Entsprechende Korrekturen müssen dann groß bzw. nur gering ausfallen. Die durchzuführende Korrektur kann demnach als zur Größe der Innovation proportional angesehen werden. Zudem sollen Innovationen von Messwerten, die mit größerer Unsicherheit als ihre Schätzungen behaftet sind, mit weniger Gewicht in die Korrektur eingehen als solche bei denen das Gegenteil der Fall ist. Diese zu fordernden Eigenschaften werden gerade von der Kalman-Matrix als dem gesuchten Proportionalitätsfaktor erfüllt. Dies wird aus der äquivalenten Formulierung
ersichtlich, die, im Rahmen dieses eher intuitiven Zugangs und damit stark vereinfachend gesprochen, als das geforderte Verhältnis der Unsicherheiten der Vorhersagen Pk zu den zugehörigen Messunsicherheiten Rk angesehen werden kann.[A 2] Die Elemente der Kalman-Matrix können in vielen Fällen analytisch, also vor Beginn des Schätzvorgangs berechnet oder wenigstens näherungsweise bestimmt werden. In weniger zeitkritischen Anwendungen wird die Kalman-Matrix mitgeschätzt, d.h. während des Schätzvorgangs immer wieder neu aus der aktuellen Vorhersage der Kovarianz berechnet.
Die exakte Herleitung und Begründung der Vorhersage- und Korrekturgleichungen erfolgt üblicherweise im Rahmen wahrscheinlichkeitstheoretischer Betrachtungen unter Benutzung des Bayestheorems.
Anmerkungen zum zeitkontinuierlichen Kalman-Filter
Im zeitkontinuierlichen Fall spricht man nicht mehr von einer rekursiven Formulierung und auch nicht von einer Prädiktor-Korrektur-Struktur. Vielmehr hat man es mit einem Satz von Differentialgleichungen, die die Schätzungen von Mittelwert und Kovarianz beschreiben, zu tun. Um Aussagen über die Schätzung zu einem bestimmten Zeitpunkt machen zu können, müssen die genannten Differentialgleichungen gelöst werden. Aufgrund eines nichtlinearen Terms in der Kovarianzgleichung, der sogenannten Matrix-Riccati-Gleichung, ist eine exakte Lösung und damit optimale Schätzung nur in wenigen Fällen möglich.
Initialisierung
Für die Startschätzung verwendet man häufig
mit der Identitätsmatrix I und einer geeigneten Konstanten c.[11]
Eigenschaften
Wie aus der Korrekturgleichung ersichtlich ist, hängt die Schätzung des Mittelwertes in linearer Weise von der Beobachtung ab, das Kalman-Filter ist demnach ein lineares Filter. Mit zunehmender Länge der Messreihe nähern sich die Schätzungen für Mittelwert und Varianz den tatsächlichen Werten beliebig genau an. Man spricht daher im statistischen Jargon von einem erwartungstreuen und konsistenten Schätzer mit minimaler Varianz. Aufgrund dieser Schätzeigenschaften, die hier einer Minimierung des mittleren quadratischen Fehlers entsprechen[12], ist das Kalman-Filter ein optimales lineares Filter. Selbst verallgemeinerte nichtlineare Filter liefern für das hier betrachtete lineare Zustandsraummodell mit normalverteilten Variablen keine besseren Ergebnisse. Im Gegensatz zu anderen (rekursiven) linearen Schätzern, die ebenso Fehlerquadrate minimieren, erlaubt das Kalman-Filter auch die Behandlung von Problemen mit korrelierten Rauschkomponenten, wie sie in der Praxis häufig anzutreffen sind.
Anwendbarkeit und Erweiterungen
Die bei der Herleitung des Kalman-Filters gemachten Voraussetzungen können in der Praxis bestenfalls nur näherungsweise erfüllt werden. Beispielsweise ist in vielen Fällen die exakte Struktur der linearen Zustands- und Beobachtungsgleichung nicht bekannt oder zu umfangreich, als dass sie im Rahmen des Kalman-Filters rechentechnisch handhabbar wäre. Der Anwender muss demnach eine Einschränkung der zu verwendenden Modellklassen vornehmen. Die damit verbundenen Ungenauigkeiten führen häufig zu einem vom Optimalen abweichendem, einem divergenten Verhalten des Filters. Daher sind vor dem Einsatz Untersuchungen zur Abhängigkeit der Schätzergebnisse von den Modellierungsfehlern (und deren Kompensation) im Rahmen einer Sensitivitätsanalyse notwendig.
Zu einer weiteren Einschränkung der Schätzgüte führen die durch den Einsatz digitaler Rechentechnik verursachten Rundungsfehler. Analog zu den Modellungenauigkeiten können diese zu einer drastischen Divergenz des Kalman-Filters führen. Abhilfe schaffen hier algebraische Umformulierungen (Faktorisierungen) der Kovarianzmatrizen, jedoch um den Preis erhöhten rechentechnischen Aufwandes. Die bekanntesten numerisch stabilen Varianten des Kalman-Filters sind die Wurzelimplementierung nach Potter et al. und deren Verfeinerung in Form des Bierman-Thornton-UD-Algorithmus.
Neben diesen Problemen ist das Kalman-Filter in vielen Fällen generell nicht einsetzbar, da es auf lineare Zustandsraummodelle beschränkt ist. Selbst einfache Aufgabenstellungen der Navigationstechnik oder das wichtige Themengebiet der Parameterschätzung führen jedoch immer auf nichtlineare Zustands- oder Beobachtungsgleichungen. Abhilfe schaffen hier beispielsweise nichtlineare Erweiterungen des Kalman-Filters wie das bereits in den 60er Jahren entwickelte Erweiterte Kalman-Filter (Abk. EKF) oder auch das neuere Unscented Kalman-Filter (Abk. UKF). Diese Kalman-Filter-Varianten nähern das nichtlineare Problem durch ein lineares, wobei entweder analytische (EKF) oder statistische Techniken (UKF) zum Einsatz kommen. Im Sinne eines unkomplizierten Sprachgebrauchs werden diese Erweiterungen häufig abkürzend auch als Kalman-Filter bezeichnet, da sie ebenso über eine rekursive sowie eine Prädiktor-Korrektor-Struktur verfügen. Im Gegensatz zum einfachen Kalman-Filter ist die Kalman-Matrix nun eine Zufallsvariable und muss während des gesamten Filtereinsatzes mitgeschätzt werden, was wiederum die Anforderungen an die Technik erhöht.
Seit dem Aufkommen leistungsfähiger digitaler Rechentechnik ist man dazu übergegangen, die meisten anspruchsvollen nichtlinearen Filterprobleme durch Simulationen (sequentielle Monte-Carlo-Methoden) oder anderweitige Näherungsverfahren (Quadratur-Filter, Gaußsummenfilter, Projektionsfilter) zu behandeln.
Beispielanwendungen
Das Kalman-Filter ist heute der wohl am weitesten verbreitete Algorithmus zur Zustandsschätzung linearer und nichtlinearer Systeme.
- Weite Verbreitung gefunden hat das Kalman-Filter in der Inertialnavigation beispielsweise von Flugzeugen: Während des Flugs werden Beschleunigungen und Drehraten des Flugzeugs von einer inertialen Messeinheit mit hohen Frequenzen gemessen, um eine Kurzzeit-Navigation zu ermöglichen. Weitere Sensoren, insbesondere satellitengestützte Positionsbestimmung (z.B. GPS) liefern Stützdaten. Diese verschiedenen Messungen müssen verknüpft („fusioniert“) werden, um eine möglichst optimale Schätzung der aktuellen Position und Orientierung zu gewährleisten.
- Zunehmend spielen Trackingverfahren und somit das Kalman-Filter als typischer Vertreter eines Trackingfilters eine Rolle im Automobilbereich. Sicherheits- oder Komfortanwendungen, die auf umfelderkennenden Systemen basieren, sind auf verlässliche Informationen (z.B. Position, Geschwindigkeit) bezüglich der Objekte in ihrem Umfeld angewiesen.
- Eine ebenfalls oft verwendete Art eines Kalman-Filters, das PLL-Filter, hat heute weite Verbreitung gefunden in Radios, Funkgeräten, Computern und in fast allen anderen Arten von Video- und Kommunikationsgeräten.
- In hochwertigen Akkumulatorladegeräten und Akkumulatorladezustandsüberwachungsgeräten kommen adaptive Kalman-Filter zum Einsatz. Strom, Spannung, Temperatur und evtl. pH-Wert sind Messgrößen und u.a. Ladezustand, maximal entnehmbare Leistung und entnehmbare Energie bei aktueller Entladerate sind Ausgabegrößen. Die Überwachung von vielen Lithium-Akkumulatorzellen ist für die Elektrifizierung von Automobilen von hervorgehobener Bedeutung.
Siehe auch
- IIR-Filter
- Adaptive Filter
- Wiener-Filter
- Sequenzielle Monte-Carlo-Methode
- Steuerbarkeit
- Beobachtbarkeit
Literatur
Neben den von Kálmán und Bucy veröffentlichten Aufsätzen existiert eine Vielzahl weiterer, hauptsächlich ergänzender und vertiefender Literatur, die sich aus mathematischer wie auch aus ingenieurstechnischer Sicht dem Thema nähern. Nachfolgend wird ein Überblick über die wichtigsten Publikationen gegeben.
Deutschsprachige Literatur
- Karl Brammer, Gerhard Siffling: Kalman-Bucy-Filter: deterministische Beobachtung und stochastische Filterung. Oldenbourg, München, Wien 1994, ISBN 3-486-22779-3.
- Jan Wendel: Integrierte Navigationssysteme: Sensordatenfusion, GPS und Inertiale Navigation. Oldenbourg, 2007, ISBN 978-3-486-58160-7.
Englischsprachige Literatur
- Analytical Sciences Corp-Technical; A. Gelb (Hrsg.): Applied Optimal Estimation. 16. Auflage. M.I.T. Press, Cambridge 2001, ISBN 978-0-262-57048-0.
- Yaakov Bar-Shalom, X. Rong Li, Thiagalingam Kirubarajan: Estimation with Applications to Tracking and Navigation: Theory Algorithms and Software. Wiley & Sons, New York 2001, ISBN 978-0-471-41655-5.
- Richard S. Bucy, B. G. Williams: Lectures on Discrete Time Filtering. Signal Processing and Digital Filtering. Springer-Verlag, New York 1994, ISBN 978-0-387-94198-1.
- Mohinder S. Grewal, Angus P. Andrews: Kalman Filtering Theory and Practice. Prentice-Hall, Upper Saddle River 1993, ISBN 978-0-132-11335-9.
- Dan Simon: Optimal State Estimation: Kalman, H Infinity, and Nonlinear Approaches. Wiley-Interscience, Hoboken 2006, ISBN 978-0-471-70858-2.
Weblinks
Einzelnachweise
- ↑ Kalman, R.E. (1960) "A New Approach to Linear Filtering and Prediction Problems", Transaction of the ASME, Journal of Basic Engineering, Seiten 35-45. Als PDF-Datei: http://www.cs.unc.edu/~welch/kalman/media/pdf/Kalman1960.pdf
- ↑ Steffen L. Lauritzen, Thiele: Pioneer in Statistics, Oxford University Press, 2002. ISBN 0-19-850972-3.
- ↑ Stratonovich, R. L. (1959). Optimum nonlinear systems which bring about a separation of a signal with constant parameters from noise. Radiofizika, 2:6, Seiten 892-901.
- ↑ Stratonovich, R. L. (1960) Application of the Markov processes theory to optimal filtering. Radio Engineering and Electronic Physics, 5:11, Seiten 1-19.
- ↑ Simon, J. Julier, Jeffrey K. Uhlmann und H. F. Durant-Whyte (1995). A new approach for filtering nonlinear systems. Proceedings of the 1995 American Control Conference. Seiten 1628-1632.
- ↑ Simon J. Julier und Jeffrey K. Uhlmann (1997) A new extension of the Kalman filter to nonlinear systems. In Int. Symp. Aerospace/Defense Sensing, Simul. and Controls.
- ↑ Potter, J. E. und Stern, R. G. (1963). "Statistical filtering of space navigation measurements." Proc. of AIAA, Guidance and Control Conf.
- ↑ Bierman, G. J. und Thornton, C. L. (1977). "Numerical Comparison of Kalman Filter Algorithms: Orbit Determination Case Study", Automatica 13, 23
- ↑ Patapoutian, A. (1999). On phase-locked loops and Kalman filters. IEEE Transactions on Communications, Volume 47, Issue 5, May 1999 Seiten 670 - 672
- ↑ Gelb et al., "Applied Optimal Estimation", The M.I.T. Press, 2001, S. 119 ff.
- ↑ Shumway, R. H., D. E. Olsen und L. J. Levy, 1981. 'Estimation and Tests of. Hypotheses for the Initial Mean and Covariance in the Kalman Filter Model.' Commun. Stat. Theory Meth.
- ↑ Einen guten Überblick und ausführliche Erklärungen hierzu findet man beispielsweise in “Least-Squares estimation: from Gauss to Kalman” von H. W. Sorenson (IEEE Spectrum, Vol. 7, Seiten 63-68, July 1970)
Fußnoten
- ↑ Der Sprachgebrauch für den Begriff Zustandsraummodell ist in der Literatur nicht einheitlich. In der Regelungstechnik versteht man darunter die bloße Modellierung der Zustandsdynamik, in der Zeitreihenanalyse dagegen bezeichnet man die Gesamtheit von Zustands- und Beobachtungsgleichung als Zustandsraummodell.
- ↑ Eine exakte Formulierung mithilfe einer expliziten Betrachtung der Matrixelemente soll aus Platz- und Übersichtlichkeitsgründen ausgelassen werden. Genaueres findet sich bei Gelb et al.: Applied Optimal Estimation.
Wikimedia Foundation.