몬테카를로 마르코프 위치 인식 방법(MCMC(Monte-Carlo Markov Chain) Localization)

몬테카를로 마르코프 위치 인식 방법

MCMC(Monte-Carlo Markov Chain) Localization

 이동 로봇이 어디선가 이동하고 있는데 현재 얻을 수 있는 정보는 거리 센서로부터 얻은 정보이거나 영상으로 부터 입력된 사진등일 경우 로봇의 현재 위치를 어떻게 추정하면 좋을까?

 바로 이전의 위치를 알고 있다면 순간이동을 하지 않는다면, 짧은 시간 내에서는 비슷한 위치에 있을 것임을 추론할 수 있다. 바로 이전의 위치를 정확하게 알 수 없다면, 확률적으로 가중치를 부여한 이전 위치에 대한 다음 위치를 마찬가지로 구해낼 수 있을 것이다.

  이것을 수식화하고 실제 구현을 통해 증명한 것이 Sebastian Thrun이다. Thrun은 현재에도 스탠포드 교수로 재직하면서 활발한 연구를 하고 있다. 구글 무인 자동차 연구 그룹의 수장으로 알려져 있다.

 마르코프 위치 인식에 대해서 이해하자면 베이지안 추정 필터에 대한 이해가 필요하다.

\( Pr(\xi^{(t)}|s^{(t)}) = \frac{Pr(s^{(t)}|\xi^{(t)})Pr(\xi^{(t)})}{Pr(s^{(t)})} \)

 확률론에서 마르코프 체인은 바로 다음의 상태는 과거의 상태가 현재까지 축적된 현재 상태에만 기인한다는 이론이다. 상식적으로도 그렇지 않은가? 로봇이 움직이는 다음 위치는 바로 이전 상태에만 관계가 있지, 그 보다 과거의 상태에 영향을 받을 이유는 없다.

 첨자들과 표기가 바뀌었지만 베이지안 추정 필터에서 소개한 것과 별반 다를 바 없는 식이다.

 실제 구현에서는 몬테카를로 기법을 여기에 함께 사용하는 이유는 연속(Continuous)신호를 표현한 수식을 구현하다 보면 필연적으로 데이터 분해능과 성능의 저하가 발생하기 때문이다. 몬테카를로 방법도 마찬가지로 반복의 횟수와 샘플의 갯수에 따라 성능의 차이가 있지만만, 충분히 많은 수의 샘플을 사용하면 만족할만한 정확도를 얻을 수 있다.

 다음 그림과 동영상은 실제로 Minerva에서 사용된 천정 영상과 Occupancy grid에 대한 위치 인식을 수행한 결과이다.