Der Partikelfilter verständlich erklärt

Ein Fahrzeug fährt an einem Funkmast vorbei, der nur misst, wie weit es entfernt ist. Es kann auf zwei Seiten sein, und beide sehen für den Mast gleich aus. Diese Seite zeigt, wie ein Partikelfilter beide Möglichkeiten offen hält, wann das nützt und was es kostet.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Ein Funkmast und zwei mögliche Orte

Ein Lieferwagen fährt eine gerade Straße entlang. Neben der Straße steht ein Funkmast. Er misst nur, wie weit der Wagen von ihm entfernt ist. Die Straße führt im festen Abstand am Mast vorbei. Ob sie links oder rechts vom Mast liegt, wissen Sie nicht.

Zwei Orte, die spiegelbildlich zum Mast liegen, sind gleich weit von ihm entfernt. Der Mast kann sie deshalb nicht unterscheiden. Es gibt also zwei Möglichkeiten, die gleich gut zur Messung passen.

Ein Alltagsbild: Ihr Handy klingelt irgendwo in der Wohnung, und Sie hören nur, wie laut es ist. Es kann im Wohnzimmer oder im Schlafzimmer liegen, beide gleich weit entfernt. Wer sich in den Flur zwischen die Zimmer stellt, steht genau dort, wo das Handy nicht liegen kann.

Ein Verfahren mit nur einem Tipp macht es zunächst wie die Person im Flur. Es nennt einen besten Ort und einen Bereich darum, der nur eine einzige Glocke bildet (Fachwort: Gauß-Filter). Dieser Ort liegt zwischen den beiden Möglichkeiten, wo der Wagen nicht sein kann.

Viele Tipps statt einem

Der Partikelfilter nutzt viele Tippgeber. Jeder tippt, wo der Wagen ist und wie schnell er fährt. Ein solcher Tipp heißt Partikel, alle zusammen heißen Wolke. Am Anfang liegen die Tipps weit gestreut, auch auf beiden Seiten des Masts.

Dann wiederholt der Filter jede Sekunde drei Schritte:

• Weiterfahren. Jeder Tipp fährt mit dem Wagen weiter, jeder mit einer eigenen kleinen Zufallsabweichung. Denn niemand weiß, ob der Fahrer Gas gibt oder bremst.
• Bewerten. Der Mast meldet eine neue Entfernung. Tipps, die dazu passen, bekommen viel Gewicht, die anderen wenig. Gewicht heißt: wie viele Stimmen ein Tipp hat. Beide Seiten passen gleich gut, also behalten beide Gruppen ihre Stimmen.
• Neu verteilen. Haben nur noch wenige Tipps fast alle Stimmen, verteilt der Filter die Wolke neu. Tipps mit vielen Stimmen werden dabei kopiert, solche mit wenigen fallen weg. Sonst verschwendet der Filter Rechenzeit an Tipps, die nichts mehr beitragen.

So bildet die Wolke zwei Haufen, einen auf jeder Seite. Mit genug Tipps legt sich der Filter nicht fest, solange nichts entscheidet. Außer der Bewegung des Wagens braucht er dafür nur eine Fähigkeit: für jeden Tipp auszurechnen, welche Entfernung der Mast dann melden würde.

Was ein zweiter Mast ändert

Nun kommt ein zweiter Funkmast an anderer Stelle dazu. Für die beiden möglichen Orte meldet er verschiedene Entfernungen. Jetzt passt nur noch ein Haufen zur Messung. Er behält seine Stimmen, der andere verliert sie, und die Wolke folgt dem richtigen Wagen.

Kommt der zweite Mast nie, bleibt die Frage offen. Der Partikelfilter hält dann beide Möglichkeiten länger offen, solange die Wolke genug Tipps hat.

Das Programm zum Ausprobieren

Die Messungen auf dieser Seite stammen aus einem Programm zum Ausprobieren im Browser, der Demo. Der erste Knopf unten öffnet es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie es nicht.

