집밖은 위험해

10.3.3 특징 선택과 지도 관리 feature selection and map management

 EKF SLAM을 현실에서 더 강인하게 만들려면 지도를 관리하기위한 추가적인 기술들이 필요합니다. 이러한 기술들 대부분은 가우시안 노이즈 가정은 비현실적이며, 많은 이상한 관측치들이 노이즈 분포의 끝에 발생한다는 사실을 고려하는데, 이러한 이상한 관측치는 지도 생성시 잘못된 랜드마크를 발생할수 있으며 위치 추정에 부정적인 영향을 주게됩니다.

 최신 기술들은 관측 공간에서 아웃라이어들을 대처하는 방법들을 다루며, 지도상에서 랜드마크의 불확실성 범위를 넘어가는 것들을 아웃라이어로 정의합니다. 이런 아웃라이어를 다루는 가장 흔한 방법은 임시 랜드마크 목록 provisional landmark list를 유지하는것인데, 새로운 랜드마크에 관측될때 지도에 추가하는것보다 그런 새 랜드마크를 우선 임시 랜드마크 목록에 추가시키는 것입니다. 이 목록은 지도처럼 다루나 목록에 존재하는 랜드마크들은 로봇의 자세에 적용시키지는 않습니다. 이 랜드마크가 일관되게 관측이 되고 불확실성 타원이 줄어들게 되면 이 랜드매크는 정규 지도에 이동하게 됩니다.

 현실에서 구현하기위해서 이 방법은 중요한 요소로서 지도에 존재하는 랜드마크의 개수를 중요하는 경향이 있는데 반면에 지도에 존재하는 랜드마크들은 매우 높은 확률을 가지게 됩니다. 더 나아가 최신 구현 방법들에서는 랜드마크 존재의 사후확률 우도를 보유하는데, 이러한 확률은 지도 상의 j번째 랜드마크의 로그 오즈비 $o_j로 표기하여 구현합니다.  j번째 랜드마크 $m_j$가 관측될때마다 고정 값은 증가하게 되고 로봇의 인지 거리 안에서 $m_j$가 관측되지 않으면 $o_j$는 감소하게 됩니다. 랜드크가 로봇의 인지 거리에 있는것으로 존재여부를 확실히 알수 없기 때문에, 그러한 사건에 대한 확률을 감소시킵니다. $o_j$가 임계치 보다 떨어지면 지도에서 랜드마크는 삭제 됩니다. 이러한 기술들은 비 가우시안 관측 노이즈에서 더 효과적이게 됩니다.

 이전에도 살펴봤지만 데이터 연관에서 최대 우도 방법은 명확한 한계를 가지고 있습니다. 이 한계는 최대 우도 방법이 확률적 로봇 공학에서 완전 사후확률 근사의 아이디어에서 얻었기 때문에 발생하는것인데, 혼합 상태와 데이터 연관들 사이 결합 사후확률을 사용하는 대신, 데이터 연관 문제를 결정론적인 결정으로 줄여 최대 우도 연관이 항상 올바른것인것 처럼 다루어지게 됩니다. 이러한 한계로 EKF는 잘못된 결과를 구하는 랜드마크 실패에 취약하며, 연구자들은 이 문제를 완화하기 위해서 다음 두 방법중 하나를 사용하기도 합니다.

- 희소 배치 spatial arrange

 랜드마크들이 서로 더 떨어질수록 이들을 잘못 결정할 경우는 줄어들게 됩니다. 그래서 충분히 멀리 떨어진 랜드마크를 선택하는것이 유용합니다. 이는 흥미로운 트레이드 오프를 보여주는데 랜드마크의 수가 증가할수록 햇갈리는 위험도 증가하게 됩니다. 랜드마크가 너무 적은 경우에는 로봇의 위치 추정을 어렵게 하여 이 역시도 랜드마크를 잘못 구할 확률이 커지게 됩니다. 랜드마크의 최적 밀도에 대해 아직 알려진것은 없어 연구자들은 직관적으로 특정 랜드마크를 선택해서 사용하기도 합니다.

- 시그니처 signature

적절한 랜드마크 선택시에 랜드마크의 구별성을 최대화 하는것이 필수적입니다. 예를들자면 다른 색을 가진 문들이 있거나, 복도가 다른 폭을 가지고 있는 경우 이러한 시그니처는 성공적인 SLAM에선 필수적입니다.

 추가적으로 보면 EKF SLAM 알고리즘은 하늘을 날거나 깊은 바다속, 버려진 광산 등을 다니는 로봇들을 포함하는 현실의 많은 범위에서 성공적으로 사용되고 있습니다. 

 EKF SLAM의 한계는 적적한 랜드마크 선택이 필수적인것이며, 이렇게 하여 대부분의 센서 정보들은 버려지게 됩니다. 더 나아가 EKF의 2차적인 갱신시간은 1,000개 특징 이하인 경우의 희소한 지도에서만 사용할수있도록 제한됩니다. 현실적으로 특징이 $10^6$개나 그 이상인 경우에는 EKF를 사용할수 없게 됩니다.

 상대적으로 저차원의 지도에서는 데이터 연관을 만들기가 어렵습니다. 이는 쉽게 확인할수 있는데, 눈을 뜨고 방안을 한번보세요 거기 아무것도 없다면 어디있는지 알기 어려울겁니다. 랜드마크가 적은 경우에도 어디있다고 판단하기 또한 어려울것입니다. EKF SLAM에서 데이터 연관은 차후에 다룰 SLAM 알고리즘보다 어렵다고 할수 있습니다. 이는 EKF SLAM 알고리즘의 원칙적인 딜레마로 빠지게 만듭니다. 최대 우도 데이터 연관이 수백만개의 특징으로 이루어진 밀집된 지도에서 잘 동작하더라도 희소한 지도에서는 불안정하게 됩니다. 하지만 EKF는 이차적인 복접도로 인해 희소 지도를 요구하고 있습니다. 차후에는 더 큰 지도를 효율적으로 다루는 SLAM 알고리즘에 대해 살펴보겠습니다. 여기서 강인한 데이터 연관 기술들을 더 다뤄볼것이고, EKF SLAM 알고리즘의 한계들을 더 역사적으로 보겠습니다.

10.4 정리

 이번장에서는 일반적인 SLAM 알고리즘의 문제와 EKF 방법에 대해 소개하였습니다.

- SLAM 문제는 동시적 위치 추정 및 지도 작성 문제로 정의되며 로봇은 주위 환경에 대한 지도를 얻고 이 지도에 대한 상대적인 자신의 위치를 추정치를 찾게 됩니다.

- SLAM 문제는 두가지 버전으로 다룰수 있는데 온라인과 전역이 있습니다. 두 문제다 지도 근사를 다루는데, 온라인 슬램에서는 순간적인 로봇의 자세를 추정한다면, 전역 문제에서는 모든 자세들을 찾게 됩니다. 두 방법다 현실적으로 중요합니다.

- EKF SLAM 알고리즘은 앞선 SLAM 알고리즘으로 확장 칼만 필터를 온라인 슬램 문제에 적용한것이 됩니다. 대응 관계가 주어진 경우 알고리즘의 결과는 증가하게 되는데, 지도상에 존재하는 랜드마크의 수에 따라서 갱신시 이차적인 시간을 요구하고 있습니다.

- 대응관계를 모르는경우 EKF SLAM알고리즘은 증가 최대 우도 근사기로 대응관계 문제를 다루었습니다. 이 알고리즘의 결과는 랜드마크가 충분히 떨어져 있을때 잘 동작하였습니다.

