확률적 로봇공학 - 4.2 파티클 필터

 

 

4.2 파티클 필터

4.2.1 기본 알고리즘

 파티클 필터는 배이즈 필터의 비모수적 구현으로 히스토 그램처럼 유한 개의 파라미터로 사후 확률을 근사화 시키지만 상태 공간 상에서 파라미터를 생성시키는 방법이 다릅니다. 파티클 필터의 키 아이디어는 사후 확률 bel($x_t$)를 이 사후 확률로부터 생성한 임의의 상태 샘플 집합으로 나타내는것입니다. 

 

그림 4.3 파티클 필터를 이용한 파티클 표현

- 우측 아래 그림은 가우시안 확률 변수 X로 샘플을 생성한 그래프로 이 샘플들은 우측 위 비선형 함수에 적용되어 결과 샘플들은 확률 변수 Y에 대해 분포됨.

 

 그림 4.3은 가우시안을 이용한 이 개념에 대해 설명하고 있습니다. 모수적 형태의 분포를 사용하는 대신 파티클 필터는 이 분포로부터 샘플 집합을 생성하여 이 분포를 표현합니다. 이러한 표현법은 근사화 된것이나 비모수적이고, 가우시안보다 넓은 분포 공간에서 나타낼 수 있습니다.

 

 파티클 필터에서 사후확률 분포의 샘플들을 파티클 particles이라 부르며 다음과 같이 적습니다.

 

 각각의 파티클 $x_{t}^{[m]}$ (1 <= m <= M)은 시간 t에 대한 상태의 인스턴스로 실제 상태에 대한 가정이 됩니다. 여기서 M은 파티클 집합 $\chi_t$에서 파티클의 개수로 보통 M = 1000이 됩니다.

 

 파티클 필터는 파티클 집합 $\chi_t$의 집합으로 신뢰도 bel($x_t$)를 근사화 시키며, 파티클 집합 $\chi_t$에 존재하는 상태 가정 $x_t$의 우도는 베이즈 필터의 사후 확률 bel($x_t$)에 비례하게 됩니다.

 (4.23)에 따라 상태 공간의 하부 영역이 샘플들로 밀집될수록 이 공간이 실제 상태에 가깝게 되어집니다. 유한한 M에 따라서 파티클들은 조금씩 다르게 분포될수 있지만, 파티클의 수가 너무 적지 않으면(M >= 100)은 이 차이는 무시해도 됩니다.

 

표 4.3 파티클 필터 알고리즘. 가중치 샘플링에 기반한 베이즈 필터의 변형

 

 이전에 살펴본 다른 베이즈 필터와 달리 파티클 필터 알고리즘은 신뢰도 bel($x_t$)를 이전 신뢰도 bel($x_{t-1}$)로부터 재귀적으로 만들며, 신뢰도들은 파티클의 집합으로 나타내기 때문에 이는 파티클 필터가 이전 집합 $\chi_{t-1}$로부터 재귀적으로 파티클 집합 $\chi_t$를 만든다고 할 수 있습니다. 파티클 필터의 기본 알고리즘은 표 4.3과 같습니다.

 

 이 알고리즘의 입력은 파트클 집합 $\chi_t-1$와 입력 $u_t$, 관측 $z_t$을 사용합니다. 처음에는 $\bar{bel}(X_t)$에 대응하는 임시 파티클 집합 $\bar{\chi}$를 생성합니다. 이는 입력 파티클 집합 $\chi_{t-1}$에서 각각의 파티클 $x_{t-1}^{[m]}$을 아래의 과정처럼 처리하여 수행됩니다.

 

1. 4번째 줄에서는 파티클 $x_{t-1}^{[m]}$과 제어 $u_t$로 시간 t에 대한 상태 가정 $x_{t}^{[m]}$을 생성합니다. 결과 샘플은 m으로 인덱싱하는데, $\chi_{t-1}$의 m번째 파티클에서 만들어 졌음을 나타냅니다. 이 단계에서 상태 전이 확률 p($x_t$ | $u_t$, $x_{t-1}$)으로 샘플링을 포함하므로 이 단계를 구현하기 위해 p($x_t$ | $u_t$, $x_{t-1}$)에서의 샘플링이 되어야 합니다. 상태 전이 확률로 부터 샘플링 시에는 p($x_t$ | $u_t$, $x_{t-1}$)만 사용되는 것은 아니며 이 책에서의 많은 분포들이 샘플 생성을 위해 효율적인 알고리즘들을 가지고 있습니다. 이 과정들이 M번 반복이 되어만든 파티클 집합이 이 필터의 $\bar{bel}(x_t)$가 됩니다.

 

2. 5번째 줄에서는 각각의 파티클 $x_{t}^{[m]}$의 가중치 요소 $w_{t}^{[m]}$ importance factor을 계산합니다. 가중치 요소는 측정 $z_t$를 파티클 집합에 적용시킬때 사용되는데, 이는 파티클 $x_{t}^{[m]}$에 대한 측정 $z_t$의 확률로 $w_{t}$ = p($z_t$ | $x_{t}^{[m]}$)이 됩니다. $w_{t}$를 파티클의 가중치로 본다면 가중치가 적용된 파티클들의 집합은 베이즈 필터 사후확률 bel($x_t$)라고 볼수 있습니다.

 

3. 파티클 필터 알고리즘의 실제 트릭은 8~11번째 줄에서 수행됩니다. 이 세 줄은 리샘플링 or 가중치 리샘플링을 구현한 것으로 임시 파티클 집합 $\bar{\chi_t}$로부터 M개의 파티클을 대체시키게 됩니다. 중요도 가중치에의해 각 파티클들의 확률이 주어지면, 리샘플링 과정에서 기존의 M개 파티클 집합을 동일한 크기의 다른 파티클 집합으로 변환시킵니다. 이 중요도 가중치를 리샘플링 과정에 적용함으로서 파티클의 분포가 변하게 되는데, 리샘플링 전에 파티클 집합은 $\bar{bel}$($x_t$)를 따랐다면 리샘플링을 수행한 이후에는 사후 확률 bel($x_t$) = $\eta$ p($z_t$ | $x_{t}^{[m]}$) $\bar{bel}$($x_t$)를 따르게 됩니다. 파티클들이 대체 되었기 때문에 결과 파티클 집합은 많은 복제된 파티클들을 가지게 됩니다. 더 중요한 점은 $\chi_t$에 포함되지 않은 파티클들은 적은 중요도 가중치를 가지는 경향이 있습니다.

 

 리샘플링 단계는 파티클들을 사후 확률 bel($x_t$)를 만드는 중요한 함수이며, 각각의 파티클의 중요도 가중치는 1로 초기화되어 곱이 수행됩니다.

 파티클 필터 알고리즘은 사후확률을 근사화 시키나 수많은 파티클들이 사후확률이 낮은 영역에 머무르게 됩니다. 그 결과 더 많은 파티클들이 필요하게 되는데 이는 사후확률의 형태에 따라 정해집니다. 리샘플링 단계는 적자생존 survival of the fittest 의 확률적인 구현으로 높은 사후 확률 역역에 존재하는 파티클 집합을 중심으로 만듭니다. 이렇게 함으로서 상태 공간 상에 문제를 다루는 영역에 한하여 필터 알고리즘의 자원 사용을 적용하게 됩니다.