Es beruht auf einem vereinfachten Rechenbild (Fachwort: Modell): Der Wagen fährt ungefähr mit gleichem Tempo, und die Zufallsschwankungen sind dem Filter bekannt.

Der Haken: genug Tipps

Die Demo spielt die Aufgabe mit dreißig festen, simulierten Fahrten durch. Der zweite Mast kommt zu einem festen Zeitpunkt dazu. Gezählt wird, in wie vielen Fahrten der Filter am Ende auf der richtigen Seite landet:

• 300 Tipps: richtige Seite in 47 % der Fahrten.
• 1000 Tipps: richtige Seite in 77 % der Fahrten.
• 3000 Tipps: richtige Seite in 97 % der Fahrten.

Woran liegt das? Bei jedem Neu-Verteilen wird gelost, und der Anteil jeder Seite wackelt ein wenig. Über viele Sekunden summiert sich das wie in einem Spiel, in dem jede Runde zufällig Spielsteine wechseln, bis einer alle hat. Dann ist eine Seite leer, und niemand holt sie zurück. Mit mehr Tipps wackelt der Anteil weniger. Das ist eine Deutung dieser Seite; die Nachzählung steht im zweiten Teil.

Zum Vergleich der UKF: ein Gauß-Filter, also das Verfahren mit einem Tipp und einer einzigen Glocke aus dem ersten Abschnitt. Sein Tipp liegt zunächst in der Mitte, wie bei der Person im Flur. Seine Glocke ist aber so breit, dass beide Orte darin liegen. Kommt der zweite Mast, springt der Tipp aus der Mitte auf die richtige Seite. Zufall löscht dabei nichts. So findet der UKF in 97 % der Fahrten die richtige Seite.

Bei der Frage nach der richtigen Seite ist der Partikelfilter hier also nicht besser, mit 1000 Tipps sogar schlechter. Sein Vorteil liegt davor: Wer wissen will, wo der Wagen sein könnte, sieht in der Wolke beide Orte. Mit 1000 Tipps sitzen 82 % der Stimmen nahe an den beiden Orten. Beim UKF liegen nur 9 % seiner Glocke dort, der Rest ist ein breiter Nebel über der Mitte. Kommt der zweite Mast nie, findet keines der beiden Verfahren die Seite zuverlässig.

Was die Wolke kostet

Mehr Tipps heißen mehr Rechenzeit. Ist die Messung eindeutig, etwa weil der Mast auch die Richtung misst, gibt es nur einen Haufen. Dann ist die Wolke ab etwa 1000 Tipps so genau wie die Verfahren mit einem Tipp, aber nicht besser.

Der größere Preis betrifft die Zahl der Größen. Man kann aber viele Angaben zugleich schätzen, etwa für viele Fahrzeuge. Jede heißt hier Größe. Ein Tipp zählt nur, wenn er bei allen Größen zugleich zur Messung passt. Eine einzelne Ziffer einer Postleitzahl raten Sie öfter richtig, als alle fünf auf einmal.

Die Demo rechnet das in einer Rechenprobe ohne Fahrzeug durch, in der Messung und Anfangswissen gleich stark streuen. Bei einer Größe zählen noch 87 % der Tipps, bei sechzehn Größen nur noch 11 %. Bei schärferer Messung geht es noch schneller bergab: Bei zweiunddreißig Größen bleibt praktisch ein einziger Tipp übrig.

Häufige Missverständnisse

• „Der Mittelpunkt der Wolke zeigt den Ort.“ Bei zwei Haufen liegt er dazwischen, wie die Person im Flur. Aussagekräftig ist, wie viel Gewicht an welchem der beiden Orte liegt.
• „Der Partikelfilter ist der genauere Filter.“ Bei der Frage nach der richtigen Seite war er hier nicht besser als der UKF.

Woran Sie das im Alltag erkennen

