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