확률적 로봇 공학 - 8. 그리드와 몬테카를로 위치 추정

8. 그리드와 몬테카를로 위치 추정 grid and monte carlo localization

8.1 소개

 이번에는 전역 위치 추정을 다룰수 있는 두가지 위치 추정알고리즘들에 대해 살펴보겠습니다. 이 알고리즘들은 이전 장에서 살펴본 가우시안 기술들과는 많은 다른점을 가지고 있습니다.

 

- 이 알고리즘은 센서 측정치를 그대로 처리하며, 센서 값에서 특징을 추출할 필요가 없습니다. 즉, 부정 정보들도 처리가 가능합니다.

 

- 이들은 비모수적으로, EKF 처럼 유니모달 분포에만 한정되지 않습니다.

 

- 이들은 전역 문제와 로봇 납치 문제들을 다룰수 있는데 EKF나 MHT는 이런 문제들을 대처할수 없습니다. 하지만 MHT는 수정하면 전역 문제를 풀수 있기는 합니다.

 

 여기서 설명하는 기술들은 로봇공학 분야의 여러 방면에서 좋은 성능을 보여주고 있습니다. 첫번째 기술은 그리드 위치 grid localization 추정으로 사후확률 신뢰도 나타내기 위해서 히스토그램 필터를 사용합니다. 이 그리드 위치 추정을 구현할때 많은 문제점이 발생하는데 그리드의 간격이 좁을수록 계싼 비용이 커지게 되어 이 알고리즘이 심하게 느려질수도 있습니다. 그리드가 큰 경우에는 이산화 과정에서 정보의 손실이 발생하여 적절히 대처하지 않는다면 필터에 부정적인 영향을 줄수도 있어 필터의 동작을 방해할수도 있습니다. 

 

 두번째 방법으로 몬테카를로 위치 추정 Monte carlo localization MCL 알고리즘이라 하며 오늘날 많이 사용되고 이씃ㅂ니다. 이 방법은 로봇의 자세에 대해 사후확률을  파티클 필터로 추정을하며 MCL의 많은 단점들이 다루어져, 로봇 납치문제나 동적인 환경에 적용할수 있는 기술들이 소개되었습니다.

 

 이번 장에서 살펴볼것은 오늘날 가장 성공적인 것들로 적절히 구현하면 이 기술들은 로봇을 전역적으로 위치를 추정하고 위치 추정 실패에서도 복원할수 있게 됩니다. 이 능력들은 신뢰할수 있는 로봇 동작이 요구되는 다양한 응용분야에서 사용되고 있습니다.

 

8.2. 그리드 위치 추정

8.2.1 기본 알고리즘

 그리드 위치 추정은 그리드로 된 자세 공간 전반을 히스토그램을 사용하여 사후확률을 근사화 하며, 이산 베이즈 필터에 대해 이미 4.1장 표 4.1에서 살펴보았습니다. 여기서 사후확률을 이산 확률로 다루며 값은 아래와 같습니다.

 각 확률 $p_{k, t}$는 이산 셀 $x_k$에 대한 확률로 정의되며, 모든 그리드 집합이 자세 공간을 형성하게 됩니다.

 그리드 위치 추정의 기본 버전에서 모든 자세 공간 영역들은 시불변이되고, 각 그리드 셀은 같은 사이즈로 이루어 집니다. 실내에서 흔히 사용되는 크기는 x-y 공간상에서 15cm정도 되고 회전 차원 상 5도 정도로 됩니다. 더 작을수록 좋은 결과를 구할수 있으나, 계산 비용이더 커지게 됩니다.

 

표 8.1 그리드 위치 추정, 이산 베이즈 필터의 변형. 함수 동작 모델은 동작 무델 중 하나를, 관측 모델은 센서 모델 중 하나를 구현하면 됩니다. 여기서 함수 mean은 그리드셀 $x_k$으 중심을 반환합니다.

 

 그리드 위치 추정은 기본적으로 이산 베이즈 필터와 동일하나 표 8.1은 기본적인 구현에 대한 슈도 코드를 보여주고 있습니다. 여기서 입력으로 이산 확률값인 {$p_{t-1, k}$}와 최근 측정, 제어, 그리고 지도 값이 사용됩니다. 내부 루프에서는 모든 그리드셀 전방에 반복을하고 3번째 줄은 동작 모델 갱신, 4번째 줄은 측정 갱신이 수행됩니다. 마지막 확률은 4번째 줄에서 정규자 $\eta$를 사용하여 정규화 되어집니다. 함수 motion_model 과 measurement_model은 5장이나 6장의 동작 모델과 측정 모델을 사용하여 구현될수 있습니다. 표 8.1의 알고리즘은 각 셀이 같은 크기를 가지고 있다고 가정하여 동작합니다.

 

