Bayes Filter
- tags
- Gaussian Filter
Notation
- \(\eta\)
- normalizing constant, to make probability distribution sum to 1.
- \(\text{bel}(t) = p(x_t | z_{1:t}, u_{1:t})\)
- posterior probabilities over state variables conditioned on available data
- \(\overline{\text{bel}}(t) = p(x_t | z_{1:t-1}, u_{1:t})\)
- belief taken before incorporating the measurement \(z_t\)
\(\overline{\text{bel}}(t)\) often called the prediction in Bayes filtering. Computing \(\text{bel}(t)\) from \(\overline{\text{bel}}(t)\) is called correction or the measurement update.
Algorithm
\begin{algorithm} \caption{Bayes Filtering} \label{bayes_filter} \begin{algorithmic}[1] \Procedure{BayesFilter}{$\text{bel}(x_{t-1}), u_t, z_t$} \ForAll{$x_t$} \State $\overline{\text{bel}}(t) = \int p(x_t | u_t, x_{t-1}) \text{bel}(x_{t-1}) dx$ \State $\text{bel}(t) = \eta p(z_t | x_t)\overline{\text{bel}}(t) (x_t)$ \EndFor \State \Return $bel(x_t)$ \EndProcedure \end{algorithmic} \end{algorithm}
Details
Mathematical derivation makes the Markovian Assumption.
Exact techniques for belief calculation are reserved for specialized cases. In most scenarios, these beliefs have to be approximated, and these approximations have important ramifications on the complexity of the algorithm.
Approximations requires trading off:
- Computational Efficiency
- Linear Gaussian approximations can calculate beliefs in time polynomial to the state space. Other approximations may be exponential. Particle filter techniques have the any-time characteristic, allowing them to trade off accuracy with computational efficiency.
- Accuracy
- Linear Gaussian approximations are limited to unimodal distributions, whereas histogram approximations are multi-modal, but have limited accuracy. Particle representations can approximate a wide array of distributions, but large number of particles may be required for high accuracy.
- Ease of implementation
- Difficulty in implementation typically arises from the form of the transition and measurement probabilities (see Robotics Probabilistic Generative Laws). Particle representations lend themselves to simple implementations for complex non-linear systems.