- 지도 관리르 위해 추가적으로 살펴본 기술들이 있는데, 아웃라이어를 식별하기 위한 두가지 흔한 방법으로 아직 충분히 자주 관측되지 않은 랜드마크들을 담는 임시 랜드마크 리스트와 랟느마크의 존재에 대한 사후확률을 계산하는 랜드마크 존재 카운트가 있습니다.

- EKF SLAM은 수많은 로봇공학 지도 작성 문제에서 사용되어 왔지만, 이 알고리즘으 ㅣ결점은 충분한 수의 구분되는 랜드마크가 필요하며 갱신시 복잡한 계산 복잡도가 필요한 점입니다.

 현실에서 EKF SLAM은 일부의 경우 성공적으로 사용되어 왔습니다. 랜드마크가 충분히 구분되면 이 방법은 사후확률을 잘 근사시켰습니다. 완전 사후확률 계산의 이점은 많은데, 이 알고리즘은 존재하는 모든 불확실성을다루고 로봇이 이 불확실성을 제어시에 고려할수 있도록 도와줍니다.

 하지만 EKF SLAM 알고리즘은 수많은 갱신 복잡도와 희소 지도에 의한 한계의 문제를 가지고 있으며, 이는 데이터 연관 문제를 어렵게 만들며,  수많은 랜드마크가 애매한 환경에서 좋지 않은 성능을 보이게 됩니다. 이는 EKF SLAM 알고리즘이  증가 최대 우도 데이터 연관 기술에 의존하기 때문에 이러한 취약성이 존재하게 됩니다. 이 기술은 데이터 연관을 개선시킬수 없게 만들어 ML 데이터 연관이 잘못된 경우 위치 추정이 실패하게 됩니다.

 EKF SLAM 알고리즘은 온라인 슬램에 적용한 것으로 완전 슬램 문제라고 볼수는 없습니다. 완전 슬램문제는 새로운 자세가 매 시간마다 상태 백터에 추가되어 상태 백터와 공분산이 한계없이 증가하게 만들어 버립니다. 이 공분산을 갱신하는것은 그래서 수없이 증가하는 시간을 필요로 하며, 프로세서가 얼마나 빠르던지간에 많은 계산시간을 필요로 하게 됩니다.

10.3 대응관계가 주어지지않을때 EKF SLAM

10.3.1 EKF SLAM 기본 알고리즘

 대응 관계가 주어진 EKF SLAM을 더 일반적인 EKF SLAM 알고리즘으로 대응 관계를 구하는 최대 우도 maximum likelihood ML 근사기를 사용하여 확상시켜보겠습니다. 표 10.2는 이 알고리즘을 보여주고 있는데, 이제 여기에는 대응관계 변수 $c_t$가 빠지게 됩니다. 대신 지도의 순간적인 크기인 $N_{t-1}$가 들어가게 됩니다.

표 10.2는 아웃라이어 제거가 가능한 ML 대응관계 근사기를 가진 EKF SLAM 알고리즘

 표 10.1의 대응관계가 주어진 경우 EKF SLAM과 마찬가지로 3~6번째 줄에서 동작 갱신은 동일합니다. 하지만 관측 갱신 루프가 다른데, 8번째 줄부터 보면 우선 새 랜드마크의 인덱스 $N_{t}$ + 1를 생성시킵니다. 이 인덱스는 기존의 지도 랜드마크의 개수 보다 하나가 더 큰것으로 새 랜드마크의 위치는 9번째 줄에서 로봇의 근사 자세와 측정으로 얻은 거리와 방위각을 계산한 기대치로 초기화 시킵니다. 9번째 줄에서는 새 랜드마크에 관측된 시그니처 값도 주게 됩니다.

 다음으로 10~19번째 줄 사이에는 새로운 랜드마크를 포함해서 모든 가능한 랜드마크에 대해 갱신 값들이 계산되는데, 19번째 줄에서는 새 랜드마크 생성시의 임계치를 설정합니다. 새 랜드마크는 지도 상에 존재하는 모든 랜드마크의 마할라노비스 거리가 임계치값 $\alpha$를 초과하면 생성이 됩니다.

 ML 대응관계는 20번째 줄에서 선택이 되는데, 관측치가 이전에 본적이 없는 랜드마크로 판단된다면 21번째 줄에서 랜드마크 카운터는 증가하게 되고, 벡터와 행렬은 증가한 수에 따라 커지게 됩니다. EKF의 갱신은 24, 25번째 줄에서 수행되는데, EKF SLAM 알고리즘은 새로운 랜드마크들 $N_t$의 평균 $\mu_t$, 공분산 $\Sigma_t$를 반환하게 됩니다.

 EKF SLAM의 정리는 이전 정리를 참고하면 되는데 9번째 줄에서 초기화는 대응 관계가 주어진 경우의 10번째 줄과 동일하며, 10 ~ 18번째 줄은 대응관계가 주어진 경우의 12 ~ 17번째 줄과 비슷하나 ML 대응관계를 계산하기 위해서 변수 $\pi_{k}$가 추가되었습니다. 가장 가능성 있는 랜드마크를 찾는데는 7.3장에서 살펴본 EKF 위치 추정기의 것을 사용하였습니다.  표 10.2의 24~,25번째 줄의 관측 갱신은 대응 관계가 주어진 경우와 동일하며 지도가 커지는 경우에도 적절한 형태의 백터와 행렬이 사용됩니다.

 EKF SLAM 구현시에는 10~18번째 줄사이에서 로봇 주위의 랜드마크로 제한시키면 더 효율적으로 만들수가 있습니다. 더 나아가 이 내부루프에서 계산된 값들과 행렬은 하나의 특징 벡터 $z_{t}^{i}$보다 여러개를 다룰때 더 빨리 계산될수 있으며, 지도 상에 특징들을 잘 관리하고 이러한 루프 최적화로 동작시간을 크게 줄일수 있습니다.

그림 10.2 대응관계가 주어진 경우 EKF SLAM. 

- 지도는 왼쪽의 것으로 각 랜드마크의 불확실성 정도에 따라 회색 레벨로 보여주고있습니다.

- 오른쪽의 행렬은 상관관계 행렬로 사후 확률 근사치의 정규화된 공분산 행렬이 됩니다.

- 일정 시간이 지난후 모든 x-y 좌표 근사치들은 완전 상관관계를 갖게 됩니다.

10.3.2 예제

 그림 10.2는 대응관계가 알려진 경우 EKF SLAM 알고리즘의 시뮬레이션을 보여주고 있습니다. 왼쪽의 3그림은 로봇의 자세와 각 랜드마크 주변의 사후확률 분포를 보여주고 있으머ㅕ, 우측의 그림들은 혼합 상태 백터 $y_t$의 상관관계 행렬을 보여주고 있으며, 이 상관관계는 정규화된 공분산이 됩니다. 그림 10.c에서는 결과를 볼수 있는데, 시간에 대해 x, y 좌표 근사치들이 완전 상관관계가 됨을 볼수 있습니다. 이 의미는 지도가 상관 관계에 대해서 다 구해진 것으로 더이상 불확실한 전역 자세를 구할수 없습니다. 이는 SLAM 문제의 중요한 특성을 강조하고 있는데, 로봇의 초기 자세로 정의되는 지도의 절대 좌표계는 근사를 통해서 결정되며, 상대 좌표계들은 점근적으로 결정됩니다.

 현실 상에서 EKF SLAM은 비행이나 잠수, 실내, 그리고 다른 기체들을 사용한 다ㅇ야한 범위의 주행 문제에 적용을할수 있는데, 그림 10.3은 오스트레일리아의 시드니 대학교에서 개발한 잠수함 로봇 오베론(그림 10.4)를 사용하여 얻은 결과를 보여주고 있습니다.