• Eine Auskunft nennt eine Mitte, wo nichts passiert. Beispiel: Der Zug fährt entweder pünktlich um acht oder als Ersatzzug um zehn, angekündigt wird „gegen neun“.
• Ein Kartengerät springt zwischen zwei nahen Straßen hin und her. Dann sind vielleicht zwei Möglichkeiten im Rennen.
• Eine Frage entscheidet sich erst durch einen zweiten Hinweis. Beispiel: Sie gehen im Haus ins Wohnzimmer, und das Klingeln wird leiser. Dann liegt das Handy im Schlafzimmer.

Was Sie mitnehmen

• Fragen Sie bei einer Schätzung, ob es auch zwei verschiedene Antworten geben könnte und ob die Auskunft beide zeigt.
• Eine Wolke von Tipps ist nur so verlässlich, wie sie Tipps hat. Wenige sind ein Glücksspiel.
• Je mehr Größen zugleich zu schätzen sind, desto eher braucht es ein anderes Verfahren als diese einfache Wolke.

Wie ernst ist das Rechenbild zu nehmen?

Fahrt, Funkmasten und Zufallsschwankungen sind simuliert. Echte Messdaten und ein echtes Straßennetz kommen nicht vor. Die Aussagen gelten für dieses Beispiel mit den gewählten Einstellungen.

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.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Die genannten Messwerte stammen aus der Beschreibung des Projekts zur Demo (verlinkt unter „Quellen“) und gelten für simulierte Fahrten, nicht für echte Daten. Zahlenwerte ohne Messwert-Charakter (Voreinstellungen, Anfangsstreuungen) sind als Worte geschrieben und stammen aus dem Quelltext der Demo.

Zustand und Bewegung. Ein Fahrzeug fährt auf einer geraden Straße bei \(p_y = 60\) m. Der Zustand \(x_k = (p_x, p_y, v_x, v_y)^\top\) enthält die Ortskoordinaten \(p = (p_x, p_y)\) und die Geschwindigkeit \(v = (v_x, v_y)\) im Takt \(k\); ein Takt dauert eine Sekunde (\(\Delta t\)). Das Bewegungsmodell hat konstante Geschwindigkeit, gestört durch eine zufällige Beschleunigung \(\eta_k\): \(x_{k+1} = F x_k + \eta_k\) mit \(\eta_k \sim \mathcal N(0, Q)\), \(F = \begin{pmatrix} I_2 & \Delta t\, I_2\\ 0 & I_2\end{pmatrix}\) und \(Q = q^2\begin{pmatrix}\tfrac{\Delta t^3}{3} I_2 & \tfrac{\Delta t^2}{2} I_2\\ \tfrac{\Delta t^2}{2} I_2 & \Delta t\, I_2\end{pmatrix}\). Die Achsen sind nicht gekoppelt. Die Fahrunruhe \(q\) ist die Stärke der zufälligen Beschleunigung; streng gerechnet hat sie die Einheit m/s hoch drei Halbe, bei einem Takt von einer Sekunde ist der Zahlenwert der einer Beschleunigung in m/s².