그림 8.1 미터 분해 metric decomposition를 이용한 그리드 위치 추정.. 각 그림은 복도에서 신뢰도 bel($x_t$)를 사용하여 로봇의 자세를 그리드 상 히스토그램으로 보여주고 있습니다.

 

 그림 8.1은 1차원 복도에서 그리드 위치 추정을 보여주고 있습니다. 그림은 일반적인 베이즈 필터에서와의 동일하나 차이는 이산 영역에서 표현하는 점입니다. 로봇은 시작하기전에 전역적인 불확실성을 가지므로 균일 분포로 표현하였으며,  관측이 될때 거기에 알맞은 그리드 셀들의 확률 값이 증가하게 됩니다. 이 예제에서는 그리드 위치 추정의 다중 모달 분포를 나타내는 능력을 보여주고 있습니다.

 

 

8.2 그리드 해상도 grid resolution

 그리드 위치 추정기의 주요 변수는 그리드의 해상도입니다. 이는 후순위 일수도 있긴한데 센서 모델이나 갱신시 계산 그리고 결과 타입 모두가 그리드의 해상도에 의존하게 됩니다.

 

그림 8.2 로봇의 자세 변수 x, y $\theta$에 대한 고정 해상도 그리드 예시. 각 그리드 셀은 로봇의 자세를 나타내며, 로봇의 방향 차이는 그리드의 다른 평면에 대응합니다. 

 

그림 8.5 이동로봇 위치 추정의 굵은 토폴로지 표현법 응용예시. 각 상태들은 구분 가능한 장소에 대응하며, 상태에 있어서 로봇의 신뢰도 bel($x_t$)는 원의 크기로 표기됩니다. (a) 초기에는 모든 자세에 대해 초기 신뢰도가 균일하며 (b) 로봇이 상태 전이를 하고 문을 감지한 후에 신뢰도를 보여주고 있습니다. 이 때 로봇은 왼쪽에 존재하지 않음을 알 수 있습니다.

 

 로봇 공학 분야에서 잘 사용되어온 두가지 표현 방법이 있는데 

- 굵은, 변수-해상도 그리드 coars, varaible-resolution grid

 어떤 경우에는 자세 공간을 장소에 적합하게 분해하는 경우가 있습니다. 그러한 장소는 문이나 창같은 특정한 랜드마크로 정의할 수 있을것이고, 복도 환경에서는 교차로, 사거리나 끝 부분에 해당할수도 있을겁니다. 이런 표현방법에서 분해 시 해상도는 환경의 구조에 의존적이게 되어 그 구조들을 따르게 됩니다. 그림 8.5는 1차원 봉도 예제에서 굵은 표현법을 보여주며 이 굵은 표현법은 공간에 대해 토폴로지 표현법과 연관됩니다.

 

- 작은-고정 해상도 그리드 find fied-resolution grid

 다른 방법은 상태 공간을 동일한 크기의 그리드로 분해하는데 이 분해시 해상도는 변수 해상도 그리드보다 훨씬 커지게 됩니다. 7장에서 일부 예시에서 15cm 정도 셀사이즈로 그리드를 분해하였는데, 이렇게 하여 이들은 더 정확해재ㅣ지만 계산 비용이 증가하게 됩니다. 그림 8.2는 고정 그리드 해상도를 보여주고 있습니다. 이와 같은 작은 해상도는 공간 미터 표현법과 관련이 됩니다.

 

 굵은 해상도를 가진 그리드 위치 추정기를구현할때 해상도의 거침에 따라 센서 모델과 동작 모델에 보상해주는것이 필수적입니다. 레이저 거리계 같은 고해상도 센서의 경우에 측정 모델 p($z_t$ | $x_t$)의 값은 그리드 셀 $x_{k,t}$안에서 매우 급격하게 바뀔수 있습니다. 이런 경우 중심에서 평가를 하면 좋지 않은 결과를 얻을 수 있습니다. 비슷하게 중심에서 로봇의 동작을 예측 시에도 좋지 못한 결과를 얻을수 있습니다. 만약 그리드 해상도가 1m이고, 로봇이 10cm/sec로 움직이는데 1초 주기로 동작을 갱신하면, 상태전이시 좋은 결과를 구하지 못할겁니다. 이는 그리드 셀의 중심에서 10cm를 갔다고 하더라도 같은 그리드 셀안에 존재하는것으로 보기 때문입니다.

 

 이 효과를 보상하기 위한 방법으로 노이즈의 크기를 키우도록 측정과 동작 모델을 바꾸는것인데 예를들어 가우시안인 거리계의 분포를 그리드 셀의 지름 절반보다 크게 할 수 있겠습니다. 이렇게 하면 새 모델은 더 부드러워지고 정확한에 대해 구한 위치는 덜 확실해질것입니다. 하지만 수정된 측정모델이 얻은 정보를 줄여 위치 추정의 정확도를 줄이게 될것입니다.

 

 비슷하게 동작 모델은 동작의 길이에 비례하는 확률만큼 근처 셀에서 임의의 전의가 예측될탠대 이러한 부풀려진 동작 모델의 결과는 연속적인 갱신에서 동작이 그리드 셀의 사이즈 보다 작을지라도 기존의 셀에서 다른곳으로 이동한것이 될 수 있습니다. 하지만 결과로 나온 사후확률은 잘못되었으며, 비합리적으로 큰 확률이 로봇 동작 갱신시 가정으로 존재하게 될것입니다.

 

 

