확률적 로봇공학 - 4 비모수적 필터

 

4 비모수적 필터 Nonparametric filters

 가우시안 기술을 대신하는 것으로 비모수적 필터가 있습니다. 비 모스적 필터는 가우시안 같은 고정된 형태의 사후확률에 의존하지 않고 대신 상태 공간 영역에서 각각에 대해 유한개의 수의 사후확률들을 근사화 시킵니다. 일부 비모수적 베이즈 필터는 상태 공간의 하부 영역에 대한 사후 밀도의 누적 함수로 상태 공간을 분해하여 활용하기도 합니다. 다른 것들은 사후 확률 분포로부터 임의의 샘플을 이용하여 상태 공간을 근사화 시킵니다. 이러한 경우에는 사후 확률을 근사화 시키기 위해 사용하는 파라미터의 갯수가 달라질 수 있습니다. 근사의 퀄리티는 이러한 사후확률을 나타내기 위해 사용하는 파라미터의 수에 따라 정해지며 파라미터의 수가 무한대에 갈수록 비모수적 기술은 정확한 사후 확률로 응집하게 됩니다.

 

 이번 장에서는 연속 공간에서 사후확률을 근사화 하는 두가지 비모수적 접근방법을 살펴보겠습니다. 첫번째는 상태 공간을 유한개의 영역으로 분해하고, 히스토그램으로 사후확률을 나타내는 방법으로 히스토그램은 각 영역에 대해 누적 단일 누적 확률 분포를 놓습니다. 이들은 연속 영역에 있어서 근사화에 있어서 최고의 방법으로 여겨지고 있습니다. 두번째 방법으로 유한한 많은 샘플들로 사후확률을 구하는 방법인데, 이를 파티클 필터라 하며 특정 로봇 공학 문제에 있어서 유용하게 사용되고 있습니다.

 

 히스토그램과 파티클 필터 둘다 사후 확률 밀도에 대한 강한 파라미터 가정을 만들지는 않고, 대신 그들은 멀티모달 신뢰도를 나타내는데 적합합니다. 이러한 이유로 전역적인 불확실성을 다룰 때나 서로 나누어 구분하기 힘든 데이터를 다룰때  사용됩니다. 하지만, 이러한 기술 가장 큰 장점은 계산량인데, 이번 장에서 설명하는 비모수적인 방법들은 사후확률의 복잡도에 따라 파라미터의 수를 조절할 수 있습니다. 사후 확률이 복잡하지 않을때(불확실성이 낮은 단일 상태를 구하는 경우), 적은 수의 파라미터만 사용하면 되고, 사후확률이 복잡한 경우(상태 공간 상에서 다양한 사후확률들을 구할 때)에는 파라미터의 수를 늘리면 됩니다.

 

 이러한 사후확률에 맞게 파라미터의 수를 조절하는 기술을 적응적 adaptive라 부르며, 이들은 신뢰도 계산에 있어서 컴퓨터 자원에 기반할 수 있다면, 자원 적응적 resoure-adaptive이라고 부를수 있습니다. 자원 적응적 기술은 로봇공학에서 중요한 역활을 하는데, 이는 컴퓨터 계산량이 가능함에 따라 실시간으로 로봇이 결정을 할수 있도록 만들어줍니다. 파티클 필터는 사용가능한 계산 자원에 따라 실시간으로 파티클 수를 조절하도록 종종 자원 적응적 알고리즘으로 구현되기도 합니다.

 

4.1 히스토그램 필터

표 4.1 이산 베이즈 필터

 히스토그램 필터는 상태 공간을 유한개의 공간을 분해하고 각각의 여역을 단일 확률값에 대한 누적 사후확률로 나타냅니다. 이를 이산 영역에 적용하면 이산 베이즈 필터라 하고, 연속 상태 공간에 적용하면 히스토그램 필터라고 부릅니다. 우선 이산 베이즈 필터를 설명할것이고 이후 연송 상태 공간에서의 사용을 다루어보겠습니다.

 

