Particle Filter

The linear and quasi-linear approaches proposed by Kalman can be applied to problems where the state is Gaussian or nearly Gaussian with a unimodal distribution: the state estimate at time $k$ is a direct function of the unique state estimate at time $k-1$ and the covariance of that estimate.

When it is required to derive the non-Gaussian probability distribution of the system state $p(x_k; u_{k-1}; z_{k})$ at time $k$, as a function of the inputs and observations, Kalman-type approaches are no longer satisfactory.

Grid-based approaches are suitable for those problems, which are quite uncommon, where the state is discretizable and finite. Histogram-based/occupancy grid approaches, on the other hand, are applicable to a broader class of problems; however, due to the uniform sampling of the state, they scale poorly as the dimensions increase.

Consider again the result expressed by equation (2.4): to extract a generic statistic $h(\cdot)$ (for example, the mean or variance) from a probability distribution $p(x)$, one utilizes the expression

$$\bar{h} \stackrel{def}{=} \int_X h(x) p(x) dx$$ (2.123)

. In cases where such an estimate cannot be obtained analytically, it is still possible to derive it indirectly through the analysis of $x_i$ independent samples, with $1 \leq i \leq N$, randomly drawn from a distribution that is exactly $p$.

Given the samples $x_i$ generated in this manner, the Monte Carlo estimate of $h(\cdot)$ is given by

$$\bar{h} \approx \frac{1}{N} \sum_{i=1}^{N} h(x_i)$$ (2.124)

Monte Carlo does not solve all problems nor does it suggest how to efficiently obtain random samples. The issue becomes sensitive in multidimensional cases where the areas where the probability takes on significant values are extremely small. The objective of Importance Sampling (IS) is to sample the distribution $p(x)$ in "important" regions in order to maximize computational efficiency.

The idea of Importance Sampling is to take a simpler distribution $q(x)$ (Importance density) instead of the true $p(x)$, which is usually difficult to sample (or reproduce), by making the substitution

$$\int_X h(x) p(x) dx = \int_X h(x) \frac{p(x)}{q(x)} q(x) dx = \int_X h(x) w(x) q(x) dx$$

where we have introduced the weight system $w(x)$. Through the use of appropriate weights, it is thus possible to modify equation (2.124) to

$$\bar{h} \approx \frac{1}{N} \sum_{i=1}^{N} w_i h(x_i)$$ (2.125)

where $w_i \propto W_i = p(x_i)/q(x_i)$ represents a corrective weight, the importance factor (important weights), to convert the support distribution $q$ to the true distribution $p$. The weights $W_i$ must be normalized

$$w_i = \frac{W_i}{\sum W_i}$$ (2.126)

to be usable.

The distribution $q(x)$ is more similar to $p(x)$, the more accurate the estimate will be. On the other hand, the distribution $q(x)$ should be very simple to sample, for example by choosing a uniform or Gaussian distribution.

Given the knowledge of Bayesian filters and Monte Carlo techniques, it is possible to address the theory of particle filters. The state at time $k$ is represented by a set of samples (particles), and each sample is a hypothesis of the state to be evaluated. One can refer to a series of particles obtained a priori of the observation by applying equation (2.125) to the state evolution function.

If Bayesian theory is applied directly to the samples of the estimated distribution, it is possible to modify the weights $w_i$ associated with the samples while simultaneously using the system and perception model (Sequential Importance Sampling):

$$w_{k,i} \propto w_{k-1,i} \frac{ p (z_k \vert x_{k,i} ) p (x_{k,i} \vert x_{k-1,i} ) } { q (x_{k,i} \vert x_{k-1,i}, z_k ) }$$ (2.127)

In this way, the initial samples remain the same, but only the weights $w_i$ associated with them change.

When possible, it is advantageous to use the Important density as the a priori distribution

$$q (x_{k,i} \vert x_{k-1,i}, z_k ) = p (x_{k,i} \vert x_{k-1,i} )$$ (2.128)

so that, when introduced in (2.127), it yields

$$w_{k,i} \propto w_{k-1,i} p (z_k \vert x_{k,i} )$$ (2.129)

The issue with the SIS approach is that after a few iterations, only a few particles will have a non-negligible weight factor (weight degeneracy).

BootStrap/Sequential Importance Resampling

A simpler solution is the Sequential Importance Resampling, where the weights do not depend on previous iterations; instead, it is the samples that change, following a resampling phase.

The resampling phase involves generating a new set of particles $x'$ by resampling $N_s$ times a discretely approximated version of $p(\mathbf{x}_k \vert \mathbf{z}_k)$ given by

$$p( \mathbf{x}_k \vert \mathbf{z}_k ) \approx \sum_{i=1}^{N_s} w_{k,i} \delta (\mathbf{x}_k - \mathbf{x}_{k,i} )$$ (2.130)

having defined

$$w_{k,i} \propto p(\mathbf{z}_k \vert \mathbf{x}_k)$$ (2.131)

SIR filters do not avoid the degenerate case (in fact, they effectively eliminate unlikely particles), however, they lead to significant computational savings and focus the search for the solution around the most probable states.

There are various algorithms for performing resampling. A non-exhaustive list of such algorithms includes: Simple Random Resampling, Roulette Wheel / Fitness Proportionate Selection, Stochastic Universal Sampling, Multinomial Resampling, Residual Resampling, Stratified Resampling, and Systematic Resampling.