[Algorithm] Kalman Filter(칼만 필터)

칼만 필터(Kalman Filter)는 시계열 데이터에서 상태 추정을 위한 알고리즘으로, 관찰 데이터(Observed Data)의 노이즈와 시스템 모델(System Model)의 불확실성이 있는 상황에서 시스템의 상태를 예측값과 노이즈가 포함된 관찰 데이터를 바탕으로 재귀적으로 예측하고 보정합니다.

칼만 필터의 개념적 구조

출처 : https://www.kalmanfilter.net/kalman1d.html

---

역사

칼만 필터는 1960년 미국의 수학자이자 제어 이론가인 루돌프 칼만(Rudolf E. Kalman)에 의해 제안되었습니다. 이 논문은 노이즈가 포함된 데이터에서 선형 동적 시스템(Linear Dynamic System)의 State를 최적 추정할 수 있는 새로운 알고리즘을 제시하였습니다.

초기에는 당시 컴퓨터 성능으로는 알고리즘의 계산을 수행하기 어렵다는 평가를 받았습니다. 하지만 NASA가 당시 아폴로 우주 계획에서 Saturn V 로켓과 아폴로 우주선의 궤적 추적 및 제어에 칼만 필터를 사용하여 성공적인 달 착륙을 이뤄내며 상황은 180도 달라지게 되었습니다.

이후 칼만 필터는 여러 파생 접근법을 양산하였고 비선형 시스템으로 확장되어 Extended Kalman Filter(EKF)로 확장되는 등 활발하게 연구되었습니다.

---

칼만 필터를 이해하기 위해서는 우선 선형 동적 시스템(Linear Dynamic System)을 알아야합니다.

선형 동적 시스템

선형 동적 시스템은 시스템의 상태가 시간에 따라 변화하며, 이 변화가 선형 방정식으로 표현될 수 있는 시스템을 말합니다.

수학적으로는 다음 수식으로 표현됩니다.

• 상태 방정식(State Equation) $$ x_t = Ax_{t-1} + Bu_t + w_t$$
  • $x_t$ : $t$-번째 시점에서의 상태 벡터
  • $A$ : 상태 전이 행렬(State Transition Matrix) - 상태가 시간에 따라 어떻게 변화하는 지를 나타냅니다.
  • $u_t$ : 입력 벡터
  • $B$ : 제어 입력 행렬 - 입력이 상태에 미치는 영향을 의미합니다.
  • $w_t \sim N(0, Q)$ : 시스템 노이즈
• 관측 방정식(Observation Equation) $$z_t = Hx_t + v_t$$
  • $z_t$ : $t$-시점에서의 관측 벡터
  • $H$ : 관측 행렬 - 상태가 관측에 미치는 영향을 의미합니다.
  • $v_t \sim N(0,R)$ : 관측 노이즈

칼만 필터는 위 시스템에서 $x_t$를 추정하는 알고리즘이라고 생각할 수 있습니다.

---

알고리즘

칼만 필터는 매 시점 $t$에서 다음 단계를 반복합니다.

예측 단계(Prediction Step)

상태 예측 (State Prediction):

$$\hat{x}_{t}^+ = A \hat{x}_{t-1} + Bu_{t}$$

• $\hat{x}_t^+$: $t$-번째 시점의 예측된 상태 벡터.
• $A$: 상태 전이 행렬 (State Transition Matrix).
• $B$: 제어 입력 행렬 (Control Input Matrix).
• $u_t$: $t$-번째 시점의 제어 입력 벡터.

오차 공분산 예측 (Error Covariance Prediction):

$$P_t^+ = A P_{t-1} A^T + Q$$

• $P_t^+$: $t$-번째 시점의 예측된 오차 공분산.

• $P_{t-1}$: 이전 시점의 오차 공분산.

• $Q$: 시스템 노이즈 공분산 (Process Noise Covariance).

갱신 단계(Update Step)

갱신 단계에서는 관측값 $z_t$를 이용해 상태 예측값 $\hat{x}_t^+$을 보정하여 최종 상태 추정값 $\hat{x}_t$를 계산합니다.

칼만이득(Kalman Gain)

관측값과 예측값의 신뢰도를 결합하기 위해 칼만이득 $K_t$를 사용합니다. 이는 관측값과 예측값의 불확실성을 고려한 가중치라고 볼 수 있습니다.

$$K_t = P_t^+ + H^T (HP_t^+ H^T + R)^{-1}$$

추정값의 갱신식

$$\hat{x}_t = \hat{x}_t^+ K_t (z_t - H\hat{x}_t^+)$$

여기서 $z_t - H\hat{x}_t^{+}$는 관측값과 예측값의 차이입니다.

칼만 이득은 이 차이에 대해 Least Square 방식으로 계산하여 유도됩니다.

상태 갱신(State Update):

상태 추정값은 예측된 상태 $\hat{x}_t^{+}$와 관측값 $z_t$의 가중합으로 갱신됩니다.

$$\hat{x}_t = \hat{x}_t^{+} + K_{t}(z_t - H\hat{x}_t^{+})$$

오차 공분산 갱신(Error Covariance Update):

갱신된 상태의 오차 공분산은 다음과 같이 유도됩니다.

$$P_t = (I - K_tH)P_t^+$$

갱신된 상태 $\hat{x}_t$는 다음 시점의 상태를 예측하는 데 사용됩니다. 예측 단계에서 이 값을 기반으로 미래의 시스템 상태를 계산하며, 이는 실시간 시스템 제어와 사전 대응을 가능하게 합니다. 또한 실시간으로 상태를 추정하고 제어하는 데도 사용됩니다.

하지만 칼만 필터는 선형 시스템과 가우시안 노이즈를 가정하기 때문에, 비선형성을 모델링하거나, 노이즈가 Non-Gaussian인 경우 어려움을 겪습니다. 이 문제를 해결하기 위해서 EKF(Extended Kalman Filter), Particle Filter 등의 방법론들이 개발되었습니다.

wikipedia Extended Kalman filter

Kalman and Extended Kalman Filters:
Concept, Derivation and Properties