The previous filters all used Gaussian distributions to represent the pose belief. Particle filters use multiple poses spread across the world to represent the belief. The probability of the actual pose being contained in an area is equal to the percentage of particles in that area. Because the samples in the particle filter can be distributed in any way, the filter is able to represent nongaussian distributions. This flexibility makes the particle filter well suited to represent the belief of a robot pose when it could be in several distinct places on a map (particle filters support multi-modal distributions).
During the action update, each particle in the prior is passed through the action model to get a new particle posterior. During the sensor update, each particle is given an importance weight by asking the sensor model to calculate the probability of observing the sensor value from the particle's location. The belief is then sampled using the importance weights.
The accuracy and performance of the particle filter is very dependent on the number of particles used to represent the distribution. Accuracy depends on a high density of particles in the area around the true state of the system. However, too many particles makes the filter more computationally expensive since the the action and sensor models must be evaluated for each and every particle.
The action update generates new particles for the posterior from the particles in the prior. Each particle in the prior is passed through the action model, along with a specific action, to generate a single particle in the posterior distribution. The action update is responsible for generating new particles to prevent particle depletion. If the action model were perfectly deterministic, the duplicated particles in the prior would remain duplicated particles in the posterior. The sensor update would then duplicate a few more particles and over time, all of the particles would be working to represent a single point. In order for the particle filter to work correctly, the action model must introduce error into the posterior generation.
There are two ways new particles can be introduced by the action model. First, the action model may have process noise. ActionModel takes a specific action and a specific state and creates a RandomDistribution that represents the possible resulting states. The Kalman filter and its variants, all generate Gaussian distributions. The covariance of these Gaussians represent the process noise in those filters. While the Kalman filters use the covariance matrix in closed form equations to calculate the posterior, the particle filter simply samples from the distribution. This means the particle filter is not limited to using action models that produce Gaussians. The SingularDistribution provides a simple method to create an action model with zero process noise.
New particles can also be introduced into the particle filter using action distributions. For each new particle in the posterior, a sample is drawn from the action distribution. This action sample is then passed to the action model, along with a prior particle, to generate a new posterior particle. It is easier to capture nonlinearities in the action model using action distributions than it is with process noise.
Because the error on a differential drive action only has two free variables, the resulting poses will reside on 2-D manifold in the 3-D space of [x, y, θ]. This prevents the belief distribution from representing the actual robot pose (which, due to actual motion noise, may not reside on that manifold). Adding a small amount of process noise will correct this limitation.
ParticleFilter can operate on any class that implements ActionModel and can use DifferentialDriveActionModel directly.
The sensor update selects particles from the prior, but does not create any new particles. For each particle in the prior, the sensor model is used to calculate the probability of sensing the observed value from that particle. This probability is referred to as the importance weight. Particles are randomly sampled from the prior according to their proportional importance weights. The sensor update does not create any new particles. All particles in the posterior existed in the prior.
Some particles in the prior may be represented multiple times in the posterior. Other particles in the prior may not be represented in the posterior at all. As the number of duplicated particles grows, the representation power and accuracy of the belief distribution drops. This is a process known as particle depletion. The particle filter relied on the noise introduced by the action update to avoid depletion.
The ParticleFilter class supports to methods for selecting samples during the sensor update. Monte Carlo sampling selects each particle by generating a random number between zero and one. The importance weights are normalized, and the particle that corresponds to the random number is added to the posterior. Low variance sampling uses a deterministic method to guarantee that no particle is over- or under-represented by chance. By default, ParticleFilter performs low variance sampling. A user can change this by creating a class that inherits from ParticleFilter and overriding the Resample function.
The following Silverlight app shows the particle filter in action.