8.2.4 설명

그림 8.6 레이저 거리계 데이터를 사용한 전역 위치 추정.

(a) 로봇의 시작점에서 레이저 거리계 스캔(최대 거리 측정치는 생략됨)

(b) 균일 분포로 시작하여 이 레이저 스캔을 반영한 후 상황

(c) 2번쨰 스캔

(d) 결과 신뢰도. 그림 (e)의 마지막 스캔을 반영한 후의 결과

(f) 로봇의 신뢰도로 실제 위치

 

 그림 8.6은 공간 해상도가 15cm, 각 해상도가 5도인 미터 그리드에서 마르코브 위치 추정 예시를 보여주고 있습니다. 여기서는 두개의 레이저 거리계가 장착된 로봇을 사용하여 전역 위치 추정을 수행해서 자기 자신으 ㅣ위치를 처음부터 찾게 됩니다 .거리계의 확률 모델은 6.3장의 빔 모델과 표 8.1에 따라 계산됩니다.

 

그림 8.7 소나 데이터를 사용해서 사무실에서의 전역 위치 추정

(a) 로봇의 주행 경로

(b) 위치 1을 통과할때 신뢰도

(c) 로봇이 몇 미터 동작 후, 로봇은 복도 상 어딘가에 있음을 알게됩니다.

(d) 로봇이 위치 3에 도달하여 복도 끝을 스캔하고, 분포가 2개의 지역 최고점에 집중하게 됩니다. 최고점 라밸 I는 실제 로봇의 위치이고 2번째는 복도의 대칭성 때문에 생기게 됩니다.(위치 II는 위치 1의 180도 회전이 됩니다.)

(e) 올바른 위치 I에서 방 A로 들어간 후에 확률은 위치 II에 있던 확률보다 더 커지게 됩니다.

(f) 로봇의 신뢰도는 올바른 자세를 중심으로 모이게 됩니다.

 

 초기에 로봇의 신로도는 로봇 자세 공간 전체에 균일하게 분포되어 있습니다. 그림 8.6a가 시작 점에서 레이저 거리계 스캔을 보여주고 있는데 여기서 최대 거리 측정치는 생략되고 관련된 지도 영역들은 회색으로 그림자가 쳐졌습니다. 이 센서 스캔을 합찬 후에 로봇의 위치는 작은 영역 공간이 되어 그림 8.6b에 회색으로 보여주고 있습니다. 이때 신뢰도는 -x-y 공간에 사영되는데 실제 신뢰도는 3차원으로 이루어져 로봇의 방위 $\theta$는 생략 됩니다. 그림 8.6d는 로봇이 2m 이동 후 그림 8.6c에서 보여주는 스캔을 반영한 신뢰도를 보여주고 있습니다. 자세 추정시 확실성이 증가하고 전역 최대치 신뢰도가 실제 로봇의 위치에 맞게 됩니다. 그림 8.6e에서는 다른 스캔이 신뢰도에 반영된 후로 로봇이 마지막으로 스캔하는 모습을 보여주고 있습니다. 이제 모든 확률 질량들은 실제 로봇의 자세에 중심을 가지게 되며 그림 8.6f와 같습니다. 이 때 로봇이 성공적으로 위치 추정이 되었다고 할 수 있으며  이 예시는 그리드 위치 추정이 로봇의 위치를 효율적으로 추정해 나가는것을 볼수 있습니다. 다음예시는 그림 8.7에서 보여주고 있습니다.

 

그림 8.8 1994년 AAAI 이동로봇 경연에서 사용한 점유 격자 지도

 

그림 8.9 (a) 그림 8.8의 환경에서 수집한 데이터 셋(오도메트리, 소나 거리 스캔). 이 데이터 집합은 그리드 위치 추정으로 전역 위치 추정에 충분합니다.

(b) - (d) 점 "A", "B", "C"에서의 신뢰도를 보여주고 있습니다.

 

 물론 전역 위치 추정은 성공하기 위해서 추가적인 센서 스캔이 필요할수도 있습니다. 이러한 경우는 대칭적인 환경으로 만약 센서가 레이저 센서보다 덜 정확환 경우입니다. 그림 8.8 ~ 8.10은  소나 센서만 장치된 이동로봇을 사용하여 전역 위치 추정을 사용한 예시로 같은 폭을 가진 많은 복도들이 존재하고 있습니다. 그림 8.8에서 점유 격자 지도를 보여주고 있으며 그림 8.9a는 복도를 따라 이동하면서 얻은 데이터 셋을 보여주며, 그림 8.9a에서 각 빔은 소나의 측정치에 대응합니다. 이런 식으로 벽은 부드럽고 소나 값에 크게 손상됩니다. 소나의 확률적 모델은 6.3에서 설명한 빔 기반 모델을 사용하고 있습니다. 그림 8.9는 추가적으로 시간에 대해 3개의 다른 지점에서의 신뢰도를 보여주며 그림 8.9a에서 "A", "B", "C"로 되어있습니다. 로봇이 5개의 소나 스캔을 반영하면서 3미터를 이동한 후에 신뢰도는 그림 8.9b와 같이 동일한