control//state estimation//particle filter

A particle filter estimates a state whose belief has no useful bell shape, by carrying thousands of samples of the state instead of a mean and a covariance. It is the tool for strongly nonlinear systems and non-Gaussian noise: a robot that could be in any of three identical corridors, a tracker that must keep two hypotheses alive until the data choose, a sensor whose likelihood has several peaks. A Kalman filter would average those possibilities into one point that is often in none of them.

A particle filter estimates a state whose belief has no useful bell shape, by carrying thousands of samples of the state instead of a mean and a covariance. It is the tool for strongly nonlinear systems and non-Gaussian noise: a robot that could be in any of three identical corridors, a tracker that must keep two hypotheses alive until the data choose, a sensor whose likelihood has several peaks. A Kalman filter would average those possibilities into one point that is often in none of them.

Each sample, a particle, is one guess of the state with a weight. Predicting moves every particle through the model with its own random draw of the process noise, so the cloud spreads as uncertainty grows. A reading then reweights them: each particle's weight is multiplied by how likely that reading would be if the particle were the truth (Bayes' rule). Resampling finally draws a new cloud from the weighted one, cloning the heavy particles and dropping the light ones, so the effort goes where the truth probably is. The estimate is the weighted mean of the cloud, or its densest region when the cloud has several.

It needs no linear model and no Gaussian noise, only a way to simulate the model and to evaluate the sensor's likelihood. Any shape of belief, including several separate peaks, is represented.

Its cost grows badly with the size of the state. The number of particles needed to cover the space grows roughly exponentially with the number of dimensions, so it is practical for a few states (a robot's position and heading, a target's position and velocity) and not for hundreds.

Without resampling it degenerates: after a few steps one particle carries almost all the weight and the rest is wasted computation. Resampling fixes that, at the price of losing diversity, which is why a little extra noise is often added to the cloned particles.

When a belief is still close to a few bells, a bank of Kalman filters is far cheaper (IMM); when it is a single bell bent by a nonlinear model, one of the nonlinear Kalman filters is (extended Kalman filter, unscented Kalman filter).