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