그림 10.3 칼만 필터를 이용한 지도와 기체 자세의 근사 예시.

그림 10.4 시드니 대학에서 개발한 잠수학 로봇 오베론

 이 잠수함은 펜실 소나가 장착되어 50m까지 장애물을 고해상도로 스캔할수 있습니다. 지도작성 문제를 다루기 위해 연구자들은 소나 스캔으로 특징을 추출해낼만한 길고 작은 수직 물체를 물 안에다가 넣었는데, 이 실험에서 이런 물체의 길이는 10m정도 차지하고 있습니다. 게다가 멀리 떨어진 절벽이 펜실 소나로 감지할수있는 점특징을 제공하고 있습니다.

 이 실험은 그림 10.3에서 보여주고 있으며 로봇은 이런 랜드마크까지 움직였다가 되돌아 오는 모습을 보여주고 있습니다. 이렇게 하는동안 이번에 살펴본 칼만 필터 방법들을 이용하여 랜드마크가 감지되고 지도상에 추가되었습니다.

 그림 10.3의 지도는 로봇의 경로를 선에 연결된 삼각형으로 표시해두었는데, 각 삼각형 주위에는 로봇의 x y 자세가 사영되는 칼만 필터 추정의 공분산 행렬을 나타내고 있습니다. 이 타원은 분산을 보여주며 이게 커질수록 연재 로봇의 자세가 덜 확실해지게 됩니다. 그림 10.3에는 많은 작은 점들이 나타나는대 이는 소나 스캔으로 감지한 매우 작고 반사하는 물체들입니다. 이들 대다수는 다음 장에서 살펴볼 기술을 사용하여 제거되었습니다. 하지만 이들의 일부는 랜드마크로 판단하여 지도상에 추가시켰습니다. 동작의 끝으로 로봇은 14개의 물체를 랜드마크로 분류하였으며 각각의 불확실성 타원을 그림 10.3에서 볼수 있습니다. 이 랜드마크들은 연구자들이 넣은 인공적인 랜드마크도 있지만 로봇 부근의 환경적인 특징들도 포함되고 있습니다. 이 예제에서 로봇은 노이즈가 크기는하지만 성공적으로 인공적인 랜드마크를 찾아내고 지도를 작성하였습니다. 

10.2 확장 칼만필터를 이용한 SLAM. SLAM with Extended Kalman Filter

10.2.1 설정과 가정들

 역사적으로 일직이 가장 영향력있는 SLAM알고리즘들은 확장 칼만필터 EKF를 기반하고 있습니다. 분명히 예기하자면 EKF SLAM 알고리즘은 EKF를 최대 우도 데이터 연관을 사용한 online SLAM에 적용한 것으로, 이렇게 하여 EKF SLAM은 많은 근사의 영향을 받으며 다음의 가정들로 제약되고 있습니다.

- 특징 기반 지도 feature based map

 EKF에서 지도는 랜드마크 점들로 이루어져있습니다. 계산상의 이유로 점 랜드마크의 수는 일반적으로 적습니다(1,000개 이하). 더 나아가 EKF 방법들은 애매한 랜드마크의 수가 적을수록 잘 동작하는 경향이 있습니다. 이러한 이유로 EKF SLAM은 특징 검출기가 중요하며, 인공적인 비콘이나 랜드마크를 특징으로 사용하기도 합니다.

- 가우시안 노이즈

 어느 EKF 알고리즘이던, EKF SLAM은 로봇의 동작과 인지시에 가우시안 노이즈 가정을 따르고 있습니다. 사후확률에서 불확실성의 크기는 상대적으로 작아야만 합니다. 사후확률에 있어서 불확실성의 크기는 EKF의 선형화시에 수용할수 없는 에러가 발생할수 있기 때문에 반드시 작아야만 합니다.

- 긍정 측정 positive measurement

 EKF 알고리즘은 7.5장에서 살펴본 EKF 위치추정기 처럼 랜드마크의 양의 정보만 처리할수 있습니다. 여기서는 센서 측정시 랜드마크의 부재로 발생하는 부정 정보를 처리할수 없는데, 이것은 가우시안 신뢰도 표현법의 결과로 7.5장에서 살펴보았습니다.

10.2.2 대응관계가 알려진 SLAM - slam with known correspondences

 대응 관계가 알려진 경우의 SLAM 에서는 SLAM에서 계속 다뤄지는 문제이기도 합니다. 이 알고리즘을 개발하려면 7.5장에서 본 EKF 위치 추정알고리즘을 이용하면 되는데, 약간의 차이는 자세 $x_t$를 근사시키는것에 더해서 EKF SLAM 알고리즘은 경로중에 만나는 모든 랜드마크의 좌표도 추정하게 됩니다. 이는 상태 벡터에 랜드마크의 좌표들을 포함해야만 하도록 만들게 합니다.

표 10.1 동시적 위치 추정 및 지도작성 문제에서의 확장 칼만 필터(EKF)

- 여기서는 특징 기반의 지도와 거리와 방위를 측정하는 센서가 로봇에 장착되어 있습니다. 이 경우는 대응관계에 대해 알고있는 경우를 가정하고 있습니다.

 쉽게 볼수 있도록 상태 백터은 로봇의 자세와 지도로 이루어졌으므로 혼합 상태 백터 combined state vector라 하고, 이 벡터를 $y_t$로 표기하겠습니다. 그러면 혼합 벡터는 다음과 같습니다.

 여기서 x, y, $\theta$는 시간 t에서 로봇의 좌표이고 $m_{i, x}$, $m_{i, y}$는 i번째 랜드마크의 좌표가 되며, $s_i$는 그 랜드마크의 시그니처입니다. 이 상태 백터의 차원은 3N+3이 되는데 여기서 N은 지도상에 존재하는 랜드마크의 수를 나타냅니다. 이 벡터는 7.5장에서 다루었던 자세 벡터보다 상당히 크며 EKF SLAM은 온라인 사후확률을 다음과 같이 계산합니다.

 EKF SLAM 알고리즘에 대해서 표 10.1에서 볼수 잇는데 표 7.2에서 본 EKF위치 추정알고리즘과 비슷합니다. 2~5번째 줄에서 동작 갱신이 이루어지고, 6~20번째 줄에서는 관측 백터가 합쳐지고 있습니다. 특히 3~5번째줄에서 동작 모델을 따르는 신뢰도의 평균과 공분산이 구해지는데, 여기서의 계산에서는 신뢰도 분포에서 로봇의 자세와 관련된 요소들만 변하게 됩니다. 지도와 관련된 나머지 모든 평균과 공분산 변수들은 변하지 않고, 자세-지도 공분산도 그렇습니다. 7~18번째 줄은 전체 측정치에 대해서 반복을 수행하게 되는데, 9번째 줄에서는 아직 초기 위치 근사가 되지않은 랜드마크에 대해서만 옳은 값을 반환합니다. 10번째 줄에서는 측정된 거리와 방위를 사영하여 랜드마크의 위치로 초기화 시킵니다. 아래에서 다뤄보겟지만 이 과정은 EKF의 선형화에 있어서 매우 중요합니다. 각각의 측정치에 대해 기대 측정치는 14번째 줄에서 계산되고, 대응하는 칼만 게인은 17번째 줄에서 계산됩니다. 칼만 게인은 크기가 3인 행렬인데, 이 행렬은 비 희소 non-spare이며, 전체 상태 추정치에 대해 이 값이 반영됩니다. 필터의 마지막 갱신은 19, 20번째 줄에서 수행되는데 로봇의 신뢰도에서 변화 innvation이 발생하게 됩니다.

 칼만 게인은 관측된 랜드마크와 로봇의 자세 뿐만이 아니라 모든 상태 변수에 완전히 영향을 주므로 매우 중요합니다. SLAM에서 랜드마크를 관찰하는 것은 이 랜드마크의 위치 근사를 개선할 뿐만이 아니라 다른 랜드마크도 개선시키게 됩니다. 이 효과는 로봇의 자세에 의해 이뤄지는데, 랜드마크를 관찰하여 로봇의 자세 근사치가 개선되고, 그 결과 로봇이 이전에 보았었던 랜드마크들의 불확실성이 줄어들게 됩니다.  이전에 없었던 이 놀라운 효과는 과거의 자세도 명확하게 나타내느데 이는 완전 슬램 full slam이 이뤄지게 하고 ekf를 비실시간 알고리즘으로 만들었습니다. 이 대응 관계는 가우시안 사후확률이 아니라 행렬 $\Sigma_t$의 비대각 공분산요소들로 찾을수 있습니다.

