Ref. Open

2014년 8월 20일 수요일

이동 로봇을 위한 칼만 필터

Kalman Filter for a mobile robot

EBS 다큐멘터리 '자본주의란 무엇인가?'에서 세계적인 석학들에게 '자본주의란?' 명제에 대해 답변해주기를 요청하는 장면에서 모두 머리를 절래절래 흔드는 장면이 나온다.

마찬가지의 관점에서 공학자로서 칼만 필터에 대해 기술한다는 것은 굉장히 괴로운 일이다. 깊은 통찰이 담겨있는 근본적인 원리이기 때문이다. 이미 인터넷을 검색하면 무수히 많은 튜토리얼과 활용예가 있음에도 불구하고 굳이 다시 한 번 거론하는 이유는 본 블로그에 게시된 글들과의 연관성을 위해서 SLAM과 관련된 내용을 게시하기 이전에 필요하기 때문이다.

베이지안 추정 필터와 관련된 글을 먼저 확인 바랍니다.

칼만 필터를 이동 로봇에 적용하는 것이 적합하다고 생각되는 이유는 물리적인 특성을 유지하는 물체이기 때문이다. 다시 말하면 뉴턴의 운동 법칙을 위배하는 물체는 이 세상에 없기 때문에 (빛보다 충분히 느린 물체의 경우에) 이동 로봇은 물론이고, 잠수정, 비행체를 포함한 모든 물체는 일정한 패턴을 가지고 움직인다. 갑자기 서울에서 있던 물체가 부산에 나타날 수는 없다는 것이다. 혹자는 금융에 칼만 필터를 적용하려는 시도를 하는 경우가 있는데, 본인이 생각하기엔 불가능하다. 왜냐하면 금융은 모델 자체가 갖는 특성이 물리적인 의미가 없는 경우가 많기 때문이다. (~~수 많은 파생상품은 투자 대상 조차도 형태가 없는 경우가 있다.~~)

아래의 글은 칼만 필터의 예측과 갱신과정에 대해서 이해하고 있는 독자를 대상으로 합니다. 칼만 필터의 기본적인 개념은 위키 백과의 글을 참고하시기 바랍니다.

칼만 필터가 실제로 좋은 방향으로 상태를 예측할 수 있는지는 다음 칼만 게인이 의미하는 바를 해석함으로써 알 수 있다.

Kalman gain

그림에서 보인 수식은 칼만 게인이 갱신 과정에서 어떤 역할을 수행하는지 해석한 것이다. 칼만 게인은 공정 잡음으로부터 발생된 오차 공분산 행렬 값 \(P_k^-\)과 측정 잡음 행렬 \(R_k\)와 관련이 있다. 측정 잡음이 '0'으로 수렴하면 칼만 게인은 \(H^{-1}\)가 되므로 상태 벡터의 갱신 값은 측정치를 따르게 된다. 반대로 오차 공분산 행렬 \(P_k^-\) 값이 '0'으로 수렴하게 되면 칼만 게인은 '0'이 되어 상태 벡터의 예측치를 따르게 된다.

이처럼 칼만 게인은 알고 있는(또는 알고 있다고 믿는) 공정 잡음과 측정 잡음 예측치와 측정치 중에서 현재 상태에 가장 최적의 값을 추론한다.

이를 이용한 위치 추정과 지도 작성에 관한 문제는 SLAM이라는 제목으로 다시 게재할 예정이므로 칼만 필터에 관해서는 여기에서 줄인다.

우분투 14.04 LTS에서 Nvidia cuda 6.0 설치

우분투 14.04 LTS에서 Nvidia CUDA 6.0 설치

우분투 14.04에서 CUDA 6.0 설치를 위해서는 몇 가지 조작이 필요하다.

새로 설치하는 경우라면 다음 명령을 확인해본다.

```
apt-get install build-essential
```

cuda 6.0 run 패키지를 다운로드 한다. 현재는 다음 버전이 최신 버전으로 확인됨.http://developer.download.nvidia.com/compute/cuda/6_0/rel/installers/cuda_6.0.37_linux_64.run
터미널을 열고 run 패키지의 압축을 해제한다. 압축을 해제하지 않고 run 패키지를 바로 실행 시켜도 설치가 되어야 하지만 아직은 호환성에 문제가 있는 것으로 보임.

mkdir ~/Downloads/nvidia_installers;
cd ~/Downloads
./cuda_6.0.37_linux_64.run -extract=~/Downloads/nvidia_installers;

기존에 설치된 nvidia 드라이버를 삭제한다.
```
sudo apt-get --purge remove nvidia-*
```

이제 X window를 ctrl+alt+F1으로 탈출하고 터미널로 로그인한 뒤 다음을 통해 설치를 진행한다.

