논문

하루에도 수만개의 글자를 읽고 있습니다. 하루에도 수백장의 종이를 들춰 읽습니다.
이것은 그 읽기에 대한 일기입니다.

An Introduction to the Kalman Filter

http://www.cs.unc.edu/~tracker/ref/s2001/kalman/

1. Introduction

SIGGRAPH 2001에서 있었던 튜토리얼 코스인 듯 합니다. 분량이 많아 일부 내용만 싣고자 합니다.

2. Probability and Random Variables

확률 및 랜덤 변수, mean, variance, 가우시안 분포에 대한 이야기를 하고 있습니다.

3. Stochastic Estimation

알고리즘을 통하여 우리가 모르는 어떤 ‘상태(state)’를 구하는 문제를 풀고 있다고 생각해 봤을 때, 많은 방법들은 관측 값에 포함된 노이즈를 고려하지 않습니다. 하지만 관측값에 노이즈가 포함되어있는 것은 매우 당연한 일이고, 때문에 그것은 stochastic 방법을 이용하여 풀어야 하는 이유가 됩니다.

3.1 State-Space Models

State-space models에서의 이전의 n개 상태를 고려하였을 때의 현재 상태를 나타내는 식은 다음과 같습니다.

$$y_{i+1} = a_{0,i} y_i + ... + a_{n-1, i}y_{i-n+1} + u_i, \ i \geq 0$$

여기서 $ u_i $는 평균 0을 갖는 random variable이고 그 autocorrelation이 $ E(u_i, u_j) = R_u = Q_i \delta_{ij} $인 random noise process입니다.

계산이 시작되기 전 상태 $i=0$에서의 초기값 $ \{ y_0, y_{-1}, ... y_{-n+1} \} $ 은 평균 0을 갖는 랜덤 변수로 이 상태들의 covariance matrix 는

$$P_0 = E(y_{-j}, y_{-k}), \ \ j,k \in \{0, n-1 \}$$

로 정의됩니다.

이 때, $ E(u_i, y_i) = 0 \ \text{for } i \geq j \geq0 $ 입니다.

이전 상태로부터 현재 상태를 계산하는 식은 아래와 같이 다시 쓸 수 있습니다.

$$\bar{x}_{i+1} =
\begin{bmatrix}
y_{i+1} \\
y_i \\
y_{i-1} \\
\vdots \\
y_{i-n+2}
\end{bmatrix} =
\begin{bmatrix}
a_0 & a_1 & \cdots & a_{n-2} & a_{n-1} \\
1 & 0 & \cdots & 0 & 0 \\
0 & 1 & \cdots & 0 & 0 \\
\vdots & \vdots & \cdots & \vdots & \vdots \\
0 & 0 & \cdots & 1 & 0
\end{bmatrix}
\begin{bmatrix}
y_i \\ y_{i-1} \\ y_{i-2} \\ \vdots \\ y_{i-n+1}
\end{bmatrix}
+
\begin{bmatrix}
1 \\ 0 \\ 0 \\ \vdots \\ 0
\end{bmatrix}
u_i$$

$$\bar{x}_{i+1} = A \bar{x}_i + G u_i \\ \bar{y}_i = [1 \ 0 \ \cdots \ 0] \bar{x} = H_i \bar{x}_i$$

결국 위의 식을 요약해보면, 이전의 n개 상태와noise process $ u_i $의 linear combination을 통하여 새로운 상태 $ \bar{x}_{i+1} $ 가 결정된다고 이야기 할 수 있습니다. 그리고 그렇게 계산된 다음 상태는 H를 통해 값 $ \bar{y}_{i+1} $로 관측됩니다.

그리고 위의 두 식은 각각 process model과 measurement model로 불리웁니다.

3.2 The Observer Design Problem

위의 모델과 관련하여 observer design problem이라는 것이 있습니다. 이 문제는 기본적으로 우리가 실제 상태를 직접적으로 알 수가 없고 시스템의 출력, 혹은 관측값만을 알 수가 있다는 것에 기인합니다. 마치 블랙박스와 같이 박스 내부의 실제 신호는 직접 알 수가 없고 외부에서만 관측할 수 있는 상황입니다.

