확률적 로봇공학 - 9.2 점유 격자 지도 작성 알고리즘

9.2 점유 격자 지도 작성 알고리즘 the occupancy grid mapping algorithm

 기본적인 점유 격자 지도 작성 알고리즘의 형태는 다음의 데이터가 주어질때 지도에 대한 사후확률을 구하는 것입니다.

 

 여기서 m은 지도 $z_{1:t}$는 시간 t까지 모든 측정치, $x_{1:t}$는 로봇의 경로로 모든 자세들의 정보가 됩니다. 제어 $u_{1:t}$는 점유 격자지도에서 아무런 역활을 수행하지 못하는데 이미 경로를 알고 있기 때문이라 이번에는 생략하겠습니다.

 

 점유격자 지도같은 형태의 지도들은 연속적인 위치 공간에 대해 고운 그리드로 정의되며, 점유 격자 지도의 주로 사용되는 형태는 2차원 평면으로 3차원 현실을 2차원으로 나타낸 것입니다. 2차원 지도는 평면에서 로봇이 주행시에 유용하게 사용됩니다. 점유 격자 기술은 3차원 표현으로 일반화시킬수도 있지만 계산비용이 커지게 됩니다.

 

 $m_i$를 인덱스가 i인 그리드 셀이라고 표기하면, 점유 격자 지도는 유한개의 많은 그리드들로 이루어지게 됩니다.

 각 $m_i$들은 이진 점유 값을 가지는데 이는 이 셀이 점유되었는지 비었는지를 나타냅니다. 만약 1이라고 하면 이 공간은 점유된것이고 0인 경우에는 비어있게 됩니다. p($m_i$ = 1) or p($m_i$)와 같은 표기법을 사용해서 그리드 셀이 점유된 확률을 보여줍니다.

 

 식 (9.1) 사후확률에 대해서 문제점은 차원인데, 지도 상의 그리드셀의 수가 그림 9.1처럼 10,000개 정도 된다면 이 공간을 계산하는대는 $2^{10000}$를 넘기게 될겁니다. 이런 지도에서 각 단일 사후확률을 계산하기에는 추적하기가 어렵습니다.

 

 표준 점유 격자 접근방법에서는 지도 근사화 문제를 분할된 문제의 컬랙션으로 바꾸는데 모든 그리드 셀 $m_i$에 대해 다음과 같이 근사화합니다.

 각각에 대한 근사하는 문제는 이제 정적 상태를 가지는 2진 문제가 되었습니다. 문제가 없다면 이런식으로 분해하는게 편리할겁니다. 특히 이렇게 함으로서 이웃한 셀 간에 의존관계를 나타낼수 있게 되는데, 지도 전반의 사후확률은 주변 확률분포의 곱으로 근사되어 집니다.

 

 이 문제에 대해서 나중에 9.4장에서 다뤄보겠고 지금은 이 분해를 적용해보겠습니다.

 

표 9.1 점유 격자 지도 알고리즘. 표4.2의 이진 베이즈 필터 버전

 

 분해한 덕분에, 각각의 그리드 셀에 대해 점유 확률 근사는 이제 정적 상태에서 이진 추정 문제가 되었습니다. 이 문제를 다루는 필터를 이미 4.1.4장에서 표 4.2에서 나타낸 대응관계 알고리즘으로 다뤄봣는데, 표 9.1의 알고리즘이 이 필터를 점유격자 지도 작성에 적용한것이 됩니다. 기존의 필터에서 사용했던것처럼 점유 격자 지도 작성 알고리즘도 점유 여부를 로그오즈 표현을 사용합니다.

 

 

 이 표현법에대해 4.1.4장에서 볼수 있었는데, 확률에 대해 로그 오즈의 장점은 수치가 0이나 1 사이에만 한정되는것을 막아줍니다. 이 확률은 로그 오즈비로 다시 되돌릴 수 있습니다.

 

 표 9.1의 점유격자 지도작성 알고리즘은 모든 그리드셀 i에 대해서 루프를 돌리고, 센서 측정 $z_t$에 의해 갱신되어 집니다. 점유값은 역 센서 모델 inverse sensor model로 갱신되는데 이 알고리즘의 4번째 줄에 해당합니다. 그러나 점유 값이 변하지 않는다면 이는 6번줄과 같이 됩니다. 상수 $l_0$은 로그 오즈비로 점유 사전확률을 나타낸 것입니다.

 

 역 센서 모델 함수는 역 측정 모델 p($m_i$ | $z_t$, $x_t$)를 로그 오즈형태로 구현한 것이며

 

 

 간단한 예시는 거리계에 대한 함수로 표 9.2와 그림 9.7a, b에서 볼수 있습니다. 이 모델은 모든 셀에 측정된 $l_occ$의 점유 값 범위에 가까운 센서치를 주며, 표 9.2에서 이 영역의 폭은 파라미터 $\alpha$로 제어 됩니다. 빔의 시작 각은 $\beta$로 주어집니다.

 

