GraphSLAM(thrun) - 1. 소개

1. 소개

 최근 이동 로봇 플랫폼을 사용하여 물리적인 환경에 대한 지도를 작성하기 위한 연구가 많이 수행되고 있습니다. 기존에 수행되던 연구로 하늘에서의 지도작성(konecy, 2002), 땅에서의 지도작성(Elfes 1987), 수중에서의 연구(William, 2001) 등이 있습니다. 또한 실내 환경에서나 (el-Hakim, 1997) 실외 환경에서(Teller, 2001), 그리고 지하에의 지도 작성(Baker, 2004)도 수행되기도 하였습니다.

 

 그러한 지도를 얻기위한 기술 개발은 다양한 목적에서 시작되었는데, 사실적인 광학 랜더링(Allen and Stamos 2000), Nocera, 2000), 감시 (Thrun 2003), 연구 측정(Baker, 2004), 로봇 가이던스(Williams, 2001) 등이 있습니다.

 

 놀랍게도, 이 영역에서의 몇몇 주요 연구들이 수많은 다른 연구 분야에서도 있었는데, 예를들면 광학기하학과 컴퓨터 비전(Tomasi and Kanade 1992), 컴퓨터 그래픽스(Levoy 1999), 로봇 공학 (Dissanayake, 2001)이 있었습니다. 

 

 SLAM 커뮤니티에서는 널리 알려진 확장 칼만필터 같은 필터 기술들이 모델을 얻기위한 방법이 되어왔습니다. 확장칼만필터 EKF는 19986년 치즈만과 스미스로 처음 수학적으로 소개되었으며, 1989년 Moutalier가 구현하였습니다. 이 연구는 최근 수백가지로 확장되었으며, 이러한 방법들 중 일부 연구들은 필터 처리 과정에서 계산 효율성을 얻기 위해 희소 그래프 구조로 사상하기도 하였습니다.(Bosse 2003, Thrun 2002).

 

 하지만 이러한 필터 기술의 주요 단점은 데이터가 처리되고 버려진다는 점인데, 이로 인해 지도 작성 중에 모든 데이터를 재사용할수 없게 됩니다. 오프라인 기술이 Lu와 Milos가 1997년에 소개하고 수많은 후속 연구들이 진행되었는데, 모든 데이터를 저장하고, 지도 작성을 이 작업이 끝날때까지 미룸으로서 개선된 성능을 보여주고 있습니다. 1998년 Golfarelli의 연구는 완전 슬램 문제의 사후확률을 희소 그래프로 구성하였습니다. 이 그래프는 비선형 이차 제약의 합이되어, 이러한 제약 조건들 사이에 최적화하는것으로 최대 우도의 지도와 이에 대한 로봇 자세들의 집합을 얻을 수 있었습니다.

 

 이 논문에서는 희소 제약 그래프를 사용하는 새로운 알고리즘을 소개할것이고, GraphSLAM이라 부르겠습니다. GraphSLAM의 기본 개념은 단순합니다. GraphSLAM은 데이터로부터 제약조건의 집합을 추출할것이고, 희소 그래프로 표현하겠습니다. 이 알고리즘은 이러한 제약조건들을 전역 일관 추정으로 풀어내어 지도와 로봇의 경로를 얻게 됩니다. 이 제약조건들은 일반적으로 비선형이지만, 그들을 풀기위한 과정은 선형화되어지고, 표준 최적화 기술로 풀수 있는 최소 제곱 문제가 됩니다. 이후에는 GraphSLAM을 비선형 제약조건들의 희소 그래프를 만드는 기술과, 선형 제약조건의 희소 정보 행렬을 구하는 기술로 나누어 보겠습니다.

 

 넓은 공간에서의 지도 작성 문제에 적용할때, GraphSLAM은 수많은 특징들을 다룰수 있고, 심지어 GPS 정보를 지도 작성 과정에 반영시킬수 있습니다. 이러한 능력들은 3차원 지도작성을 위한 이동로봇으로 획득한 데이터를 기반으로 하고 이습니다.

 

 이 논문은 다음과 같은 순서대로 살펴보겠습니다. 우선 관련 연구들을 살펴볼것이고, GraphSLAM에 대해 직관적으로 설명한 다음에 그래프 이론과 정보 이론을 사용하여 자세히 보겠습니다. 기본 알고리즘을 소개할것이고, 이를 수학적으로 어떻게 구했는지 정리하겠습니다. 그러고나서 데이터 연관 문제를 다루어 보겠습니다. 마지막으로 실험 결과를 보여주고 이후 연구방향으로 마치겠습니다.