cd ~/Downloads/nvidia_installers;
sudo service lightdm stop
sudo killall Xorg
sudo ./NVIDIA-Linux-x86_64-331.62.run

nvidia 드라이버가 설치되면 이제 X window를 ctrl+alt+F1으로 탈출하고 터미널로 로그인한 뒤 다음을 통해 설치를 진행한다.

sudo modprobe nvidia
sudo ./cuda-linux64-rel-6.0.37-18176142.run
sudo ./cuda-samples-linux-6.0.37-18176142.run

설치가 제대로 되었는지 확인

cd /usr/local/cuda/samples
sudo chown -R <username>:<usergroup> .
cd 1_Utilities/deviceQuery
make .
./deviceQuery

X window로 복귀
```
sudo service lightdm start
```

설치가 제대로 되었는지 확인할 수 있다.
```
lsmod | grep nv
```

Dijkstra, Best First Search, A* search

전역 경로 계획

거창하게 전역 경로 계획(Global path planning)이라고 이름을 붙이기는 했지만, 지역 경로 계획에 대비되는 용어일 뿐이다.

지역 경로 계획은 가까운 곳의 장애물을 회피하기 위한 방법이라면 전역 경로 계획은 출발점에서 도착점까지 가장 가까운 거리를 찾는 것을 목적으로 한다. 그러므로 전역 경로 계획으로 생성된 경로에서 지역적으로 발생하는 장애물을 회피하는 방법을 복합적으로 사용하는 것이 바람직하다. 전역 경로 계획은 컴퓨터 공학 그래프 이론에서 출발한 것들이기 때문에 지역 경로 계획과는 근본적으로 조금 다른 성향을 가진다.
실상이 없는 노드와 에지의 연결체에서 최단 경로를 찾는 것은 로봇의 모션 플래닝의 관점과는 조금 맞지 않을 수도 있다.

이외에도 다른 방법들이 많이 있지만 다음 세가지에 국한해서 예시를 든다.

Dijkstra
Best First Search
A* Search

워낙 오래되고 많이 사용되는 방법들이기 때문에 특별히 많은 설명이 필요하지는 않을 것 같다. 다음그림으로 세 가지 방법의 차이점을 명확히 이해할 수 있다.

Dijkstra, BFS, A* 비교(왼쪽부터)

Occupancy grid와 같은 평면 지도를 작성했다면 위의 그림처럼 경로 계획을 하는 것이 적합한 것임을 이해할 수 있다. 각 셀을 노드로 셀간의 연결(4개 또는 8개)을 에지로 생각하면 그래프와 같기 때문이다.

Dijkstra에서는 인접 셀에 거리 측정 방법(Manhattan distance, Euclidean distance)으로 측정된 비용에 따라 도착점 까지의 비용이 산출된다. 각 인접셀에 도달하는 비용은 동일하기 때문에 도착점까지의 가능한 모든 경로에 대해서 비용을 산출한 뒤에야 최단 경로가 생성되지만 최단 거리를 보장해준다는 장점이 있다.

BFS에서는 도착점까지의 거리가 가장 가까운 지점을 먼저 방문한다. Dijkstra보다 빠르지만 그림에서 보는 것처럼 최단경로를 찾지 못할 수 도 있다는 단점이 있다.

A* search algorithm은 상기 두 가지 방법을 적절히 혼용한 것으로 볼 수 있다. 출발점으로 부터 인접셀의 비용을 계산하되 도착점까지의 거리가 적을 것으로 생각되는 지점을 먼저 계산한다. 아래 그림에서 경로를 계산하는 순서를 확인할 수 있다.

게시물 작성중에 최근에 새로운 것이 있는지 확인해본 결과 흥미로운 것을 발견했다. 기존의 Dijkstra's algorithm을 GPGPU를 이용해서 비약적으로 성능을 확장시킨 것이다. 가능한 인접셀을 모두 병렬로 방문함으로써 반복의 횟수를 절감했다.

2014년 8월 19일 화요일

VFF(Virtual Force Field), VFH(Vector Field Histogram)

VFF또는 APF(Artificial Potential Field)는 가상 중력 벡터장 정도로 번역해서 사용된다. 기본적인 개념은 국소지역에서 장애물을 회피하기 위해서는 장애물에서 밀어내는 힘이 발생하고, 목적지에서 당기는 힘이 발생되는 단위 벡터장을 만드는 것이다. 벡터장위의 로봇은 물이 아래로 흐르는 것처럼 자연스럽게 목적지로 인도된다.

VFF
원본이미지: http://www-personal.umich.edu/~johannb/vff&vfh.htm

VFF 방법의 약점은 좁은 통로와 같이 장애물이 빈번하게 자리 잡고 있는 지역을 통과해야 하는 경우에 척력의 힘이 교차하기 때문에 아래 그림 처럼 진동하는 성향을 보인다는 것이다.

VFH
원본이미지: http://www-personal.umich.edu/~johannb/vff&vfh.htm

그 대안이 VFH이다. 그림에서 보는 것처럼 극좌표로 형성된 히스토그램의 굴곡에서 계곡으로 진행하면 장애물이 가장 없는 방향으로 진행하는 것이 되고 그 중에서 목적지와 가장 가까운 방향을 선택하면 된다.

VFH
원본이미지: http://www-personal.umich.edu/~johannb/vff&vfh.htm

어떻게 갈 것인가?(How do I get there? - Path planning)

어디를 가고 있는지, 어디에 있는 문제가 해결되고 나면 정말로 지능화된 행동을 취할 수 있는 필요조건을 갖춘 셈이다. 정보만 있다고 이동을 할 수 있는 것은 아니니 어떻게 갈 것 인가의 문제가 대두된다. Path planning은 Localization과 Mapping문제와는 조금 다른 성향을 가지는데, 실제로 운동을 하기 때문에 로봇의 움직임을 제어 해야하고, 실험실내의 환경이 아니라면 위험한 상황이 발생할 수 있기 때문이다.

다른 분야의 연구와 마찬가지로 다른 전제 조건이 주어진 상태에서 출발된 개념이 많다. 크게는 국소지역에서 장애물을 회피 주행하는 기법과 출발점과 도착점이 주어졌을 경우 최단거리를 계산하는 방법으로 나누어 볼 수 있으며 몇 가지 대표적인 방법에 대해서만 소개한다.

번외글: 드라마 '카이스트'와 VFF

드라마 '카이스트'와 VFF

VFF를 우리나라에서 일반인들에게 친숙하게(?) 만든 것은 드라마 '카이스트'에서 였을 것이다.

당시 모래시계로 이름을 알린 김정현씨가 게으른 천재 느낌으로 출연하는데, 로봇 축구에서 상대 로봇을 회피해서 골을 넣은 방법을 회의하는 장면이 나온다. 그 때 김정현씨가 외치는 말 "Magnetic force field!" 정확한 대사는 기억이 나지 않지만 비슷한 느낌으로 말했던 것 같다.
장애물에서는 척력(repulsive force)이 발생하고 목적지에서는 인력(attractive force)가 발생하는 방법을 사용하면 되지 않냐고 말한다. 사실 드라마의 배경이 되었던, 카이스트의 전자과의 김종환 교수는 우리나라 로봇축구를 세계에 알린 인물이다. 실제로 그 연구실에서 기법을 개발했던 사람은 어떤 기분이 들었을까? VFF(Virtual Force Field)를 우리나라에서 처음 만든 것은 아니지만 로봇 축구에 실제 적용으로 당시에 많은 호응을 얻었던 것으로 기억한다.
의학, 법학과 관련된 드라마는 많지만 공학에 관련된 드라마는 그리 많지 않다. 미국의 'Big bang theory'의 출연자들이 차기작을 엄청난 거액의 출연료로 계약한 사례를 보면 우리도 공학분야로도 충분히 재미있는 작품을 만들 수 있을 거라는 기대가 든다.(출연자의 계약 금액이 드라마의 질과 반드시 비례하지는 않지만 인기가 반영된 결과라는 추정에서) 꼭 미국식 nerd 개그가 아니라도 말이다.

점유 격자 지도(Occupancy grid)

Occupancy grid mapping

점유 격자 지도

이동 로봇의 지도 작성에 대해 관심을 가지기 시작한 시절(1980년대 후반)에는 현재보다 센서와 프로세서의 성능이 현저히 낮았다. 센서들은 물리적인 모델을 잘 따라오지 못했고, 바퀴의 인코더로부터 얻을 수 있는 오도메트리(Odometry) 정보는 그 불확실성을 더하게 만들었다.

그러한 상황에서 확률 기반의 지도 작성 방법을 가장 이상적으로 적용할 수 있는 현실적인 방법이었을 것이다. 여기서 다시 한 번 베이지안 추론 방법이 적용된다.

각 셀의 점유 확률을 구하는 것이 목적이며, 사전 정보가 없는 미확인 지역에 대해서는 0.5의 사전 확률로 채운다. 그림에서 보인 것은 초음파 센서의 확률 모델인데, 이것이 현재 로봇 위치에서 취득된 값에 대한 우도(Likelihood)가 된다. 초음파 센서는 편각 15도를 가지는 원뿔형태로 방사되는 특징을 가지고 있다. 그러므로 초음파 센서가 인식한 거리는 방사각 만큼의 불확실성을 가지고 있다는 의미가 있다.

이미지 원본: www.frc.ri.cmu.edu

Metric mapping은 실제 거리 정보에 대해 알고 있으므로 경로 계획에도 중요한 자산이 된다.