Zustandsschätzung und Filter erklärt
Neun Stücke mit demselben wachsenden Beispiel: ein Lieferfahrzeug, dessen Position nur über verrauschte Messungen bekannt ist (GPS, ein Radsensor, Entfernung und Peilung zu einer Bake, ein Straßengitter). Die Wurzel ist der Kalman-Filter: Er fasst alle Messungen zu einer Schätzung und einer Aussage über deren Unsicherheit zusammen, und die Demo prüft, ob diese Unsicherheit ehrlich ist (mittlere NEES 2,0 bei richtigem Modell, 61, wenn der Filter zehnmal weniger Prozessrauschen glaubt). Die Folgestücke beheben je eine Schwäche: Der Glätter nutzt auch die Zukunft, der erweiterte Kalman-Filter rechnet mit Entfernung und Peilung, der robuste Filter widersteht GPS-Ausreißern, HMM-Dekodieren findet die Straße, der Partikelfilter hält mehrere Orte zugleich offen, die Mehrzielverfolgung ordnet Messungen den Fahrzeugen zu, das IMM erkennt Manöver, und Baum-Welch lernt die Übergänge aus Daten.
Mehrere Stücke enden mit einem Negativbefund: Viterbi ist nicht genauer als der Glätter, der Partikelfilter beim Positionsfehler nicht besser als der UKF, die globale Zuordnung vertauscht je nach Zeitversatz öfter die Identitäten als die einfache Regel, und gelernte Übergänge machen die Trefferquote in der Standardeinstellung schlechter (60 % gegen 75 % mit den Handparametern). Alle Zahlen stehen in den README der Demos, und jede Demo prüft ihren Kern gegen eine unabhängige Referenz (Orakel-Tests). Die Wahrheit ist in allen Stücken das Modell selbst: Es gibt keinen echten GPS-Datensatz, die Demos zeigen, was die Verfahren unter diesen Annahmen leisten.
In short: Covers state estimation and filtering: Kalman filter, smoothers, EKF and UKF, robust filters, hidden Markov models (HMM), particle filters, multi-target tracking, IMM and Baum-Welch. Interactive demos track one vehicle from noisy measurements.
Hintergrund zum Thema: Tourenplanung.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Der Kalman-Filter verständlich erklärt
Wie ein Filter aus einer Vorhersage und verrauschten GPS-Punkten eine bessere Positionsschätzung mischt und dazu angibt, wie sehr man ihr glauben darf: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die neun Stücke im Überblick
Der Kalman-Filter ist die Wurzel: ein Filter für Zustände mit linearem Modell und gaußschem Rauschen. Daraus verzweigt die Linie nach der Schwäche, die jeweils behoben wird: der RTS-Glätter (der Filter sieht keine Zukunft), der erweiterte Kalman-Filter (die Messung ist nicht linear), der robuste Filter (Ausreißer verzerren die Schätzung), HMM-Dekodieren (der Zustand ist eine Straße, kein gaußscher Punkt) und die Mehrzielverfolgung (welche Messung gehört zu welchem Fahrzeug?).
Der Partikelfilter (Doppelrahmen) führt den erweiterten Kalman-Filter und das HMM zusammen: nicht gaußsch und mehrgipflig. Das IMM folgt dem robusten Filter (Manöver oder Ausreißer?), Baum-Welch dem HMM (die Übergänge waren von Hand gesetzt). Die gestrichelten Fremdknoten sind Bausteine anderer Linien: die exponentielle Glättung aus der Zeitreihen-Prognose (der Kalman-Filter mit fester Verstärkung), Dijkstra aus den Kürzesten Wegen (Viterbi ist ein kürzester Weg im Trellis) und die Ungarische Methode aus dem Matching.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Verwandt in anderen Linien
- Zeitreihen-Prognose — Der Kalman-Filter mit fester Verstärkung ist die exponentielle Glättung der Zeitreihen-Prognose: Im Lokales-Niveau-Modell gilt α = (√(q²+4q) − q)/2, bei q = 0,01 ist α = 0,0951, bei q = 1 ist α = 0,6180. Die Kalman-Filter-Demo zeigt diese Brücke im letzten Experiment.
- Kürzeste Wege — Viterbi ist ein kürzester Weg im Trellis: Die HMM-Dekodieren-Demo prüft ihn gegen Dijkstra mit den Kosten −log A − log b und gegen die Aufzählung aller Pfade; der Befund bleibt, dass er nicht genauer ist als der Glätter, nur zulässig.
- Matching-Algorithmen — Die globale Zuordnung der Mehrzielverfolgung ist ein lineares Zuordnungsproblem, gelöst mit der Ungarischen Methode der Matching-Linie und geprüft gegen scipy.optimize.linear_sum_assignment und gegen die Aufzählung aller Zuordnungen. Dass sie die Identitäten bei gleichzeitigem Aufeinandertreffen schlechter erhält als die nächste Messung, ist ein Befund dieser Linie.
- Ranking — Die Ranking-Linie führt beide Gedanken für Paarvergleiche weiter: Elo ist ein Filter mit fester Verstärkung (die Kalman-Verstärkung dient als Vergleichswert), Glicko und TrueSkill führen die Varianz mit, und WHR glättet über die Historie wie der RTS-Glätter.
- Inverse Probleme und Regularisierung — Das Kalman-Update läuft in der Linie Inverse Probleme und Regularisierung nicht über die Zeit, sondern einmal über das ganze Signal: Dort ist es die Bayes-Sicht mit exaktem Posterior und, mit einem Ensemble statt Kovarianzen, die Ensemble-Kalman-Inversion.
- Spektral- und Wavelet-Analyse — Wo sich eine Frequenz mit der Zeit ändert, schätzt das Spektrogramm sie in jedem Fenster für sich, ohne Zustandsmodell; das Kalman-Filter dagegen führt einen Zustand und gewichtet jede Messung nach ihrer Unsicherheit.
- Mittelwerte und Lagemaße — Die Trimm-und-Huber-Demo der Linie Mittelwerte und Lagemaße schätzt die Lage einer Zahlenreihe ohne Zustandsmodell und dämpft große Abweichungen nach Huber. Im robusten Filter zählen GPS-Messungen mit großer Abweichung im Kalman-Filter ebenfalls nach Huber weniger, und ein echtes Manöver sieht zuerst wie ein Ausreißer aus.
Kalman-Filter: Zustand schätzen aus verrauschten Messungen
Verfolgen Sie, wie der Kalman-Filter aus verrauschten GPS-Punkten und einem Radsensor Position und Geschwindigkeit eines Lieferfahrzeugs schätzt und zugleich angibt, wie sehr man der Schätzung glauben darf. Regler für Rauschen und Annahmen des Filters zeigen, ob diese Angabe ehrlich bleibt. Der Haken: Die Fahrt entsteht mit dem Modell des Filters selbst, und glaubt er zehnmal weniger Prozessrauschen, liegt die Wahrheit nur 80 % der Zeit in seinem 95-%-Band.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →RTS-Glätter: die Schätzung im Nachhinein verbessern
Verfolgen Sie, wie der Rauch-Tung-Striebel-Glätter dieselbe Fahrt rückwärts durchrechnet: Der Filter kennt nur die Vergangenheit, der Glätter schätzt jeden Zeitpunkt aus allen Messungen. Die Demo vergleicht beide bei steigendem GPS-Rauschen, im Tunnel und mit einigen Sekunden Verzögerung. Der Haken: Verzögerung ist teuer, ein Lag von 5 s holt im Standardfall nur 21 % des Gewinns, wer echtzeitnah arbeitet, gewinnt also wenig.
Demo starten →Erweiterter Kalman-Filter: Entfernung und Peilung statt Position
Sehen Sie, wie der Erweiterte Kalman-Filter mit Entfernung und Peilung zu einer Bake zurechtkommt, indem er die gekrümmte Messung durch eine Gerade an der Schätzung ersetzt. Ein Vergleich mit dem Unscented-Filter über steigendes Peilrauschen zeigt, ob sich dessen Aufwand lohnt. Der ehrliche Befund: Beim Positionsfehler ist der UKF nicht besser, doch der EKF wird bei 10 m Mindestabstand und 0,5 Grad Peilrauschen in etwa 10 % der Fahrten sehr überselbstsicher.
Demo starten →Robuster Filter: GPS-Ausreißer, ohne echte Manöver zu verwerfen
Verfolgen Sie vier Filter auf derselben Fahrt, die GPS-Sprünge unterschiedlich behandeln: ungeschützt, mit hartem Tor (zu weit entfernte Messungen werden verworfen), mit Tor und Rückfall und mit Huber-Gewichtung (sie zählen weniger). Regler für Ausreißer und Bremsmanöver zeigen den Preis des Schutzes. Der Haken: Ein echtes Manöver sieht zuerst aus wie ein Ausreißer, und beim Bremsen mit 8 m/s verliert das harte Tor in etwa 60 % der Fahrten die Spur.
Demo starten →HMM-Dekodieren: Map-Matching mit Filter, Glätter und Viterbi
Sehen Sie, wie ein Hidden-Markov-Modell verrauschte GPS-Punkte einer von mehreren nahen Straßen zuordnet, statt einen Mittelwert dazwischen zu bilden. Die Demo vergleicht nächste Straße, Filter, Glätter und Viterbi bei steigendem Rauschen. Bei 20 m Rauschen trifft die nächste Straße in 39 % der Sekunden, der Glätter in 90 %. Der Gewinn kommt vom Blick in die Zukunft: Viterbi ist hier nicht besser als der Glätter, garantiert aber einen befahrbaren Weg.
Demo starten →Partikelfilter: mehrgipflige Verteilungen mit Stichproben darstellen
Sehen Sie, wie der Partikelfilter mit einer Wolke von Stichproben zwei mögliche Orte offen hält, wo ein Gauß-Filter dazwischen landet, wo das Fahrzeug nicht sein kann. Ein Vergleich über Partikelzahl und zweite Bake zeigt den Preis. Der Haken: Beim Positionsfehler ist er nicht besser als der UKF, und mit 1 000 Partikeln findet er die richtige Seite nur in 77 % der Fahrten; erst 3 000 Partikel holen auf.
Demo starten →Mehrzielverfolgung: welche Messung gehört zu welchem Fahrzeug?
Sehen Sie, wie zwei Fahrzeuge, deren Sensor nur anonyme Punkte liefert, ihren Spuren zugeordnet werden: die nächste Messung je Spur gegen eine globale Zuordnung per Ungarischer Methode. Regler für Kreuzungswinkel und Zeitversatz zeigen den Unterschied. Der Haken: Die globale Zuordnung macht weniger falsche Zuordnungen, vertauscht aber beim gleichzeitigen Eintreffen am Kreuzungspunkt (10 Grad) in 30 % der Begegnungen die Identitäten, die nächste Messung in 13 %.
Demo starten →Mehrere Bewegungsmodelle: Manöver erkennen, ohne Ausreißer zu glauben
Verfolgen Sie, wie das IMM zwei Bewegungsmodelle, ruhig und unruhig, parallel rechnet und nach der Messwahrscheinlichkeit gewichtet, damit ein echtes Manöver nicht wie ein Ausreißer behandelt wird. Die Demo vergleicht fünf Verfahren bei steigender Manöverstärke, mit und ohne Ausreißer. Der Haken: Ohne Manöver ist das IMM mit 5,3 m schlechter als das ruhige Modell mit 4,5 m, und das Manöver wird nur langsam und unscharf erkannt.
Demo starten →Baum-Welch: Übergänge aus den Daten lernen, und wann das nichts bringt
Verfolgen Sie, wie Baum-Welch die Übergangsgewichte eines Straßenmodells aus Trainingsfahrten lernt, statt sie von Hand zu setzen, und prüfen Sie, ob das hilft. Die Demo variiert Rauschen, Startwerte und Zahl der Trainingsfahrten. Der ehrliche Befund: Die Trainingsfahrten werden wahrscheinlicher, aber bei viel Rauschen sinkt die Trefferquote auf Testfahrten von 75 % mit Handparametern auf 60 %, und bei wenig Rauschen gibt es nichts zu gewinnen.
Demo starten →Welches Verfahren passt zu meiner Schätzaufgabe?
Ein Entscheidungsbaum über alle neun Stücke: Er fragt nach dem, was geschätzt werden soll, und danach, was die Messung schwierig macht, nicht nach dem Verfahren.
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Alle neun Antworten sind durch die Messreihen der Demos belegt (siehe jede README), auch dort, wo das einfachere Verfahren genügt: Der UKF ist beim Positionsfehler nicht besser als der EKF, Viterbi nicht genauer als der Glätter, und gelernte Übergänge schlagen die Handparameter in der Standardeinstellung nicht.
Weitere Linien in diesem Bereich
Quellentrennung
Aus gemischten Messungen die Quellen zurückgewinnen, am Beispiel Spike-Sorting: ICA, SOBI, SCA, NMF, Pipeline, Vorlagenabgleich und der Verzögerungsgraph aus meiner Dissertation.
Inverse Probleme und Regularisierung
Eine unscharfe, verrauschte Messung und eine bekannte Wahrheit, sechzehn Stücke: vom schlecht gestellten Problem über Strafterm, Abbruch und Parameterwahl, Vorwissen und Bayes-Sicht bis zu gelernten Priors und dem Vergleich der Verfahren.
Spektral- und Wavelet-Analyse
Eine endliche, verrauschte Aufzeichnung und die Frage, welche Frequenzen darin stecken und wie sie sich mit der Zeit ändern: sechzehn Stücke vom Periodogramm über Fenster, Modelle und Wavelets bis zum Verfahrensvergleich.