Particle Filter 혹은 Sequential Monte Carlo 방식은 몬테카를로 알고리즘을 통해 신호처리와 베이지안 추정을 통한 필터링문제 해결 방안이다.
여기서 필터링문제란 관측되고 있는 동적인 환경에서 현재 상태를 추정하는 것으로 particle filter의 목표는 노이즈가 많고 부분적인 관찰이 진행되었을 때 일부 마르코프 결정 과정 상태의 사후 분포를 계산하는 것이다.
그럼 마르코프 결정 과정은 무엇인가?
마르코프 결정 과정(MDP, Markov Decision Process)은 의사결정 과정을 모델링하는 수학적인 틀을 제공한다.
어떤 시점에서 마르코프 결정과정은 어떠한 상태 s에 존재한다.
의사결정자는 해당 상태 s에서 어떤 행동 a를 취할 수 있으며 다음 시점에서 마르코프 결정 과정은 확률적으로 새로운 상태 s'으로 전이한다.
이 때 의사결정자는 상태전이에 해당하는 보상(R_a(s, s')) 을 받는다.
기존의 상태 s에서 새로운 상태 s'으로 전이하는 확률은 의사결정자의 행동에 영향을 받고 즉 전이 확률 함수는 P_a(s, s')로 표현되고 결과적으로 다음상태 s'은 현재상태 s와 의사결정자의 행동 a에만 영향을 받으며 이전의 상태와는 확률적으로 독립적일 때의 결정과정 상태를 얘기한다.
그럼 다시 Particle Filter, Sequential Monte Carlo에 대해 얘기해보자.
보통 Dynamic Programming을 진행할때 Planning 혹은 Learning을 진행한다.
Planning이란 주변 Environment에 대한 Model을 구하여 이를 푸는 과정이고
Learning이란 Environment의 model은 모르지만 상호작용을 통해서 문제를 푸는 과정을 말한다.
여기서는 Environment Model은 정확히 모르지만 Trial-and-error 의 과정(강화학습)을 통해 실재 측정되는 정보들을 통해 update하는 과정을 진행하게 된다.
(https://daeson.tistory.com/327)
Monte-Carlo란 단어는 무엇인가를 random하게 측정하는 것을 의미하고 강화학습에서는 "averaging complete returns"하는 방법을 의미한다고 한다.
그럼 이제 본격적으로 Particle Filter의 과정을 살펴보겠다.
2D Lidar센서를 장착한 모바일로봇이 있다고 가정해보자.
위의 그림에서 현재 로봇의 위치는 초록색 점으로 표시된 좌측 상단이고 붉은 점들은 particles에 해당한다.
particle은 좌표와 방향(x, y, yaw)의 값을 갖고있다.
그리고 전역지도의 랜덤한 위치에 particle을 분포한 것이다.
그리고 로봇이 이동하게 되면 이 모든 파티클 역시 이동하게 된다.
예를들어 로봇이 앞으로 3m를 이동하였다 가정하자.
그럼 모든 파티클이 현재의 방향(yaw)로 3m를 이동할 것이고 그때 로봇의 라이다 센서에서 관측되는 주변 환경이 있을 것이다.
그럼 각각의 파티클에 라이다센서가 장착되어있다 가정하고 로봇에서 관측된 측정값과 유사한 파티클의 경우 가중치(weight)를 높이고 관측된 측정값이 차이가 크게 발생할 것으로 예상되는 경우 가중치의 값을 낮춘다.
그리고 가중치의 값을 선택 확률로하여 다시 particle들을 샘플링한다.(resampling)
그럼 위의 이미지와 같이 현재 로봇의 위치로 추정되는 위치에 파티클들이 모이게 된다.
이 상태에서 다시 로봇을 이동시키고 관측되는 신호화 각각의 파티클에서 관측될 것으로 예상되는 신호들을 비교하여
파티클들의 가중치를 설정하고 다시 리샘플링(resampling)을 진행하면 다음과 같이 나타날 것이다.
위의 과정을 반복하면 결과적으로 현재 로봇의 위치를 정확하게 추정할 수 있게 된다.
아래 그림은 가중치에 대한 정보를 도식화한 것이다.
베이지안은 X_k의 상태를 이전의 확률밀도를 통해 계산하게 된다.
필터링 문제는 연속적인(sequentially) 상황에서 상태를 나타내는 X_1, X_2, X_3, ... 이 있다고 할때
이때 측정되는 신호(관측되는 신호) Y_1, Y_2, Y_3, ... 로 할때 어떠한 상태 X_k를 이전의 상태 X_(k-1)과 현재 관측되는 값 Y_k를 통해 추정하는 것이다.