Particle Filter

Auch genannt: sequential Monte Carlo, SMC, bootstrap filter
Kategorie: State estimation & navigation › Localisation
Schlagwörter: state-estimation, localization, bayesian-filtering, probabilistic-robotics, monte-carlo

Ein Verfahren der Zustandsschätzung, das eine Belief-Verteilung als Menge gewichteter Stichproben darstellt, diese mit einem Bewegungsmodell verschiebt, sie nach der Sensor-Likelihood gewichtet und neu zieht.

Definition

Ein Partikelfilter (particle filter) ist ein rekursiver Bayes-Schätzer, der die Wahrscheinlichkeitsverteilung über den Zustand eines Systems durch eine Menge von Stichproben darstellt, die Partikel heißen und jeweils ein Gewicht tragen. Der Ansatz ist auch als Sequential Monte Carlo bekannt; seine vielzitierte Form, der Bootstrap-Filter, wurde 1993 von Gordon, Salmond und Smith veröffentlicht. In der Robotik wurde er durch die Monte-Carlo-Lokalisierung zum Standard, entwickelt von Dellaert, Fox, Burgard und Thrun, und wird in Probabilistic Robotics ausführlich behandelt.

Jede Aktualisierung hat drei Schritte. Im Prädiktionsschritt wird jedes Partikel gemäß dem Bewegungsmodell verschoben, wobei Rauschen hinzugefügt wird, um die Unsicherheit in Odometrie oder Steuerung widerzuspiegeln. Im Korrekturschritt (update) wird jedes Partikel danach gewichtet, wie gut die jüngste Sensormessung mit dem Zustand übereinstimmt, den es darstellt. Im Resampling-Schritt wird eine neue Partikelmenge proportional zu den Gewichten gezogen, sodass wahrscheinliche Hypothesen vervielfältigt werden und unwahrscheinliche verschwinden. Die Schätzung lässt sich aus dem gewichteten Mittel, dem besten Partikel oder einem Partikelcluster ablesen.

Anders als das Kalman-Filter und seine Erweiterungen nimmt ein Partikelfilter nicht an, dass die Belief-Verteilung gaußförmig ist. Er kann mehrere getrennte Hypothesen gleichzeitig halten, etwa einen Roboter, der sich in einem von zwei identischen Fluren befinden könnte, oder ein Objekt in der Hand, das in mehreren Posen sein könnte, die mit den bisher gespürten Kontakten vereinbar sind. Der Preis ist der Rechenaufwand: Die Zahl der benötigten Partikel wächst schnell mit der Dimension des Zustands, und wenn zu wenige Partikel nahe am wahren Zustand landen, kann der Filter auf eine falsche Antwort kollabieren. Praktische Filter verwenden daher Low-Variance-Resampling, resamplen nur, wenn die effektive Stichprobengröße sinkt, passen die Partikelzahl an und injizieren zufällige Partikel, um sich von Fehlern zu erholen.

Warum es wichtig ist

Viele Schätzprobleme in der Robotik sind nichtlinear und mehrdeutig, mit Belief-Verteilungen, die mehrere Gipfel statt eines haben. Der Partikelfilter behandelt diese direkt, weshalb er die Grundlage der Standard-2D-Lokalisierung auf mobilen Robotern und ein verbreitetes Werkzeug zur Schätzung von Objektposen aus Kontakt und Berührung ist.

Wichtige Anwendungen

Lokalisierung mobiler Roboter gegenüber einer bekannten Karte (Monte-Carlo-Lokalisierung)
Schätzung der Objektpose in der Hand aus Propriozeption und taktilem Kontakt
Verfolgung von Personen und Objekten in unübersichtlichen oder verdeckten Szenen
SLAM mit Rao–Blackwellized-Partikelfiltern wie FastSLAM und GMapping
Globale Lokalisierung und Wiederherstellung, wenn ein Roboter ohne sein Wissen versetzt wird

In der Praxis

Ein Lagerroboter mit dem ROS-Navigations-Stack lokalisiert sich typischerweise mit AMCL, einem Paket für adaptive Monte-Carlo-Lokalisierung. Beim Start gibt der Bediener eine grobe Anfangspose vor, und einige tausend Partikel werden um sie herum verteilt. Während der Roboter fährt, verschiebt die Radodometrie die Partikel, und jeder LiDAR-Scan gewichtet sie gegenüber der gespeicherten Belegungskarte neu; die Wolke zieht sich innerhalb weniger Meter Fahrt um die wahre Pose zusammen. Ingenieure stimmen die Odometrie-Rauschparameter auf den realen Antriebsstrang ab, legen minimale und maximale Partikelzahlen fest und beobachten die Partikelwolke in RViz: Eine Wolke, die sich in einem sich wiederholenden Gang in zwei Cluster teilt, ist ein Zeichen, dass der Filter zwei Hypothesen verfolgt und ein markantes Merkmal braucht, um sie aufzulösen.

Häufige Missverständnisse

Mehr Partikel lösen Genauigkeitsprobleme immer — der Partikelbedarf wächst schnell mit der Zustandsdimension, daher brauchen hochdimensionale Probleme bessere Vorschlagsverteilungen oder Struktur, nicht nur mehr Stichproben
Ein Partikelfilter ist nur ein langsameres Kalman-Filter — er stellt nicht gaußförmige, mehrgipflige Belief-Verteilungen dar, die Filter vom Kalman-Typ nicht darstellen können
Resampling in jedem Schritt ist immer am besten — zu häufiges Resampling verwirft Vielfalt; viele Filter resamplen nur, wenn die effektive Stichprobengröße unter einen Schwellwert fällt
Der Filter erholt sich immer von einer falschen Schätzung — sind die Partikel einmal fern vom wahren Zustand kollabiert, können sie nicht zurückkehren, es sei denn, es werden zufällige Partikel injiziert

Wer das wissen sollte

Ingenieure für Lokalisierung und Navigation mobiler Roboter
Entwickler für Zustandsschätzung und SLAM
Forschende in der Manipulation, die Objektposen aus Berührung schätzen
Robotikstudierende, die probabilistische Robotik lernen

Videos

Understanding the Particle Filter | | Autonomous Navigation, Part 2: MATLAB
Particle Filter - 5 Minutes with Cyrill: Cyrill Stachniss

Wikipedia

Sequenzielle Monte-Carlo-Methode

Open Source Robotics