그림 10.1 EKF를 온라인 슬램에 적용한 결과.

- 로봇의 경로는 점선, 자세 근사치는 회색 타원

- 위치는 모르는 8개의 구분 가능한 랜드마크들은 작은 점으로 되어있고, 이 랜드마크들의 자세 추정은 흰색 타원으로 되어있습니다.

- (a)-(c)에서 랜드마크들을 만날때마다 로봇의 자세 불확실성이 증가하고 있습니다.

- (d)에서 로봇이 첫번째 랜드마크를 다시 만나면서 모든 랜드마크와 자세의 불확실성이 줄어듭니다.

 그림 10.1은 EKF SLAM알고리즘을 시뮬레이션 예제에 사용한 경우를 보여주고 있습니다. 로봇은 시작점을 좌표계의 원점으로 삼아서 주행을 시작하게 되는데, 로봇이 움직이는 동안 자세 불확실성은 증가하게 되며 이 불확실성 타원의 지름이 증가하는것으로 보여주고 있습니다. 로봇은 근처에 존재하는 랜드마크를 감지하고 이들을 불확실성을 가진것으로 지도 작성을 수행하는데 고정된 관측 불확실성에 증가중인 자세 불확실성이 합쳐지게 됩니다. 그 결과 랜드마크 위치 불확실성은 시간이 흠름에 따라 증가하게 됩니다. 흥미로운 변화는 그림 10.1d에서 일어나는데 지도 작성 시작때 보았던 랜드마크 즉, 상대적으로 잘 알고있는 장소를 관측할때를 보여주고 있습니다. 이 관측을 통해 로봇의 자세 오차가 줄어들어 최종 로봇의 자세를 나타내는 타원이 매우 작아진것을 알수 있습니다. 더 나아가 이 관측은 지도상에 존재하는 다른 랜드마크들의 불확실성도 줄여줍니다. 이 현상은 가우시안 사후확률의 공분산 행렬상의 상관 관계에서 일어나게 되는데, 랜드마크 대부분의 불확실성은 로봇의 자세에 의해 발생하게 되는데 이 불확실성은 시간에 따라 가면서 랜드마크의 위치 근사치는 상관관계를 가지게 됩니다. 로봇의 자세에 대한 정보를 얻을때 이 정보는 이전의 관측 된 랜드마크에 퍼지게 되고, 이 효과는 SLAM 사후 확률의 가장 중요한 특성이라 할수 있습니다. 여기서 정보는 로봇의 위치 추정을 돕고, 지도 전반에 퍼지게 되며, 결과적으로 지도 상에 존재하는 다른 랜드마크의 위치추정도 개선하게 됩니다.

10. 동시적 위치 추정 및 지도작성 SLAM Simultaneous Localization And Mapping

10.1 소개

 이제부터 로봇 공학에서 주요 문제중 하나인 동시적 위치 추정 및 지도작성에 대해서 살펴보겠습니다. 이 문제를 SLAM이라고 하며 Concurrent Mapping and Localization CML이라고 부르기도 합니다. SLAM은 로봇이 지도 정보를 가지고 있지 않을때를 다루며, 자신의 위치또한 모르는 상태입니다. 여기에는 SLAM에서는 주어지는건 측정 $z_{1:t}$와 제어 $u_{1:t}$ 뿐입니다. 동시적 위치 추정 및 지도 작성이란 단어는 이 문제를 통해 얻는 결과물로 SLAM에서는 로봇은 주변에 대한 지도를 만들고 동시에 이 지도에서 상대적인 자신의 위치를 추정하게 됩니다. SLAM은 이전에 다루었던 모든 로봇 공학 문제들보다 상당히 어렵습니다. 자세를 모르기 때문에 맵핑 하는 중간에 추정을 해야되므로 자세가 주어질때 지도를 작성하는 경우 보다 어렵습니다.

 확률적인 관점에서 SLAM 문제를 2가지 형태로 주로 다루는데 둘다 현실적으로 동일하게 중요합니다. 하나는 online slam 문제로 지도 상에 순간적인 자세에 대한 사후확률을 추정합니다.

여기서 $x_t$는 시간 t에서의 자세, m은 지도, $z_{1:t}$, $u_{1:t}$는 관측과 제어치가 됩니다. 시간 t에서의 변수 추정치만을 다루는 문제를 온라인 슬램 문제라 부릅니다. 온라인 슬램문제를 다루는 많은 알고리즘들이 만들어 지고 있으며, 이들은 과거의 측정치와 제어입력을 처리후에 버리게 됩니다.

 두번째 슬램 문제를 full slam이라고 부릅니다. 풀 슬램에서는 지도가 주어질때 현재 자세 $x_t$가 아니라, 전체 경로 $x_{1:t}$에 대한 사후확률을 계산하게 됩니다.

 온라인과 풀 슬램 사이 형태의 미세한 차이는 어디까지 다룰것인지에 대해 영향을 주게 됩니다. 특히 온라인 슬램은 풀 슬램의 전체 과거 자세를 적분한 결과로

 온라인 슬램은 그때 그때 이러한 적분과정이 수행되고 슬램의 의존 구조의 변화를 만드는데 이에 대해서 다음에 살펴보겠습니다.

 슬램의 두번째 주요 특성은 슬램은 근본적으로 추정문제라고 할수 있습니다. 슬램에서는 연속 영역과 이산 요소가 있는데, 연속 추정 문제는 지도 상에서 물체의 위치와 로봇 자신의 자세 변수들을 가지게 됩니다. 여기서 물체란 특징 기반의 제도에서 랜드마크 일수도 있고, 거리계로 감지한 물체의 일부분이 될수도 있습니다. 이산 요소는 다음의 대응관계를 가지게 된느데, 물체가 감지되면 슬램 알고리즘은 이전에 감지한 물체와 이 물체의 관계를 추론합니다. 이 이유는 이산적이기 때문에 물체가 이전에 감지한 것인지 아닌지 보게됩니다.

 이미 이전에 연속-이산 추정문제들을 다뤄봤었습니다. 7.5에서 EKF 위치추정기로 로봇의 자세를 연속 공간에서 추정하였는데, 이때 지도 상에 존재하는 이산적인 랜드마크와 관측차 사이 대응관계를 추정하였었습니다. 이번과 차후에는 슬램에서 연속과 이산 요소들을 다루는 다양한 기술들을 살펴보겠습니다.

 7장 위치추정 문제에서 했던것 처럼 대응관계 변수를 명시하는것이 편리한데, 온라인 슬램 사후확률은 다음과 같이 되고,

 풀 슬램 사후확률은 아래와 같습니다.

 온라인 슬램 사후확률은 풀슬램의 사후확률을 로봇의 모든 과거 자세들의 적분과 모든 대응관계들의 합으로 얻을수 있습니다.

 slam의 두가지 버전인 online과 full은 식 10.4나 10.5의 풀 사후확률을 근사시키며 이는 slam의 핵심이 됩니다. 이 풀 사후확률은 지도와 자세/경로에 대한 알려진 것들이라 할수 있습니다. 하지만 현실적으로 풀 사후확률을 계산하는것은 불가능하다고 할수 있는데 여기서 2가지 문제가 발생하게 됩니다. (1) 연속 파라미터 공간의 고차원성과 (2) 많은 이산 대응관계 변수 갯수. 최신 SLAM 알고리즘에서는 수만개의 특징과 그이상으로 이루어진 지도를 작성하게 되는데, 대응 관계가 알려진 경우 이 지도에 대한 사후확률은 $10^5$이나 그이상의 차원을 가진 공간에 대해 확률 분포를 다루어야 할것입니다. 이는 3차원 연속 공간에서 사후확률을 추정했던 위치 추정문제와는 상당히 다르다고 할수 있습니다. 대다수 활용에서 이런 대응관계들은 알수없으므로 모든 대응관계 변수들의 벡터에 할당해야 하는 수 $c_{1:t}$는 시간 t에 대해 지수적으로 증가하게 됩니다. 그래서 현실적인 SLAM 알고리즘은 대응관계 문제에서도 근사화를 시켜야 하게 됩니다.

 SLAM 문제에 대해서 차후에 수많은 것들을 다뤄보겠지만 이번에 주로 살펴볼 것은 온라인 슬램 문제를 다루는 EKF 알고리즘을 개발하겠습니다. 대부분의 내용들은 3.3장에서 EKF에 대해 소개를하고, 7.5장에서 EKF 알고리즘을 위치추정 문제에 적용하면서 살펴봤었씁니다. 이제 이 EKF 알고리즘을 대응관계가 알려진 SLAM 문제로 다뤄볼것이며 더 일반적인  대응관계를 모르는 경우도 살펴보겠습니다.

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

