Sequenzielle Monte-Carlo-Methode

Sequenzielle Monte-Carlo-Methoden (SMC-Methoden) gehören zur Klasse der stochastischen Verfahren zur Zustandsschätzung in einem dynamischen Prozess (z. B. in der mobilen Robotik), dessen Dynamik nur im statistischen Mittel bekannt ist (wesentliche Störgrößen) und der nur unvollständig beobachtet werden kann (Unterteilung in innere, verborgene und äußere, sichtbare Variable). Ein Anwendungsbeispiel ist die genaue und kontinuierlich aktualisierte Bestimmung des Ortes und der Geschwindigkeit eines Objektes aufgrund einer ungenauen und fehlerhaften Messung des Ortes (vgl. Tracking). SMC-Filter sind auch bekannt als Partikel-Filter, sampling importance resampling (SIR), sequential importance sampling (SIS), bootstrap filters, condensation trackers, interacting particle approximations oder survival of the fittest.

Problemstellung

Beispielhafter Signalverlauf (rot) nach einem Partikel-Filter

Häufig steht man vor dem Problem, dass der Zustand eines dynamischen Systems (z. B. der Ort von Objekten) für einen Beobachter nicht direkt, sondern nur über Messungen zugänglich ist. In diesem Fall spricht man von verborgenen Zuständen (engl. hidden state). Eine Messung des Zustandes ist aber prinzipiell immer fehlerbehaftet (verrauscht), d. h. im Allgemeinen gibt die Messung den wahren Zustand nicht korrekt wieder. Aufgrund der Messung ist es aber möglich, den unbekannten Zustand zu schätzen.

Für den Fall eines linearen Prozessmodells und unter Annahme normalverteilter Störgrößen und Messfehler wurde 1961 das kontinuierliche Kalman-Filter von Kalman und Bucy eingeführt, um den wahrscheinlichsten Zustand rekursiv aus den vorhergehenden Schätzungen und den erhaltenen Messwerten zu bestimmen. Im Falle, dass das Prozessmodell wesentlich nichtlinear ist oder die Störeinflüsse nicht als normalverteilt angenommen werden können, kann nicht von einer Normalverteilung des zu schätzenden Zustandes ausgegangen werden. Es muss weiter u. a. in Betracht gezogen werden, dass die Wahrscheinlichkeitsdichte mehrere Maxima aufweist, d. h. die gemachten Beobachtungen zu mehreren inneren Zuständen kompatibel sind. Ein gitterbasierter Ansatz zur Lösung dieses erweiterten Problems besteht in der Transformation der Systemdynamik in eine Dynamik der Wahrscheinlichkeitsdichte auf den Zustandsraum (s. Stochastische Differentialgleichung). Die Lösung der dabei entstehenden partiellen Differentialgleichungen mittels Finite-Elemente-Methoden bzw. Finite-Differenzen-Methoden ist im Allgemeinen recht rechenintensiv.

Grundidee der SMC-Methoden

Ziel der SMC-Methoden ist es, die gerade aktuelle, aber unbekannte Wahrscheinlichkeitsdichte auf dem Zustandsraum zu schätzen, um daraus Aussagen über den wahrscheinlichsten Systemzustand des dynamischen Systems abzuleiten. Dazu wird eine Wolke bzw. ein Schwarm sogenannter Partikel erzeugt, die Paare aus einem Gewicht und einem Punkt im Zustandsraum sind. Dabei soll der Schwarm als Ganzes die Wahrscheinlichkeitsdichte in einem Anfangszustand repräsentieren (Bootstrap). Jedem einzelnen Partikel wird nun mittels des stochastischen Modells der Systemdynamik eine oder mehrere Lösungskurven zugeordnet. Je nachdem, wie die aus dieser Lösungskurve abgeleiteten Vorhersagen der Messwerte mit den tatsächlichen übereinstimmen, kann das Gewicht der Partikel angepasst werden, woraus sich in sequenzieller Weise eine verbesserte Schätzung der Evolution der Wahrscheinlichkeitsdichte im Zustandsraum ergibt. Aufgrund dessen kann sogar die anfängliche Zusammensetzung des Schwarms angepasst werden, um genauere Ergebnisse zu erhalten (Re-Bootstrap). Da in die zeitliche Entwicklung des Systems zufällige Störgrößen eingehen, handelt es sich um eine Monte-Carlo-Simulation. Der Übergang von der gewichteten Partikelwolke zur Wahrscheinlichkeitsdichte kann mit Methoden der nichtparametrischen Dichteschätzung erfolgen.

Vorteile der SMC-Methoden

Die Vorteile von SMC-Filter sind:

• Sie schätzen die gesamte unbekannte A-posteriori-Wahrscheinlichkeitsdichte und lassen sich für nicht-gaußsche Verteilungen anwenden.
• Die geschätzten Verteilungen können multimodal sein, d. h. die Verteilung kann mehrere Maxima haben.
• Die Systemdynamik und die Messdynamik können auch nichtlinear sein.
• Die Simulation der einzelnen Partikel ist sehr einfach parallelisierbar.

Literatur

• Arnaud Doucet, Nando DeFreitas, Neil Gordon: Sequential Monte Carlo Methods in Practice, ISBN 0-387-95146-6.
• Branko Ristic, Sanjeev Arulampalam, Neil Gordon: Beyond the Kalman Filter: Particle Filters for Tracking Applications, Artech House Publishers 2004, ISBN 1-58053-631-X.

Weblinks

• Videobeispiele (engl.)
• Sequential Monte Carlo Methods (Particle Filtering), University of Cambridge (engl.)
• Tech Talk über eine Weiterentwicklung der Partikelfiltermethode (engl.)