'센서네트워크/이론'에 해당되는 글 2건

  1. 2007.05.18 칼만필터 기본 이론. (1)
  2. 2007.05.16 [ETRI] 전자통신동향분석 통권104호/제22권 제2호 2007년 4월 p48-57
http://blog.empas.com/icewater47/2747037 에서 퍼옴.

칼만필터는 1960년 R.E.Kalman (Kalman, Rudolph, Emil) 의 논문
"A New Approach to Linear Filtering and Prediction Problems"
에 그 시초를 두고 있다.
칼만필터에 대한 자세한 설명과 관련자료는 아래주소 Greg Welchd의 홈페이지에 잘 정리되어 있다.
http://www.cs.unc.edu/~welch/kalman/
여기서는 처음 칼만필터의 내용을 접하는 초보자를 위해 한글로 몇가지 중요한 내용을 정리해본다.
 
칼만필터는 흔히 " an optimal recursive data processing algorithm" 이라고 불린다.
이에 대한 직접적인 설명을 하기 전에 간단한 예로써 그 의미를 전달해보자.
어느 고등학교 선생님이 자신의 학급 학생들의 수학점수 평균을 알고 싶다고 가정하자. 물론 모든 학생의 점수를 더한 후 이를 학생 수로 나누는 방법이 가장 쉽고 간편할 것이다. 그러나, 한가지 재미를 더하기 위해 상황을 설정하자면 아직 선생님은 학생들의 점수를 전혀 알고 있지 못한 상황이고, 학생들은 한번에 한명씩만 선생님께 점수를 말해준다고 가정하자. 이때 선생님이 평균을 짐작해보기 위한 가장 좋은 방법은 학생 한명한명이 점수를 말할 때마다 이들의 평균으로 전체의 평균을 짐작해보는 것이다. 즉 다음과 같은 관계식을 생각해볼 수 있다.
 
X'(1) = X1
X'(2) = (X1+X2)/2 = (X'(1)*1+X2)/2
X'(3) = (X1+X2+X3)/3 = (X'(2)*2+X3)/3
X'(4) = (X1+X2+X3+X4)/4 = (X'(3)*3+X4)/4
  :
  :
X'(n) = (X1+X2+.......+Xn)/n = (X'(n-1)*(n-1)+Xn)/n
 
위 식의 일반식은 다음과 같이 변형할 수도 있다.
X'(n) = X'(n-1)*((n-1)/n)+(1/n)*Xn
그럼 위 식이 갖고 있는 특징은 무엇일까? 위와 같은 식을 사용할 때의 간편한 점은 지나간 개개의 값들을 모두 기억해 둘 필요가 없다는 것이다. 즉 n번째 평균을 구할 때 선생님은 X'(n-1) 과 지금 n번째라는 두개의 값만 기억하면 아무 문제없이 n번째의 평균을 구할 수 있게된다.
이와 같은 기법을 "반복적 자료 처리 (recursive data processing)" 이라고 하며, 최초 Kalman Filter 이론의 개발 이유이기도 하다. 처리할 자료의 양이 그리 많지 않을 때는 모든 자료를 기억해두었다가 한번에 계산하는 것이 간편할 수도 있겠으나, 그 자료의 양이 방대하다면, 저장 장소 및 처리 시간을 고려하지 않을 수 없게 된다. 칼만필터가 개발된 60년대는 컴퓨터의 발달이 초보적인 상태였기에 자료의 효율적 저장 및 처리가 절실할 시절임을 감안한다면 어쩌면 당연한 고안이라고 생각할 수 있겠다.
그럼 이제 "최적 (optimal)" 이라는 단어에 초점을 둬 보자. 위에서 제시한 예는 개개의 데이터 (각 학생의 수학점수)에 동일한 가중치, 즉 새로 받아들이는 모든 값에는 1/n의 가중치가 두어졌다. 그렇다면 가중치가 다른 경우에는 어떠할까? 같은 점수를 갖고 있는 학생 3명이 함께 와서 "우리점수는 ㅇㅇ점 입니다."라고 한다면 이점수에 대한 가중치는 3/n을 주어야 할 것이다. 이와 같이 각 데이터가 갖고 있는 평균에 대한 중요도를 "경중률"이라고 한다. 경중률에 대한 개념은 측량에 있어서 여러방법으로 길이를 재고 이들의 평균을 구해봄으로써 더욱 쉽게 이해할 수 있다.
이번에는 위의 수학선생님이 학생 두명에게 각기 다른 방법으로 교실의 길이를 재보라고 했다고 하자. 한 학생은 자신의 보폭을 이용하고, 다른 학생은 줄자를 이용하여 교실의 길이를 측정했을때, 첫번째 학생은 10m, 두번째 학생은 12m 라는 값을 얻었다. 만약 둘 모두 같은 방법으로 길이를 측정하였다면, 선생님은 주저없이 두 값을 평균하여 11m 를 교실의 길이라고 말할 수 있겠다. 그러나, 누가 보더라도 보폭으로 잰 길이보다는 줄자로 잰 길이가 정확하다고 느낄 것이다. 그렇다면 이들 두 값을 어떻게 평균해야 할까? 이때 도입되는 개념이 경중율이다.
측량학에 있어서 관측값의 경중률은 각 값이 갖고 있는 표준편차를 기준으로 정한다. 즉 각 관측치에 대한 경중률은 표준편차 제곱에 반비례한다. 표준편차가 크면 클수록 그 값의 경중률은 떨어지며 평균에 대한 기여도가 적어지게 된다.
줄자로 잰 거리가 10m이지만, 수많은 경험 또는 수많은 반복 측정을 통해 얻어진 표준편차가 +-0.1m라고 가정한다면, 그리고 보측은 12m +-1.0m라고 가정한다면, 이들의 평균은 다음과 같이 구해진다.
 
평균 = (10*(1.0)^2 + 12*(0.1)^2 ) / (0.1^2+1.0^2)
       = 10.02m
 
위의 식을 일반화 하면,
 
X = (X1*(sd2)^2 + X2*(sd1)^2) / ((sd1)^2+(sd2)^2)
     = (X1*(sd1)^2 - X1*(sd1)^2 + X1*(sd2)^2 + X2*(sd1)^2) / ((sd1)^2+(sd2)^2)
     = X1 + (X2-X1)* [(sd1)^2 / ((sd1)^2+(sd2)^2)]
 
여기서, X : 상태변수 (state variables)
           sd : 표준편차 (standard deviation)
 
위의 마지막 식이 칼만 필터에 있어서 시스템 출력값 (위에서는 X1) 과 새로운 입력값 (X2) 을 이용하여 새로운 최적값 (optimized state variables) 을 계산하는 "관측갱신 알고리즘 (measurement update algorithm)" 의 스칼라 형태이다. (일반적으로 칼만필터의 기본식은 행렬 또는 벡터형태로 나타나 있다.)
더불어 새로운 최적값, X, 의 표준편차는 다음과 같이 계산된다.
 
(sd)^2 = [(sd1)^2+(sd2)^2] / [(sd1)^2*(sd2)^2]
 
이제 위의 두 식, 최적값 X와 표준편차 sd를 구하는, 을 이용하면 앞에서 말한 두 관측 값 이외에 다른 관측값을 추가적으로 얻어서 다시 새로운 최적값을 구할때도 같은 방법을 계속 사용할 수 있다. 이때는 앞에서 얻어진 X 는 X1 이 되고, sd 는 sd1 이 되며, 새로운 관측값과 표준편차(경중률)은 각각 X2 와 sd2 가 된다.
이와 같은 반복적인 (recursive) 연산 (data processing) 을 통해 최적 (optimal) 값을 추적하는 것이 칼만 필터의 기본개념이라 할 수 있겠다.