4.1.1 이상 베이즈 필터 알고리즘 The Discrete Bayes Filter Algorithm

 이산 베이즈 필터 알고리즘은 확률 변수 $X_t$가 유한 값을 가질수 있는 유한 상태 공간 문제에 사용됩니다. 이미 이산 베이즈 필터를 2.4.2장에서 문이 열렸는지 닫혔는지 확률을 추정하는 예제에서 살펴보았습니다. 이후에 살펴볼 일부 로봇 공학 지도 작성 문제들도 이런 이산 확률 변수를 다룹니다. 예를들면 점유 격자 지도 작성 알고리즘에서는 각각의 공간들이 점유되었는지 비어있는지를 정하게 됩니다. 이러한 확률 변수는 이진값이 되어 2가지의 값만 가질수 있습니다. 그래서 유한 상태 공간은 로봇 공학에 있어서 중요한 역활을 하게 됩니다.

 

 표 4.1은 이상 베이즈 필터의 슈도 코드가 됩니다. 이 코드는 표 2.1의 기본 베이즈 필터에서 적분을 유한 합으로 바꾸어서 구할수 있으며 변수 $x_i$와 $x_k$는 유한개의 상태가 됩니다. 시간 t에 대한 신뢰도는 상태 $x_k$에 대한 확률로 $p_{p,t}$로 표기하며, 이 알고리즘에 대한 입력은 이산 확률 분포 $p_k,t$와 최근 제어 입력 $u_t$, 측정치 $z_t$가 됩니다. 3번째 줄은 예측 과정으로 제어 입력으로 새 사애에 대한 신뢰도를 계산합니다. 이 예측은 4번째 줄에서 측정 값을 합치면서 갱신 됩니다. 이산 베이즈 필터 알고리즘은 다양한 신호처리(음성 인식 같은)분야에서 사용되며 히든 마르코므 모델이라고 불립니다.

 

4.1.2 연속 상태 contiunuos state

 이 첵에서 연속 상태 공간 상에서 근사 추론도구로 이산 베이즈 필터를 사용하겠습니다. 이러한 필터를 히스토그램 필터라 하며, 히스토그램 필터는 연속 상태 공간을 유한개의 영역으로 분해합니다.

 

 

 여기서 $X_t$는 로봇의 상태를 나타내는 확률 변수로 함수 range($X_t$)는 상태 공간입니다. 각각의 $X_{k, t}$는 볼록한 공간 convex region이 됩니다. 이 영역들은 상태 공간들의 일부분이 되어 이들은 i != k일때 $x_{i,t}$ $\cap$ $x_{k,t}$ = $\o$이고 $U_k$ $x_{k,t}$ = range($X_t$)가 됩니다. 연속 상태 공간을 분해하여 이차원 그리드가되어 각각의 $x_{k,t}$는 그리드 셀이 됩니다. 입자 분해 granularity of the decomposition을 통해 정확도와 계산 효율 사이 조절을 할 수 있습니다. 분해를 많이 할 경우 추정 에러가 그러지 않을 경우보다 작겠지만 계산 복잡도 비용은 증가하게 됩니다.

 

 이미 이산 베이즈 필터로 각각의 영역 $x_{k,t}$와 확률 $p_{k,t}$에 대해 살펴보았고, 이 영역들에서 이산 베이즈 필터는 신뢰도 분포에서 아무런 정보를 주지 않습니다. 그래서 사후 확률은 각각의 영역 $x_{k,t}$와 상태 $x_t$에 대해 균일 분포를 따르는 상수 확률 밀도 함수가 됩니다.

 

 

 여기서 |$x_{k, t}$|는 $x_{k, t}$의 크기를 말합니다.

 

 상태 공간이 완전히 이산적이라면 조건부 확률 p($x_{k, t}$ | $u_{t}$, $x_{i, t-1}$) 와 p($z_t$ | $x_{k, t}$)가 정의되어 알고리즘을 구현할 수 있습니다. 연속 상태 공간에서 확률 밀도 p($x_t$ | $u_t$ , $x_{t-1}$)와 p($z_t$ | $x_t$)가 주어질때 이는 상태 공간에서 일부 영역이 아니라 각각의 상태를 정의하는게 됩니다. 

 

 각각의 영역 $x_{k, t}$이 작거나 같은 크기인 경우에 이러한 밀도들은 $x_{k, t}$를 해당 영역을 나타내는 값으로 대체하여 근사화 시킬수 있습니다. 예를 들어 $x_{k, t}$의평균상태를구한다면

 

 아래와 같이 바꿀 수 있습니다.

 

 이 추정은 (4.2)에서 살펴본 이산 베이즈 필터의 균일 분포 구현한 결과가 됩니다.

 식 (4.4)는 합리적인 근사화로 p($z_t$ |  $x_{k, t}$)는 다음의 적분으로 표현할 수 있습니다.

 

 이 표현식은 식 (4.2)에서 균일 분포 모델에 따른 확률을 정확히 구할 수 있습니다. 만약  p($z_t$ |  $x_{k, t}$)를 p($z_t$ |  $\hat{x_{k, t}}$)$으로 근사화 시킨다면, 식 (4.4)의 근사화 구문으로 아래의 식을 얻을 수 있습니다.

 식 (4.5)에서  p($x_{k, t}$ | $u_{t}$, $x_{i, t-1}$)의 근사 시에도 비슷한데, 조건부 확률 양 쪽을 각각의 영역에 대해 다루기 때문입니다. 위에서 살펴본 변환처럼 아래의 식을 얻을 수 있습니다.

 

 

 이전에 $x_{t-1}$과 $u_t$ 사이에 독립이라 하는 마르코브 가정을 사용하면 p($x_{t-1}$ | $u_t$) = p($x_{t-1}$)으로 식 (4.8)은 아래와 같이 정리됩니다.

 