(a) 와 같은 환경이 주어진다고 할때

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

(c), (d) 분해 방법으로 센서 빔을 각각의 그리드 셀과 각 빔에 대해 확률적인 지도로 맵핑한 경우를 보여주며

(e) 에서 두 결과의 합을 보여주고 있습니다. 하지만 원으로 표시한곳에 충돌이 발생하고 있습니다.

(f) 충돌이 일어나지 않는 경우의 지도. 

9.4 점유격자 지도작성 사후확률 최대화 maximu a posterior occupancy mapping

9.4.1 의존관계를 유지사는 경우 the case for maintaining dependencies

 이번에는 점유 격자 지도 작성 알고리즘의 기본 가정중 하나를 다시 볼건데 9.2에서 지도상 모든 다차원 공간에 대해 정의되는 지도 추론 문제를 단일 셀의 모음에 대한 지도 작성 문제로 분해하였습니다. 이 가정은 9.4에서 분해하여 사용되었는데, 이렇게 강하게 분해할 경우 알고리즘의 결과는 얼마나 신뢰할수 있을까라는 질문을 하게 됩니다.

 그림 9.7은 이 분해의 결과로 생기는 문제를 보여주고 있습니다. 로봇은 벽과 만나는 두 소나 거리 측정치를 받는 상황을 보여주고 있습니다. 분해 방법으로 측정 거리에 존재하는 호 형태로 물체를 예측할 수 있기 때문에 이 호를 따라서 그리드 셀의 점유 값이 증가하게 됩니다. 그림 9.7c, d의 두 다른 측정치들을 합칠때, 그림 9.7e에서 충돌이 발생되는데, 표준 점유 격자 지도 작성 알고리즘은 이 충돌을 점유 값의 양과 음으로 합하여 이 충돌을 해결합니다. 하지만 이 결과는 신로할수 없는 두 측정치의 상대적인 프리퀀시를 반영하게 됩니다.

 하지만 그림 9.7f와 같이 이런 충돌이 발생하지 않은채 센서 측정을 보여주는 지도가 존재하는데, 이는 센서 측정을 설명할수 있기 때문에 이 장애물을 존재하거나 안할수도 있는 곳으로 가정할수 있습니다. 다르게 보면, 원뿔형태의 측정에서 여러 그리드셀을 지울수 있는 사실은 이웃한 그리드셀사이 중요한 의존관계가 있음을 의미하기도 합니다. 지도 작성을 수ㅈ천개의 개별적인 그리드 셀 추정 문제로 분해시에는 이러한 의존관계를 고려해야하는 부분을 잃게 됩니다.

9.4.2 전방향 모델을 사용한 점유 격자 지도 작성 

 이 의존관계는 전체 사후호가률 대신 사후확률의 모드를 출력으로하는 알고리즘에 합칠수 있습니다. 이 모드를 지도 사후확률 로가리즘의 최대화 라고 정의할수 있는데 식 (9.1)에서 보았습니다.

이  지도 사후확률은 지도 사전 확률과 관측 우도(식 9.11)로 나눌 수 있는데

  로그우도 log p($z_{1:t}$ |  $x_{1:t}$, m)은 개별적인 관측 로그 우도 log p($z_t$ | $x_t$, m)의 합으로 나눌수 있습니다. 더 나아가 로그 사전확률 log p(m)은 아래 형태의 합이 되며 여기서 M은 그리드 세의 수 $l_0$은 식 9.7로부터 구할수 있습니다.

M log(1 - p($m_i$))항은 지도에 독립이라, 다음의 식과 로그 우도 데이터를 최적화를 수행할수 있습니다.

표 9.3 최대 사후확률 점유격자 알고리즘으로 역 모델 대신에 기존의 관측 모델이 사용되었습니다.

 표 9.3은 이러한 로그 확률을 최대화 하는 언덕 오르기 hill climbing 알고리즘으로 2번째 줄에서) 자유 지도에서 시작합니다. 이 알고리즘은 4 ~ 6번째 줄에서 데이터의 로그 우도가 증가하면 그리드 셀의 점유 값을 뒤집습니다. 여기서는 점유 사전 확률 p($m_i$)이 1에 가까워서는 안되는데 이러면 전체가 점유된 지도로 될수 있기 때문입니다. 언덕 오르기 알고리즘으로 이 방법은 지역 최대를 찾게 되는데, 현실적으로 지역 최대치는 매우 적습니다.

그림 9.8 (a) 노이즈가 없는 시뮬레이션으로부터 초음파 거리 측정치들

(b) 문이 열린 곳에서 표준 점유 지도작성기의 결과

(c) 최대 사후확률 지도

