Particle Filter Algorithms

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] ).


  • [1] Pitt, M.K. and Shephard, N., [ 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.