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

- 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

- 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

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

- 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

- this pseudo-code is from a paper by Marchetti et al.:

- here is another slide with the pseudo-code:

- and here is the pseudocode proposed here by Roncalli and Weisang with my annotation:

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

public/particle_filter.txt · Last modified: 2013/04/10 18:33 (external edit) · []