여기에서는 칼만필터의 기본식을 바탕으로 각 식이 갖고 있는 의미를 짚어본다.
칼만필터의 기본식은 여러가지 형태로 표현되곤 하지만 가장 일반적으로는, 다음과 같은 시스템 방정식과 관측방정식을 갖고 있는 시스템에 대한 칼만필터를 다음과 같이 표현할 수 있다. (from Welch & Bishop's lecture note)




먼저 시스템 방정식과 관측방정식을 살펴보자.
칼만필터를 도입하기 위해서는 기본적으로 위와 같은 두 선형방정식이 필요하다. 비선형 방정식에 대한 "확장형 칼만필터 (Extended Kalman Filter)" 는 비선형 방정식을 테일러 급수전개 등을 이용하여 선형화 한 후 적용한 형태일 뿐이다. (다만 비선형의 선형화에 따른 변환계수 -그림에서 A 또는 H와 같은- 의 형태가 달라질 뿐이다. 이에 대해서는 "확장형 칼만필터"에서 다시 자세히 설명하겠다.)
시스템 방정식에서 x는 우리의 관심, 즉 최적화를 하고자 하는 상태변수를 의미하고 계수 A 는 한 단계에서의 상태변수와 다음 단계의 상태변수를 연결하는 변환계수를 표현한다. B 와 u 는 한 덩어리로 인식할 수 있으며 이들은 시스템에 무관한 추가 입력값이다. 마지막으로 w 는 k 단계에서 상태변수 x 의 참값과의 차이값 또는 "시스템 오차(system error or system noise)" 이다. (우리가 알고 있는 x 는 참값에 근접한 계산값일 뿐이다.) w 는 개별적으로 값을 구하거나 지정할 수 없으며, 단지 오랜 관측 및 시스템의 제작시부터 알고있는 참값에 대한 표준편차로써 -칼만필터 안에서는 분산의 형태로써- "Q" 라는 변수로 적용된다.
관측방정식에서 z 는 관측값이고 이는 상태변수 x 와 변환계수 H 에 의해 표현되며 v 는 관측값 z 와 관측참값과의 오차 (measurement error or measurement noise) 이다. v 는 w 와 마찬가지로 개개의 값을 알 수는 없고 관측 참값에 대한 분산인 "R" 라는 변수로써 칼만필터 안에서 사용된다.
 
여기에서 칼만필터의 기본가정을 소개하자면, 이는
[오차 w 및 관측방정식에서의 v 는 각각의 참값에 대해 정규분포하며 그 평균은 0 이고 분산은 각각 Q 와 R 이다.] 이다.
이 가정은 칼만필터의 가장 큰 장점인 반면 또한 가장 큰 단점으로 작용하기도 한다. 시스템 연산값 및 관측값이 참값에 대해 정규분포하는 일반적인 경우에는 위와 같이 간단한 칼만필터 알고리즘을 통해 최적화 할 수 있는 강력한 도구가 되지만, 그렇지 않은 경우 -오차가 참값에 대해 정규분포하지 않는 경우 또는 그렇다 하더라도 그 분산을 알 수 없는 경우- 에는 그 적용에 있어 문제와 어려움이 크다. 그러나 오차의 확률분포가 정규분포가 아닌 경우라 하더라도 이를 정규분포로 간주함에 있어 그리 큰 무리가 없는 경우에는 칼만필터는 아직까지 유용하고 강력한 도구로 사용된다.(???수정필요!!!)
 
위에 설명한 시스템 방정식과 관측방정식의 이해를 위해 간단한 예를 들어 본다면, 등속운동을 하고 있으며 때때로 추가적인 가속 또는 감속을 하고 있는 자동차를 생각해보자. 이는 기본적으로 등속운동을 하고 있으니 k-1 단계에서의 속도와 k 에서의 속도는 동일하므로 A는 "1" 이다. 또한 추가적인 가감속에 따른 속도변화는 그것이 이루어진 단계에서 Bu 에 그 값을 적용할 수 있다. 그리고 그 자동차를 외부에서 스피드건을 이용해 관측한다면 이는 그 속도를 직접 관측하는 것이므로 H 역시 "1" 이다.
신고
Posted by remos

지능형 로봇 공간을 위한 실내 측위 기술
Indoor Localization Technique for Intelligent Robotics Space
(안효성, 이재영, 유원필, 한규서) - ETRI 지능형 작업제어연구팀

지능형 로봇 공간에서는 이동성과 조작성으로 대표되는 독특한 기능을 분산센싱, 분산처리환경을 구축하여 고기능화 하여, 자연스러운 이동, 조작 기능의 구현이 가능하다.

물리 공간에서의 가장 핵심 이슈인 실내 위치 측위 기술에 대해 알아본다.

현재 위치 추적에는 실외 환경에서의 GPS를 이용한 실외 네비게이션 시스템이 대표적이다.
하지만 미국 FCC가 권고한 모든 911요청자의 정밀한 위치 파악에 대한 요구 사항이 실내 위치 인식의 필요성을 대두시킨다.

실내 위치 인식에는 Coarse(광역) to Fine(정밀)한 과정으로 측위가 이루어 진다.
하지만 현재 주도적인(Dominant)한 솔루션이 없다.

실내 위치 인식을 나누어 보자면, 클라이언트 기반의 방법(Client based design)과 기준노드 기반(Beaocon based)의 방법으로 나뉜다.

클라이언트 기반의 방법은 WLAN의 fingerprint 과 같은 방식으로 AP에서 Client에게 전파를 송신하여 위치를 결정한다.

기준노드 기반의 방법은 Beacon의 신호세기/신호방향/전파 시간차를 이용하여 구하며, 기준노드의 변위에 따라, Fixed beacon/Moving beacon/Beacon free 등으로 구분이된다.
이러한 Beacon으로 부터 수신된 전파를 거리 기반(Ragne based) 방식과 거리 독립(Range free)방식으로 사용된다.

거리 기반 방식은 삼각 측량법 등에 의해 변위가 측정 되며
거리 독립 방식은 셀단위의 좌표 분류에 의한 위치 결정으로 이루어 진다.

이러한 방식중 거리 기반 방식은 신호를 다각도로 이용한다.

1. RSSI : I =K/(r^alpha) : (cc2420,cc2431의 디바이스를 이용)
2. ToA : 속도(c)로 움직이는 전파를 발신 시간과 수신 시간의 차이를 이용한 거리 측정
        송신기와 수신기의 동기화가 어렵다. 이러한 점을 보안하기 위해 TDoA방식을 적용한다.
3. TDoA : 수신되는 신호의 시간 차이를 이용 - 송수신기 간의 동기화는 요구되지 않고, 시각 동기화만 요구된다. 시각 동기화 및 캘리 브레이션 및 전파 직진성에 장점을 보인다.
4. AoA : 수신 방향을 결정 한다.
5. Fusion :
  AoA + TDoA
    'Networked based Wireless location"  안테나 배열 기법
    'Mobile Positioning using Wireless Location' 관측식 기반의 필터링 기법
  TDoA + RSSI

결론.

지능형 로봇 측위의 목적
: 로봇이 사용자의 개입 없이 스스로 사물이나 사람의 위치를 계산 가능 한것

Wifi,Zigbee,UWB 등 여러 방식이 있지만 이전 기술을 유연하게 연동시키는 끊김 없는 Coarse to fine 위치 결정 시스템 개발도 중요한 연구 영역이라 할 수 있다.

ps. 간단하게 제게 필요한 부분을 요약하였습니다.
     본문과 목적과 방향이 틀릴수도 있으나 이해해 주십시요~^^

신고
Posted by remos


티스토리 툴바