8.64 입자 필터(파티클 필터)의 원리

1. 입자 필터의 개요

입자 필터(Particle Filter) 또는 순차 몬테카를로(Sequential Monte Carlo, SMC)는 비선형·비가우시안 시스템에서 사후 분포를 가중 샘플(입자)의 집합으로 근사하는 재귀적 베이즈 필터이다. 칼만 필터가 가우시안 가정에 제한되는 반면, 입자 필터는 임의의 분포를 근사할 수 있어 다봉, 비가우시안 사후 분포를 표현하는 데 적합하다.

2. 입자 기반 분포 근사

사후 분포를 $N$ 개의 가중 입자로 근사한다.

$p(\mathbf{x}_t \vert \mathbf{z}_{1:t}) \approx \sum_{i=1}^{N}w_t^{(i)}\delta(\mathbf{x}_t - \mathbf{x}_t^{(i)})$

여기서 $\mathbf{x}_t^{(i)}$ 는 $i$ 번째 입자의 상태, $w_t^{(i)}$ 는 그 가중치 ( $\sum w_t^{(i)} = 1$ ), $\delta$ 는 디랙 델타이다. 입자 수 $N$ 이 증가하면 근사가 참 사후 분포에 수렴한다.

3. 입자 필터의 단계

3.1 예측 단계

이전 시각의 입자들을 동역학 모델을 통해 전파한다.

$\mathbf{x}_t^{(i)} \sim p(\mathbf{x}_t \vert \mathbf{x}_{t-1}^{(i)}, \mathbf{u}_{t-1})$

제어 입력과 프로세스 잡음을 반영하여 각 입자를 독립적으로 샘플링한다.

3.2 갱신 단계

새 관측 $\mathbf{z}_t$ 에 의해 가중치를 갱신한다.

$w_t^{(i)} \propto w_{t-1}^{(i)}p(\mathbf{z}_t \vert \mathbf{x}_t^{(i)})$

관측 가능도가 높은 입자에 큰 가중치가 부여된다. 정규화 후 $\sum_i w_t^{(i)} = 1$ 을 만족한다.

3.3 리샘플링 단계

가중치의 분산이 커지면(소수의 입자가 지배적이 되면) 리샘플링(resampling)을 수행한다. 유효 입자 수 $N_{eff} = 1/\sum_i (w_t^{(i)})^2$ 가 임계값 이하면 리샘플링한다.

리샘플링: 기존 입자 집합에서 가중치에 비례한 확률로 새 입자를 추출하고, 모든 가중치를 $1/N$ 로 재설정한다. 이 과정에서 가중치가 큰 입자는 복제되고, 작은 입자는 제거된다.

4. 입자 변성(Particle Degeneracy)

순차적으로 가중치를 갱신하면 몇 번의 반복 후 대부분의 가중치가 소수의 입자에 집중되는 입자 변성이 발생한다. 이는 입자 필터의 가장 큰 도전이며, 리샘플링이 주된 해결책이다.

4.1 리샘플링 방법

다항식 리샘플링(Multinomial Resampling): 누적 가중치 분포로부터 $N$ 개의 독립 샘플을 추출한다.

계층 리샘플링(Stratified Resampling): 누적 분포를 $N$ 등분하고 각 구간에서 독립 샘플을 추출한다. 다항식보다 분산이 작다.

체계적 리샘플링(Systematic Resampling): 하나의 균일 난수로 $N$ 개의 등간격 점을 생성한다. 계산이 단순하고 분산이 작다.

4.2 샘플 빈곤(Sample Impoverishment)

리샘플링에 의해 서로 다른 입자의 수가 감소하는 현상이다. 이를 완화하기 위해 소량의 잡음을 추가하거나 MCMC 단계를 삽입한다.

5. 제안 분포의 선택

5.1 부트스트랩 필터(Bootstrap Filter)

가장 단순한 구현으로, 제안 분포를 전이 분포 $p(\mathbf{x}_t \vert \mathbf{x}_{t-1})$ 로 선택한다. 구현이 쉽지만 관측 정보를 활용하지 않아 비효율적일 수 있다.

5.2 최적 제안 분포

이론적으로 분산을 최소화하는 제안은 $q(\mathbf{x}_t \vert \mathbf{x}_{t-1}, \mathbf{z}_t) = p(\mathbf{x}_t \vert \mathbf{x}_{t-1}, \mathbf{z}_t)$ 이다. 이 조건부 분포는 일반적으로 해석적으로 구할 수 없으므로 근사가 필요하다.

6. 계산 복잡도

입자 필터의 계산 복잡도는 $O(N)$ (입자 수에 선형)이다. 각 시각에서 입자의 전파, 가중치 계산, 리샘플링이 모두 $O(N)$ 이다. 상태 차원이 증가함에 따라 필요 입자 수가 증가하지만, 칼만 필터와 달리 $O(n^3)$ 행렬 연산은 없다.

7. 로봇 공학에서의 입자 필터

7.1 몬테카를로 위치 추정(MCL)

실내 이동 로봇의 위치 추정에서 표준 방법이다. 2차원 또는 3차원 자세 공간에서 입자 집합이 사후 분포를 근사한다. 초기에 분포를 광범위하게 설정하여 글로벌 위치 추정을 수행한다.

7.2 FastSLAM

랜드마크 기반 SLAM에서 로봇 궤적을 입자로 표현하고, 각 입자에 대해 랜드마크의 EKF를 조건부로 유지한다. 궤적의 불확실성과 랜드마크의 조건부 가우시안을 결합하여 효율적인 SLAM을 구현한다.

7.3 다중 목표 추적

여러 이동 물체를 동시에 추적할 때, 각 물체의 가능한 상태를 입자로 표현한다.

8. 참고 문헌

Thrun, S., Burgard, W., & Fox, D. (2005). Probabilistic Robotics. MIT Press.
Doucet, A., de Freitas, N., & Gordon, N. (Eds.). (2001). Sequential Monte Carlo Methods in Practice. Springer.
Arulampalam, M. S., Maskell, S., Gordon, N., & Clapp, T. (2002). “A Tutorial on Particle Filters for Online Nonlinear/Non-Gaussian Bayesian Tracking.” IEEE Transactions on Signal Processing, 50(2), 174–188.
Barfoot, T. D. (2017). State Estimation for Robotics. Cambridge University Press.

version: 1.0