• Messung: Eine Bake im Ursprung misst die Entfernung \(\sqrt{p_x^2 + p_y^2}\) mit gaußschem Rauschen der Standardabweichung \(\sigma_r\) (in den Befunden 3 m). Optional misst ab einer gewählten Sekunde eine zweite Bake bei \((0, 30)\) ebenfalls die Entfernung. Die zweite Messart, Entfernung und Peilung zur Bake im Ursprung (Peilrauschen drei Grad), ist eindeutig.
• Zweideutigkeit: Die Entfernung zur Bake im Ursprung hängt nur von \(p_x^2 + p_y^2\) ab, ist also für \((p_x, p_y)\) und \((p_x, -p_y)\) gleich. Spiegelt man einen ganzen Zustand samt \(v_y\) an der Achse \(p_y = 0\), erzeugt er dieselben Messungen, und das Bewegungsmodell ist zu dieser Spiegelung symmetrisch. Die zweite Bake bricht die Symmetrie: \(\lvert 60 - 30\rvert \neq \lvert -60 - 30\rvert\) (Rechnung dieser Seite).
• Vorwissen und Fahrt: Der Anfangszustand ist normalverteilt: \(p_x\) mit Streuung fünf Meter um den Startpunkt (hundert Meter vor der Bake), \(p_y\) mit Streuung sechzig Meter und Mittel null, die Seite der Straße ist also unbekannt und beide Seiten haben dasselbe Gewicht. Die Geschwindigkeit hat Mittel fünf Meter pro Sekunde in \(p_x\)-Richtung, null in \(p_y\)-Richtung und je Komponente Streuung ein Meter pro Sekunde. Eine Fahrt hat siebzig Takte.
• Einstellbereiche: Partikelzahl 100 bis 10 000 (Voreinstellung 1000); Entfernungsrauschen von einem bis zehn Meter (Voreinstellung 3 m); Fahrunruhe von zwei bis fünfzig Hundertstel (Voreinstellung fünf Hundertstel); zweite Bake ab Sekunde zwanzig, 30 (Voreinstellung), vierzig, fünfzig oder nie.
• Verfahren: Der EKF linearisiert die Messfunktion an der Vorhersage. Der UKF verwendet Sigma-Punkte statt einer Linearisierung (Skalierungsparameter: Streuung eins, Verteilungsparameter zwei, Zusatzparameter eins); beide führen eine Normalverteilung. Der Partikelfilter ist der einfache Bootstrap-Filter: Er braucht die Auswertung der Messfunktion \(h\) (keine Ableitung, keine Sigma-Punkte), dazu das Bewegungs- und das Rauschmodell.
• Maße: Der Positionsfehler ist die Wurzel des mittleren quadratischen Fehlers einer Fahrt, ohne die ersten fünf Takte (Einschwingzeit). „Gefunden“ heißt: Der Positionsfehler am Ende der Fahrt liegt unter 15 m. Die Gipfelmasse ist das Gewicht der Partikel (beim Gauß-Filter die Wahrscheinlichkeit), die weniger als 15 m von einem der beiden möglichen Orte \((p_x, p_y)\) und \((p_x, -p_y)\) der Wahrheit entfernt liegen. Die Schwelle 15 m dient also zwei Zwecken: dem Endfehler und dem Umkreis der Gipfelmasse. Als „obere Seite“ gilt \(p_y > 0\), die wahre Seite der Straße.
• Die Wahrheit ist das Modell: Fahrt und Filter teilen Bewegungsmodell, Messmodell und Rauschwerte. Echte Sensordaten sind nicht im Spiel.

Der Filter und seine Formeln

Der Partikelfilter stellt die Verteilung \(p(x_k \mid z_{1:k})\) des Zustands gegeben alle Messungen \(z_1, \dots, z_k\) als gewichtete Stichprobe \(\{(x_k^{(i)}, w_k^{(i)})\}_{i=1}^N\) dar. Pro Takt: (1) Vorhersagen: \(x_k^{(i)} \sim \mathcal N(F x_{k-1}^{(i)}, Q)\), jedes Partikel mit eigenem Rauschen. (2) Gewichten: \(w_k^{(i)} \propto w_{k-1}^{(i)}\, p(z_k \mid x_k^{(i)})\) mit \(p(z \mid x) \propto \exp(-\tfrac{1}{2} (z - h(x))^\top R^{-1} (z - h(x)))\), danach auf Summe eins normiert; \(h\) ist die Messfunktion, \(R\) die Kovarianz des Messrauschens. Weil die Vorschlagsverteilung hier die Bewegung selbst ist, bleibt vom Gewicht nur die Likelihood der Messung. (3) Neu ziehen, wenn die effektive Stichprobengröße unter \(N/2\) fällt:

\[N_{\mathrm{eff}} = 1 \Big/ \textstyle\sum_i (w^{(i)})^2\]

