# 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 

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 

## 4. Approximate Optimal Sampling (pfAuxiliaryPFOptimal)

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