표 9.2 거리계를 장착한 로봇의 단순 역 관측 모델. $\alpha$는 장애물의 두께, $\beta$는 센서빔의 폭이 됩니다. 9, 11번째 줄의 값 $l_occ$, $l_free$는 두가지 다른 경우에 측정값을 의미합니다.

 

 점유 격자 지도 작성 알고리즘은 역 모델을 우선 셀 $m_i$의 질량 중심에 대해서 빔 인덱스 k와 거리 r를 구하여 계싼하는데, 이 계산은 표 9.2의 2~5번재 줄에서 수행됩니다. 보통 로봇의 자세 $x_t$ = (x y $\theta$$)^T$로 가정해오다보니 7번쨰 줄에서는  셀이 센서 빔 측정 범위 밖이나 감지된 거리 $z_t^k$에서 $\alpha$/2보다 더 큰 경우 로그 오즈로 사전 확률을 반환한 것입니다. 9번째 줄에서 셀의 거리가 측정 거리 $z_t^k$의 +-$\alpha$/2일 경우 $l_occ$를 반환하며, 9번째 줄에서 셀의 거리가 $\alpha$/2보다 더 짧은 경우 $l_free$를 반환하게 됩니다. 그림 9.7의 좌측과 중앙은 시작각이 15도일때 소나빔 계산을 보여주고 있습니다.

 

그림 9.2 두 다른 측정 거리에 대한 역 측정 모델 예시. 그리드 셀의 검은 부분이 점유된 경우가 됩니다.

 

그림 9.3 (a) 점유 격자 지도 (b) 박람회장 구조 설계도. 설계도가 특정 장소에서 부정확한것을 알수 있습니다.

 

 그림 9.3은 박람회장에 대한 지도와 설계도를 보여주고 있으며 로봇이 점유격자지도를 어떻게 얻었는지 볼 수 있습니다. 이 지도는 몇 분동안 레이저 거리 데이터로 생성되었으며 점유 격자 지도의 회색 래밸은 격자에 대한 점유 사후 확률을 알려주고 있습니다. 그리드 셀이 더 어두울수록 점유되어있을 가능성이 더 큰게 됩니다.

 

 점유 격자 지도는 본질적으로 확률이 사용되면서 이들은 두가지 양끝(1, 0) 사후확률에 가깝게 근사화 되는 경향이 있습니다. 작성되 지도와 설계도를 비교해보면 점유 격자 지도는 모든 구적 요소들을 보여주고 있고, 레이저와 같은 높이에 존재하는 장애물들을 확인할 수 있습니다. 자세히 살펴보면 설계도와 실제 환경사이에는 다른점들을 찾을수가 있습니다.

 

그림 9.4 (a) 보정된 자세 정보와 처리되지 않은 레이저 거리 데이터. 각 점들은 감지된 장애물들에 해당합니다. 대부분의 장애물들은 정적(벽이나 기타 등등)이며, 하지만 일부 사람들이 로봇 주위에서 걸어다녔었습니다. 