\(N_{\mathrm{eff}}\) liegt zwischen eins (ein Partikel hat das ganze Gewicht) und \(N\) (alle Gewichte gleich). Beim systematischen Resampling genügt ein Zufallswert \(c \in [0, 1)\): Die \(N\) Stützpunkte \((c + j)/N\), \(j = 0, \dots, N-1\), laufen gleichmäßig über die Summenfolge der Gewichte, jedes Partikel wird so oft kopiert, wie Stützpunkte in sein Intervall fallen, und danach sind alle Gewichte gleich. Die Zahl der Kopien weicht um weniger als eins vom Erwartungswert \(N w^{(i)}\) ab.

Der gewichtete Mittelwert \(\hat x_k = \sum_i w_k^{(i)} x_k^{(i)}\) ist bei mehreren Gipfeln kein Ort der Verteilung. Die Demo liest deshalb die Gipfelmasse (siehe „Maße“).

Gewichtskollaps in hoher Dimension, Schritt für Schritt

Rechenprobe ohne Fahrzeug, nur ein Gewichtungsschritt. Die Herleitung ist eine Rechnung dieser Seite; ihr Ergebnis ist die Formel, die die Demo gegen die Messung hält.

• Aufbau: Der Prior ist \(\mathcal N(0, I_d)\) in \(d\) Dimensionen, \(\theta\) ein Vektor daraus. Jede Komponente wird einzeln mit der Streuung \(s\) gemessen (in Einheiten der Prior-Streuung), und der Messwert fällt auf den Prior-Mittelwert. Das Gewicht eines Partikels ist dann \(w(\theta) \propto \exp(-\lVert \theta\rVert^2 / 2s^2)\).
• Näherung: Mit nicht normierten Gewichten \(\tilde w_i\) ist \(N_{\mathrm{eff}}/N = (\tfrac1N\sum_i \tilde w_i)^2 / (\tfrac1N\sum_i \tilde w_i^2)\). Für großes \(N\) geht das nach dem Gesetz der großen Zahlen gegen \((E\,w)^2 / E\,w^2\).
• Eine Komponente: Für \(\theta_1 \sim \mathcal N(0, 1)\) gilt \(E\,e^{-a \theta_1^2} = (1 + 2a)^{-1/2}\). Mit \(a = 1/(2s^2)\) und \(a = 1/s^2\) folgen \(E\,w = (1 + 1/s^2)^{-1/2}\) und \(E\,w^2 = (1 + 2/s^2)^{-1/2}\).
• Alle Komponenten: Sie sind unabhängig, die Erwartungen multiplizieren sich über \(d\) Faktoren. Das ergibt:

\[\frac{N_{\mathrm{eff}}}{N} \approx \frac{(E\,w)^2}{E\,w^2} = \left(\frac{1 + 2/s^2}{(1 + 1/s^2)^2}\right)^{d/2}.\]

Der Klammerwert liegt für jedes endliche \(s\) unter eins, denn mit \(u = 1/s^2\) ist \((1 + 2u) - (1 + u)^2 = -u^2\). Der Anteil wirksamer Partikel fällt also mit \(d\) exponentiell. Für \(s = 1\) ist der Klammerwert drei Viertel: Die Formel liefert \(\sqrt{3/4}\) bei \(d = 1\) (rund 87 %) und \((3/4)^2\) bei \(d = 4\) (rund 56 %). Für \(d = 16\) liefert sie ein Zehntel, die Messung 11 %.

Die schärfere Messung der Demo hat ein Streuungsverhältnis etwas unter einem Drittel (gut dreimal schärfer). Für genau ein Drittel (\(u = 9\)) wäre der Klammerwert neunzehn Hundertstel, und die Formel sagte für \(d = 8\) gut einen wirksamen Partikel von 1000 voraus; beim etwas kleineren Verhältnis der Demo ist es etwas weniger als einer (Rechnung dieser Seite). Gemessen wurden 3 von 1000, unter anderem weil \(N_{\mathrm{eff}} \geq 1\) gilt und die Näherung für große \(N\) bei so kleinen Anteilen nicht mehr gilt. Die Aussage hängt also an dem genauen Verhältnis.

Durchgerechnet: warum die zweite Bake entscheidet

Rechnung dieser Seite, keine Messung der Demo. Ein Partikel auf der falschen Seite liegt an einem Ort, dessen Entfernung zur zweiten Bake sich stark von der wahren unterscheidet. Beispiel am Ort \(p_x = 0\), den das Fahrzeug in Sekunde zwanzig erreicht: Die wahre Entfernung zur Bake bei \((0, 30)\) ist \(\lvert 60 - 30\rvert\), die des Spiegelorts \(\lvert -60 - 30\rvert\), also dreimal so groß. Der Unterschied beträgt das Zwanzigfache des Messrauschens von 3 m, und das Gewicht der falschen Gruppe sinkt um mehr als achtzig Zehnerpotenzen (im Exponenten steht das halbe Quadrat des Abstands in Streuungen). Bei der Voreinstellung, zweite Bake ab Sekunde 30, steht das Fahrzeug bei \(p_x\) gleich fünfzig Meter; dort ist der Unterschied rund fünfzehn Streuungen und der Faktor noch rund achtundvierzig Zehnerpotenzen. Solange die richtige Gruppe noch Partikel hat, fällt die Entscheidung damit praktisch mit der ersten Messung der zweiten Bake. Hat die richtige Gruppe keinen Partikel mehr, gewinnt die falsche trotzdem, denn nach dem Normieren hat sie das ganze Gewicht, auch wenn sie schlecht passt. Das betrifft das Gewicht der Seiten, nicht die Schwelle „gefunden“ (siehe Grenzen). Bei der Voreinstellung der Fahrunruhe reicht die Zufallsbeschleunigung nicht, um Partikel über den Abstand der beiden Orte zu bringen (Abschätzung dieser Seite aus der Streuung der Zufallsbeschleunigung über die Fahrtdauer).

Befunde

Alle Zahlen: Anteil, Median oder Mittel über 30 feste, simulierte Fahrten, Entfernungsrauschen 3 m, 1000 Partikel, wo nichts anderes steht. Der Positionsfehler ist der Median der Fehler je Fahrt, der Anteil „gefunden“ ein Anteil von Fahrten, die Gipfelmasse ein Mittel über Fahrten. Die Dimensionsrechnung kommt ohne Fahrten aus und bildet Mittel über Wiederholungen.

Frage	Befund
Wie viele Partikel bei eindeutiger Messung (Entfernung und Peilung)?	Positionsfehler 6,1 m (100 Partikel), 3,4 m (300), 2,4 m (1000), 2,3 m (10 000); EKF 2,4 m, UKF 2,2 m. Ab etwa 1000 Partikeln liegt der Partikelfilter auf dem Niveau der Gauß-Filter. Die Rechenzeit des Partikelfilters wächst mit der Partikelzahl; von 1000 auf 10 000 Partikel grob auf das Vierfache (Nachmessung dieser Seite, rechnerabhängig; der Test verlangt mehr als das Dreifache). Rechenzeiten von EKF und UKF misst die Demo nicht.
Mehrdeutige Entfernungsmessung, zweite Bake ab Sekunde 30: Wer findet die richtige Seite?	EKF 0 %, UKF 97 %, Partikelfilter (1000 Partikel) 77 %.
Und mit anderer Partikelzahl?	Partikelfilter: 47 % (300 Partikel), 77 % (1000), 97 % (3000).
Wo liegt der Vorteil des Partikelfilters?	Vor der zweiten Bake liegen 82 % seines Gewichts auf den beiden möglichen Orten (innerhalb 15 m), beim UKF 9 %.
Wenn die zweite Bake nie kommt	Gefunden: UKF 0 %, Partikelfilter 13 %. Das Gewicht des Partikelfilters auf der oberen Seite (\(p_y > 0\)) beträgt im Mittel über die Fahrten 44 %.
Wie viele Partikel bleiben wirksam? (ein Gewichtungsschritt, 1000 Partikel, Mittel)	Messstreuung gleich Prior-Streuung: 87 % (1 Dimension), 56 % (4), 32 % (8), 11 % (16). Bei gut dreimal schärferer Messung (Streuungsverhältnis etwas unter einem Drittel): 40 % (1), 2,6 % (4), 3 von 1000 Partikeln (8), praktisch einer (32).