(d) 개별적인 그리드셀에 대해 지도 우도 함수의 민감도를 측정하면서 구한 지도상에 존재하는 불확실성들

 그림 9.8은 MAP 점유 격자 알고리즘의 결과를 보여주고 있습니다. 그림 9.8a는 로봇이 문 열린 곳을 지나가면서 수집한 노이즈 프리 데이터집합을 보여주고 있습니다. 그림 9.8b에선 초음파 측정치의 일부가 문열림을 감지하는 반면에 일부는 문의 뒷면에서 반사되고 있습니다. 역모델을 사용한 표준 점유격자 지도작성 알고리즘은 문 열림을 획득하는대 실패했으며, 그림 9.8c에서 사후확률의 모드를 보여주고 있는데 이 모델은 문열림을 올바르게 찾았으며 표준 점유 격자 지도작성 알고리즘보다 더 적합한것을 알수 있습니다. 그림 9.8은 지도의 불확실성을 보여주고 있는데, 이 그림은 셀 단위 민감도 분석의 결과로 그리드 셀의 뒤집힘이 로그 우도를 감소시킴으로서 이 크기는 셀의 회색공간형태로 나오게 됩니다. 이 그림은 장애물뒤 그리드셀에 대해 최대 불확실성을 가지는 일반적인 점유 격자 지도와 비슷한데 여기서는 그림 9.8a와 같은 수직선이 존재하지 않습니다.

 MAP 점유 격자 지도 작성 알고리즘은 수많은 제한들을 가지고 있으며 다양한 방법으로 개선될 수 있씁니다. 이 알고리즘은 최대 사후확률을 구하는 방법으로 남은 지도에 대한 불확실성을 반환하지 않습니다. 민감도 분석으로 이 불확실성을 근사시켰으나 이 근사치는 지역적인 모드만을 분석하기 때문에 과신된 것입니다. 더 나아가 이 알고리즘은 배치 알고리즘으로 증가적으로 수행될수가 없습니다. MAP 알고리즘은 모든 데이터를 메모리 상에 저장해야 하여 아무것도 없는 지도를 사용하는 대신에 기존의 점유 격자 지도 작성 알고리즘의 결과로 초기화 함으로서 계산상의 문제를 개선할 수 있습니다. 마지막으로 표 9.3의 5번째줄에서 그리드 셀 뒤집기에 의해 소수의 측정치가 영향을 받게 되는데, 각각의 합은 클지 몰라도 소수의 요소들은 최대치를 계산할때 확인됩니다. 

9.5 정리

 이번에는 점유 격자를 학습하는 알고리즘들을 살펴보았습니다. 여기서 다룬 모든 알고리즘들을 로봇의 위치 정보가 필요하여, 일반적인 지도 작성 문제를 해결할수는 없습니다.

- 표준 점유 지도 작성 알고리즘은 각 그리드 셀의 개별적인 점유 확률을 추정합니다. 이는 정적 환경에서의 2진 베이즈 필터 적응이라고 할수 있습니다.

- 다중 센서로부터 얻은 데이터는 단일 지도에서 2가지 방법으로 합칠수 있는데, 베이즈 필터를 이용하여 단일 맵을 유지시키거나 여러 지도를 각각의 센서 모델에 대해 유지시키고, 주행 결정시에 가장 신뢰성있는 점유값을 추출시키는 것입니다. 후자의 방법은 서로 다른 센서들이 다른 장애물타입에 따라 민감할때 선호되는 방법이기도 합니다.

- 표준 점유 격자 지도 작성 알고리즘은 역 측정 모델에 의존하는데 영항(관측)으로부터 원인(점유여부)를 구하기 때문입니다. 이는 이전에 살펴본 위치 추정에 있어서 베이즈 필터의 응용과는 다른데, 여기서 베이즈 필터는 원인으로부터 영향을 다루는 기존의 관측 모델을 기반으로 합니다.

- 기존의 관측 모델로 역 센서모델을 학습시키는것도 가능합니다. 이렇게 하기위해서 샘플들을 생성해야만하며, 함수근사기를 통해 역 모델을 학습하게 됩니다.

- 표준 점유 격자 지도작성 알고리즘은 각 점유 근사치에 대해 의존관계를 유지시키지 않는데 이는 지도의 사후확률 근사 문제를 수 많은 단일 셀 사후확률 근사 문제로 분해한 결과입니다.

- 전체 지도 사후확률은 일반적으로 그리드로 정의할수 있는 지도의 크기 때문에 계산할 수가 없습니다. 하지만 이는 최대화 될수 있는데, 사후확률 최대화는 지도가 항상 데이터에 대해 일관성을 갖도록 만들어 줍니다. 하지만 최대화를 위해서는 가능한 모든 데이턱 ㅏ필요하며 최대 사후확률 지도의 결과는 지도상에 남아있는 불확실성들을 반영할수가 없습니다.(그림 9.7f같은)

 점유 격자 지도와 이 확장판들은 로봇 공학에서 많이 사용되고 있습니다. 이는 이 점유격자 지도를 얻기 쉬우며 로봇 주행에서 중요한 요소들을 구할수 있기 때문입니다.

9.3.3 에러 함수 the error function

 함수 근사기를 학습하려면 적절한 에러 함수가 필요합니다. 가장 흔한 예시는 역전파 알고리즘을 이용하여 학습한 인공 신경망이 있는데, 역전파는 신경망을 파라미터 공간에서 경사 하강을 이용하여 신경망을 학습시키게 됩니다. 신경망에서 실제 출력과 목표 출력사이의 차이를 측정하는 에러 함수가 주어지면 역전파 알고리즘은 목표 함수와 신경망 파라미터들의 1차 미분을 계싼하고, 이 파라미터들이 차이(실제 출력과 목표 출력 사이의 차이)를 감소하는 방향으로 적응시키도록 합니다. 여기서 에러 함수가 어디서 쓰이는지 궁금하실수 있습니다.

 가장 일반적인 방법은 훈련데이터의 로그우도를 최대화하도록 함수 근사기를 학습시키면 됩니다. 다음 형태의 훈련 집합이 주어진다고 해봅시다.

occ($m_i$$)^{[k]}$는 목표 조건부 확률의 i번째 샘플이고, $input^{[k]}$는 함수 근사기의 입력치가 됩니다. 입력의 형태는 인코딩의 결과에 따라 다양해질수 있습니다.

 이제 함수 근사기의 파라미터들을 W라고 합시다. 훈련 집합의 개개별적인 데이터들이 독립적으로 생성된다고 가정하면, 훈련 데이터의 우도는 다음과 같고

 로그 형태는 아래와 같습니다.

여기서 J는 훈련이 수행되는동안 최대화를 시키는 함수가 됩니다.

이제 함수 근사기를 f($input^{[k]}$, W)로 정의하고 이 함수의 출력 구간을 [0, 1]로 합시다. 훈련 후에는 점유 확률을 출력으로하는 함수 근사기를 원하는데 이는 다음과 같습니다.

 훈련 예제들을 사용하여 예측과 실제 결과의 차이를 최소화 시켜주도록 W를 조절하는 에러 함수를 찾아야 합니다. 이 에러 함수를 구하기 위해 식 (9.18)을 다음과 같이 다시 정리 할 수 있겠습니다.

 식 (9.18)과 이 곱형태의 식은 동일한 것인데, 곱 형태의 식에서 하나의 항은 지수가 9이므로 항상 1이 됩니다. 이 곱을 (0.20)에 대입하고 - 1한것을 곱하면 다음의 식을 얻을 수 있게 됩니다.

J(W)는 함수 근사기를 훈련시킬때 최소화 하는 에러 함수로 경사 하강법을 사용하는 어느 함수추정기로도 사용할 수 있습니다.

그림 9.6 센서 해석하기 : 세개의 초음파 스캔 샘플(위의 행), 신경망으로 생성된 지역 점유 지도(아래의 행). 밝은 영역은 자유 공간이고 어두은 공간은 벽이나 장애물을 의미합니다.