(b) 이 데이터로 생성한 점유격자 지도로 회색 영역은 사후확률을 말해주고 있습니다. 검은 곳이 높은 확률로 점유된 곳이며 흰곳은 높은 확률로 텅빈 공간입니다. 배경의 회색은 사전확률을 나타냅니다. 그림 (a)스테픈 구트만이 만들었습니다.

 

 그림 9.4는 처리되지 않은 데이터셋과 이를 이용해 작성한 점유 격자 지도를 비교하고 있습니다 .(a)의 데이터는 SLAM알고리즘으로 전처리되어 자세들은 정렬되어 있고, 일부 데이터들이 사람이 존재하여 훼손되어 있습니다. 하지만 점유 격자 지도에서는 사람을 필터링하였습니다. 이는 점유 격자 지도가 스캔 끝점 데이터 집합보다 로봇의 주행에 더 적합하다는것을 보여주고 있습니다. 로 센서데이터를 가진 경우에 경로 계획기는 이런 장애물들 때문에 경로를 찾는데 시간이 오래 걸릴수도 있습니다.

 

 센서 측정을 이용하여 베타직은 점유를 결정하는 알고리즘들을 살펴보았씁니다. 대안으로 사용할 정보로 로봇의 자세가 있으며, 표 9.2의 역 측정 알고리즘을 이러한 정보들을 반영하도록 쉽게 변경할수 있습니다. 로봇이 $x_t$에 존재할 때 점유된 모든 그리드 셀에대해 부정적인 값을 반환하는 식으루요. 현실적으로 지도를 생성할때 로봇의 값들을 반영하는것은  특히 지도 작성을 수행하는중에 복잡한 환경에서 좋은 방법이 될수 있습니다.

 

9.2.1 다중 센서 퓨전 multi sensor fusion

 로봇은 여러개의 센서를 장비하는 경우도있는데, 이 목적은 단일한 지도에 여러개의 센서 정보를 합치는 것입니다. 어떻게 하면 여러개의 센서로부터 얻은 데이터를 가장 좋게 합칠지에 대한 질문은 센서들이 다른 특성을 가지고 있는 경우에는 매우 흥미로울 수 있습니다.

 

그림 9.5 스테레오 비전을 이용한 점유 격자 지도 추정.

(a) 카메라 이미지

(b) sparse disparity map

(c) 디스패리티 영상을 2차원 평면에다가 사영시키고, 가우시안을 컨볼루션하여 얻은 점유격자 지도

 예를들어 그림 9.5는 스테레오 비전을 이용한 점유격자 지도를 보여주고 있는데, 차이들이 평면상에 사영되고 가우시안과 컨볼루션이 수행되었습니다. 스테레오 비전의 특성은 명확하게 소나 기반 거르계와 다른데, 다른 타임의 장애물에 따라 민갑합니다.

 베이즈 필터를 사용하여 여러 센서로부터 데이터를 퓨전하기 위해서 2가지 기본 접근방법이 있습니다. 이때 표 9.1의 점유 격자 지도 알고리즘을 다른 센서 모델에 맞게 사용하거나 역 센서 모델을 대신 사용할수도 있습니다. 하지만 이런 방법은 명확한 결점을 가지고 있는데, 서로다른 센서가 다른 타입의 장애물들을 감지하면  베이지안 필터의 결과가 다르게 정의될수 있습니다.

 

 예를들자면 센서 A에서 감지할수 있는 장애물이 있으나 센서 B에서는 감지하지 못하는 경우가 있습니다. 이 두 센서는 서로 상충되는 정보를 만드는데 결과 지도는 각각의 센서 시스템으로부터 얻은 정거의 양에 의존하므로 셀은 더 자주 감지된 센서의 값에 따라 점유 여부를 판단하므로 이는 잘못될수 있습니다.

 

 두번째 이유로는 다중 센서로부터 정보를 통합하기위해 더 이반적인 방법은 각가의 센서 타입에 따라 지도를 나누어 생성하고 이들을 가장 보수적인 추정치로 합치는것인데, 지도 $m^k$ = {$m_i^k$는 k번째 센서로 만든 지도를 의미합니다. 그래서 합쳐진 지도는 다음과 같이 나타낼 수 있겠습니다.

 

 이 지도는 각 구성요소들이 주어질때 가장 비관적인 지도가 되는데, 어느 센서의 지도가 그리드 실에 점유되었다고 하면 지도 상에서도 그럴겁니다. 이 혼합 추정기는 점유 지도의 요소에 편향적인 반면에, 다른 특성을 가진 센서들을 합칠때 베이즈 필터보다 적절한 방법일수도 있습니다.

 

그림 9.7 9.2장에서살펴본 표준 점유 격자 지도작성 알고리즘의 문제

(a) 이와 같은 환경에서

(b) 로봇은 지나가면서 다음과 같은 관측치를 가지게 될것입니다.

(c)