Particle filter

(For example, in mobile robotics ), the response is known only on a statistical average Sequential Monte Carlo methods (SMC methods) belong to the class of stochastic method for estimating state of a dynamic process ( substantial interference) and the incomplete can be observed ( division into inner, hidden and external visible variable). An example of application is accurate and continuously updated determination of the location and speed of an object due to an inaccurate and erroneous 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 ( eg, the location of objects ) for an observer is not directly, but only accessible by measurements. In this case one speaks of hidden states ( engl. hidden state). A measurement of the state is in principle always subject to error ( noisy), that is, in general, is the measurement of the true status correctly again. Due to the measurement, it is possible to estimate the unknown state.

For the case of a linear process model and under the assumption of normally distributed disturbances and measurement error, the continuous Kalman filter of Kalman and Bucy has been introduced in 1961 to recursively determine the most likely state of the previous estimates and the measurement values ​​obtained. In the event that the process model is significantly non-linear or the interference can not be assumed to be normally distributed, can not be assumed a normal distribution of the state to be estimated. It must be taken inter alia, be considered that the probability density has a plurality of maxima, i.e. the observations made are compatible with a plurality of internal states. A lattice- based approach to solve this extended problem is to transform the system dynamics in 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 quite computationally expensive in general.

Basic idea of ​​the SMC methods

The aim of SMC methods is to estimate the just current but unknown probability density on the state space in order to derive statements about the likely system state of the dynamic system. For this, a cloud or a swarm of so-called particles is generated, the pairs of a weight and a point in the state space are. This is the swarm as a whole, the probability density in an initial state representing ( bootstrap ). Each individual particle is then assigned one or more solution curves by means of the stochastic model of the system dynamics. Depending on how the derived graph of this solution predictions of the measured values ​​correspond with the actual weight of the particles can be adjusted, resulting in a sequential manner provides an improved estimate of the evolution of the probability density in the state space. Due to this, even the initial composition of the swarm to be adjusted in order to obtain more accurate results (re- bootstrap ). As we receive random disturbances in the temporal evolution of the system, it is a Monte Carlo simulation. The transition from the weighted particle cloud of probability density can be effected using methods of non-parametric density estimation.

Advantages of the SMC methods

The advantages of SMC filters are:

• Approximate the total unknown a posteriori probability density and can be applied for non- Gaussian distributions.
• The estimated distributions can be multimodal, ie the distribution can have several maxima.
• The system dynamics and the dynamic can also be non-linear.
• The simulation of the individual particles is very easy to parallelize.