Home › Tutorials › Tutorials: Programming › Statistics and Bayes filtering

Particle Filter Algorithms

Submitted by jlblanco on Fri, 08/06/2010 - 23:52

This page describes the theory behinds the particle filter algorithms implemented in the C++ libraries of MRPT. See also the different resampling schemes.

For the list of corresponding C++ classes see Particle Filters.





1. Sequential Importance Resampling - SIR (pfStandardProposal)

Standard proposal distribution + weights according to likelihood function.



2. Auxiliary Particle Filter - APF (pfAuxiliaryPFStandard)

This method was introduced by Pitt and Shephard in 1999 [1]

Let's assume the filtered posterior is described by the following $ M $ weighted samples:

$ p(x_t|z_{1:t}) \approx \sum_{i=1}^M \omega^{(i)}_t \delta \left( x_t - x^{(i)}_t \right) $

Then, each step in the algorithm consists of first drawing a sample of the particle index $ k $ which will be propragated from $ t-1 $ into the new step $ t $. These indexes are auxiliary variables only used as an intermediary step, hence the name of the algorithm. The indexes are drawn according to the likelihood of some reference point $ \mu^{(i)}_t $ which in some way is related to the transition model $ x_t|x_{t-1} $ (for example, the mean, a sample, etc.):

$ k^{(i)} \sim P(i=k|z_t) \propto \omega^{(i)}_t p( z_t | \mu^{(i)}_t ) $

This is repeated for $ i=1,2,...,M $, and using these indexes we can now draw the conditional samples:

$ x_t^{(i)} \sim p( x_t | x^{k^{(i)}}_{t-1}) $

Finally, the weights are updated to account for the mismatch between the likelihood at the actual sample and the predicted point $ \mu_t^{k^{(i)}} $:

$ \omega_t^{(i)} \propto \frac{p( z_t | x^{(i)}_t) } { p( z_t | \mu^{k^{(i)}}_t) } $



3. Optimal Sampling (pfOptimalProposal)

Use the exact optimal proposal distribution (where available!, usually this will perform approximations).

In the case of the RBPF-SLAM implementation, this method follows [2]



4. Approximate Optimal Sampling (pfAuxiliaryPFOptimal)

Use the optimal proposal and a auxiliary particle filter (see paper [3] ).


References

  • [1] Pitt, M.K. and Shephard, N., [http://www.nuff.ox.ac.uk/economics/papers/1997/w13/sir.pdf Filtering Via Simulation: Auxiliary Particle Filters], Journal of the American Statistical Association, vol. 94, pp. 590-591, 1999.
  • [2] Grisetti, G. and Stachniss, C. and Burgard, W., "Improving grid-based slam with rao-blackwellized particle filters by adaptive proposals and selective resampling", ICRA 2005.
  • [3] J.-L. Blanco, J. González, and J.-A. Fernández-Madrigal,An Optimal Filtering Algorithm for Non-Parametric Observation Models in Robot Localization, IEEE International Conference on Robotics and Automation (ICRA), Pasadena (California, USA), May 19-23, 2008, pp. 461–466.


{{BACK_MAIN_TUTORIALS}}

Syndicate content
The Mobile Robot Programming Toolkit (MRPT) initiative (C) 2012