파이썬 로보틱스 - 점유 격자 지도 작성 알고리즘 복습

 가우시안 점유 격자 지도 작성예제를 다루기에 앞서

점유 격자 지도작성 알고리즘들을 다시 한번 복습해봅시다.

 

 이전에 살펴본 위치 추정 알고리즘들은 로봇의 자세를 구하는 기술들로 지도가 존재하는 상황에서만 사용가능 합니다. 하지만 대부분의 경우에는 그런 지도 정보가 없을 것이고, 건물 설계도 조차 실제 건물과는 조금씩 다를것입니다. 그래서 로봇이 실내 공간을 주행하기 위해서 지도 작성은 중요한 기술이라 할수 있겠습니다.

 

 지도 작성은 다음과 같은 이유들로 매우 중요한 문제라고 할수 있겠습니다.

 

지도 작성의 중요성

 

- 모든 가능한 가정 공간들이 매우 거대하며, 지도는 연속 공간상에서 정의되므로 무한대의 차원이 될수 있겠습니다. 그러므로 그리드 근사화를 통해 이산 추정을 통해 구하면 계산량을 크게 줄일수가 있겠습니다. 

 

- 지도 작성은 "닭이 먼저일까 계란이 먼저일까"의 문제와 동일한 것이며 동시적 위치 추정 및 지도 작성 slam이라고 부르기도 합니다. 로봇은 주행하면서 오도메트리 상에 오차가 누적이되고, 오도메트리 정보로만 어디에 존재하는지 신뢰하기는 어렵습니다. 하지만 지도가 존재할때 로봇의 자세를 추정하는 방법들을 살펴봤었고, 로봇의 위치를 알때 지도를 만든느것은 상대적으로 쉬운 문제가 됩니다. 하지만 일반적으로는 지도 정보도 없고 자세 정보도 없으니 로봇은 지도 근사화와 위치 추정 둘다 수행해야만 합니다.

 

 

 

지도 작성 문제가 어려운 이유

 

- 크기 : 로봇 센서의 측정 가능거리보다 큰 공간에서는 완전한 지도를 만들기가 더 어렵스비다.

 

- 노이즈 : 로봇 센서와 엑추에이터들은 노이즈를 가지고 있으므로, 노이즈가 클수록 지도 작성이 더 여렵습니다.

 

- 관측시 모호함 : 비슷하게 생깃 곳이 많을 수록, 이전에 찾은 장소와 다른 장소들 간에 관계를 구분하기가 더 힘들게 됩니다.

 

- 사이클 : 이전 장소에 돌아와서 만들어지는 사이클이 지도 작성 문제를 더 어렵게 합니다. 왜냐하면 오도메틜 정보가 다시 되돌아왔을때는 누적이 되있고, 다른 경로로 돌아아와 사이클이 닫히면서 누적된 오도메트리 오차가 커질수 있습니다

 

 

지도 작성 예시

 아래의 그림은 오도메트리 정보와 레이저 관측 정보로 만든 실내 지도 예시가 되겠습니다.

a 그림은 오도메트리 위치에따라 인덱싱 된 처리되지 않은 관측 데이터들로 단순히 겹쳐지면서 지도의 형태가 되어있지 않습니다.

b 그림은 지도 작성 알고리즘에 이 데이터를 사용하여 만든 지도를 보여주고 있습니다.

 

 일단 이번에는 로봇의 위치 정보가 주어진 상황이라고 생각해보고 지도 작성 문제를 다뤄볼것이고

이후 slam의 경우도 살펴볼 것이며, 아래의 그림처럼 가장 일반적인 지도 작성 기술을 점유격자 지도작성 이라고 합니다.

 

 

 

 

 

점유 격자 지도작성 알고리즘 개요

 점유 격자 지도작성 알고리즘은 로봇의 자세 정보를 알고 있을때 불확실한 관측 데이터만가지고

일관성 있는 지도를 만들어내는 문제를 다룹니다.

 

 점유 격자의 기본 개념은 지도를 임의의 확률 변수값을 가진 그리드 셀로 표현하고,

이 변수는 이진 값이되에 이 장소가 점유 된것인지 아닌지 판단하는 것입니다.

 

 즉, 점유 격자 지도작성 알고리즘은 이러한 점유 여부 값 변수들을 이용하여 사후확률 추정치를 근사화하는것이라고 할수 있겠습니다.

 

 

 

 

점유 격자 지도작성 알고리즘

 기본 적인 점유 격자 지도작성 알고리즘은 로봇의 경로와 관측 데이터들을 이용하여

지도에 대한 사후확률을 계산하는것이라 할수 있겠습니다.

 

 

 여기서 지도는 연속 공간을 그리드로 분할하여 나타내므로,

지도를 인덱스 i의 각 그리드 셀을 합한것이라고 할수 있겠습니다.

 

 그러면 각 그리드 셀의 값은 어떻게 될까요?

기본 점유 격자 지도작성 알고리즘에는 그리드 셀은 이진값을 가지게 됩니다.

즉, 점유되어있으면/ 장애물이 있으면 1이고, 없다면 0이 됩니다.

 

 위 기본 점유격자 지도작성알고리즘 9.1을 각 셀의 사후확률 근사에 대한 식으로 정리해보면 다음과 같으며,

전체 지도에 대한 사후확률은 각 그리드의 주변 확률들의 곱으로 근사하여 계산할수 있겠습니다.

 

  지도를 각 그리드셀에 대해 분해한 덕분에, 각 그리드 셀에 대한 점유 확률 추정은 정적 상태에서 이진 추정 문제가 되었습니다.

 이 정적 상태에서 이진 추정 문제는 이전에 4.1.4장서 살펴본적이 있었는데

 

 이 이진 베이즈 필터를 점유 격자 지도 작성에 적용한 알고리즘이 아래와 같겠습니다.

 

 

 

 점유 격자 지도 알고리즘과 로그 오즈

 위 알고리즘에서는 점유 여부를 로그 오즈를 사용해서 구하였다.

 확률을 로그 오즈로 계산시 장점은 확률 값이 0, 1사이에만 한정되는것을 방지할수 있고, 다음의 로그 오즈비로 손쉽게 확률로 되돌릴수 있다.

 

역 센서 모델 

 지금 살펴보고 있는 기본 점유 격자 지도 알고리즘은 역 센서 모델을 사용하고 있다.

역 센서 모델은 역 관측 모델의 로그 오즈 형태로 나타낸 것이다.

 

역 관측 모델

 기존의 관측 모델은 로봇의 상태가 주어질때 관측값에 대한 확률이니

역 관측 모델은 관측값이 주어질때 로봇의 상태에 대한 확률일 것이다.

 

 이 모델에서는 각 셀에다가 이진 값 l_occ와 l_cc을 저장하는데,

여기서 값이 할당되는 셀의 범위는 장애물의 두께인 alpha와 센서 빔 폭, 각도 beta가 된다.

 

 

역 관측 모델 예시

 역 관측모델에서는 로봇의 자세와 관측 값이 주어질때 지도에 반영하는 것으로

alpha 폭의 장애물과 beam 각도가 파라미터가 되어

모든 셀에대해 동작하면서 올바른 점유 이진값을 저장한다.