9.3.4 추가적인 고려사항

 그림 9.6은 역 센서모델을 흉내내는 훈련된 인공신경망 결과를 보여주고 있습니다. 이 예제에서 로봇은 탁자 높이의 원형 초음파 측정기가 장착되어 있습니다. 신경망의 입력은 극좌표계상에 좌표값들로 거리 측정치 5개가 집합으로 들어갑니다. 출력은 점유 확률이 되는데, 셀이 검을수록 점유될 가능성이 높아 집니다. 장애물뒤의 더 회새 공간은 점유 사전 확률로 점유 겨자 맵핑 알고리즘이 사용될때까지 변화하지 않습니다. 그림 9.6b는 아래의 왼쪽에 잘못된 짧은 입력치를 가지고 있는데, 이 단일 값은 장애물을 예측하는대 높은확률로 실패한것을 볼 수 있습니다. 

 전방향 모델로 구한 시뮬레이션 대이터 대신 로봇으로 구한 실제 데이터를 사용하여 함수 근사기를 학습시키는 많은 방법들이 존재하는데, 일반적으로 관측 모델은 근사화가 필요하므로 이게 학습에 사용할 더 정확한 데이터가 됩니다. 한 방법은 로봇을 지도가 주어진 이미 알고 있는 공간에서 수행하늗네, 마르코브 위치 추정으로 로봇의 위치를 추정학 실제 관측치와 알고있는 지도 점유 격자를 이용해서 훈련 데이터들을 모을 수 있습니다. 아니면 더 나은 지도를 생성하기 위해서 이미 학습된 센서 모델을 사용하여 근사된 지도에서 시작하는것도 가능합니다.  

9.3 역관측모델 학습 learning inverse measurement models

9.3.1 관측 모델 뒤집기 inverting the measurement model

 점유 격자 지도 작성 알고리즘은 주변 역관찰 모델 marginalized inverse measurement model p($m_i$ | x, z)을 필요로 합니다. 이 확률을 역이라고 부르는 이유는 관측치가 주어질때 지도 정보를 전달하기 때문입니다. 이는 i번째 셀에 대해 주변화 marginalized가 되는데, 전체에 대한 역모델의 경우는 p(m | x, z)가 됩니다. 이 기본 알고리즘을 확장하여 표 9.2에서 다뤄봤었습니다. 원칙적인 모델을 구하려면 일단 고전적인 측정 모델에서 시작하면 됩니다.

 베이즈 정리로 

 여기서 p(m | x) = p(m)이라 하면, 로봇의 자세는 지도에 대해서 아무런 정보를 주지 않으므로, 더 쉽게 다룰수 있게 됩니다. 목표가 전체 지도에 대한 역 모델을 계산하는거라면 이제 끝났습니다. 하지만 구현할 점유 격자 지도작성 알고리즘은 각 그리드 셀 $m_i$의 주변부에 대한 사후확률을 근사시켜야 합니다. i번째 그리드 셀에 대한 역 모델은 i번째 그리드 셀의 주변을 선택하여 얻을수 있는데

 이 표현은 지도 전체에서 그리드 셀 i의 값과 같은 $m_i$들을 적분시키게 됩니다. 지도 전체 공간은 너무 크기 때문에 적분을 할수는 없는데, 이 표현을 근사화하는 방법에 대해 소개하겠습니다. 이 알고리즘에서는 측정 모델로부터 샘플을 만들고, 다항식, 로지스틱 회귀, 신경망 같은 함수 근사기를 사용해서 역모델을 근사시키게 됩니다.

9.3.2 전방향 모델로부터 샘플링 Sampling from the forward model

 기본 아이디어는 단순합니다. 어느 그리드 셀 $m_i$에 대해 자세 $x_{t}^{[k]}$, 관측 $z_{t}^{[k]}$, 지도 점유 값 $m_{i}^{p[k]}$의 샘플을 생성한다면 입력을 자세 x, 측정 z로 하고 출력을 $m_i$에 대해 점유 확률로 하는 함수로 학습할수 있씁니다.

($x_{t}^{[k]}$, $z_{t}^{[k]}$, $m_{i}^{p[k]}$) 형태의 샘플을 다음 과정으로 구할수 있습니다.

1. 임의의 지도 $m^{[m]}$ ~ p(m)을 샘플해주세요. 예를들어 p(m)로 나타낼수 있는 지도 정보를 가지고 있다면, 정보로 임의의 지도를 그릴수 있습니다.

2. 지도 안에서 자세 $x_t^{[k]}$를 샘플해야합니다. 여기서 자세는 균일분포로 가정할수도 있습니다.

3. 관측 $z_{t}^{[k]}$ ~ p(z | $x_{t}^{[k]}$, $m^{[k]}$)를 샘플해주세요. 이 샘플 단계는 센서 측정치를 확률적으로 시뮬레이션하는 과정이 됩니다.

4. 지도 m에서 목표 그리드 셀에 대해 실제 점유 값 $m_i$를 추출해주세요.

 이 결과는 샘플된 자세 $x_{t}^{[k]}$, 측정 $z_{t}^{[k]}$, 그리고 그리드 셀 $m_i$의 점유값이 됩니다. 샘플 단계를 반복하여 다음의 데이터 셋이 만들어 집니다.

 이 트리플랫은 구하려는 조건부 확률 p($m_i$ | z, x)를 근사화 시키는데 사용할 함수 근사기의 예제들로 사용하겠습니다. 여기에 관측 z와 자세 x가 입력 값이고, 점유 값 occ($m_i$)가 함수 근사기 출력의 목표가 됩니다.

 이 방법은 많은 속성들을 구하는데 실패할수도 있기 때문에 다소 비효율적일수도 있습니다.

- 센서의 인식 거리를 벗어난 관측치는 그리드셀에 대한 정보를 전달해서는 안됩니다. 이 관측은 2가지 의미를가지고 있는데, 첫째는 셀 $m_i$가 관측 범위 안에 있을때 트리플랫에 대한 샘플 생성 과정이 수행되는 점이고,두번째는 이 셀에 예측이 수행될때 측정치 z의 데이터 일부분만 함수 추정기의 입력으로 사용되기 때문입니다.

- 센서의 특성은 관측시에 로봇이나 그리드 셀의 절대 좌표에 시불변인데, 상대 좌표에서 문제가 발생합니다. 로봇의 자세를 (x y $\theta$$)^T$, 그리드셀 좌표 $m_i$ = ($x_{m_{i}}$ $y_{m_{i}}$$)^T$이면, 그리드 셀의 좌표는 아래의 변환을 통해 로봇의 지역 기준 좌표계 상으로 맵핑시킬수 있습니다.

 원형 거리계를 가진 로봇에서는 그리드 셀의 자세를 극 좌표계(거리와 방위)를 사용해서 앤코드가 됩니다.

- 근처에 존재하는 그리드 셀들은 역 센서 모델을 이용해서 비슷하게 다루어져야 하는데, 각 그리드 셀에 별개의 함수로 학습하기 보다는 그리드 셀 좌표를 입력으로 사용하는 단일 함수로 학습시키는것이 효율적입니다.

- 만약 로봇이 기능적으로 동일한 센서로 처리를 한다면 역 센서 모델은 다른 센서들 사이에 같이 사용해도 됩니다. 원형 거리계를 장착한 로봇의 경우에 같은 역 센서 모델로 결과 센서 빔의 특성을 나타내게 됩니다.

 이러한 불변성을 강화하기 위한 방법으로 적절한 입력변수로 함수 근사기를 만들면 되는데, 함수 근사기가 절대 좌표계에서 기반으로 하지 않도록 상대 자세 정보를 사용하는것이 좋습니다. 또 점유 예측과 관련없는 센서 관측치를 생략하고, 예측 과정을 센서의 인지거리 안에 있는 그리드 셀만으로 제한하는거이 좋은 방법이 될수 있씁니다. 이런 불변성을 개선하여 훈련 집합의 크기를 더욱 줄일수 있습니다.

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) 

9. 점유 격자 지도 장성 occupancy grid mapping

