Histogram Filter
The state space is decomposed into finitely many regions, and the cumulative posterior for each region is represented by a single probability value. In discrete spaces, these are known as discrete Bayes filters, while in continuous spaces, as histogram filters.
Discrete Bayes Filter
The discrete Bayes filter is directly obtained from the Bayes filter, replacing the integral with a sum. The input is a discrete probability distribution \(\{p_{k,t}\}\), and most recent control and measurement \(u_t\) and \(z_t\).
\begin{algorithm} \caption{Discrete Bayes Filter} \label{discrete_bayes_filter} \begin{algorithmic}[1] \Procedure{DiscreteBayesFilter}{$\left\{p_{k,t-1}\}, u_t, z_t$} \ForAll{$k$} \State $\overline{p}_{k,t} = \sum_i p(X_t = x_k | u_t, XK_{t-1} = x_i) p_{i, t-1}$ \State $p_{k,t} = \eta p(z_t | X_t = x_k)\overline{p}_{k, t}$ \EndFor \State \Return $\{p_{k,t}\}$ \EndProcedure \end{algorithmic} \end{algorithm}
Histogram Filter
Histogram filters decompose a continuous state space into finitely many regions:
\begin{equation} \text{range}(X_t) = x_{1,t} \cup x_{2,t } \dots x_{K, t} \end{equation}
where \(X_t\) is the random variable describing the robot at time \(t\). Each \(x_{k,t}\) is a convex region, and form a partitioning of the state space. A simple decomposition is a multi-dimensional grid.
Decomposition Techniques
Static Techniques
Static techniques rely on a fixed decomposition that is chosen in advance. These are easier to implement, but can be computationally wasteful.
Dynamic Techniques
Dynamic techniques adapt the decomposition to the shape of the posterior distribution.
Density trees decompose the state space recursively, adapting the resolution to the posterior probability mass.
Selective updating chooses a subset of grid cells to update for the posterior. These are the grid cells whose posterior probability exceeds some user-set threshold.