Jethro's Braindump

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.

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