Grid-based Methods

Grid-based approaches are particularly well-suited for problems where the state assumes only a limited number of discrete values (these are referred to as Discrete Filters), while they also allow for an approximate estimation in the case of continuous states (histogram filters) transformed into discrete representations through spatial quantization. Each element of the grid (or histogram) is associated with the probability that the state is actually located in that particular cell. The theory of Bayesian filters (hence multimodal distributions and strongly nonlinear systems) is directly utilized, albeit limited to the discrete points where the state can exist.

Let us assume that $m$ points are used to represent the state $\mathbf{x} \in \mathbb{R}^{n}$. If the original state is continuous, this is clearly an approximation, and it is preferable that $m \gg n$. At each iteration $k$, there are therefore $\mathbf{x}_{i,k} \in \mathbb{R}^{n}$ with $i=1,\ldots,m$ possible states associated with a probability distribution $p_{i,k}$ that evolves over time according to the dynamics of the problem.

The previously discussed equations hold, namely the a priori estimate:

$$p^{-}_{i,k} = \sum_{j=1}^{m} p(x_{i,k} \vert x_{j,k-1}) p^{+}_{j,k-1}= \sum_{j=1}^{m} f_{i,j} p^{+}_{j,k-1} \quad \forall i$$ (2.91)

and the a posteriori state update equation for the observation $z_k$:

$$p^{+}_{i,k} = c_k p(z_k \vert x_{i,k}) p^{-}_{i,k} \quad \forall i$$ (2.92)

with $c_k$ always being the normalization factor such that $\sum p^{+}_i = 1$.

The grid-based methods thus allow for the direct application of Bayesian recursive theory.