9.1 소개

 이전의 두 장에서는 로봇의 자세를 추정시키는 저차원 인지 문제들에 대한 확률적 기술의 응용들을 살펴보았습니다. 하지만 이 경우들은 지도가 주어진 경우를 다루는 것이고, 지도가 사전에 준비되거나 만들어진다면 현실적으로도 되기는 합니다. 하지만 다른 응용분야에서는 이런 식으로 사전에 지도가 주어지지 않는 경우도 있습니다. 대다수의 빌딩들은 도면 대로 되어있지도 않을 분더러, 설계도가 정확한다해도 로봇 관점에서 가구나 다른 물건들을 포함하고 있지 않은체 벽과 문같은 환경의 형태만 나타내고 있습니다.  지도에 대해서 처음부터 배우는 것은 이동 로봇 설치시에 발생하는 노력들을 줄일수 있고 로봇이 사람의 도움없이 변화에 적응할수 있게 됩니다. 지도 작성 mapping은 자율주행 로봇의 가장 핵심 기능중 하나가 됩니다.

 이동로봇을 이용하여 지도를 얻는 것은 다음의 많은 이유들로 해결해야되는 문제가 됩니다.

- 가정 공간 hypothesis은 지도 상에 가능한 모든 공간으로 큰 편입니다. 지도는 연속 공간에서 정의되기 때문에 모든 지도의 공간은 많은 차원들을 가지고 있으며, 이번에 살펴볼 그리드 근사같은 이산 근사에서도 지도는 10^5 또는 더 많은 변수들로 나타내게 됩니다. 고차원 공간에서의 크기는 지도에상 전체 사후확률을 계산하기가 더 힘들며, 위치 추정시에 잘 동작하는 베이즈 필터 방법들도 지금까지 살펴본 방법만으로는 지도를 작성하는 문제에서 적용할수 없습니다.

- 지도 작성 learning map은 "닭과 달걀" 문제이기도 한데, 동시적 위치 추정 및 지도작성 Simultaneous localization and mapping SLAM이나 concurrent mapping and localization problem 문제라고도 합니다. 로봇이 이동하면서 오도메트리상에 오차들이 누적되어, 결국에 로봇이 어디에 존재하는지 점차 잃어버리게 됩니다. 지도가 주어지는 경우 로봇의 자세를 추정하는 방법들은 이전 챕터에서 봤지만, 로봇의 자세를 알때 지도를 작성하는것은 상대적으로 쉬워지며 이번과 다음 장에서 살펴보겠습니다. 하지만 초기 위치와 정확한 자세 정보 없이는 로봇은 지도 추정과 이 지도상에서 자신의 위치 추정을 동시에 해야만 합니다.

 물론 모든 지도 작성문제들이 똑같이 어렵지는 않습니다. 지도 작성 문제의 어려움은 중요하게 다룰지 요소들에 따라서 정해지게 됩니다.

- 크기

 로봇이 인식할 수있는 범위보다 환경이 커질수록 지도를 얻기가 더 힘들어 집니다.

- 구동과 인지 시 노이즈 noise in perception and actuation

 로봇의 센서와 구동기가 노이즈가 없는 경우에 지도 작성은 쉽겠지만 노이즈가 클수록 이는 더 어려워집니다.

- 인지 모호함 perceptual ambiguity

 비슷하게 생긴 장소가 더 많을수록 서로 다른 장소간에 대응관계를 만들기가 더 어려워집니다.

- 사이클 cycle

 지도 작성시에 사이클은 특히 어렵습니다. 만약 로봇이 복도를 왔다갔다한다면, 사이클은 돌아오면서 오도메트리 에러를 고칠수 있는데, 로봇이 다른 경로로 되돌아오면서 누적된 오도메트리 정보를 가진체 닫힐때 에러가 커질수 있습니다.

표 9.1 (a) 오도메트리로 자세가 인덱싱된 기존 거리 데이터, (b) 지도

 지도 작성의 어려움을 보려면 그림 9.1을 보시면 됩니다. 여기에는 큰 내부 공간에서 수집한 데이터 셋을 보여주고 있는데, 그림 9.1a는 로봇이 기존의 오도메트리 정보를 가지고 생성한 것입니다. 검은 점은 로봇이 거리계로 감지한 장애물을 의미합니다. 그림 9.1 b는 이 데이터를 맵핑 알고리즘에 적용한 결과를 보여주고 있으며 이번 장에서 이런 기술들에 대해 살펴보겠습니다. 

 이번 장에서는 로봇의 자세를 알고있다는 제한아래에 지도 작성 문제를 배워볼것이고, 추가적으로 경로 정보가 주어지더라도 SLAM의 어려움을 살펴보겠습니다. 여기서 다뤄볼 알고리즘 군을 점유 격자 occupancy grid라 부릅니다.

 점유 격자 지도는 로봇의 자세를 알고있는 경우에 측정 데이터의 불확실성과 노이즈로부터 일관된 형태의 지도를 작성하는 문제들을 다룹니다. 점유 격자의 기본 아이디어는 지도를 확률 변수의 필드로 나타내는 것으로 각 환률변수는 해당 장소가 점유되었는지를 나타내는 2진 값으로 이루어집니다. 점유 격자 지도 작성 알고리즘은 이러한 확률 변수에 대해 사후확률 추정치 근사를 구현하게 됩니다.

 이러한 지도 작성 기술에서 자세 정보의 중요함을 아직은 잘 모를텐데, 이후에 로봇의 오도메트리가 없는 경우를 보겠습니다. 점유 격자 기술의 주요 도구는 후처리이며, 이후 살펴볼 많은 SLAM 기술들은 경로 계획과 주행에 적합한 지도를 생성하지 못합니다. 점유 격자 지도는 다른 의미로 SLAM 문제를 풀기 위해서 사용되기도 하는데, 이 점유 격자 지도는 경로 추정에 사용되기도 합니다.

8.5 현실적인 고려사항들

 표 8.5는 직므까지 살펴본 주요 위치추정 기술들을 정리하였습니다. 기술을 선택 시에는 많은 요구사항들이 조절되어야 하는데, 첫번째로 고려할 것은 센서 측정치에서 특징들을 추출할것인지의 여부입니다. 특징을 추출한다면 계산량은 줄일수 있겠지만 정확도나 강인함이 줄어들게 될 수도 있습니다.

표 8.5 마르코브 위치 추정의 서로 다른 구현 방법간의 비교

8.6 정리

 이번 장에서는 두가지 확률적 위치 추정 알고리즘인 그리드 기술과 몬테카를로 위치 추정 방법에 대해서 살펴보앗스빈다.

- 그리드 방법은 사후확률을 히스토그램으로 나타내었습니다.

- 그리드의 크기로 정확도와 계산 효율성 사이 조절을 하였습니다. 굵은 그리드인 경우 굵은 표현을 사용하면서 생기는 영향들을 고려하여 센서와 동작 모델을 조절하여야 합니다. 작은 그리드를 사용하는 경우 전체적인 계산량을 줄일수 있도록 그리드 셀을 선택적으로 갱신하는것이 필요합니다.

- 몬테카를로 위치 추정 방법은 파티클들을 사용하여 사후확률을 나타내는데, 정확도과 계산비용간 조절을 파티클의 크기를 통해 수행할 수 있습니니다.

- 그리드 위치 추정과 MCL 둘다 전역 위치 추정을 수행할 수 있습니다.

- 임의의 파티클들을 추가하여 MCL은 로봇 납치 문제도 다룰수 있습니다.

- 혼합 MCL은 파티클 생성 과정을 뒤집은 확장판으로 로봇의 센서 노이즈가 적을때 더 나은 성능을 보입니다. 하지만 구현 복잡도가 더 커지게 됩니다.

- 설계되지 않은 동적인 환경은 센서 데이터를 필터링하거나 고려되지 앟은 물체에 높은 우도 대응치를 제거하여 대응할수 있습니다 레이저 거리계를 사용하는 경우 로봇은 아주 짧은 측정치들을 제거할수 있습니다.