imported>MrBenjo: +Normdaten

2024-03-04T20:10:29Z

+Normdaten

Neue Seite

'''Sequenzielle [[Monte-Carlo-Simulation|Monte-Carlo-Methoden]]''' (SMC-Methoden) gehören zur Klasse der stochastischen Verfahren zur [[Bayessche Schätzung|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 [[Messfehler|fehlerhaften Messung]] des Ortes (vgl. [[Tracking (Spurverfolgung)|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 ==
[[Datei:Particle filter example small.png|mini|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 (''[[Rauschen (Physik)|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 [[Lineares System (Systemtheorie)|linearen Prozessmodells]] und unter Annahme [[Normalverteilung|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 [[Nichtlineares System|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 [[Partielle Differentialgleichung|partiellen Differentialgleichungen]] mittels [[Finite-Elemente-Methode]]n bzw. [[Finite-Differenzen-Methode]]n 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|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 [[Parallelrechner|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 ==
* [http://www.robots.ox.ac.uk/~misard/condensation.html Videobeispiele] (engl.)
* [http://www-sigproc.eng.cam.ac.uk/smc/ Sequential Monte Carlo Methods (Particle Filtering), University of Cambridge] (engl.)
* [https://www.youtube.com/watch?v=b6gPXKfJA5g Tech Talk über eine Weiterentwicklung der Partikelfiltermethode] (engl.)

{{Normdaten|TYP=s|GND=7603568-2}}

[[Kategorie:Stochastik]]
[[Kategorie:Robotik]]

Sequenzielle Monte-Carlo-Methode - Versionsgeschichte

imported>MrBenjo: +Normdaten