§ 1문제 정의
숲에 흩어진 수십 개 센서가 죄인의 위치를 보고한다. 각 센서는 노이즈가 있어 “정확한 좌표 ± Gaussian”로 알려준다. 매 턴 죄인은 일정 패턴으로 움직이고, 다시 새 센서 보고가 들어온다. 끝까지 추적하라.
단일 점 추정(평균, 중앙값)은 빠르게 깨진다 — 다중 모드의 사후 분포가 생기면 평균이 “두 봉우리 사이의 빈 골짜기”에 떨어진다.
해법: 확률 분포 자체를 다수의 파티클로 표현. 베이지안 갱신 + 중요도 재샘플링이 자연스럽게 다중 모드를 유지하고, 시간이 흐를수록 진짜 위치 쪽 모드가 지배적으로 무거워진다.
한 점은 거짓말한다. 1000개 점이 그리는 구름이 진실이다.
§ 2파티클 필터 시뮬레이션
초기 균일 분포 → 센서 갱신 → 가중 → 재샘플링 → 점점 수렴. 분포가 어떻게 “진짜 위치”로 응축되는지 관찰.
FIG. 18 — particle filter convergence
STEP 01 / 6
SPACE play/pause · ← → step · R reset
§ 3왜 파티클 필터가 최적인가
| 접근법 | 한계 |
|---|---|
| Kalman Filter | 가우시안 단일 모드 가정 → 다중 모드 폭주 |
| Grid Bayesian | O(N²) 공간 메모리, 큰 맵 불가 |
| 최단거리 평균 | 중앙값/평균이 진짜 위치 밖으로 빠짐 |
| Particle Filter | ✓ 다중 모드 자연 표현, O(N) 시간 |
핵심 정리: 사후분포 p(x | z) ∝ p(z | x) × p(x). 파티클은 prior에서 샘플링, 가중치 = likelihood, 재샘플링이 사후를 근사한다. Monte Carlo Importance Sampling의 점진적 적용.
파티클 1000개는 그리드 1,000,000셀의 베이지안 갱신을 1/1000 비용으로 흉내 낸다 — 차원의 저주를 회피.
§ 4알고리즘 골격
init():
particles = uniform_random_sample(N=1000)
weights = [1/N] × N
step(sensor_readings):
# 1) Predict — 모션 모델
for p in particles:
p.pos += motion + gauss_noise(σ_motion)
# 2) Update — 베이지안 갱신
for p in particles:
weights[p] = 1
for sensor in sensor_readings:
d = dist(p.pos, sensor.reading)
weights[p] *= gauss_pdf(d, σ_sensor)
normalize(weights)
# 3) Resample — 중요도 재샘플링
new_particles = []
for i in 0..N:
idx = weighted_random_pick(weights)
new_particles.append(jitter(particles[idx]))
particles = new_particles
# 4) Estimate — 점추정이 필요하면 평균/MAP
estimate = weighted_mean(particles, weights)
return estimate
# 공간 가속: kd-tree로 근처 파티클 검색 O(log N)
# 또는 quadtree로 영역별 가중치 합산