Kalman Filter
The Kalman filter is a technique for belief computation in linear systems. It implements belief computation over continuous states, and is not suitable for discrete or hybrid state spaces.
It uses the moments representation. At time \(t\), the belief is represented by mean \(\mu_t\) and covariance \(\Sigma_t\). It makes the following assumptions:
- The Markovian Assumption (Markovian Assumption)
- The next state probability \(p(x_t | u_t, x_{t-1})\) is a linear function in its arguments with added Gaussian noise:
\begin{equation} x_t = A_t x_{t-1} + B_t u_t + \epsilon_t \end{equation}
\(x_t\) and \(\u_t\) are column vectors. This assumption defines the state transition probability \(p(x_t | u_t, x_{t-1})\) by substituting the mean \(A_t x_{t-1} + B_t u_t\) and covariance \(R_t\) in the multi-variate normal distribution formula.
- The measurement probability \(p(z_t | x_t)\) is linear in its arguments:
\begin{equation} z_t = C_t x_t + \delta_t \end{equation}
for some multivariate Gaussian noise \(\delta_t\) with 0 mean and co-variance \(Q_t\).
- The initial belief \(\text{bel}(x_0)\) is normally distributed, with initial belief \(\mu_0\) and covariance \(\Sigma_0\)
These 4 assumptions give rise to the Kalman Filter algorithm.
\begin{algorithm} \caption{Kalman Filter} \label{kalman_filter} \begin{algorithmic}[1] \Procedure{KalmanFilter}{$\mu_{t-1}, \Sigma_{t-1}, \mu_t, \z_t$} \State $\overline{\mu}_t = A_t \mu_{t-1} + B_t \mu_t$ \State $\overline{\Sigma}_t = A_t \Sigma_{t-1} A_t^T + R_t$ \State ${K}_t = \overline{\Sigma}_t C_t^T (C_t \overline{\Sigma}_t C_t^T + Q_t)^{-1}$ \State $\mu_t = \overline{\mu}_t + K_t(z_t - C_t\overline{\mu}_t)$ \State $\Sigma_t = (I - K_t C_t) \overline{\Sigma}_t$ \State \Return $\mu_t, \Sigma_t$ \EndProcedure \end{algorithmic} \end{algorithm}
Cons
The linearity assumptions are often unfulfilled in practice. For example, circular trajectories cannot be described with linear state transitions. To overcome this difficulty, people use the Extended Kalman Filter.