# Particle Filter

## Other names

• Sequential Monte Carlo filter / method (SMC)
• Sequential Importance Resampling (SIR)
• Bootstrap filter
• Condensation

## What is it good for? Key idea?

• particle ﬁlters estimate the posterior probability density over the state space of a dynamic system
• key idea of this technique is to represent probability densities by sets of samples
• “The efﬁciency of particle ﬁlters lies in the way they place computational resources. By sampling in proportion to likelihood, particle ﬁlters focus the computational resources on regions with high likelihood, where good approximations are most important.” (Dieter Fox)
• resampling is done by a Monte-Carlo approach –> particle filter = probabilistic algorithm: we draw randomly samples from the current pdf according to the particle weights
• particles that can explain the measurement gain weight
• particles that cannot explain the measurement loose weight
• “filtering” refers to determining the distribution of a latent variable at a specific time, given all observations up to that time

## Relation to Bayes Filtering?

• particle filters can be seen as a sample-based implementation of Bayes filtering
• key idea of Bayes ﬁltering is to recursively estimate the posterior probability density over the state space conditioned on the data collected so far
• Bayes ﬁlters are an abstract concept in that they only provide a probabilistic framework for recursive state estimation. To implement Bayes ﬁlters, one has to specify the perceptual model p(z_t |x_t), the dynamics p(x_t | x_t−1 , u_t−1), and the representation of the belief Bel(x_t)
• where x_t is the state at time t, u_t is a control measurement, and z_t is an observation

## Visualization

Here is a slide with an excellent visualization from a intro talk to particle filters by Michael Pfeiffer:

## Pseudocode

• particle ﬁlters require two models for the estimation process:
• a motion model
• a perception model
• 3 steps:
• predict new locations / states for each particle
• update weights, i.e. compute importance weights
• resample particles according to the importance weights

• here is another slide with the pseudo-code:

## Why resampling?

Resampling is used to avoid the problem of degeneracy of the algorithm, that is, avoiding the situation that all but one of the importance weights are close to zero

## Demo

A particle set with 100 particles tries to track 3 objects: