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 filters 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 efficiency of particle filters lies in the way they place computational resources. By sampling in proportion to likelihood, particle filters 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 filtering is to recursively estimate the posterior probability density over the state space conditioned on the data collected so far
  • Bayes filters are an abstract concept in that they only provide a probabilistic framework for recursive state estimation. To implement Bayes filters, 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 filters 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:

 
public/particle_filter.txt · Last modified: 2013/04/10 18:33 (external edit) · []
Recent changes RSS feed Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki