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

## References

{{BACK_MAIN_TUTORIALS}}

Tags: