확률적 로봇공학 - 14. 빠른 증분 지도작성 알고리즘

14. 빠른 증분 지도작성 알고리즘 fast incremental mapping algorithms

14.1 개요

 이전의 두 장에서는 동시적 지도 작성과 위치 추정에 대한 원칙적인 방법들을 살펴보았습니다. 이 방법들은 통계학적이며, 로봇의 자세와 지도상에 존재하는 불확실성을 합쳤습니다. 하지만 이들은 중요한 결점을 가지고 있는데, 칼만 필터 방법은 인식시 애매함암을 다룰수 없어 데이터 연관을 통해 해결하였습니다. 또한 상대적으로 적은 수의 특징들만 사용가능합니다. 이러한 한계들로 고해상도 구조적인 지도를 만들기에는 어렵습니다. 하지만 EM 방법은 데이터 연관에서 좋은 해결방안을 제시하고 있으나 실시간으로 동작되지 않고 저장되어야 합니다. 이는 중요한 한계인데, 예를들자면 실시간 탐사나 모르는 환경에 대한 지도작성 알고리즘을 사용할수 없게 됩니다.

 

 이번 장에서는 실시간으로 지도를 생성하며 데이터 연관 문제를 동시에 다룰수있는 알고리즘군을 살펴보겠습니다. 이러한 방법의 핵심은 비확률적인데, 지도 근사치에 대한 불호가실성을 나타내는 대신 증분 지도 작성 문제로 최대 우도 방법으로 얻을수 있는 단일 지도를 계산합니다. 명확한것은 불확실성 표현을 사용하지 않는것으로 문제가 야기되는데, 이 알고리즘은 사이클이 존재하는 환경에서도 지도가 작성가능합니다. 사이클은 로봇이 이전에 맵핑한 곳을 다른 방향으로 와서 다시 연결해야 하기 때문에 일반적으로 지도 작성하기는 어렵습니다. 이 문제를 극복하기 위해서 로봇의 자세에 대한 사후확률 근사기와 확률적 근사기를 사용한 알고리즘을 만들겠습니다. 이 근사기는 자세 공간에서 최대 우도의 에러를 설계하여, 실시간으로 동시적 지도 작성을 하는 동안 큰 사이클과 같은 문제를 다룰수 있게 됩니다. 여기서 살펴볼 이 알고리즘은 현실적으로 중요하며, 레이저 거리계 같은 센서의 타입에 다라 실시간 환경에서 상대적으로 큰 공간의 지도를 만들수가 있씁니다. 이들은 상대적으로 구현하기 쉽고 이동로봇에서 널리 사용되고 있습니다.

 

 이번 장의 마지막에는 로봇공학에서 탐사되지 않은 곳에 대한 두가지 중요한 지도작성 문제에 대해 살펴볼것인데, 다중 로봇 지도 작성 문제로 로봇들이 협동하여 지도를 획득하는 것과 3차원 지도작성 문제로 로봇이 주변 환경에 대한 3차원 지도를 생성하는 문제가 있습니다. 살펴보겠지만 다중 로봇 지도 적상과 3차원 지도작성 알고리즘들은 이번 장에서 주로 다룰 알고리즘들에 약간의 노력을 더하면 구현할 수 있을 겁니다.

 

 이번 장은 다음과 같이 구성하였습니다.

 

- 14.2장에서는 증분 지도 작성 문제와 최대 우도 추정기를 사용한 증분하는 지도를 만드는 기본 알고리즘에 대해 살펴보았습니다.

 

- 14.3장에서는 연속 탐색 공간에서 최대 우도 지도를 찾는것을 목표로 로그 우도 공간에서 언덕 오르기를 위해 경사 하강 방법에 대해 살펴보았습니다. 여기서는 인지 모델과 동작 모델에 강인한 경사 하강 알고리즘들을 소개하겠습니다.

 

- 14.4장에서는 로봇의 자세애 대한 사후확률을 동시적으로 추정하는 개념에 대해 소개하고 사이클을 닫을때 발생하는 큰 에러를 수용하는 방법을 소개합니다. 이 장에서는 MCL 스타일의 사후확률 추정기와 증분 최대 우도 도 추정을 결합한 핵심 알고리즘을 보여주고 있습니다.

 