따라서 위의 process model과 measurement model을 조금 수정합니다.

$$x_k = A x_{k-1} + B u_k + w_{k-1}$$

$$z_k = H x_k + v_k$$

여기서 $ w_k, v_k $는 각각 process, measurement에서의 노이즈를 나타냅니다.

Measurement noise는 센서 등의 이유로 인하여 관측시의 노이즈를 고려한 것입니다. Process noise는 우리가 정한 모델이 정확히 맞다고 볼 수 없기 때문에 그것을 고려한 것입니다.

4. The Kalman Filter

4.1 The Discrete Kalman Filter

칼만 필터는 discrete-time controlled process 의 상태 $ x \in R^n $ 를 추정하는 문제를 풀기 위해 사용됩니다. 이 문제의 linear stochastic difference euqation은 다음과 같습니다.

$$x_k = Ax_{k-1} + B u_k + w_{k-1}$$

그리고 measurement $ z \in R^n $ 는,

$$z_k = H x_k + v_k$$

로 계산됩니다.

앞에서와 마찬가지로 $ w_k, v_k $는 process, measurement 노이즈입니다. 이는 서로 독립인 white noise로 normal probability distribition을 따릅니다.

$$p(w) \sim N(0, Q)$$

$$v(w) \sim N(0, R)$$

Process noise covariance Q와 measurement noise covariance R은 매 타임 스텝마다 바뀔 수 있는 값들이지만 여기서는 변하지 않는 상수라고 가정합니다.

이전 k-1에서의 상태를 다음 k에서의 상태로 변화시키는 것과 관련이 있는 행렬 A와, x에 추가적으로 덧붙여지는 행렬 B, 그리고 관측에 대한 모델인 H 모두 매 시각마다 변화할 수 있는 값이긴 하나 여기서는 고정된 값으로 가정합니다.

여기서 한가지는 생각해볼 수 있습니다. 만약 우리가 아무런 조건이 주어지지 않았을 때의 a priori 추정 값을 $ \hat{x}^-_k \in R^n $이라고 하여봅시다. 그리고 관측값 $ z_k $이 주어지고 나서의 a posteriori 추정 값을 $ \hat{x}_k \ in R^n $이라고 합시다. 그렇다면 이제 둘과 실제 상태 사이의 오차를 정의할 수 있습니다.

$$e^-_k = x_k - \hat{x}^-_k$$

$$e_k = x_k - \hat{x}_k$$

나아가 a priori 추정과 a posteriori 의 오차 covariance는 다음과 같이 계산할 수 있습니다.

$$P^-_k = E[ e^-_k e^{-\ T}_k]$$

$$P_k = E[ e_k e_k^T ]$$

칼만 필터는, 관측 값 $z_k$와 예측 했던 관측 값 $H\hat{x}^-_k $의 차이에 가중치를 준 다음 a priori 추정 값 $ \hat{x}^-_k $과의 합을 통하여 최적의 a posteriori 상태를 계산하는 것입니다. 이를 식으로 나타내면 아래와 같습니다.

$$\hat{x}_k = \hat{x}^-_k + K(z_k - H\hat{x}^-_k)$$

여기서 $ z_k - H\hat{x}^-_k $ 를 measurement innovation 혹은 residual이라고 부릅니다.

행렬 K는 kalman gain 혹은 blending factor라고 부르는데, a posteriori error covariance 가 최소가 되도록 정해집니다. 이를 정하는 방법은 논문에 나와있는대로 위의 언급한 식을 치환을 통하여 새로운 식으로 만든 뒤 이를 미분한 값을 0으로 놓고 풀게 됩니다. 최종적으로 K는 다음의 식으로 계산됩니다.

$$K_k = P^-_kH^T (HP^-_kH^T + R)^{-1}$$

이렇게 계산된 K는, 오차 R이 작아질 수록 큰 값을 가지게 되고, P가 작아질 수록 0에 가까운 값을 가지게 되어 a priori와 a posteriori 중 어느 것을 더 신뢰하여 가중치를 많이 줄 것인지 결정하게 되는 역할을 하게 됩니다.

