14.3 경사 하강을 이용한 최대 우도 maximum likelihood as gradient descent
14.3.1 자세 공간 탐색 search in pose space
어떻게 식 14.9의 증분 우도 함수를 최대화 시킬지에 대한 질문을 살펴보겠습니다. 이것은 시간 t에서 모든 자세와 지도 공간에서 탐색을 수행합니다
하지만 지도 작성에서 고정된 루틴만 수행한다면, 모든 자세 공간에 대해 탐색하면 중분합니다. 이것은 지도의 공간이 매우 거대한 3차원의 자세 공간에서 계산량을 크게 줄여주는데, 이에 대해 살펴보기위해서 로봇의 자세가 주어진 상황을 생각해봅시다.
t번째 지도 $m^{(t)}$가 이전의 지도 $m^{(t-1)}$로부터 고정되고 결정론적인 루틴(점유 격자 지도 작성같은)으로 생성된다고 가정해봅시다. 여기서 최적화가 되어야할 파라미터는 자세로 다음과 같습니다.
여기서 $\bar{m}^{(t)}$($\bar{s}^{(t)}$, $o^{(t)}$, $m^{(m-1)}$)은 주장 자세 alleged pose $\bar{s}^{(t)}}$에서 지도 $m^{(t-1)}$에 관측 $o^{(t)}$를 증분적으로 반영하는것으로 구할수 있는 지도를 의미합니다. 여기서 자세를 알고있다고 고려하기 때문에 이 지도를 최근 센서 관측 $o^{t}$로 바꿀수 있으며 다음의 식을 얻을수 있습니다.
식 14.8 증분 신뢰도의 정의에 따라 다음과 같이 정리됩니다.
로그 우도 형태로 정리하면 다음과 같습니다.
정리하기 위해서 커지는 지도는 고정된 루틴으로 수행되며 전체 지도 공간을 탐색할 노력을 줄여줍니다. 이 결과 최대 우도 표현은 모든 자세 공간을 탐색하게 됩니다.
식 14.3의 결과는 이제 탐색을 수행하기 좋게 단순해졌는데, 특히 증분 사후확률을 최대화 하는 자세를 찾기 위해 시간 t에서 모든 자세 공간을 탐색하겠습니다. 연속 공간을 탐색하는 가장 일반적인 방법은 로그 우도 공간에서 경사 하강을 하는것이며, 다행이도 식 14.13의 모든 확률들은 미분가능합니다. 식 14.13의 우항에 있는 자세에 대한 로그 확률의 기울기는 다음과 같이 정리할 수 있습니다.
기울기는 추가되므로, 다음의 동작모델로부터 인지 확률의 기울기를 나눌수 있습니다.
경사 하강은 점차 내려가는 방향으로 추정치 $\bar{s}^{(t)}$를 바꾸고 이는 다음의 탐색 알고리즘에 적용할 수 있습니다.
여기서 k > 0는 경사 하강에서 필요한 단계의 크기로 0에 가깝습니다. 경사 하강의 시작점은 자세에 대한 간단한 동작(오도메트리 측정치)를 적용하여 구할수 있으며 다음과 같습니다.
이는 5장에서 살펴본 노이즈 파라미터가 0으로 설정한 기구학적인 동작 모델을 이용하여 계산할수 있습니다. 경사 하강은 그러면 14.16의 갱신 법칙을 따라 반복하여 적용이 되고, 수렴 한계치를 만나게 됩니다.
14.3.2 기울기 계산
식 14.16에서 원하는 기울기를 계산하기 위하여 필요한 기술적인 세부사항들을 살펴보겠습니다. 인지 모델과 동작 모델에 대해 새부적으로 살펴보기 전에 미분 함수의 기울기 계산을 강조하는것이 중요합니다 로그 우도 함수의 기울기는 복잡할수 있으나 이들은 어느 동작 모델과 인지 모델을 미분하여 얻을수 있습니다. 이 모델은 미분할수 있으며 그래서 기울기는 이들 모두에서 계산될수 있습니다.
표 14.2는 로그 인지 모델의 일차 미분을 계산하는 알고리즘을 보여주고 있습니다.
표 14.2. 표 6.3의 거리계 모델을 이용한 로그 확률의 1차 미분 계산 알고리즘
기울기 계산은 직관적으로 수행될수 있는데 표 14.2에서 미분 계수 계산을 이해하기 쉽도록 정리하였습니다.
표 14.3 오도메트리 정보(표 5.5)를 이용한 동작 모델 p(s; | a, s)의 로그 일차 미분 계산 알고리즘
비슷하게 표 14.3은 오도메트리 기반 모델의 로그에 대한 일차 미분을 계산하는 알고리즘을 보여주고 있습니다.
표 14.4 분산이 b인 0평균 정규 분포의 1차미분 계산 알고리즘(표 5.2)
이 알고리즘은 0평균 노이즈 모델 prob()의 일차 미분이 필요하며 표 14.4에서 볼수 있습니다. 이 모델은 14.16에서 명확하게 요구되는것은 아니지만 중요합니다. 이는 미분의 연쇄법칙을 사용해서 복소수 함수의 미분을 계산하는 여러 방법들을 보여주고 있습니다. 빠른 경사 하강을 구현할때 여기있는 알고리즘들을 복수하는데신에 손으로 기울기를 계산해보시기를 추천합니다.
14.3.3 구현시 제안들 suggestion for the implementation
스캔 정렬에 대해서 이 알고리즘은 비대칭입니다. 이는 관측이 지도 m의 자유공간에 들어가기 때문인데, 지도가 점유된 지역을 보여주고 있는데 이 지역은 스캔 s에따라 자유로워야 합니다. 이 미스매치는 조정에 사용되지 않습니다. 이는 인지모델의 기본이 부족한것인데, 만약 이 모델의 대칭버전을 구현시에는 지도 m의 자유 공간에 들어가는 스캔 s 관측과 스캔 s의 자유공간이 들어가는 m의 지역 둘다 패널티를 주어야 합니다. 결과적인 인지 모델은 약간 더 복잡할수 있는데, 자세 s'에 대해 기울기를 계산하는것은 여기서 주어진 알고리즘에 아날로그적일수 있습니다.
더하자면 기울기 계싼은 특정 정보를 캐싱하여 속도를 크게 높일수 있습니다. 위에서 설명한대로 구현된다면 팬티엄 2 500MHz 프로세서를 사용할때 초당 10개의 기울기 계산이 수행되는것을 볼수 있겠습니다. 그리고 인지 모델과 일차 미분을 계산하는 과정은 더 오래 걸릴것입니다. 표 14.2의 기울기 알고리즘 9번째 줄에서 수행하는 가장 가까운 점유 공간 탐색또한 비용이 큰데, 추정 자세 $s^{(t)}$가 변할때 탐색은 또 반복되어야 합니다.
대안으로 x-y 공간의 그리드 공간에서 가장 가까운 위치의 일차 미분을 계산할수도 있습니다. 이 그리드 계산은 시작 시간이 다소 걸릴수는 있어도 테이불 룩업 작업을 사용하여 탐색시간을 줄여줍니다. 이 탑색의 결과는 근사화된것으로 가장 가까운 이웃을 찾아야 하는 지도의 모든 그리드셀 공간에서 수행되지는 않습니다. 이 기술을 사용하여 그리드 해상도가 10~20cm정도라면, 기울기의 결과가 우도 공간에서 언덕오르기로 잘 맞는것을 볼수있습니다. 게다가 기울기 계산은 2차수로 더 속도를 오릴수 있고 초당 수백회의 반복이 수행 될수 있습니다.
14.3.4 예제
그림 14.1은 스캔 정렬의 경사 하강을 사용한 두가지 예제 시퀀스를 보여주고 있습니다. 이 예제 둘다 표 14.2의 함수 일차 미분 로그 거리계 모델2를 사용하여 우도를 최대화 하였습니다. 두 예제들은 로봇이 이동하면서 기록되었고, 두번째 스캔은 첫번째에 상대적으로 축에 대해10cm, 30도 회전 에러를 가지게 추가하였습니다.
이러한 큰 에러에도 불구하고 루틴은 100회정도 반복하면 올바르게 정렬되었습니다. 그림 14.1은 초기 정렬과 10, 50, 100회 기울기 하강을 수행후 정렬결과를 보여주고 있습니다. 이 예지들은 우도 함수가 전역 최적화의 근접에 있어서 약간의 지역적 최소치들을 가지고 있음을 보여주고 있습니다. 현실에서 (3Hz) 시퀀스로 기록된 스캔을 사용하여 경사 하강 탐색 루틴은 실용적으로 항상 올바른 최대치로 수렴하고 높은 정확도로 이 스캔들을 정렬하였습니다.
표 14.1 스캔 정렬시 경사 하강을 이용한 예제. 두 경우다 초기 평행이동 에러가 각 축에대해 10cm씩, 회전 에러가 30도 정도로 존재합니다. 경사 하강 알고리즘은 최대 우도 정렬로 복원하였습니다.
14.3.5 한계 limitations
우도 최대화를 이용한 방법의 한계는 전역적인 최적 해를 구하는데 실패할수 있습니다. 이 문제는 단일 복도나 사이클이 존재하지 않은 환경을 지도 작성할때 이 문제는 발견할수 없는데, 여기에는 인접한 관측사이에 지역적 일관성만으로 역적으로 일관된 지도를 만드는데 충분하기 때문입니다. 하지만 사이클이 존재하는 공간에서 로봇은 이전에 모은 잠재적인 오도미터 에러가 포함된 데이터와 대응관계를 만들어야 하는데, 뒤의 자세 추정을 고쳐야만 합니다. 그 결과 증분 우도 함수 방법에서 지역 일관성은 전역 일관성을 만드는데 불충분하게 됩니다.
그림 14.2 가장 단순한 증분 최대 우도 방법을 사용하여 얻은 지도
- 지도는 지역적으로 일관적이지만 사이클이 닫힐때 이 방법은 실패하여 일관적이지 않은 지도로 만들게 됩니다. 단계별 우도 최대화의 한계를 보여주고 있으며, 사이클이 존재하는 환경에서 지도 작성의 어려움을 보여주고 있습니다.
그림 14.2는 이 예시를 사용한 문제를 보여주고 있습니다. 이 지도는 사이클이 존재하는 환경에서 얻은것을 보여주고 있습니다. 로봇은 여러 복도를 지나가 결국 초기 위치로 도달하게 됩니다. 지도를 따라가서보면 지역적으로 일관성을 가지고 있어 위치 추정의 에러가 발생하지 않습니다. 하지만 로봇이 사이클을 닫을때 누적된 위치 추정 에러가 지역적으로 수용하기에는 너무커지게 되어 이후 시간에서 지도를 고칠수 없게 되어 위 그림과 같은 영구적인 미스매치가 존재하게 됩니다. 이 결과 지도는 여전히 주행하는데 좋지만 더 큰 사이클은 더 큰 미스매치를 만들것이고 주행을 어렵게 할것입니다.
정리하자면 증분 최대 우도 방법은 다음의 주요 한계를 가지고 있습니다.
1. 이 방법은 큰 오도메트리 에러를 다룰수 없고
2. 이후 시간의 자세를 고칠수가 없습니다.
다음에는 이 두가지 결점을 다루기위한 확장된 개념들을 다룰것이고, 사이클이 존재하는 환경에서 더 신뢰성있는 동작을 수행하는 알고리즘을 구하겠습니다.
14. 빠른 증분 지도작성 알고리즘 fast incremental mapping algorithms
14.1 개요
이전의 두 장에서는 동시적 지도 작성과 위치 추정에 대한 원칙적인 방법들을 살펴보았습니다. 이 방법들은 통계학적이며, 로봇의 자세와 지도상에 존재하는 불확실성을 합쳤습니다. 하지만 이들은 중요한 결점을 가지고 있는데, 칼만 필터 방법은 인식시 애매함암을 다룰수 없어 데이터 연관을 통해 해결하였습니다. 또한 상대적으로 적은 수의 특징들만 사용가능합니다. 이러한 한계들로 고해상도 구조적인 지도를 만들기에는 어렵습니다. 하지만 EM 방법은 데이터 연관에서 좋은 해결방안을 제시하고 있으나 실시간으로 동작되지 않고 저장되어야 합니다. 이는 중요한 한계인데, 예를들자면 실시간 탐사나 모르는 환경에 대한 지도작성 알고리즘을 사용할수 없게 됩니다.
이번 장에서는 실시간으로 지도를 생성하며 데이터 연관 문제를 동시에 다룰수있는 알고리즘군을 살펴보겠습니다. 이러한 방법의 핵심은 비확률적인데, 지도 근사치에 대한 불호가실성을 나타내는 대신 증분 지도 작성 문제로 최대 우도 방법으로 얻을수 있는 단일 지도를 계산합니다. 명확한것은 불확실성 표현을 사용하지 않는것으로 문제가 야기되는데, 이 알고리즘은 사이클이 존재하는 환경에서도 지도가 작성가능합니다. 사이클은 로봇이 이전에 맵핑한 곳을 다른 방향으로 와서 다시 연결해야 하기 때문에 일반적으로 지도 작성하기는 어렵습니다. 이 문제를 극복하기 위해서 로봇의 자세에 대한 사후확률 근사기와 확률적 근사기를 사용한 알고리즘을 만들겠습니다. 이 근사기는 자세 공간에서 최대 우도의 에러를 설계하여, 실시간으로 동시적 지도 작성을 하는 동안 큰 사이클과 같은 문제를 다룰수 있게 됩니다. 여기서 살펴볼 이 알고리즘은 현실적으로 중요하며, 레이저 거리계 같은 센서의 타입에 다라 실시간 환경에서 상대적으로 큰 공간의 지도를 만들수가 있씁니다. 이들은 상대적으로 구현하기 쉽고 이동로봇에서 널리 사용되고 있습니다.
이번 장의 마지막에는 로봇공학에서 탐사되지 않은 곳에 대한 두가지 중요한 지도작성 문제에 대해 살펴볼것인데, 다중 로봇 지도 작성 문제로 로봇들이 협동하여 지도를 획득하는 것과 3차원 지도작성 문제로 로봇이 주변 환경에 대한 3차원 지도를 생성하는 문제가 있습니다. 살펴보겠지만 다중 로봇 지도 적상과 3차원 지도작성 알고리즘들은 이번 장에서 주로 다룰 알고리즘들에 약간의 노력을 더하면 구현할 수 있을 겁니다.
이번 장은 다음과 같이 구성하였습니다.
- 14.2장에서는 증분 지도 작성 문제와 최대 우도 추정기를 사용한 증분하는 지도를 만드는 기본 알고리즘에 대해 살펴보았습니다.
- 14.3장에서는 연속 탐색 공간에서 최대 우도 지도를 찾는것을 목표로 로그 우도 공간에서 언덕 오르기를 위해 경사 하강 방법에 대해 살펴보았습니다. 여기서는 인지 모델과 동작 모델에 강인한 경사 하강 알고리즘들을 소개하겠습니다.
- 14.4장에서는 로봇의 자세애 대한 사후확률을 동시적으로 추정하는 개념에 대해 소개하고 사이클을 닫을때 발생하는 큰 에러를 수용하는 방법을 소개합니다. 이 장에서는 MCL 스타일의 사후확률 추정기와 증분 최대 우도 도 추정을 결합한 핵심 알고리즘을 보여주고 있습니다.
- 14.5장에서는 협력하는 다중 로봇 문제를 다루기 위해 기본 알고리즘의 확장판을 다뤄볼것인데 이 알고리즘은 서로 알수없는 초기위치를 가진 여러 로봇 플랫폼으로부터 데이터를 합칠수 있습니다. 하지만 여기서 이 로봇들은 팀리더의 지시를 받고 다른 로봇들은 팀리더에 의해 지도 작성을 수행합니다.
- 마지막으로 14.6장에서는 로봇이 3차원 공간에 대한 지도를 작성하게 해주는 기본 알고리즘의 확장판에 대해 보겠습니다. 이 3차원 지도는 구조와 질감 정보를 결합하여 실제 비디오게임에서 사용하는것과 비슷하게 나옵니다. 이들은 두개의 레이저 거리계와 파노라마 카메라로 얻을수 있습니다.
뒤에 살펴볼 두 알고리즘들의 이론적 근거로 우도 최대화가 있습니다. 지도에 대한 사후확률을 계산하는 대신 이 알고리즘들은 가장 가능성 있는 로봇의 자세에 따라 가장 확실한 지도를 계산하는것이 됩니다. 이 것을 다음과 같이 표기할 수 있겠습니다.
불행히도 차우의 두 챕터에서 보겠지만 이 표현은 추적할수 없습니다. 그래서 이번 장에서 살펴볼 방법은 증분 최대 우도 추정기를 사용하겠습니다. 이 방법들은 커져가는 지도에 최근 센서 측정을 추가하여 다음과 같은 각 자세와 지도의 시퀀스들을 계산 합니다.
주의해야 할 점은 이 추정치는 확률적인게 아닙니다. 지도와 자세 전반에 대한 확률을 계산하는데신 이들은 단지 단일 지도 생성과 단일 자세를 다루고 있습니다. 완전 확률적인 방법과 비교할때 이 제약은 계산상 부하를 크게 줄여주며, 증분 최대 우도 지도작성에서의 불안정성의 주요 원인이 됩니다. 아래에서 보면 특정한 추정 에러로부터 복원할수 있는 확률적인 자세 추정기를 추가하겠습니다.
우리가 해야할 첫 질문은 어떻게 로봇이 이런 지도와 자세의 증분 시퀀스를 찾을수 있을까요? 그동안 살펴본 알고리즘의 핵심인 기본 베이즈 필터에서 다시 시작해 봅시다.
증분 동시적 지도작성과 위치 추정에서 자세 전반에 대한 신뢰도 뿐만이 아니라 지도에 대한 신뢰도도 계산하여야 합니다. 그래서 지도와 자세에 대한 신뢰도를 계산해야만 합니다. 게다가 증분방법에서 우리는 지도의 전체 시퀀스를 생성할것이므로 시간에 따라 지도에 인덱싱을 하는것이 편리합니다. 그래서 동시적 위치 추정 및 지도작성에서 베이즈 필터는 다음과 같은 형태를 가지게 됩니다.
이 방정식은 베이즈 필터를 지도 추정으로 확장하는 점에서 중요합니다. 하지만 불행이도 베이즈 필터는 현실적으로 사용할수 없습니다. 베이즈 필터는 위치 추정 문제에서만 계산되므로 동시적 지도 작성과 위치 추정 문제에서는 적합하지 않습니다. 이 원인은 추적가능성이란 이유로 단순합니다. 로봇의 자세가 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에서의 지도와 자세를 계산한다.
로봇은 연속 공간에서 동작하고 모든 지도와 자세에 대한 공간이 충분하게 탐색되지 않았기 때문에 이 계산은 어려울수도 있다. 하지만 아래에서 보겠지만 효율적인 언덕 오르기 방법이 존재하여 빠르게 전역 최적치로 수렴하게 된다. 이 알고리즘의 결과는 실시간에서 사용하게 적합한 성질을 가지게 됩니다.
두번째 질문은 더 대답하기가 어렵습니다. 시간에서 각 지점에서 가장 가능성 있는 자세와 지도를 유지하는것에 의해 이 알고리즘은 불안정하게 되는데, 특정 환경에서 우도 함수는 쉽게 분해되고 불안정함을 견딜수도 있습니다. 하지만 커다란 사이클이 존재하는 복도 같은 환경에서 이러한 분해는 불가능 하고 결과로 나온 지도는 우도가 최대화 되더라도 불안정하게 됩니다. 이 이유를 아래에서 살펴볼것이고 로봇의 자세에 대한 사후확률 추정기와 경우에 따라 조절을 수행하는 알고리즘을 포함헤서 고치는 방법을 살펴보겠습니다.
불행히도, 최대 우도 추정기의 언덕 오르기로 인한 추가적인 불안정함도 설명할 것이고, 만약 이 추정기가 지역 최소점에서 멈추게 된다면 이 알고리즘은 여기서 복원될수 없습니다. 현실적으로 이는 증분 최대 우도 방법으로 지도작성 가능한 환경의 크기와 타입에 따라 제한됩니다. 그럼에도 불구하고 상대적으로 더 크고 정확한 센서의 경우에 지도는 실시간으로 만들수 있으며 이알고리즘이 현실적으로 중요함을 가지게 됩니다.
SEIF 갱신의 외부 루프는 표 12.1에서 볼수 있습니다. 이 알고리즘은 정보 행렬 $\Omega_{t-1}$과 정보 벡터 $\xi_{t-1}$ 그리고 추정 상태 $\mu_{t-1}$, 관측 $z_t$, 제어 $u_t$, 대응관계백터 $c_t$를 입력으로 하고있습니다. 이 SEIF SLAM known correspondence 알고리즘의 출력은 새로운 추정 상태로 정보 행렬 $\Omega_t$, 정보 벡터 $\xi_t$로
나타냅니다. 이 알고리즘은 또한 개선된 추정치 $\mu_t$를 출력하고 있습니다.
표 12.2 SEIF에서 동작 갱신
SEIF 갱신은 4가지 단계로 구현됩니다. 표 12.2의 동작 갱신은 제어 $u_t$를 필터 추정에 반영하는데, 많은 동작이 수행되지만 계산상 효율성을 확보하고 있습니다. 이 갱신에서 정보 벡터와 행렬에서 바뀌는 요소는 로봇의 자세와 활성 특징입니다.
표 12.3 SEIF에서 관측 갱신 단계
표 12.3의 관측 갱신은 관측치 $z_t$와 알려진 대응관계 $c_t$를 합치는 과정으로 이 단계 역시 동작 갱신 단계와 마찬가지로 지역적으로 수행됩니다. 지도상에서 로봇의 자세와 관측된 특징의 값만 갱신됩니다.
표 12.4 SEIF에서 희소화 단계
표 12.4에서는 희소화 단계를 보여주고 있는데 이는 근사화 돤계가 됩니다. 정보 행렬과 정보 벡터를 변환하여 활성 특징들을 제거하는데, 이 단계는 로봇과 활성 특장사이의 연결만 변경하여 효율성을 가지게 됩니다.
표 12.5 SEIF에서 상환된 상태 갱신 단계로 약간의 상태 추정치를 갱신합니다.
표 12.5의 상태 추정 갱신 단계는 상태 추정치 $\mu_t$를 복원하기 위해서 상환된 좌표계 하강 기술을 적용합니다. 이 단계에서도 SEIF의 희소성이 사용되어 다른 상태 백터 요소의 일부만 변경시키게 됩ㄴ디ㅏ.
SEIF의 전체 갱신 루프는 상수시간에에서 동작하여 처리 시간은 지도 크기에 독립이 됩니다. EKF가 지도의 크기에 따라 갱신 시간이 이차적으로 증가하던것과는 다른데, 하지만 이 상수 시간이란 말에 소금 한알을 덧붙이면, 환경에 커다란 사이클이 존재한다면 상태 추정의 복원이 비선형 시간이 걸리는 계산 문제라는 점입니다. 그래서 SEIF의 결과는 상수 시간 필터로서 동작할때 지도 크기 증가를 저하시킬수도 있습니다. 이 문제의 개선방안에 대해서 끝에서 살펴보겠습니다.
이번에는 그림을 사용해서 SEIF 갱신에 대해서 설명하겟습니다. SEIF 갱신은 4가지 단계로 구성되는데 동작 갱신 단계, 관측 갱신 단계, 희소화 단계, 상태 추정 단계로 이루어 집니다.
그림 12.2 정보행력에서 측정의 효과와 관련된 특징 네트워크
(a) $y_1$의 관측으로 정보 행렬 $\Omega_{x_t, y_1}$ 요소가 바뀌게 됩니다.
(b) 비슷하게 $y_2$를 관찰하는이 $\Omega_{x_t2 y_2}에 영향을 줍니다.
- 위 두 갱신은 상수 시간에서 수행됩니다.
우선 그림 12.2의 관측 갱신 단계에서 시작해보겠습니다. 각각의 두 그림은 SEIF의 정보행렬과 정보 링크로 정의되는 그래프를 보여주고 있습니다. 정보 갱신시에는 특징 $y_1$을 감지하면 SEIF가 로봇의 자세 추정 $x_t$와 관측 특징 $y_t$를 연결시키는 정보 행렬의 비대각 요소를 갱신하게 됩니다. 이는 그림 12.2a에서 볼수 있습니다.
비슷하게 $y_2$를 감지하면 로봇의 자세 $x_t$와 특징 $y_2$ 사이의 연결시키는 정보행렬에서의 요소를 갱신하게 되는데 그림 12.b에서 볼수 있습니다. 이러한 갱신들인 정보행렬(과 정보 벡터)에서 지역적인 초가가 되는것을 볼수 있습니다. 이 두가지 경우 다(정보 행렬과 벡터) 이러한 추가는 로봇의 자세와 관측된 특징의 연결에 대한 요소만 다루며, 이 점은 EKF의 갱신 단계보다 SEIF의 측정 갱신이 더 효율적으로 동작하게 도와줍니다. 특히 측정에 대한 SEIF 갱신 복잡도는 지도의 크기에 독립적인 시간이 수행됩니다.
그림 12.3 정보행렬에서 동작의 효과와 연관된 특징 네트워크
(a) 동작전, (b) 동작 후
- 만약 동작이 비결정론적이라면 동작 갱신은 두 능동적인 특징 사이에 새로운 링크(혹은 기존에 존재하는 링크 보강)을 만들고, 로봇과 이러한 특징들 사이의 링크는 약해집니다. 이 단계는 특징쌍 사이의 링크를 보여주고 있습니다.
동작 갱신은 그림 12.3에서 볼수있습니다. 여기서 로봇의 자세가 변화하게 되는데 그림 12.3a는 이전의 정보 상태를 보여주며 그림 12.3b는 동작후를 보여주고 있습니다. 동작은 다양한 방법으로 정보 상태에 영향을 주는데, 첫번째로 로봇의 자세와 특징 $y_1$, $y_2$사이의 연결이 약해지게 됩니다. 이는 로봇의 동작이 에러를 가진 결과로 그래서 우리가 로봇이 특징에 상대적으로 존재하던 곳에 대한 정보를 잃어버리게 만듭니다. 하지만 이정보는 완전히 사라지는것은 아닙니다. 이 일부는 쌍 특징사이의 정보 연결로 맵핑되어, 이 정보의 변화는 로봇의 자세에 대한 정보를 잃었더라도 지도에 존재하는 특징 위치의 상대적인 위치 정보를 잃은것이 되지는 않습니다. 이러한 특징들은 로봇의 자세를 통해 간접적으로 연결되었었지만 갱산 단계를 수행하는 후에는 직접적으로 연결이 됩니다.
로봇의 자세 연결에서 두 특징쌍 연결로 정보의 변화는 SEIF의 핵심 요소로서 이전에 살펴본 EIF는 특징 쌍사이에 어떠한 연결을 다루지도 않았었습니다. 이것은 online SLAM 문제를 다루기 위해 정보 형태를 필터로 사용한 결과입니다. 이전의 모든 자세 변수들을 적분함으로서 이러한 링크들을 잃어버리지만, 이들은 정보 행렬의 특징 요소들사이에 영향을 주게 됩니다.
이 과정에서 특징쌍의 직접 연결을 얻기 위해서 갱신 전에 두개다 능동적이여야 하며, 정보 행렬상에서 이들을 로봇의 자세에 연결시키는 요소들은 0이 되어서는 안됩니다. 이는 그림 12.3에서 볼수 있는데, 특징 사이 연결은 특징 $y_1$과 $y_2$에서만 존재합니다. 특징 $y_3$은 활성상태가 아니므로 다뤄지지는 않습니다. 특정 시간에 활성 랜드마크의 수를 제어함으로서 동작 갱신의 계산 복잡도와 정보 행렬에서 연결의 수를 제어할수 있습니다. 만약 활성 링크의 수가 적게 유지된다면, 이는 동작 갱신시 갱신복잡도가 될것이며, 정보 행렬에서 랜드간의 요소들 중 0이아닌 값의 수가 될것입니다.
그림 12.4 희소화 : 특징은 로봇에대한 연결을 제거하여 비활성화가 되어집니다.
- 정보 상태에서 이 변화를 보완하기 위해서 활성 특징들사이에 또는 로봇과의 연결이 갱신됩니다. 전체 동작은 상수 시간에 수행됩니다.
SLAM 문제에서 정보 행렬은 근사적으로 희소합니다. 위에서 살펴보앗지만 정보 행렬은 근처에 존재하는 특징들 사이의 적은 수의 요소로 좌우되며, 멀리 떨어진 특징간의 연결은 비교적 작습니다.하지만 희소성은 근사치일 뿐이며 정확한것은 아닙니다. 그래서 SEIF는 희소화 단계를 다루는데 그림 12.4에서 볼수 있습니다. 의소화는 로봇과 활성 특징사이의 연결 제거도 다루는데, 효과적으로 활성 특징을 수동 상태로 변경하게 됩니다. SEIF에서 이러한 제거는 정보를 이웃한 링크, 즉 다른 활성 특징과 로봇의 자세 사이의 링크로 재배포를 유도하고, 희소화 수행 시간은 지도의 크기에 독립이 됩니다. 하지만 이는 근사화로 로봇의 사후 확률에서 정보 손실이 발생합니다. 이 근사화의 이점은 실제 희소함을 구하여, 필터를 효율적으로 갱신할수 있게 해줍니다.
여기에 SEIF 알고리즘의 마지막 단계가 존재하는데, 여기서는 그림으로 구하지는 않았습니다. 이 단계에서는 그래프를 통해 평균 추정치의 전파를 다룹니다. 3장에서 살펴봤지만 확장 정보 필터는 동작과 갱신 모델의 선형화를 위해 상태 $\mu_t$의 추정치를 필요로 합니다. SEIF도 이런 희소화 단계에서 상태 추정치가 필요합니다.
$\Omega$는 정보 벡터 $\xi$가 정보 행렬인 상태에서 식 $\mu$ = $\Omega^{-1}$ $\xi$로 추정 상태를 복원할수 있습니다. 하지만 이는 큰 행렬의 역행을 필요로하며 SEIF를 비효율적으로 수행하게 됩니다. SEIF는 정보 그래프를 통해 효과적으로 상태 추정치를 전파해가는 반복적이 ㄴ알고리즘으로 이 단계를 피해갈수 있습니다. 각 지역 상태 추정치는 정보 그래프에서 이웃의 최적의 추정치에 기반하여 갱신됩니다. 이 반복하는 알고리즘은 실제 평균인 $\mu$에 수렴하게 됩니다. 이러한 정보 형태는 SEIF에서 희소하기 때문에 각 갱신은 상수 시간을 필요로 하며, 많은 유한개의 갱신이 수행되어야 하는 경우에 좋은 결과를 얻을수 있습니다. 이 계산이 상태 공간의 크기에 독립하기 위해서는 SEIF는 반복시에는 고정된 개수의 갱신을 수행합니다. 상태 벡터 결과는 근사치일 뿐으로 모든 갱신 단계에서 평균을 근사화한것 대신에 사용됩니디ㅏ.
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 문제에 있어서 첫번째로 효율적인 온라인 알고리즘이 되었습니다.
그림 11.1 그라운드호그 로봇. 1500파운트 차량으로 온보드 컴퓨터와 레이저 샌서, 가스 센서, 비디오 저장 장치 등이 장착되어 있습니다. 이 로봇은 버려진 광산에 들어가 지도를 작성하였습니다.
이번 장을 정리하면 EIF SLAM 구현에 있어서 경험적인 결과를 강조하였습니다. 그림 11.1은 실험에서 사용한 차량으로 버려진 광산에서 지도 작성을 수행하였습니다.
그림 11.2 광산에서 쌍 스캔 매칭으로 얻은 지도. 이 환경의 직경은 250미터 정도 되며, 여러개의 복도에서 불일치가 발생한것을 명확하게 볼수 있습니다.
로봇이 수집한 지도 타입은 11.2에서 볼수 있는데, 이 지도는 점유 격자 지도로 로봇의 자세를 복원하여 쌍 스캔 매칭을 사용해 만들었습니다. 쌍 스캔 매칭은 EIF SLAM의 버전으로 대응관계는 연속적인 스캔들사이에서 즉시 만들어집니다. 이 방법의 결과는 그림 11.2의 지도에서 명확한 결함을 보여주고 있습니다.
그림 11.3 광산 지도 스캘래톤, 지역 지도를 시각화하였음.
EIF SLAM 알고리즘을 적용하기 위해, 개발한 소프트웨어로 지도를 작은 하부 지도로 5m에 한개로 나누었습니다. 이 5미터 안에서는 충분히 작은데, 일반적으로 드리프트가 작기 때문이며, 그래서 스캔 매칭 데이터 연관 기술은 결함없이 수행되어 집니다. 각 하부 지도의 좌표계는 EIF SLAM의 자세 노드가 되고, 인접한 하부지도간에 이들 사이에 동작 제약조건으로 연결 됩니다. 이 구조의 결과는 그림 11.3과 같습니다.
그림 11.4 데이터 연관 탐색
다음으로 재귀적인 데이터 연관 탐색을 적용하였습니다. 두 겹쳐진 지도 사이 상관관계 분석을 사용하여 대응관계 시험이 구현되었으며 가우시안 매칭 제약조건이 가우시안을 이용한 이 매치함수를 근사화하여 복원되었습니다. 그림 11.4는 이 데이터 연관 과정을 보여주고 있습니다. 각 원들은 새 재약조건에 대응하며, 이들은 EIF의 정보 형태를 계산할때 생기게 됩니다. 이 그림은 반복함으로서 탐색을 보여주고 있는데, 특정한 대응관계는 다른게 진행되고 다른것들은 탐색되지 않은 경우 발견되기도 합니다.
그림 11.5 데이터 연관에 대해 최적화 수행후 최종적인 지도
마지막 모델이 안정적이므로 추가적인 데이터 연관이 수행되지 않습니다. 이를 그리드 맵상으로 표시하면 2차원 지도가 그림 11.5와 같이 나오게 됩니다. 이 지도는 (지역 지도 제약 조건 매칭을 기본적으로 구현했기 때문에) 완벽하지는 않지만 이전에 스캔 매칭을 사용한것보다는 나은 결과를 보여주고 있습니다.
11.8 정리
이번 장에서는 완전 슬램 문제를 다루기위한 확장 정보 필터 EIF에 대해 살펴보았습니다.
- EIF SLAM 알고리즘은 완전 슬램 문제를 고려한 것으로, 지도와 함께 전체 로봇의 경로에 대한 사후확률들을 계산합니다. 그러므로 EIF SLAM은 배치 알고리즘으로 EKF SLAM과 같은 온라인 알고리즘이 아닙니다.
- EIF SLAM알고리즘의 핵심은 정보의 구조가 희소하다는 점인데
-> 관측들은 측정 시간 당시에 로봇의 자세에 대해 상대적인 특징들의 정보를 전달합니다. 정보 공간상에서 이들은 변 수 쌍 간의 제약관계를 형성하게 됩니다.
-> 비슷하게 동작은 연속적인 2 자세간의 정보를 제공하게 됩니다. 정보 공간 상에서 각 동작 명령은 연속적인 두 자세 변수간에 제약관계를 형성하게 됩니다.
EIF SLAM은 모든 정보를 기록하고, 자세와 특징 그리고 이어지는 자세 쌍 사이의 연결이 정의 됩니다. 하지만 이 정보 표현법은 지도나 로봇 경로에 대한 근사치를 제공하지는 않습니다.
- EIF SLAM 알고리즘은 다음의 3단계를 반복하여 지도 복원을 수행합니다. 우선 태일러 전개를 통해 선형 정보 형태를 만듭니다. 다음으로 이 형태를 축소시키고, 최적화 문제를 해결을 수행합니다. 이 3단계는 정보를 효율적으로 다루게되는데, 경로와 지도에 대해 일관된 확률적 사후확률을 만들어 냅니다. EIF SLAM이 배치로 수행되므로 선형화 단계를 반복하여 더나은 결과를 점차 얻을수 있습니다.
- EIF SLAM에서 대이터 연관은 동일한 좌표계를 가지는 두 특징의 확률을 계산하여 수행됩니다. EIF SLAM은 배치 알고리즘으로 쌍 특징을 이용할수 있는데, 이는 모든 데이터 연관 변수에 대해 반복 탐용 탐색 알고리즘을 수행하고, 재귀적으로 특징의 쌍을 식별합니다.
- EIF SLAM을 현실적으로 구현에 있어서 계산량을 적게 유지하고, 잘못된 정보 연관을 피하기 위해 추가적인 트릭을 사용합니다. 특히 현실적인 구현에서 지역 지도를 추출하고 각 지도를 기본 개체로 사용하여 데이터 복잡도를 줄이는 경향이 있씁니다. 이들은 여러 특징들을 매치 시키고 부정적인 정보를 데이터 연관시에 고려합니다.
- 분해를 이용한 EIF SLAM의 변형으로 거리 스캔을 이용한 점유 격자 지도로 결과를 만들었습니다. 여기서 근사화에도 불구하고 EIF 데이터 연관과 추론이 넓은 범위의 맵핑 문제에서 좋은 결과를 구할수 있었습니다.
EIF에서 정보 연관은 EKF SLAM처럼 대응 변수들을 통해 구할수 있습니다. EKF SLAM에서와 마찬가지로 EIF는 최적의 단일 대응 벡터를 탐색합니다. 이 대응관계 백터를 찾는 찾는 과정은 탐색 문제가 됩니다. 하지만 EIF SLAM에서 대응관계들은 약간 다르게 정의되는데, 이들은 특징에 대한 관측치들의 연관 보다 지도상에 특징의 쌍으로 정의가 됩니다. 자세하게 보면 , $m_j$와 $m_k$ 현실에서 물리적으로 같은 특징을 나타낸다면 c(j, k) =1이라 할수 있습니다. 그렇지 않는다면 c(j, k) = 0이 됩니다. 이 특징 대응관계는 이전에 살펴봤던 대응관계에 대한 정의와 논리적으로 동일하지만 기본 알고리즘에 대해 간소화 시킨것입니다.
우리가 대응관계 공간 탐색하기 위해 사용할 기술은 탐욕으로 EKF에서 했던것과 같습니다. 최적의 대응관계 값의 탐색에 있어서 각 단계는 적절한 로그우도함수에의해 개선되게 됩니다. 하지만 EIF는 동시에 모든 데이터를 고려하기 때문에 EKF 처럼 증가하는것보다 상당히 효과적인 대응관계 기술로 고칠수 있습니다. 자세히 설명하면
1. 탐색시 어느점에서, EIF는 랜드마크의 어느 집합의 대응관계들을 고려할수 있으며, 관측된 랜드마크를 순차적으로 처리하기위해 요구하는게 없습니다.
2. 대응관계 탐색에서 지도 계산이 끼워질 수 있는데, 두 관측된 랜드마크를 동일한 물리적인 랜드마크로 가정하는것이 결과 지도에 영향을 끼치게 됩니다. 이러한 대응관계 가정을 지도에 반영함으로서, 다른 대응관계 가정들이 순차적으로 더 확률이 높아지거나 낮아지게 됩니다.
3. EIF에서 대응관계 결정은 수행되지 않을수 있습니다. 이 데이터 연관의 좋은점은 다른 데이터 연관 결정의 값에 의존하는 것이고, 이후 탐색 중에 좋은 선택을 찾을수도 있습니다.
이번 장에서는 우선 한두가지의 설정들을 따르는 대응관계 탐색 알고리즘을 설명하겠습니다. 여기서 사용할 데이터 연관 알고리즘은 탐욕 알고리즘으로, 순차적으로 가능한 대응관계 공간을 탐색할것입니다. 하지만 모든 탐욕 알고리즘처럼 이 접근 방법은 지역 최대점에 영향을 주게되며, 대응관계의 실제 공간이 지도상에 존재하는 특징 수에 지수적이게 되고, 이들을 이용한 탐색은 대부분의 환경에서 실행할수 없습니다. 그래서 이것을 언덕 오르기 알고리즘에 대해서도 다루겠습니다.
11.5.1 대응관계가 주어지지 않을때 EIF SLAM 알고리즘
이 알고리즘의 주요 요소는 대응관계에 대한 우도 시험이 있습니다. 자세하게 보면 EIF 대응관계는 단순한 시험에 기반을하는데, 지도 상에 존재하는 다른 두 특징 $m_j$와 $m_k$가 실제 세계에서 동일한 물리적 특징을 나타낼 확률이 얼마나 될까요? 만약 이 확률이 임계치를 초과하면 이 가정을 따를것이고 두 특징은 지도상에서 합쳐지게 될것입니다.
표 11.8 EIF SLAM 대응관계 시험. 입력으로 SLAM 사후확률의 정보 표현법과 EIF sovle 단계의 결과가 사용됩니다. 그리고 출력은 $m_j$가 $m_k$에 대응하는 사후확률이 됩니다.
표 11.8에서 이 대응시험을 보여주고 있습니다. 이 시험에서 입력은 두 특징의 인덱스로 j와 k이며, 두 특징이 물리적 세계에서 동일한 특징인지에 대한 확률을 계산할것입니다. 이 확률을 계산하기 위해서 이 알고리즘은 많은 수치들을 사용할것인데, SLAM 사후확률의 정보 표현법인 $\Omega$와 $\xi$와 EIF solve 과정의 결과인 평균 벡터 $\mu$와 경로 공분산 $\Sigma_{0:t}$이 됩니다.
대응관계 시험은 다음의 방법으로 수행이 됩니다. 우선 두 타겟 특징에 대한 주변 사후확률을 계산합니다. 이 사후확률은 정보 행렬 $\Omega_{[j, k]}$와 벡터 $\xi_{[j, k]}$로 2,3번째 줄에서 계산되어 구합니다. 이 계산 단계는 정보 형태의 많은 내부 요소들을 사용합니다.
다음으로 새 가우시안 확률 변수의 파라미터를 계싼하는데 이 변수의 값은 $m_j$와 $m_k$ 차이가 됩니다. 이 차이를 $\Delta_{j, k}$ = $m_j$ - $m_k$라 표기하고, 정보 파라미터 $\Omega_{\Delta j, k}$, $\xi_{\Delta j, k}$는 4, 5번째 줄에서 계산됩니다. 이 차이에 대한 대응 기대값은 6번째 줄에서 계산되어, 마지막 7번째 줄에서 원하던 확률이 반환됩니다. 이 확률은 $m_j$와 $m_k$의 차이가 0일 확률을 나타냅니다.
표 11.9 대응관계가 주어지지 않는 완전 SLAM 문제를 다루기위한 EIF SLAM알고리즘.
- 이 버전의 내부 루프는 특징쌍 $m_j$, $m_k$를 선택적으로 탐색하거나 방정식 집합의 결과를 구하기 전에 다중 대응관계를 구함으로서 더 효율적으로 만들 수 있습니다.
이 대응관계 시험은 EIF SLAM에서 데이터 연관 탐색을 수행하기위한 알고리즘을 제공하며 표 11.9와 같은 알고리즘을 보여주고 있습니다. 이 알고리즘은 대응관계 변수를 유니크한값으로 초기화 시키고, 다음의 3~7번째 줄사이의 4과정이 수행되는데 표 11.5에서 살펴본 대응관계가 주어진 경우 EIF SLAM 알고리즘과 동일 합니다. 하지만 이 기본 SLAM 알고리즘은 그러고 나서 데이터 연관 탐색이 수행됩니다. 지도에 존재하는 다른 특징 쌍 각각에 대해 이 알고리즘은 9번째 줄에서 대응 관계의 확률을 계산하고, 이 확률이 임계치 $\chi$를 초과한다면 이 대응관계 백터는 동일한 값을 가지게 됩니다 (11번째 줄). EIF SLAM 알고리즘은 그러고나서 생성, 축소, SLAM 사후확률 풀기 등의 과정을 반복하고(12 ~ 14번째 줄). 이 결과에 따라 차후에 수행되는 대응관계 시험은 이전의 대응관계 결정에 따라 새롭게 작성한 지도에 반영됩니다. 이 지도 생성은 더이상 내부 루프에서 추가적인 특징이 발견되지 않는다면 종료 됩니다.
EIF SLAM 알고리즘은 효율적이지는 않습니다. 이는 하나 뿐만이 아니라 모든 대응관계 특징 쌍을 시험하고, 더나아가 단일 대응관계가 찾아질때마다 지도를 다시 만들게 됩니다. 하지만 이런 변경은 상대적으로 직관적이며 EIF SLAM의 좋은 예시는 이 기본 구현체를 이용해서 재정의 할수 있습니다.
11. 확장 정보 형태 알고리즘 extended information form algorithm
11.1 소개
이전에 살펴본 EKF SLAM은 수많은 한계점들을 가지고 있습니다. 이번에는 다른 방법인 확장 정보 형태 SLAM 알고리즘 extended information form SLAM algorithm EIF SLAM에 대해서 살펴보겠습니다. EIF SLAM은 가우시안으로 사후확률을 나타내는 EKF처럼 흔하게 사용되며, 온라인 슬램 문제를 푸는 EKF SLAM과 다르게 EIF SLAM은 완전 슬램 문제를 풀게 됩니다. 이전에 보았지만 온라인 슬램 사후확률은 지도가 주어질때 가장 최근 로봇의 자세로 정의하였고, 완전 슬램의 사후확률은 지도가 주어진대에 대해 전체 로봇의 경로를 정의하였었습니다. 다른 중요한 차이는 EIF SLAM은 정보 행렬과 정보 상태로 이루어진 정보 형태로 가우시안 사후확률을 표현한다는 점입니다. 명확하게, 정보와 모멘트 표현법은 같은 정보를 전달하지만, 정보 형태의 갱신 동작이 EKF와 다르게 동작합니다.
EIF SLAM은 증가하는 알고리즘이 아닌데, 이는 로봇 경로에 대한 사후확률을 구하기 때문입니다. 대신 EIF SLAM은 완전 슬램 사후확률을 구하기 위해 전체 데이터 집합을 처리하게 됩니다. 이 접근 방법은 증가하면서 로봇이 지도를 갱신했던던 EKF SLAM과는 근본적으로 다릅니다. EIF SLAM은 고정된 크기의 데이터셋으로부터 지도를 작성하고, 데이터를 메모리에 유지시킬 여유가 있는경우 가장 적합한 방법이 됩니다.
EIF SLAM은 지도 작성하는 동안 모든 데이터를 가지므로, 개선된 선형화와 데이터 연관 기술들을 적용할수 있습니다. 반면에 EKF SLAM에서 관측에 대한 선형화와 대응관계가 시간 t의 데이터를 기반으로 계산하였던것과는 다르게 EIF SLAM은 모든 데이터를 선형화와 대응관계 계산에 사용합니다.
더 나아가 EIF SLAM은 지도 작성과 대응관계 변수 계산, 관측 모델과 동작 모델의 선형화 등 최적의 근사치를 얻기위한 작업들을 반복하면서 EKF 보다 더 정확한 지도를 만들게 됩니다. EIF SLAM은 잘못된 데이터 연관시에 덜 불안정해지며, EKF SLAM보다 더 큰 회전 불확실성에 대처할 수 있습니다. 마지막으로 EIF SLAM은 EKF에서 사용했던것보다 더 큰 크기의 지도에 사용할수 있게 됩니다.
이번 장에서는 EIF SLAM에 대해 간략한 설명과 기본 갱신 단계를 우선 다루어보갰습니다. 그러고 나서 수학적으로 다양한 갱신 단계들을 구하고 선형 가정에서 올바르게 구한것인지 증명하겠습니다. 지도가 주어질때 사후확률을 계산할수 있도록 실제 구현하는 과정에 대해 살펴봅시다.
11.2 개요 설명
EIF SLAM의 개본 개념은 매우 간단합니다. 우선 연관 대응 변수 $c_{1:t}$와 관측치 집합 $z_{1:t}$, 제어 집합 $u_{1:t}$가 주어졌다고 가정해봅시다. EIF SLAM의 첫 단계는 이러한 데이터를 사용하여 지도 m = {$m_j$}와 로봇 자세 $x_{1:t}$의 결합 공간에 대한 정보 행렬과 정보 벡터를 만들게 됩니다. 여기서 정보 행렬을 $\Omega$, 정보 벡터를 $\xi$라고 표기하겠습니다. 아래에서 보면 각각의 측정과 제어는 $\Omega$와 $\xi$의 지역적인 갱신을 수행시키는데, 제어나 관측치를 $\Omega$, $\xi$에 반영하는것은 지역적인 추가가 되어 정보는 추가되는 양으로서 중요한 역활을 하게 됩니다.
관측치 $z_t^i$로 살펴보겠습니다. 이 관측치는 시간 t에 대해 로봇의 자세 $x_t$와 랜드마크 j = $c_t^i$의 위치 사이의 정보를 제공하고 있습니다. 이 정보는 일종의 제약조건으로 생각할수 있는데, EIF에서 각 갱신들은 자세 $x_t$와 지도 특징 $m_j$의 연결 요소들 사이에 값을 더하는것이라 할수 있습니다. 이러한 값의 크기는 관측 노이즈 때문에 불확실성을 반영하게 되며, 센서의 노이즈가 작을수록 $\Omega$와 $\xi$에 더해지는 값이 커지게 됩니다.
모든 관측 $z_{1:t}$와 제어 $u_{1:t}$를 합친 후에 정보 행렬 $\Omega$를 얻게 되는데, 이 행렬의 비대각 요소는 2가지를 제외하고 모두 0이 됩니다. 두 연속적인 자세 $x_{t-1}$과 $x_t$사이에 0이 아닌 값이 되는데 이는 제어 $u_t$에 의한 정보 연결을 의미하고, 로봇이 $x_t$에 서 특징 $m_j$가 관측되었을때 지도 특징 $m_j$와 자세 $x_t$사이를 나타내는 요소도 0이 아닌 값이 됩니다. 이는 상대적인 위치에 대한 정보를 얻는것이 아니라 SLAM을 통해 얻는 것들은 로봇의 자세에 상대적인 랜드마크의 위치 제약을 나타내는 관측치만을 얻을 수 있습니다. 그래서 정보 행렬은 희소하게 되며, 많은 선형 요소들이 0이 됩니다.
물론 정보 표현법은 지도를 주지 않으며 로봇의 추정 경로를 알려준다고 할수 없습니다. 이 둘다는 $\mu$ = $\Omega^{-1}$ $\xi$(식 3.72)로 구할수 있는데, 이 연산은 희소 행렬의 역을 포함하고 있으며 이는 얼마나 효율적으로 지도와 사후확률 $\Sigma$를 복원할수 있을까 에 대한 질문을 주게 됩니다. 이는 EIF SLAM의 핵심저인 질문으로 EIF는 수백만개의 특징으로 이루어진 지도에 적용되고, 이 크기의 역행렬을 계산하는건 어려울 것입니다.
이런 복잡도 질문에 대한 답은 위상에 의존하게 되는데, 특징이 한번만 보여진다면 $\Omega$에서의 제약을 나타내는 그래프는 선형이 될겁니다. 그래서 $\Omega$는 밴드 대각 행렬이 되도록 재정렬할수 있고, 모든 0이 아닌 값들은 대각 근처에 존재하게 됩니다. 이러한 역행렬의 표준 변수 제거 기술은 $\Omega$를 한번 돌면서 선형 시간에서 $\Omega$를 뒤집어 버리고,이는 한번 가로질러지는 사이클이 없는 공간에 대해 연속적인 시간동안 짧게 각 특징들이 보여집니다.
하지만 더 일반적인 경우는 긴 시간 딜레이를 가지는 여러 시간동안 관측된 특징들을 다루는데, 로봇이 복도를 갔다 오거나 사이클이 존재하는 경우, 로봇이 완전 사이클로 돈 경우가 이런 경우라 할수 있겠습니다. 이런 경우에 매우 다른 시간 간격 $x_{t1}$, $x_{t_2}$ , $t_2$ >> $t_1$을 두는 특징 $m_j$가 존재할수도 있습니다. 우리가 사용할 제약 그래프 constraint graph에서 이 사이클 의존성을 소개할건데 $x_{t1}$과 $x_{t2}$는 제어 $u_{t1 + 1}$, $u_{t1 + 1}$, ..., $u_{t2}$의 시퀀스와 $x_{t1}$, $m_{j}$, $x_{t2}$의 결합 관측 링크 전반에 연결 됩니다. 이러한 연결은 선형 행렬 역행의 트릭을 사용할수 없게 만들며, 역행렬은 더 복잡해집니다. 많은 세상이 사이클을 가지고 있으므로 흥미로운 경우가 됩니다.
중략
11.3 EIF SLAM 알고리즘
이제 EIF SLAM을 계산하는 단계들을 다뤄보겠습니다. 완전 EIF 슬램 알고리즘은 수많은 단계로 이루어지는데, 추가 정보 알고리즘 구현에 있어서 주된 어려움은 조건부 확률 p($z_t^i$ | $x_t$, m)과 p($x_t$ | $u_t$, $x_{t-1}$)를 정보 행렬에서의 링크로 유지시키는 것인데, 이 정보 행렬 요소들은 모두 선형이며, 그래서 이 단계는 p($z_t^i$ | $x_t$, m)과 p($x_t$ | $u_t$, $x_{t-1}$)를 선형화하는 과정을 포함시킵니다. EKF SLAM 에서 이 선형화 과정을 근사 평균 자세 $\mu_{0:t}$에서 자코비안을 계산하면서 볼수 있었는데, 우리의 경우 초기 정보 행렬 $\Omega$와 $\xi$를 만들기 위해서 모든 자세 $x_{0:t}$에 대한 초기 근사 $\mu_{0:t}$가 필요합니다.
이 선형화에 적합한 초기 평균 $\mu$를 찾는 다양한 해결방법이 있는데, 예를들어 EKF SLAM을 실행하고 선형화한 근사치를 사용할수 있겠습니다. 이 장에서는 더 쉬운 방법을 사용할 것인데, 우리가 사용할 초기 근사치는 동작 모델 p($x_t$ | $u_t$, $x_{t-1}$)를 바꾸어서 구할수 있습니다. 표 11.1의 EIF initialize EIF 초기화가 이러한 알고리즘을 보여주고 있습니다.
표 11.1 EIF SLAM 알고리즘에서 평균 자세 백터 $\mu_{1:t}$ 초기화
이 알고리즘은 제어 $u_{1:t}$를 입력으로 가지며 결과는 추정 자세 시퀀스 $\mu_{0:t}$가 됩니다. 이 알고리즘은 우선 자세를 0으로 초기화하고, 속도 동작 모델을 사용하여 이후 동작들을 재귀적으로 계산합니다. 우리가 관심있는것은 평균 자세 백터 $\mu_{0:t}$이므로 EIF initialize는 동작 모델의 결정론적인 부분만을 사용하고, 근사에서 다른 관측치를 고려하지 않습니다.
초기 $\mu_{0:t}$이 주어지면, EIF SLAM 알고리즘은 완전 슬램 정보 행렬 $\Omega$와 대응 정보 벡터 $\xi$를 만듭니다. 이는 EIF construct 알고리즘으로 수행되며 표 11.2와 같습니다.
표 11.2 EIF 알고리즘에서 $\Omega$와 $\xi$ 계산
이 알고리즘은 많으며 좋은 수학적 표기들을 사용하는데, 아래의 알고리즘의 수학적 정리에서 명확하게 볼수 있습니다. EIF construct는 입력으로 제어 집합 $u_{1:t}$와 관측 $z_{1:t}$, 그리고 ㄱ연관 대응 변수 $c_{1:t}$와 평균 자세 근사치 $\mu_{0:t}$를 사용합니다. 그러면 각각의 관측치와 제어로 얻은 정보에 따라 지역적으로 내부 행렬들을 추가하여 정보 행렬 $\Omega$와 정보 벡터 $\xi$가 점차 만들어집니다.
부분적으로보면 EIF construct의 2번째 줄은 정보 요소를 초기화 시킵니다. 여기서 3번째 줄의 무한대 정보 요소들은 초기 자세 $x_0$에서 (0 0 0$)^T$로 고정시킵니다. 이는 상대 정보만으로 절대 근사치를 복원할수 없는 사실을 반영하기 때문에 결과 행렬이 특이해가 되므로 필요합니다.
EIF construct의 4 ~ 9번째 줄은 제어치들이 합쳐지게 됩니다. 자세 $\hat{x}$와 자코비안 $G_t$가 5, 6번째 줄에서 계산되고 이는 비선형 관측함수 g의 선형 근사를 의미합니다. 이러한 방정식들로부터 명확한점은 이 선형화 단계는 $\mu_0$ = (0 0 0$)^T$과 자세 근사치 $\mu_{0:t-1}$를 사용하며 7,8번째줄에서 $\Omega$, $\xi$를 갱신하게 됩니다. 두 항은 $\Omega$와 $\xi$의 대응하는 행과 열에 추가 됩니다. 이 추가된 값은 새로운 제약조건을 SLAM 사후확률에 포함시키는 것으로 이전 색션에서 자세하게 살펴보았습니다.
EIF construct의 10 ~ 21번째 줄은 관측치가 합쳐지고 있습니다. 11번째 줄에서 계산된 행렬 $Q_t$는 측정 노이즈 공분산이며, 13 ~ 17번째 줄에서 관측 함수의 태일러 전계를 계산하고 있습니다. 이 계산은 18, 19번째 줄에서 관측 갱신 계산에 반영하면서 끝나게 됩니다. 18번째 줄의 $\Omega$에서 다루는 행렬은 5 x 5 차원으로 이루어지는데, 이 행렬을 추가시키기 위해 3 x 3차원의 자세 $x_t$에 대한 행렬과 2 x 2차원 특징 $m_j$의 행렬, 그리고 $x_t$와 $m_j$ 사이의 링크에 대한 3 x 2, 2 x 3차원의 두 행렬로 분해됩니다. 이 행렬들은 $\Omega$의 올바른 행과 열에 더해지게 되며, 벡터 또한 정보 벡터 $\xi$에 더하게 됩니다. 이 또한 크기가 3과 2인 두 벡터로 분해하여 $x_t$와 $m_j$에 대한 요소로서 더할수 있습니다.
EIF construct의 결과는 정보 벡터 $\xi$와 정보 행렬 $\Omega$가 됩니다. $\Omega$는 경로들 사이, 그리고 자세와 특징 사이에서 주대각성분을따라 0이아닌 하부 행렬들을 가지는 희소행렬이 됩니다. 만약 지도 특징의 수가 자세보다 10배 정도 크다면, $\Omega$의 99% 요소들이 0이 됩니다. 이 알고리즘의 동작 시간은 t에 대해 선형이 됩니다.
표 11.3 사후확률의 정보 표현 크기를 줄이기 위한 알고리즘
EIF SLAM 알고리즘의 다음 단계는 정보 행렬/백터의 차원을 줄이는것으로 이는 표 11.3의 EIF reduce알고리즘으로 수행됩니다. 이 알고리즘은 입력으로 모든 자세와 특징에 대해 정의된 $\Omega$와 $\xi$을 사용하며, 출력은 축소된 $\widetilde{\Omega}$와 $\widetilde{\xi}$으로 모든 자세에 대해 정의됩니다. 이 변환은 EIF reduce의 4 ~ 9번째 줄에서 시간마다 특징 $m_j$를 제거하여 수행됩니다.
생략
EIF SLAM 알고리즘에서 마지막 단계는 로봇의 주행 경로상에 모든 자세에 대한 평균과 공분산, 그리고 지도 상에 존대하는 모든 특징들의 평균 위치 근사치를 계산하게 됩니다. 이는 표 11.4의 EIF solve에서 수행됩니다. 2, 3번째 줄은 $\widetilde{\Omega}$를 역변환하고, 정보 벡터와 공분산을 곱함으로서 경로 추정 $\mu_{0:t}$를 계산합니다. $\widetilde{\Omega}$에 사이클이 존재할때 이 역변환은 EIF SLAM 알고리즘에서 계산상에서 더 비용이 커지게 됩니다. 다음으로 EIF solve는 4 ~ 7번째 줄 사이에서 각 특징들의 위치를 계산하며, 반환 값은 로봇의 경로와 지도상에 존재하는 모든 특징을 포함하나 공분산은 로봇의 경로에 대한것만 존재합니다.
EIF SLAM 알고리즘의 결과 퀄리티는 EIF initialize로 계산된 초기 평균 추정치가 좋은지에 따라 결정되는데, 이 추정치의 x y 요소들이 선형으로 각 모델에 영향을 주어, 선형화는 이들의 값에 의존하지는 않습니다. 초기 추정치에서 에러는 테일러 근사의 정확도에 영향을 주어 회전시 결과에 영향을 줍니다.
초기 $\mu_{0:t}$의 에러를 보완하기 위해서 EIF construct, EIF reduce, EIF solve를 같은 데이터셋을 이용하여 여러번 돌리면 되는데, 각 반복시 입력은 모든 자세에 대한 평균 추정 벡터 $\mu_{0:t}$와 출력은 개선된 추정치가 됩니다. EIF SLAM 최적화 반복은 초기 자세 추정치가 높은 경우(방위 에러가 20도 이상인 경우)에만 필수적이며, 반복 횟수가 작더라도 충분합니다.(3번 정도)
표 11.5는 이 알고리즘의 결과를 요약하였습니다. 평균으로 초기화 시키고, 생성 단계와 축소, 해결 단계들을 반복하며 2~3번 정도 반복을 수행하면 충분합니다. 결과로 구한 $\mu$는 로봇의 경로와 지도에 대한 최적의 추정치가 됩니다.
칼만필터의 쌍둥이로 정보 필터가 있습니다. 이는 칼만필터와 그의 비선형 버전인 EKF 처럼 정보필터 IF는 가우시안으로 신뢰도를 나타냅니다. 그래서 표준 정보필터는 칼만필터와 동일한 가정을 따르게 됩니다. 칼만 피렅와 정보 필터사이의 큰 차이는 가우시안 신뢰도가 표현되는 방법인데, 칼만 필터 알고리즘 군에서는 가우시안이 모멘트(평균, 공분산)으로 표현되는 반면에, 정보 필터는 가우시안을 표준 표현법인 정보 행렬과 정보 백터로 표현합니다. 이 표현법의 차이는 다른 갱신 방정식을 만드는데, 하나의 표현법이 계산상으로 복잡하다면 다른것은 단순하다고 할수있습니다. 표준 표현법과 모멘트 표현법은 서로 서로의 쌍둥이라고 하며 그래서 IF와 KF가 됩니다.
3.4.1 표준 표현법 canonical representation
다변수 가우시안의 표준 표현법은 행렬 $\Omega$와 행렬 $\xi$로 나타낼수 있습니다. 행렬 $\Omega$는 역 공분산 행렬로 아래와 같으며 $\Omega$는 정보 행렬 information matrix나 정밀 행렬 precision matrix라 불립니다.
벡터 $\xi$는 정보 벡터 information vector로 다음과 같이 정의됩니다.
$\Omega$와 $\xi$는 가우시안의 파라미터로 볼수 있습니다. 특히 가우시안의 평균과 공분산은 표준 표현법 (3.65)와 (3.66)의 역으로 쉽게 얻을수 있습니다.
표준 표현법은 가우시안의 지수를 곱하여 구할수 있는데, 일단 식 (3.1)에서 다변수 정규 분포를 다음과 같이 정의하였습니다.
다음의 직관적인 변환으로 아래의 파라미터화를 할수 있고,
여기서 "const"라고 라밸한 항은 목표 변수 x에 의존하지 않으므로 이를 정규자 $\eta$에 포함시키겠습니다.
이형태는 정규 파라미터 $\Omega$와 $\xi$으로 가우시안을 파라미터화 시키게 됩니다.
많은 경우 표준 표현법이 모멘트 표현법보다 더 명쾌한데, 가우시안의 부정 로가리즘은 표준 파라미터 $\Omega$와 $\xi$에 대한 이차 함수가 됩니다. 여기서 "const"는 상수 입니다.
여기서 왜 이 상수를 $\eta$로 표기하지 않는지 궁금할수 있는데 확률의 부정 로가리즘은 1로 정규화 할수 없기 때문입니다. 확률 분포 p(x)의 부정 로가리즘은 x에서 이차적이며 이차 항은 $\Omega$로, 선형 항은 $\xi$로 나타냅니다. 가우시안에서 $\Omega$는 양의 준정부호 positive semidefinite여야만 하는데, 그래서 - log p(x)는 평균 $\mu$ = $\Omega^-1$ $\xi$인 이차 거리함수가 됩니다. 이는 식 3.73의 일차 미분을 0으로 할때 쉽게 구할수있습니다.
행렬 $\Omega$는 다른차원의 변수 x에서 거리 함수가 증가시키는 비율을 결정합니다. 이 행렬 $\Omega$로 가중되는 이차 거리를 마할라 노비스 거리라고 부릅니다.
3.4.2 정보 필터 알고리즘
표 3.4 정보 필터 IF 알고리즘
표 3.4는 정보 필터라는 갱신 알고리즘을 보여주고 있습니다. 여기서 입력은 표준 표현법의 가우시안인 $\xi_{}t-1$과 $\Omega_{t-1}$로 시간이 t-1일때 신뢰도를 나타내는 값이 됩니다. 베이지안 필터에서 입력을 제어 $u_t$, 측정 $z_t$로 한것과 동일합니다. 출력은 갱신되는 가우시안의 파라미터인 $\xi_t$와 $\Omega_t$가 됩니다.
갱신과정에서 행렬 $A_t$, $B_t$, $C_t$, $R_t$, $Q_t$를 포함하는데, 이들은 3.2장에서 정의하였었습니다. 정보 필터는 상태 전이와 측정 핼렬은 다음의 선형 가우시안 가정을 따르며, 식 (3.2)와 (3.5)에서 정의하였었습니다.
여기서 $R_t$, $Q_t$는 0평균 노이즈 변수 $\varepsilon$, $\delta$의 공분산이 됩니다.
칼만피렅와 마찬가지로 정보 행렬은 두 단계로 갱신이 수행되며, 예측 단계와 측정 갱신 단계로 이루어집니다. 예측 단계는 2, 3번째 줄에서 구현되었으며 여기서 파라미터 $\bar{\xi_{t}}$, $\bar_{\Omega_{t}}$는 제어 $u_t$를 반영한 후, 관측 $z_t$를 반영하기 전인 $x_t$에 대한 가우시안 신뢰도를 의미합니다. 후자는 4,5줄에서 수행되며 이 신뢰도는 관측 $z_t$에 딸 ㅏ갱신되어 집니다.
여기서 두 갱신 단계는 상태 공간이 많은 차원을 다룬다면 복잡도가 달라질수 있습니다. 표 3.4의 예측 과정에서 크기가 n x n인 행렬의 역을 포함하고 있어 이 역행렬은 O($n^{2.8}$)시간을 요구하게 됩니다. 칼만필터에서 갱신 시간은 더 들어서 O($n^2$)이 필요하였으며, 일부 변수만 제어의 영향을 받는다면 더 적은 시간이 소요되게 합니다. 이 역활은 갱신단계에서는 뒤집어 지는데 관측 갱신에서 정보 필터가 추가적인 시간이 필요하게 되어 O($n^2$) 시간을 소모하게 되어 상태 변수의 일부 정보만 관측이 전달하는 경우 더 효울적으로 됩니다. 관측 갱신은 칼만 필터에서 더어렵게 수행됩니다.