4.1.3 분해 기술들 Decomposition Techniques

 로봇 공학에서 상태 공간을 분해하기 위한 방법들로는 크게 정적과 동적으로 2가지 종류로 나눌 수 있습니다. 정적 기술들은 지정한 고정 크기로 분해하여 근사화된 사후확률의 형태를 무시하게 됩니다. 동적 기술은 사후 확률 분포의 형태에 따라서 분해를 합니다. 정적 기술들이 먼저 구현이 되었으나 이들은 자원 사원량에 낭비를 초래할수 있습니다.

 

(a) 2차원 확률 밀도의 그리드 기반 표현법. 이 확률 밀도는 상태 공간 상에서 우측 위와 좌측 아래에 집중되어 있습니다. (b)는 같은 확률 분포의 밀도 트리

 

 동적 분해 기술의 대표적인 예로 밀도 트리 density tree 군이 있습니다. 밀도 트리는 상태 공간을 재귀적으로 분해하여 사후 질량 확률의 해상도에 적응시킵니다. 이 분해의 중요한 점은 분해의 세부적인 레벨이 사후 확률 함수이 되어, 영역이 적은 경우 분해도 적게 될겁니다. 그림 4.1은 2차원 확률 밀도 상에서 정적 그래드 표현법과 밀도 트리 표현법을 보여주고 있습니다. 두 표현법은 같은 근사치를 가지고 있지만, 밀도 트리가 그리드 표현법보다 소형이 됩니다. 밀도 트리 같은 동적 기술들은 정적의 것보다 계산 량을 줄일 수 있으나 구현하는데 더 많은 노력이 필요합니다.

 

 이러한 동적 분해와 비슷한 효과를 선택적 갱신 selective updating을 통해서도 수행할 수 있습니다. 그리드에서 표현한 사후확률을 갱신할때 선택적 기술은 일부 그리드만 갱신시킵니다. 이 방법의 구현물은 사용자가 지정한 임계치를 초과한 사후 확률의 그리드 셀만 갱신하도록 하여 선택적 갱신은 상태 공간을 세밀한 그리드로 분해하고 전체 영역중에서 일부 부분만 선택하는 점에서 하이브리드 분해라고 볼수 있습니다. 또, 이 방법은 실시간으로 사후 확률의 형태에 따라 갱신할 그리드 셀을 선택한다는 점에서 동적 분해 기술로도 볼수 있습니다. 선택적 갱신 기술은 갱신할 신뢰도를 고르는대 관여함으로서 계산 량을 줄일수 있고, 3, 4차원 공간에서도 그리드 분해를 사용할수 있도록 도와줍니다.

 

 이동 로봇 책에서는 종종 공간에 대해 미터 표현법과 위상학을 구분해서 다루기도 합니다. 여기 용어에는 명확한 정의가 없지만 토폴로지 표현법에서는 그래프 표현법도 사용되는데, 그래프의 노드들은 주위 환경에서 지점(특징)들에 대응합니다. 실내 환경에서 교차점이나 T점, 등등 같은 공간이 그러한 특징들이 됩니다. 이런 곳에서 분해 해상도는 주위 환경에 의해 정해지며, 다른 방법으로 그리드를 사용해 상태 공간을 분해할수도 있습니다. 이 경우 분해 시에는 주위 환경 특징의 위치나 형태에 의존하지 않게 됩니다.

 

 그리드 표현법은 종종 미터법으로 여겨지는데, 이 공간이 분해가 아니라 미터 공간으로 보기도 하기 때문입니다. 이동 로봇공학에서 그리드 표현법의 공간 해상도는 토폴로지 표현법보다 큰 편이며, 7장에서 몇가지 예시에서는 10cm이하의 셀사이즈를 가지는 그리드 표현법을  사용할 것입니다. 이는 정확도를 올리긴 하나 계산 비용을 증가시키게 됩니다.