파티클 필터와 Monte Carlo Localization

Particle Filter 를 이용해서 Localization 을 하는 방식을 Monte-Carlo Localization 이라고 합니다.

 

지금까지는 칼만 필터를 사용했는데, 칼만 필터의 가장 기본적인 전제는 선형성과 가우시안 필터였습니다. 이 말은 확률 분포를 (랜드마크, 혹은 로봇이 있을 확률 등) 두 개의 파라미터로 표현할 수 있다는 것입니다. State 가 진행됨에 따라서 그 가우시안 분포가 계속 유지되게 하기 위해서는 선형성을 유지해야 했습니다. 다만 실제 세계에서는 선형적으로 State 가 바뀌는 경우가 잘 없기 때문에 EKF 등을 도입했습니다.

 

칼만 필터는 가우시안 분포를 사용하기 때문에 Parametric 한 방법이라고 말 할 수 있습니다. 그렇지만 이는 선형성을 가정했고, 아무리 EKF 라 하더라도 비선형성이 큰 시스템에 있어서는 잘 적용되지 않습니다.

 

Particle Filter 는 비선형적인 시스템에서 사용되기 위한 Non-parametric 한 방식을 제안합니다. 잘 알지 못해서 식으로 표현할 수 없는 분포들이 있을 때, 우리는 어떻게 접근해야 할까요 ?

 

Particle Filter 자체는 단순한 아이디어입니다. 확률 분포라는 것은 어떤 x 가 y 라는 특정 scalar 에 매칭되는 것입니다. 하지만 생각을 바꿔서, 하나의 scalar, 즉 크기를 가지는 것이 아니라 동일한 크기를 가지는 something 을 여러 개 가지고 있다고 가정을 해 봅시다. 예를 들어 구슬이라고 할 수도 있습니다.

제가 여러분들께 100개의 구슬을 주고 이들로 가우시안 분포를 나타내 보세요, 라고 한다면 높은 부분은 구슬을 많이 쌓고, 낮은 부분은 구슬을 적게 쌓겠죠 ?

이런 방식으로, 어떤 x 라는 값이 있을 때 확률값을 “갯수”로 표현하는 것이 파티클 필터의 일반적인 개념입니다.

Particle Set

j 번째 Particle 은 State 과 Weight 을 가지고 있습니다. 그리고 모든 파티클은 동일하지 않습니다. 동일하지 않다는 것은 각각의 weight 들이 다르다는 의미입니다. 파티클의 weight 을 통해서 다시 확률분포를 재 계산할 수 있습니다.

가우시안을 파티클 필터로 나타내고 파티클을 선이라고 했을 때, 이 그림에서는 선의 밀도가 높은 곳이 확률값이 크고, 밀도가 낮은 곳이 확률값이 낮습니다. 오른쪽 그림처럼 우리가 모르는 임의의 확률분포가 있을 때도 우리는 이 distribution 을 가우시안과 마찬가지로 파티클들의 밀도로 그 분포를 추정할 수 있습니다.

Sampling

 

이전에 구슬들처럼 그저 확률값의 크기를 보고 파티클을 분배하는 샘플링을 할 수도 있지만, 때때로 그런 방식은 정확하지 않습니다. 분포로부터 정확하게 샘플링을 하는 방식 (Closed Form) 이 규명된 분포는 그렇게 많지 않습니다. 예를 들어, 가우시안 분포는 이와 같이 샘플링을 하는 것이 정확하다고 수학적으로 증명되어 있습니다.

하지만 이런 Closed Form 이 모든 분포에 대해서 규명된 것이 아니기 때문에, 우리는 (임의의 분포 ↔ 가우시안 분포 ↔ 샘플) 이런 식으로 가우시안 분포를 거쳐서 임의의 분포를 샘플링하게 됩니다.

1. 가우시안으로 샘플을 만든다.
2. 임의의 분포와 가우시안의 차이에 따라 샘플들에 weight 을 준다.
3. weight 이 큰 샘플들을 분할해서 전체 샘플들의 크기를 동일하게 한다.

Particle Filter

• Recursive Bayes Filter
• Non-parametric Approach
• Models the distribution by samples
• Prediction : draw from the proposal
• Correction : weighting by the ratio of target and proposal

그래서 정리를 하자면, 파티클 필터는 Recursive Bayes Filter 의 일종입니다. Prediction 하고 Correction 을 반복하는 것이 베이즈 필터입니다. 샘플을 모션 모델로 옮기는 것이 Prediction 이고, 옮긴 각각의 파티클에게 weight 을 부여하는 것이 Correction 입니다.

Algorithm

Pseudo Code 를 보면,

• Prediction : 3 째 줄
• Correction : 4 째 줄
• Resampling : 7~10 째 줄

이라고 할 수 있습니다.

Monte Carlo Localization

 

파티클 필터는 도박과 유사한 점이 있습니다. 랜덤하게 뿌려 놓고 그 결과에 따라서 나의 행동을 바꿔 가는 것입니다. “몬테 카를로” 는 도박으로 유명한 도시입니다.

랜덤하게 뿌려놓고 결과값에 따라서 계속 업데이트를 해 나가는 방식을 몬테 카를로 라고 합니다. 이름에서도 알 수 있듯이, Localization 에서는 Map 이 주어져 있습니다.

 

이해를 돕기 위해 예시를 들어보겠습니다. 여러분들이 별다방 창업주인데, 전 세계에서 100개의 점포만 운영할 수 있습니다. 그렇지만 전 세계 어디든 원하는 곳에 점포를 개설할 수 있습니다.

수익을 극대화하기 위해서 다양한 전략이 있을 수 있겠죠 ? 그 중 하나의 전략은 다음과 같습니다.

처음에는 100개의 점포를 균일하게 개설하는 것입니다. 이후 1년이 지나면 매출액을 알 수 있습니다. 한국, 미국에서는 매우 크고 아프리카에서는 매출이 많이 없고… 그런 통계를 보고 잘 되는 곳에 점포를 더 열고, 안 되는 곳의 점포를 폐점하는 것입니다. 이런 방식을 반복할 수 있겠죠 ?

 

몬테 카를로 Localization 도 똑같은 원리입니다. 어떤 map 이 있을 때, 초기에는 파티클 (로봇이 있을 확률 분포) 들을 균일하게 뿌립니다. 이후 ut (여기서는 모션입니다) 가 진행된 후에 Correction 을 해야 하는데, correction 을 하기 위해서는 weight 이 필요하겠죠 ?

 

바로 그때 사용하는 것이 observation model 입니다. 나의 관측 결과에 따라서 weight 를 부여합니다. 내가 예측한 값과 실제 관측한 값의 유사도를 정의해서 weight 을 줍니다. 이후 resampling 과정에서 이들을 weight 에 따라서 같은 크기의 파티클로 분할하게 됩니다.

이런 방식의 파티클 필터를 이용한 localization 은 2D map 같은 low-dimensional space 에서 잘 작동합니다.

 

---

위 내용은 경희대학교 소프트웨어융합학과 황효석 교수님의 2021년 <로봇프로그래밍> 수업 내용을 요약한 것입니다.