- 14.5장에서는 협력하는 다중 로봇 문제를 다루기 위해 기본 알고리즘의 확장판을 다뤄볼것인데 이 알고리즘은 서로 알수없는 초기위치를 가진 여러 로봇 플랫폼으로부터 데이터를 합칠수 있습니다. 하지만 여기서 이 로봇들은 팀리더의 지시를 받고 다른 로봇들은 팀리더에 의해 지도 작성을 수행합니다.

 

- 마지막으로 14.6장에서는 로봇이 3차원 공간에 대한 지도를 작성하게 해주는 기본 알고리즘의 확장판에 대해 보겠습니다. 이 3차원 지도는 구조와 질감 정보를 결합하여 실제 비디오게임에서 사용하는것과 비슷하게 나옵니다. 이들은 두개의 레이저 거리계와 파노라마 카메라로 얻을수 있습니다.

 

 

14.2 증분 우도 최대화 incremental likelihood maximization

 뒤에 살펴볼 두 알고리즘들의 이론적 근거로 우도 최대화가 있습니다. 지도에 대한 사후확률을 계산하는 대신 이 알고리즘들은 가장 가능성 있는 로봇의 자세에 따라 가장 확실한 지도를 계산하는것이 됩니다. 이 것을 다음과 같이 표기할 수 있겠습니다.

 

 불행히도 차우의 두 챕터에서 보겠지만 이 표현은 추적할수 없습니다. 그래서 이번 장에서 살펴볼 방법은 증분 최대 우도 추정기를 사용하겠습니다. 이 방법들은 커져가는 지도에 최근 센서 측정을 추가하여 다음과 같은 각 자세와 지도의 시퀀스들을 계산 합니다.

 

 주의해야 할 점은 이 추정치는 확률적인게 아닙니다. 지도와 자세 전반에 대한 확률을 계산하는데신 이들은 단지 단일 지도 생성과 단일 자세를 다루고 있습니다. 완전 확률적인 방법과 비교할때 이 제약은 계산상 부하를 크게 줄여주며, 증분 최대 우도 지도작성에서의 불안정성의 주요 원인이 됩니다. 아래에서 보면 특정한 추정 에러로부터 복원할수 있는 확률적인 자세 추정기를 추가하겠습니다.

 

 우리가 해야할 첫 질문은 어떻게 로봇이 이런 지도와 자세의 증분 시퀀스를 찾을수 있을까요? 그동안 살펴본 알고리즘의 핵심인 기본 베이즈 필터에서 다시 시작해 봅시다.

 

 증분 동시적 지도작성과 위치 추정에서 자세 전반에 대한 신뢰도 뿐만이 아니라 지도에 대한 신뢰도도 계산하여야 합니다. 그래서 지도와 자세에 대한 신뢰도를 계산해야만 합니다. 게다가 증분방법에서 우리는 지도의 전체 시퀀스를 생성할것이므로 시간에 따라 지도에 인덱싱을 하는것이 편리합니다. 그래서 동시적 위치 추정 및 지도작성에서 베이즈 필터는 다음과 같은 형태를 가지게 됩니다.

 

 

 이 방정식은 베이즈 필터를 지도 추정으로 확장하는 점에서 중요합니다. 하지만 불행이도 베이즈 필터는 현실적으로 사용할수 없습니다. 베이즈 필터는 위치 추정 문제에서만 계산되므로 동시적 지도 작성과 위치 추정 문제에서는 적합하지 않습니다. 이 원인은 추적가능성이란 이유로 단순합니다. 로봇의 자세가 3차원의 값이라면 지도는 수천개의 많은 값들이 될겁니다.

 

 최대 우도 추정기는 완전 사후확률 계산보다 단둔산 문제인데, 최대 우도 추정기에서 사후 확률에 대한 최대 우도를 다음과 같이 계산할 수 있습니다.

 최대 우도 추정기는 자기자신의 불확실성에 대한 표기를 가지고 있으나, 우도를 최대화 하는 지도를 계산하는것은 힘든 문제입니다. 최대 우도 추정기는 전체 사후확률을 계산하기 쉬운 반면에, 여전히 이 문제는 매우 추적하기가 어렵습니다. 

 

 증분 최대 우도 추정기 incremental maximum likelihood estimator는 최대 우도 추정 문제를 지역적인 시퀀스로 분해하여 추적 가능한 문제로 만듭니다. 더 자세하게는 이들은 시간 t에서 각 지점들을 가정하고 하나는 이전의 시간 단계에서 시간 t-1까지 모든 데이터릅 반영하여 구한 지도와 자세 추정치가 됩니다. 이들은 시간 t에 대한 지도와 자세의 최대 우도를 계산하고 계산은 효율적으로 수행 됩니다.

 

 더 정리해서 설명하자면 증분 최대 우도 추정기는 다음의 조건부 신뢰도를 최대화 합니다.

 이것은 한시간 이른 데이터와 자세, 지도가 주어질때 시간 t에서 자세와 지도의 확률이 됩니다. 마르코브 가정은 시간 t-1 이전에 모은 데이터를 만드는데, 이 데이터들은 시간 t에서 지도와 자세와 시간 t-1에서 주어진 자세와 지도에 조건부 독립이 됩니다. 그래서 이를 다음과 같이 정리할수 있습니다.

 

 여기서는 시간 t-1과 t사이에 모은 데이터들이 고려되어야 합니다. 이 증분 추정기의 결과는 식 (14.4)보다 간단한데 다음과 같습니다.

 

 왜 이게 간단하단 말인가? 식 (14.4)와 비교해보면 더이상 지도와 자세에 대해 적분할 필요가 없어진다. 식 (14.8)의 증분 사후확률은 닫힘 폼으로 계산할수도 있으며 이는 온라인 추정에서 매우 편리하다. 하지만 어떻게 증분 최대 우도 방법이 각 시간에 대한 자세 추정과 지도를 얻는지, 왜 자세와 지도에 대한 확률 대신에 단일 자세와 지도의 트랙을 유지하는것만으로 충분한지 궁금증이 남는다.

 

 첫번재 답은 간단한데, 증분 최대 우도 알고리즘은 식 (14.8)을 최대화하여 시간 t에서의 지도와 자세를 계산한다.

 

 로봇은 연속 공간에서 동작하고 모든 지도와 자세에 대한 공간이 충분하게 탐색되지 않았기 때문에 이 계산은 어려울수도 있다. 하지만 아래에서 보겠지만 효율적인 언덕 오르기 방법이 존재하여 빠르게 전역 최적치로 수렴하게 된다. 이 알고리즘의 결과는 실시간에서 사용하게 적합한 성질을 가지게 됩니다.

 

 두번째 질문은 더 대답하기가 어렵습니다. 시간에서 각 지점에서 가장 가능성 있는 자세와 지도를 유지하는것에 의해 이 알고리즘은 불안정하게 되는데, 특정 환경에서 우도 함수는 쉽게 분해되고 불안정함을 견딜수도 있습니다. 하지만 커다란 사이클이 존재하는 복도 같은 환경에서 이러한 분해는 불가능 하고 결과로 나온 지도는 우도가 최대화 되더라도 불안정하게 됩니다. 이 이유를 아래에서 살펴볼것이고 로봇의 자세에 대한 사후확률 추정기와 경우에 따라 조절을 수행하는 알고리즘을 포함헤서 고치는 방법을 살펴보겠습니다.

 

 불행히도, 최대 우도 추정기의 언덕 오르기로 인한 추가적인 불안정함도 설명할 것이고, 만약 이 추정기가 지역 최소점에서 멈추게 된다면 이 알고리즘은 여기서 복원될수 없습니다. 현실적으로 이는 증분 최대 우도 방법으로 지도작성 가능한 환경의 크기와 타입에 따라 제한됩니다. 그럼에도 불구하고 상대적으로 더 크고 정확한 센서의 경우에 지도는 실시간으로 만들수 있으며 이알고리즘이 현실적으로 중요함을 가지게 됩니다.