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


Icon by Laymik from The Noun Project. Website built with ♥ with Org-mode, Hugo, and Netlify.