확률적 로봇공학 - 12. 희소 확장 정보 필터

12. 희소 확장 정보 필터 the sparse extended information filter

12.1 소개

 이전의 2장에서 SLAM 알고리즘의 두 가지 스택트럼에 대해 살펴보았습니다. 여기서 EKF는 능동적인 알고리즘이었는데 매 시간 정보를 얻을 때 마다, 이 정보를 확률 분포로 정리하였었습니다. 이 단계는 계산량이 큰데 지도 상에 n개의 특징이 있는 경우 매 갱신때마다 O($n^2$)의 계산 복잡도를 가지게 됩니다.

 

 EIF SLAM 알고리즘은 다른데, 여기서는 단순히 정보를 누적시켰습니다. 이런 식으로 누적하는 EIF SLAM은 게으르다고 할수 있는데 데이터 획득이 끝날때, EIF SLAM은 이 받은 정보를 저장합니다. 이 누적된 정보를 지도로 바꾸기 위해서 EIF SLAM은 추론을 수행해야만 하며, 이 추론은 모든 정보를 얻은 후에서야 수행됩니다. 이 점이 EIF를 오프라인 알고리즘으로 동작하게 합니다.

 

 여기서 정보 표현법의 효율성을가진 온라인 슬램 알고리즘을 만들수 있을지 궁금해 할수 있는데, 정답은 가능 합니다. 하지만 많은 근사가 필요해요. 희소 확장 정보 필터 sparse extended information filter로 SEIF라고도 하며 온라인 슬램 문제에서 정보를 이용한 방법을 구현한 것을 의미합니다. EKF처럼 SEIF는 과거 로봇의 자세들을 적분하여 현재 로봇의 자세와 지도에 대한 사후확률만 유지합니다. 하지만 EIF 처럼, EKF와는 달리 SEIF는 정보 표현법으로 모든 정보들을 유지합니다. 이렇게 해여 SEIF 갱신은 늦은 정보 시프트 연산이 되는데 이는 EKF의 확률적인 능동 갱신보다 뛰어납니다. 그래서 SEIF는 온라인으로 동작하고 효율적이라는 점에서 세계 최고라고 할수 있습니다.

 

 온라인 알고리즘으로서 SEIF는 EKF와 동일한 상태벡터로 신뢰도를 유지합니다.

 

 

 여기서 $x_t$는 로봇의 상태 m은 지도가 됩니다. 대응관계가 주어진 경우 사후확률은 p($y_t$ | $z_{1:t}$, $u_{1:t}$, $c_{1:t}$)가 되며, 이 사후확률은 EIF에서 전체 경로를 복원한 것과는 달리 EIF로 하나만 추정한다는 점에서 다릅니다.

 

그림 12.0 온라인 슬램에서 정보 필터 사용 유도

- 왼쪽 : 시뮬레이션된 로봇의 주행으로 주위에 50개의 랜드마크가 존재

- 중간 : EKF의 상관관계 행렬로 두 랜드마크 좌표계 사이에 강한 상관관계가 존재함

- 오른쪽 : EKF의 정규화된 정보 행렬로 희소함. 이 희소성은 SLAM 알고리즘을 더 효율적으로 갱신하도록 도와줌

 

 온라인 슬램 알고리즘에서 EIF 사용의 이점은 그림 12.0에서 볼수 있습니다. 이 그림은 EKF SLAM 알고리즘의 결과를 보여주며 이 환경에는 50개의 랜드마크가 들어있습니다. 왼쪽 그림은 움직이는 로봇과 그 주위에 50개의 특징 위치의 확률적 근사치가 같이 존재합니다. EKF SLAM으로 얻은 중심 정보는 이러한 근사치의 공분산 행렬이며, 정규화된 공분산인 상관관계는 중간의 그림에서 보여주고 있습니다. 각 두 축은 로봇의 자세와 50개의 랜드마크의 2차원 위치에 대해 보여주고 있습니다. 검은 요소들은 강한 상관관계를 보여주고 있습니다. 여기서의 한계를 EKF SLAM 장에서 다루었는데 모든 특징 좌표들이 강하게 상관관계를 가지고 있어 상관관계 행렬이 채커보드 형태로 보이게 됩니다.

 

 그림 12.0의 오른쪽에는 정보 행렬 $\Omega_t$를 보여주고 있는데 이는 공분산 행렬을 정규화 한것이 됩니다. 이전 장에서 보았지만 정규화된 정보 행렬 요소는 제약조건이나 링크, 즉 지도상에 존재하는 특징 쌍의 상대적인 위치를 제약시킨것으로 볼수 있습니다. 여기서 요소가 더 검을수록 강한 연결관계를 가진다고 할수 있습니다. 이 그림은 정규화된 정보 행렬이 희소하다는것을 보여주며, 소수의 강한 연결에 좌우되며, 정규화가 될때 많은 수의 연결들이 0에 가까운것을 볼수 있습니다.

 

 더 나아가 각 연결의 강도는 대응관계 변수의 거리와 관련된느데, 강한 연결에서는 가까운 거리의 특징간에서만 보이며, 두 특징간의 거리가 멀수록 이들의 연결은 약해집니다. 이 희소성은 이전 장에서 살펴본것과는 달리 구분하기 쉬운 차이가 존재합니다. 첫째로 랜드마크의 쌍 사이에 강한 연결이 존재합니다. 이전 장에서는 이런 연결이 존재하지 않았습니다. 두번째는 희소성은 근사치인데, 사실 정규화된 정보행렬의 모든 요소들은 0이 아니나 이들 대부분은 0에 매우 가깝습니다.

 

그림 12.1 이 방법으로 생성한 특징들의 네트워크 그림

- 왼쪽 그림은 희소 정보 행렬을 보여주고 있으며, 오른쪽 지도에선 정보 행렬 요소가 0이 아닌 요소들의 연결을 보여주고 있습니다.

- SLAM 문제에서 구조적인 핵심 요소는 모든 특징들이 연결되지 않았다는 점이고 시간 문제의 핵심이 됩니다.

 

 SEIF SLAM 알고리즘은 희소 정보 행렬을 유지하는것으로 서로 가까이 존재하는 특징의 연결만이 0이 아닌 요소가 됩니다. 이 네트워크 구조의 결과는 그림 12.1의 오른쪽에서 볼수 있는데, 여기서 원은 점 특징이고, 점선은 링크를 의미하고 이에 대한 정보 행렬은 좌측에서 볼수 있습니다. 여기서 능동 특징이라 부르는 특징들은 검은색으로 그려져 있습니다. 강한 희소 정보 행렬은 특징의 수에서 선형 공간이 되어야 하며 더 중요한것은 SEIF SLAM에서 모든 갱신이 지도에 존재하는 특지으이 개수와 상관없이 상수 시간에 수행되어 진다는 점입니다. 이 결과는 정보 필터에서 동각 갱신을 구현시에 전체 정보행렬의 역변환을 요구했던것처럼 놀라울수 있습니다.

 

 SEIF는 온라인 슬램 알고리즘으로 희소 정보 행렬을 유지하고, 지도의 크기에 독립적인 갱신 시간을 요구합니다. 이는 SEIF가 이책에서 본 SLAM 문제에 있어서 첫번째로 효율적인 온라인 알고리즘이 되었습니다.