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.

Contents

1. Sequential Importance Resampling – SIR (pfStandardProposal)
2. Auxiliary Particle Filter – APF (pfAuxiliaryPFStandard)
3. Optimal Sampling (pfOptimalProposal)
4. Approximate Optimal Sampling (pfAuxiliaryPFOptimal)
References

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.