Sequential Monte Carlo method
Sequential Monte Carlo methods (SMC methods) belong to the class of stochastic methods for state estimation in a dynamic process (e.g. in mobile robotics ), the dynamics of which are only known as a statistical mean (significant disturbance variables) and which are only incomplete can be observed (division into inner, hidden and outer, visible variables). An application example is the precise and continuously updated determination of the location and the speed of an object based on an imprecise and incorrect measurement of the location (see tracking ). SMC filters are also known as particle filters , sampling importance resampling (SIR), sequential importance sampling (SIS), bootstrap filters , condensation trackers , interacting particle approximations or survival of the fittest .
Problem
Often one is faced with the problem that the state of a dynamic system (e.g. the location of objects) is not directly accessible to an observer, but only through measurements. In this case one speaks of hidden states. A measurement of the state is in principle always error-prone ( noisy ), i.e. H. in general, the measurement does not correctly reflect the true state. However, based on the measurement, it is possible to estimate the unknown state.
For the case of a linear process model and assuming normally distributed disturbance variables and measurement errors, the continuous Kalman filter was introduced by Kalman and Bucy in 1961 in order to determine the most likely state recursively from the previous estimates and the measured values obtained. In the event that the process model is essentially non-linear or the interfering influences cannot be assumed to be normally distributed, a normal distribution of the state to be estimated cannot be assumed. It must continue u. a. it can be considered that the probability density has several maxima, i. H. the observations made are compatible with several internal states. A grid-based approach to solving this extended problem consists in the transformation of the system dynamics into a dynamics of the probability density on the state space (see stochastic differential equation ). The solution of the resulting partial differential equations using finite element methods or finite difference methods is generally quite computationally intensive.
Basic idea of the SMC methods
The aim of the SMC methods is to estimate the current but unknown probability density in the state space in order to derive statements about the most probable system state of the dynamic system. For this purpose, a cloud or a swarm of so-called particles is generated, which are pairs of a weight and a point in the state space. The swarm as a whole should represent the probability density in an initial state (bootstrap). One or more solution curves are then assigned to each individual particle using the stochastic model of the system dynamics. Depending on how the predictions of the measured values derived from this solution curve agree with the actual values, the weight of the particles can be adapted, which results in an improved estimation of the evolution of the probability density in the state space in a sequential manner. Because of this, even the initial composition of the swarm can be adjusted in order to obtain more precise results (re-bootstrap). Since random disturbance variables are included in the temporal development of the system, it is a Monte Carlo simulation. The transition from the weighted particle cloud to the probability density can be made using methods of nonparametric density estimation.
Advantages of the SMC methods
The advantages of SMC filters are:
- They estimate the total unknown a posteriori probability density and can be used for non-Gaussian distributions.
- The estimated distributions can be multimodal; H. the distribution can have several maxima.
- The system dynamics and the measurement dynamics can also be non-linear.
- The simulation of the individual particles is very easy to parallelize .
literature
- 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 .