Warum der UKF die Seite findet (Nachmessung dieser Seite mit dem Programmcode der Demo, fünf Fahrten, zweite Bake ab Sekunde 30, kein Befund der Demo): Vor der zweiten Bake liegt der UKF-Mittelwert in \(p_y\) bei null, mit einer Streuung, die etwas größer ist als der Abstand der beiden Orte von der Mitte (60 m). Die Normalverteilung überdeckt also beide Orte, verteilt ihre Wahrscheinlichkeit aber dünn über einen großen Bereich; das erklärt die niedrige Gipfelmasse von 9 %. Die zweite Bake zieht den Mittelwert dann von der Mitte auf die richtige Seite, und nach wenigen Sekunden ist die Streuung in \(p_y\) auf wenige Meter geschrumpft.

Nachmessung zum Partikelverlust (ebenso, dreißig Fahrten, zweite Bake ab Sekunde 30, kein Befund der Demo): Gelesen wurde das Gewicht der Partikel auf der wahren Seite in der Sekunde vor der zweiten Bake. Als „fast leer“ gilt eine Seite mit weniger als einem Zwanzigstel des Gewichts. Bei 300 Partikeln war in sechsundzwanzig von dreißig Fahrten eine Seite fast leer (zehnmal die wahre, sechzehnmal die falsche), bei 1000 Partikeln in sechs (viermal die wahre), bei 3000 Partikeln in keiner. Von den zehn Fahrten mit fast leerer wahrer Seite wurde bei 300 Partikeln eine gefunden, von den vier bei 1000 Partikeln ebenfalls eine. Ohne zweite Bake war nach der ganzen Fahrt bei 1000 Partikeln noch in acht von dreißig Fahrten eine Seite fast leer.

Grenzen und was die Messung zeigt

