# Histogram Filter Histogram filters decompose the state space into finitely many regions and represent the cumulative posterior for each region by a single probability value. When applied to finite spaces, they are called **discrete Bayes filters**; when applied to continuous spaces, they are known as **histogram filters**. ## Discrete Bayes Filter We use discrete Bayes filter when the problem has finite state spaces, where random variable $$X\_t$$ can take on finitely many values, like a door is open or closed. Let the variables $$x\_i$$ and $$x\_k$$ denote individual states, of which there may only be finitely many. The belief at time $$t$$ is an assignment of a probability to each state $$x\_k$$, denoted $$p\_{k, t}$$. $$ \tag{1} \text{for all $k$ do:}\\;\\ \overline{p}*{k, t} = \sum\_i p(X\_t = x\_k \mid u\_t, X*{t-1} = x\_i) p\_{i, t-1} \\ p\_{k, t} = \eta; p(z\_t \mid X\_t = x\_k)\overline{p}*{k, t} \\;\\ \text{endfor and return $p*{k,t}$} $$ The input to the algorithm is a discrete probability distribution $$p\_{k, t}$$, along with the most recent control $$u\_t$$ and measurement $$z\_t$$. The first step is to calculate the prediction, the belief for the new state based on the control alone. The second step is to incorporate the measurement and update the new belief. This is exactly identical to the Bayes filter except that the integral has been replaced by a discrete sum. ## Histogram Filter We want to use discrete Bayes filters as an approximate inference tool for continuous state spaces, this brings us to the histogram filter. Histogram filter decomposes a continuous state space into finitely many bins or regions. $$ \text{dom}(X\_t) = x\_{1, t} \cup x\_{2, t} \cup ... \cup x\_{K, t} $$ Here $$X\_t$$ is the familiar random variable describing the state of the robot at time $$t$$. The function $$\text{dom}(X\_t)$$ denotes the state space, which is the universe of possible values that $$X\_t$$ might assume. A straightforward decomposition of a continuous state space is a multi-dimensional grid, where each $$x\_{k,t}$$ is a grid cell. If the state is truly discrete, the conditional probabilities are well-defined, and the algorithm can be implemented as equation (1). In continuous state space, one is usually given the densities $$p(x\_t \mid u\_t, x\_{t-1})$$ and $$p(z\_t \mid x\_t)$$ which are defined for individual states and not for the regions in the state space. We need to perform an approximation for the region by taking the mean state in $$x\_{k, t}$$. $$ \hat{x}*{k, t} = \frac{1}{\lvert x*{k,t}\rvert}\int\_{x\_{k,t}} x\_t ;dt $$ Now we have it. $$ \tag{1} \text{for all $k$ do:}\\;\\ \overline{p}*{k, t} = \sum\_i \eta ; \lvert x*{k,t}\rvert ; p(\hat{x}*{k, t} \mid u\_t, \hat{x}*{i, t-1}) p\_{i, t-1} \\ p\_{k, t} = \eta; p(z\_t \mid \hat{x}*{i, t-1})\overline{p}*{k, t} \\;\\ \text{endfor and return $p\_{k,t}$} $$ ## Decomposition Techniques Decomposition techniques of continuous state spaces come in two basic flavors, *static* and *dynamic*. State technique rely on a fixed decomposition that is chosen in advance. Dynamic technique adapt the decomposition to the specific shape of the posterior distribution. State techniques are usually easier to implement, but they can be wasteful with regards to computational resource. --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://calvinfeng.gitbook.io/probabilistic-robotics/basics/nonparametric-filters/01-histogram-filter.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.