4.1.4 The Discrete Kalman Filter Algorithm

이제 칼만 필터가 어떤 식으로 돌아가는지 살펴보도록 합시다. 칼만 필터는 피드백을 이용하여 동작합니다. 필터가 (1) 상태를 추정하고, 그 후 (2) 실제 관측 값을 얻으면 이것으로부터 피드백을 받아 추정 값을 업데이트합니다. 이렇게 반복되는 두 과정을 각각 time update, measurement update이라고 합니다. 또한, predict, correct라고 부르기도 합니다.

Time update 단계에서는 이전 상태(k-1)에서 다음 상태(k)로의 전환을 추정합니다. 이것은 미리 정해진 모델로부터 생성된 전환 식을 이용합니다. 행렬 A, B에 해당하는 부분입니다. 추가적으로 process noise에 대한 행렬 Q가 사용됩니다. 아직 다른 조건이나 정보가 없이 추정하였기 때문에 a priori 입니다. 식을 정리해보면 다음과 같습니다.

  1. Project state ahead
    $ \hat{x}^-_k = A \hat{x}_{k-1} + B u_k $
  2. Project the error covariance ahead
    $ P^-_k = A P_{k-1} A^T + Q $

Measurement update 단계에서는 먼저 kalman gain K를 계산합니다. 그리고 관측 값 $ z_k $를 이용하여 a posteriori 상태를 계산합니다.

  1. Compute the Kalman gain
    $ K_k = P^-_kH^T (HP^-_kH^T + R)^{-1} $
  2. Update estimate with measurement $ z_k $
    $ \hat{x}_k = \hat{x}^-_k + K_k (z_k - H \hat{x}^-_k) $
  3. Update the error covariance
    $ P_k = (I - K_k H) P^-_k $

위의 두 단계를 매 시각 k마다 반복하게 됩니다. 직전에 추정한 a posteriori는 다음 시각에서 a priori를 추정하는데 사용되고, 이 a priori는 측정된 관측 값과 함께 새로운 a posteriori를 추정하는데 다시 사용됩니다.

4.2 The Extended Kalman Filter (EKF)

모든 문제들이 선형 방정식으로 나타낼 수 있으면 좋겠지만 실제로는 그렇지 않은 경우가 많습니다. 이런 문제를 해결하기 위해 확장된 칼만 필터가 있습니다. 이것은 행렬 A, B 대신 비선형 함수 $ x_k = f(x_{k-1}, u_k, w_{k-1}) $와 행렬 H 대신 관측 함수 $ z_k = h(x_k, v_k) $를 사용합니다. 이들 함수의 jacobian 행렬을 사용하여 칼만 필터에서 사용할 수 있도록 식을 수정합니다.

식만 간단히 정리해보도록 하겠습니다.

Time update

  1. $ \hat{x}^-_k = f(\hat{x}_{k-1}, u_k, 0) $
  2. $ P^-_k = A_k P_{k-1} A_k^T + W_k Q_{k-1} W_k^T $

Measurement update

  1. $ K_k = P^-_k H^T_k (H_k P^-_k H^T_k + V_k R_k V_k^T)^{-1} $
  2. $ \hat{x}_k = \hat{x}^-_k + K_k(z_k - h(\hat{x}^-_k, 0)) $

행렬 A, W, H, V는 각각 $ \frac{\partial f}{\partial x}, \frac{\partial f}{\partial w}, \frac{\partial h}{\partial x}, \frac{\partial h}{\partial v} $의 jacobian 행렬입니다.

4.3 An Example: Estimating a Random Constant

변화하지 않는 전압이 노이즈를 포함하여 관측되는 상황에서 전압을 추정하는 문제를 예로 매우 간단한 예제를 설명하고 있습니다.

5. Other Topics

Noise covariance Q, R의 선택에 관한 문제와 여러 모델을 사용하고 있는 경우 여러 칼만 필터를 이용 한 뒤 이를 통합하는 문제에 관한 설명을 하고 있습니다.


Add a Comment Trackback