• Die Wahrheit ist das Modell. Es gibt keine echten Sensordaten und kein Straßennetz. Die Befunde zeigen, was die Verfahren bei richtigen Annahmen leisten.
• Beim Positionsfehler ist der Partikelfilter nicht besser als der UKF. Bei 1000 Partikeln findet der UKF die richtige Seite häufiger (97 % gegen 77 %); bei 3000 Partikeln liegen beide gleichauf (97 %). Ein Anteil aus 30 Fahrten hat einen Zufallsfehler von grob acht Prozentpunkten (Nachrechnung dieser Seite, binomial), der Abstand von zwanzig Punkten liegt darüber; einzelne Prozentpunkte sind nicht belastbar. Ein Gaußsummenfilter, der mehrere Gipfel führt, gehört nicht zum Vergleich.
• Warum der EKF scheitert, ist nur teilweise erklärt. Der Anfangsmittelwert hat \(p_y = 0\); dort ist die \(p_y\)-Komponente der Jacobi-Zeile der Entfernung zur ersten Bake null, die Messung zieht also nicht zu einer Seite, und der Mittelwert bleibt bis zur zweiten Bake bei \(p_y = 0\) (Nachmessung dieser Seite an einigen Fahrten). Die zweite Bake hat dort eine von null verschiedene Ableitung; die Linearisierung aus der Mitte führt dann weit daneben, mit Fehlern von mehreren hundert Metern am Ende. Warum genau, ist nicht untersucht.
• Der Mittelwert einer zweigipfligen Wolke ist kein Ort. Für „nie“ gibt es keinen sinnvollen Punktschätzer; man liest die Masse um die möglichen Orte.
• Ein Mittel über Fahrten sagt nichts über die einzelne Fahrt. Die 44 % auf der oberen Seite, wenn die zweite Bake nie kommt, mischen nach der Nachmessung Fahrten mit ausgewogener Wolke und Fahrten, in denen schon fast eine Seite fehlt. „Beide Möglichkeiten offen“ gilt je Fahrt nur, solange genug Partikel da sind.
• Der Verlust einer Seite erklärt nicht alle verfehlten Fahrten. Bei 1000 Partikeln waren sieben Fahrten nicht gefunden: In dreien war die wahre Seite fast leer. In den vier anderen lag die Schätzung auf der richtigen Seite, der Fehler von sechzehn bis einunddreißig Metern fast ganz in \(p_y\) (Nachmessung dieser Seite). Eine mögliche Deutung (nicht nachgewiesen): Bei großem \(p_x\) ändern sich beide Entfernungen kaum noch mit \(p_y\), die Seitenlage ist dort schwach bestimmt, und eine dünne Wolke bildet das nicht genau ab. Dass der Verlust einer Seite Zufall des Resamplings ist, ist ebenfalls eine Deutung dieser Seite.
• Die Dimensionsrechnung ist der günstigste Fall. Sie misst nach einem Gewichtungsschritt, mit Messwert im Prior-Mittel und unabhängigen Komponenten. Wiederholtes Gewichten und Resampling in hoher Dimension zeigt sie nicht; die Formel gilt für große \(N\), bei sehr kleinen Anteilen liegt die Messung darüber.
• Bootstrap-Filter, nichts Besseres. Bessere Vorschlagsverteilungen, Rao-Blackwellisierung und Ensemble-Filter für hohe Dimension sind nicht umgesetzt; die Dimensionsaussage gilt für den einfachen Filter.
• Rechenzeiten sind Messungen eines bestimmten Rechners und plattformabhängig; nur ihre Größenordnung gilt.

Wie die Demo geprüft ist

Die Tests rechnen den Kern auf anderem Weg nach: Mit 40 000 Partikeln liegt der Partikelfilter im linear-gaußschen Grenzfall nahe am exakten Kalman-Filter. Der UKF gleicht bei linearer Messung dem EKF. Nach einer Entfernungsmessung stimmt der Partikelfilter mit dem exakten Posterior auf einem Gitter überein, einschließlich der beiden Gipfel mit je etwa der Hälfte der Masse. Effektive Stichprobengröße, Gipfelmasse und systematisches Resampling werden gegen Formel, Schleife und Handrechnung geprüft, die zitierten Messzahlen mit Toleranzbändern. Das zeigt, dass die Rechnung zum Modell passt, nicht, dass das Modell die Wirklichkeit trifft.

Quellen

• Gordon, N. J., Salmond, D. J., Smith, A. F. M. (1993): Novel approach to nonlinear/non-Gaussian Bayesian state estimation. IEE Proceedings F (Radar and Signal Processing) 140(2), 107–113 (der Bootstrap-Filter).
• Snyder, C., Bengtsson, T., Bickel, P., Anderson, J. (2008): Obstacles to high-dimensional particle filtering. Monthly Weather Review 136(12), 4629–4640 (der Bedarf an Partikeln wächst beim einfachen Filter exponentiell mit der Dimension; Resampling behebt das nicht).
• Julier, S. J., Uhlmann, J. K. (2004): Unscented filtering and nonlinear estimation. Proceedings of the IEEE 92(3), 401–422 (der UKF).
• Quelltext, Messreihen, Tests und Projektbeschreibung der Demo: github.com/sebastian-hanisch/particle-filter-demo.

Die drei Werke wurden für diese Seite nicht nachgeschlagen; die ersten beiden Angaben stammen aus der Demo, die dritte aus dem Gedächtnis. Die Herleitung des Gewichtskollapses, die Rechnungen zur zweiten Bake und die Nachmessungen sind Rechnungen dieser Seite, nicht gegen die Literatur geprüft.