확률적 로봇 공학 - 8.3몬테카를로 위치추정

8.3 몬테카를로 위치추정 Monte Carlo Localization

8.3.1 몬테카를로 위치 추정 알고리즘 MCL Algorithm

 이번에는 신뢰도 bel($x_t$)를 파티클로 나타내는 위치 추정 방법을 살펴보겠습니다. 이를 몬테카를로 위치 추정 MCL이라고 하는데, 그리드 기반 마르코브 위치 추정처럼 MCL은 지역과 전역 위치 추정문제에 사용할수 있습니다. 이 방법은 비교적 오래되지는 않았지만 이미 로봇 공학에서 가장 많이 사용하는 위치 추정 알고리즘중하나가 되었습니다. 이 방법은 구현하기 쉽고 위치 추정문제에서 넓게 잘 동작하는 모습을 보여줍니다.

 

 표 8.2 MCL or Monte Carlo Localization, 파티클 필터 기반 위치 추정 알고리즘

 

 표 8.2는 기본적인 MCL 알고리즘을 보여주며, 표 4.3의 파티클 필터에 적절한 확률적 동작 모델과 측정 모델을 대입하여 구할수 있습니다. 기본적인 MCL 알고리즘은 신뢰도 bel($x_t$)를 M개의 파티클 집합 $\chi_t$ = {$x_{t}^{[1]}$, $x_{t}^{[2]}$, $x_{t}^{[3]}$, . . ., $x_{t}^{[M]}$}로 나타냅니다. 표 8.2의 4번째 줄은 현재 신뢰도를 시작점으로 파티클을 사용해 동작 모델로부터 샘플링을 수행합니다. 5번째 줄에서는 파티클의 중요도 가중치를 구하기 위해 빔 측정모델이 사용되는데, 초기 신뢰도 bel($x_0$)는 사전 확률 분포 p($x_0$)에서 파티클 M을 임의로 생성하고 각각의 파티클에 대해 $M^{-1}$ 균일 중요도 가중치를 할당하여 얻을 수 있습니다. 그리드 위치 추정으로서 동작 모델과 측정 모델은 5장이나 6장의 어느것을 사용해도 됩니다.

 

 

그림 8.11 이동 로봇의 위치 추정에 파티클 필터가 적용된 몬테카를로 위치 추정

 

 그림 8.11은 1차원 복도 예시에서 MCL을 사용한 경우를 보여주고 있습니다. 초기 전여 불확실성은 그림 8.11a처럼 전체 공간에 균일한 임의의 파티클을 그려 만들수 있고, 로봇이 MCL 알고리즘의 5번째 출에서 문을 감지할 경우 각각의 파티클의 중요도 요소를 줍니다. 그림 8.11b가 그 결과인 파티클 집합을 보여주고 있는데 이 그림에서 각 파티클들의 높이가 중요도 가중치가 됩니다. 여기서 그림 8.11a에서 사용한 파티클 집합과 동일한 것이 중요한데, 이들은 측정 갱신에 의해 중요도 가중치가 변경됩니다.

 

 그림 8.11c는 MCL 알고리즘의 8~11줄에서 수행하는 리샘플링 후와 로봇 동작(4번째 줄)을 반영한 후 파티클 집합을 보여주고 있습니다. 이렇게 하여 새로운 파티클 집합은 균일 중요도 가중치를 가지게 되나 세 장소 근처에 파티클 수가 증가하였습니다. 그림 8.11d에서 새로운 관측은 파티클 집합에 균일 분포를 따르지 않는 중요도 가중치를 주는데, 이때 누적 확률 질량은 2번째 문을 중심으로 하게 되며 실제 로봇이 있는 가능성있는 위치가 됩니다. 더 나아가 동작은 다른 리샘플링 단계를 수행시키게하고, 새로운 파티클이 동작 모델에 따라 생성됩니다(그림 8.11e). 이 예시로 부터 파티클은 올바른 사후확률을 근사화 시키며 베이즈 필터로 계산된것이 됩니다.

 

그림 8.12 몬테카를로 위치 추정 예시. 여기서 54m x 18m인 사무실 공간에서 수행하였습니다.

(a) 5m 이동한 후 로봇은 여전히 자세에 대해 높은 불확실성을 가지고 파티클들이 넓게 퍼져있습니다.

(b) 로봇이 지도의 왼쪽 위 코너에 도달할때 신뢰도가 4가지 지점으로 모여들게 됩니다.

(c) 약 55m정도 이동한 후에 이 애매함이 해결되어 로봇은 자신의 위치를 알게 됩니다. 이 전체 계산과정은 저성능 PC에서 실시간으로 수행되었습니다.

 

 그림 8.12는 실제 사무실에서 여러개의 초음파 거리계를 장비한 로봇으로 MCL을 사용한 결과를 보여주고 있습니다. 각 그림들은 5, 28, 55m 이동한 후에 파티클의 집합을 보여주며 각각의 파티클 집합은 3차원 자세에서 정의되며 그림 상으로 각각의 파티클들은 x, y 좌표만 보여주고 있습니다.

 

 

그림 8.13 천장을 보는 카메라를 이용한 전역 위치 추정

 

 그림 8.13은 카메라를 천장으로 향하도록 하였고, 이전에 획득한 천장 지도에 이미지 중심에서의 밝기를 이용한 관측모델이 사용되었습니다.

 

8.3.2 MCL의 성질들

 MCL은 현실적으로 사용되는 어느 분포든 근사화 시킬수 있습니다. 그래서 EKF 위치 추정과같은 제한된 모수적인 분포에만 한정되지 않습니다. 근사의 정확도는 파티클 집합 M의 크기에 따라 결정되는데 전체 파티클의 개수를 늘릴수록 근사 정확도가 증가하게 됩니다. 파티클개수 M는 MCL을 동작시킬때 정확도와 계산 자원을 트레이드 오프 할수있는 파라미터가 됩니다. 일반적인 방법은 M를 다음 $u_t$와 $z_t$를 할떄까지 유지 시킵니다. 이 방법은 계산 자원에 따라 적응할수 있도록 구현이 가능한데, 프로세서가 더 빠를수록 더 나은 위치 추정성능을 구할수 있습니다. 이러한 자원 적응적인 방법은 그리드 위치 추정이나 가우시안 방법들의 경우 수행하기 어렵습니다.

 

 마지막으로 MCL의 이점은 근사시 비모수적인 방법을 사용하고, 위에서 본 설명들은 MCL이 멀티모달 확률 분포로 보여주며, 이들이 중심이 되는 가우시안 분포들로 섞이게 됩니다. 이는 MCL이 전역 위치 추정 문제를 높은 신뢰도를 가지는 위치 추적을 할수 있는 능력을 보여주고 있습니다.