FastSLAM - 3. FastSLAM 1.0

3. FastSLAM 1.0

 이번 장에서는 파티클 필터를 사용하는 SLAM 방법인 FastSLAM 기본 알고리즘을 살펴보겠습니다.

 FastSLAM 알고리즘은 EKF가 실패하게 되는 SLAM 문제의 구조적인 성질에 기반하는 것으로, 로봇에 의해 얻은 각 제어 입력과 관측은 적은 수의 상태변수만을 제약하게 됩니다. 제어는 로봇의 이전 자세에 상대적인 현재 로봇의 자세로 제한하며, 관측은 로봇에 상대적인 랜드마크의 위치를 제한합니다. 많은 수의 확률적 제약들이 반영이 된 후에서야 지도는 완전 상관관계를 가지게 됩니다. EKF는 상태 변수에서 어느 구조적인 가정을 가지지 않아 이 희소성으로인한 이점을 가지지 못하게 됩니다.

 

 FastsSLAM은 조건부 독립을 사용하는데, 이는 사후 확률을 저차원 추정 문제로 분해하여 SLAM 문제에서 구조적인 희소성의 결과가라고 할수 있습니다. 이 알고리즘의 결과로 큰 맵을 효율적으로 스케일 조정할수 있고, 데이터 연관에있어서 애매한 경우에도 강인해 질 수 있습니다.

 

3.1 파티클 필터링

 칼만 필터와 확장 칼만필터는 파라미터 모델(다변수 가우시안)으로 확률 분포를 나타냅니다. 하지만 파티클 필터는 유한개의 상태 샘플들의 집합을 사용하여 분포를 나타내는데, 이 상태 샘플들을 파티클이라고 합니다. 높음 확률을 가진 영역은 높은 밀도의 파티클들을 가지고 확률이 낮은 공간에는 적은 수의 파티클을 가지게 됩니다. 충분한 수의 샘플들이 주어짐으로서, 이 비모수적인 방법은 재멋대로이며 복잡한 다중 모달 분포를 근사화 할수 있겠습니다.

 

 샘플의 수를 제한하여 실제 분포는 쉽게 복원될수 있겠습니다. 이 표현을 이용해서 베이즈 필더 갱신 식은 간단한 샘플링 과정을 사용하여 구현할수 있습니다.

 

 파티클 필터는 현실 세게에서 다양한 추정 문제에 성공적으로 적용되어 왔습니다. 가장 흔한 피티클 필터링의 예시중 하나는 몬테카를로 위치추적 MCL인데, MCL에서 파티클의 집합은 고정된 지도상에 상대적인 로봇의 가능한 자세들에대한 분포를 나타냅니다.

 

 그림 3.1이 이 예시를 보여주고 있는데, 그림 3.1 a는 로봇은 자세에 대한 정보가 주어지지 않으므로 불확실성은 파티클들을 균일 분포를 따르도록 맵 전반에 뿌려 보여주고 있습니다. 그림 3.1 b는 여러 제어와 관측이 반영된 후의 파티클 필터를 보여주고 있습니다. 여기서 사후 확률은 근사화되는 단봉 분포로 모여들고 있습니다.

 

그림 3.1 파티클 필터링을 이용한 로봇 위치 추정

 

 멀티 모달 신뢰도를 추적하고, 비선형 동작, 관측모델을 사용하는 능력은 파티클 필터가 더욱 강인하게 수행하게 만들어 줍니다. 하지만 최악의 경우에 주어진 신뢰도를 추적하는데 필요한 파티클의 수가 상태 공간의 차원에 따라 지수적으로 증가할수도 있습니다. 그래서 표준 파티클 필터링 알고리즘은 상대적으로 저차원의 문제에서만 사용 가능합니다. 파티클 필터는 특히 수백만 차원으로 이루어진 SLAM 문제에서는 부적합합니다.

 

 하지만 앞으로 볼 파트에서 어떻게 SLAM이 로봇 경로 추정치가 주어질때 독립된 랜드마크 추정의 문제들로 분해하는지 살펴보겠습니다. 로봇 경로 사후확률은 저차원이며 파티클 필터로 쉽게 추정할수 있으며 FastSLAM이라고 부르는 결과 알고리즘은 Rao-Blackwellized 파티클 필터의 하나의 예시라고 할수 있겠습니다.

 

3.2 분해된 사후확률 표현법

 대다수의 SLAM 방법들은 지도와 로봇 자세에 대한 사후확률 추정에 기반하고 있습니다.

 FastSLAM은 약간 다른 양을 계산하는데, 지도와 로봇의 경로가 주어질때에 대한 사후확률을 계산하여야 합니다.

 이런 미묘한 차이는 SLAM 사후확률을 단순한 항들의 곱으로 분해할수 있게 도와줍니다. 그림 3.2는 동적 베이즈 네트워크 DBN으로 SLAM 문제를 해석한 것을 보여주고 이씃ㅂ니다. DBN에서 묘사된 시나리오에서 로봇은 시간 t=1일때 랜드마크 $\theta_1$를 관측하고, 시간 t=2일떄 $\theta_2$를 관측합니다. 시간 t=3에서는 랜드마크 $\theta_1$을 제관측하고 있습니다. 여기서 회색 영역은 로봇의 경로를 보여주고 있습니다. 이 다이어그램으로부터 SLAM문제에서 중요한 조건부 독립들을 볼수 있습니다.

 

 특히 만약 로봇의 진짜 경로를 안다면, 랜드마크 $\theta_1$의 위치는 랜드마크 $\theta_2$에 조건부 독립이 됩니다. 이러한 DBN의 터미놀로지를 사용하여 로봇의 경로는 두 랜드마크 노드 $\theta_1$과 $\theta_2$를 나눌수 있게 됩니다.

 

이 조건부 독립은 매우 중요한 결과를 만드는데, 로봇의 경로에 대한 정보가 주어지면 한 랜드마크에 대한 관측은 다른 랜드마크의 위치에 대한 아무런 정보를 주지않는다는 것입니다. 다시말하면, 한 장애물이 로봇의 진짜 경로를 알려준다면, 모든 랜드마크의 위치를 독립적인 양으로서 추정할수 있습니다. 이는 사후확률 (3.2)가 단순한 항들의 곱으로 분해할수 있음을 의미합니다.

 

 이 분해는 머피가 처음 개발하였으며, 거기서 SLAM 사후확률이 로봇 경로 사후확률과 로봇의 경로가 주어질때 N개의 랜드마크 사후확률의 곱으로 분해할수 있게 됩니다. 이 분해는 매우 중요하며, SLAM 문제의 구조로부터 구할수 있습니다.

 

3.2.1 FastSLAM 분해 증명

 FastSLAM 분해는 SLAM 경로 사후확률 (3.2)로부터 얻을수 있습니다. 조건부 확률 정의를 사용하여 SLAM 사후확률을 다음과 같이 다시 정리할 수 있습니다.

 그래서 분해된 사후확률 (3.3)을 구하기 위해서, 다음과 정리하기만 하면 충분하겠습니다.