어디를 가고 있는가?(Where am I going? - Mapping)

어디를 가고 있는가?(Where am I going? - Mapping)

 어디를 가고 있는가?라는 문제를 해석하기 위해서는 반드시 자기 위치 인식이 필요하다. 이동 로봇의 플랫폼에 장착되어 있을 거리 센서와 영상 정보들은 최초 설정된 글로벌 좌표가 아닌 현재 구동중인 위치를 기준으로 결과를 얻을 수 있기 때문이다.

 \(x_t\)에서 취득한 센서 정보는 \(x_t\)좌표에 대한 것이며, 글로벌 좌표 \(X_g, Y_g\)로 변환해야 하나의 지도에서 관측량을 정의할 수 있다. 불운하게도, 이 과정에서 로봇의 이동 변위에 대한 오차 때문에 정확한 위치에 기입하지 못하는 경우가 생길 수 있다.(이 부분은 Dead reckoning이 가지고 있는 치명적인 단점이다. 관성항법에서도 비슷한 문제를 경험할 수 있는데, 절대 위치를 보정할 수 있는 GPS가 있기 때문에 다행이 특수한 경우가 아니면 큰 문제가 발생하지 않는다.)

 더욱이, 초기에 로봇의 위치를 측정하는 기준은 고가의 센서가 아니라 바퀴에 달린 엔코더에 의존하는 경우가 많았고, 센서의 정확도도 현재보다 더욱 부정확했기 때문에 다시 한 번 확률 기반의 지도 작성 방법이 제안되었다.

 환경 지도를 작성하는 방법론의 관점에서 크게 

• 위상 지도(Topological mapping)
• 격자 지도(Metric mapping)

로 분류하여 볼 수 있는데, 위상 지도는 에지와 노드로 구성된 그래프로 중요한 지점과 그 연결정를 가지고 있는 형태의 지도를 말한다. 반대로 격자 지도는 일반적으로 3차원 공간을 2차원 평면에 투영한 형태의 지도를 말한다. Metric이란 수식어에서 알 수 있는 것처럼 각 지점 간의 거리를 스케일로부터 얻을 수 있다.

격자 지도를 대표하는 방법은 Occupancy grid이다.

베이지안 추정 필터(Bayesian recursive filter)

베이지안 추정 필터(Bayesian recursive filter)

 기본적인 베이즈의 정리는 다음과 같다.

 확률론을 기반으로 한 로봇의 위치 추정 문제의 근본이 되는 개념이다.

 베이즈의 정리를 구체적으로 기술한 문서들은 많이 있으므로 기본적인 개념만 서술하면, 모르는 사후확률을 계산할 때 알고 있는 확률과 현재 상태에 대한 확률을 이용하는 개념이다. 가령 스팸메일로 추정되는 메일에는 "대리운전"이라는 문자가 포함되어 있을 확률을 알고 있다면, 해당 메일이 스팸메일일 확률을 계산할 수 있다는 식이다.

 이동 로봇처럼 연속된 상태를 갖는 경우에는 시간의 흐름에 대해서 재귀적으로 베이지안 추정을 적용할 수 있게 된다. 위치 추정뿐만 아니라 물체 인식/분류와 같은 분야에도 광범위하게 적용될 수 있는데, 최근엔 naive bayes라는 이름으로 적용되고 있다. 1700년대에 최초로 제안되었던 것을 생각하면 베이즈의 위대함을 느낄 수 있다.

 마르코프 체인과 함께 정리하면 다음 그림과 같다.

 베이지안 추정 필터의 원리를 재미있는 예로 소개한 것이 S. Thrun의 저서 Probabilistic Robotics에 있는데, 이것을 소개한다.

 문제 정의 : 로봇의 팔이 문을 여는 동작을 할 경우 문이 열릴 확률과 센서로 문이 열렸는지 감지했을 때 정말로 열려있을 확률을 알고 있을 때 문의 현재 상태에 대해서 베이지안 추론을 적용할 수 있는가?

 문제 적용 : 문의 현재 상태(열림, 닫힘)는 상태 벡터를 \(x_t\),  문에 대한 사전 확률은 \(x_{t-1}\)로 정의할 수 있다. 센서를 통해서 감지하는 문의 상태 우도(likelihood)는 \(p(z_t|x_t)\)가 된다.

몬테카를로 마르코프 위치 인식 방법(MCMC(Monte-Carlo Markov Chain) Localization)

몬테카를로 마르코프 위치 인식 방법

MCMC(Monte-Carlo Markov Chain) Localization

 이동 로봇이 어디선가 이동하고 있는데 현재 얻을 수 있는 정보는 거리 센서로부터 얻은 정보이거나 영상으로 부터 입력된 사진등일 경우 로봇의 현재 위치를 어떻게 추정하면 좋을까?

 바로 이전의 위치를 알고 있다면 순간이동을 하지 않는다면, 짧은 시간 내에서는 비슷한 위치에 있을 것임을 추론할 수 있다. 바로 이전의 위치를 정확하게 알 수 없다면, 확률적으로 가중치를 부여한 이전 위치에 대한 다음 위치를 마찬가지로 구해낼 수 있을 것이다.

  이것을 수식화하고 실제 구현을 통해 증명한 것이 Sebastian Thrun이다. Thrun은 현재에도 스탠포드 교수로 재직하면서 활발한 연구를 하고 있다. 구글 무인 자동차 연구 그룹의 수장으로 알려져 있다.

 마르코프 위치 인식에 대해서 이해하자면 베이지안 추정 필터에 대한 이해가 필요하다.

\( Pr(\xi^{(t)}|s^{(t)}) = \frac{Pr(s^{(t)}|\xi^{(t)})Pr(\xi^{(t)})}{Pr(s^{(t)})} \)

 확률론에서 마르코프 체인은 바로 다음의 상태는 과거의 상태가 현재까지 축적된 현재 상태에만 기인한다는 이론이다. 상식적으로도 그렇지 않은가? 로봇이 움직이는 다음 위치는 바로 이전 상태에만 관계가 있지, 그 보다 과거의 상태에 영향을 받을 이유는 없다.

 첨자들과 표기가 바뀌었지만 베이지안 추정 필터에서 소개한 것과 별반 다를 바 없는 식이다.

 실제 구현에서는 몬테카를로 기법을 여기에 함께 사용하는 이유는 연속(Continuous)신호를 표현한 수식을 구현하다 보면 필연적으로 데이터 분해능과 성능의 저하가 발생하기 때문이다. 몬테카를로 방법도 마찬가지로 반복의 횟수와 샘플의 갯수에 따라 성능의 차이가 있지만만, 충분히 많은 수의 샘플을 사용하면 만족할만한 정확도를 얻을 수 있다.

 다음 그림과 동영상은 실제로 Minerva에서 사용된 천정 영상과 Occupancy grid에 대한 위치 인식을 수행한 결과이다.

이동 로봇의 3대 문제(Fundamental problem of mobile robots)

이동 로봇의 3대 문제(Fundamental problem of mobile robots)

 이동 로봇에 대한 전반적인 기술과 역사에 대해서 기술합니다. 로봇 분야에 처음으로 발을 딛는 분들에게 우리말로 도움을 줄 수 있는 문서가 되었으면 좋겠습니다. 편의상 경어를 생략하오니 양해하여 주시기 바랍니다.

 자율 이동 로봇을 위한 여러가지 문제들 중에서 핵심적으로 다음 세 가지를 정의할 수 있다. 각각의 분야는 모두 서로 연결되어 있으므로 하나의 문제를 해결하면 다른 문제를 보다 쉽게 해결할 수 있거나, 반대로 하나의 문제를 해결하지 못하면 다른 문제도 해결할 수 없는 관계가 있다.

1. 어디에 있는가?(Where am I? - Localization)

2. 어디를 가고 있는가?(Where am I going? - Mapping)

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

 자율 이동 로봇의 알고리즘이 시작되는 시기에는 연구자들이 각 문제를 따로 생각하는 경향이 있었으나, 90년대 후반부터 현재에는 1, 2번의 문제를 동시에 확률 적으로 해석하는 방법을 취하게 된다. 이것을 CML(Concurrent Mapping and Localization) 또는 SLAM(Simultaneous Localization and Mapping)이라고 정의하고 부른다.  SLAM이라는 키워드로 IEEE 검색을 해보면 2600여개의 논문이 검색되고, 지금도 새로운 연구 결과가 제시될 정도로 활발한 연구분야이다.

 각 문제 하나를 해석하는 것 만으로도 당시의 이동 로봇의 발전에 많은 기여를 한 것으로 이름을 알린 분들이 많다. 그 만큼 한 가지 기술분야에 대해서 정복하는 것도 많은 노력이 필요하다는 방증일 것이다. 각 기술의 상세 내용은 해당 링크에서 소개하고, SLAM은 별도의 분류로 소개하도록 한다.

어디에 있는가?(Localization)

어디에 있는가?(Localization)

 위치 인식을 위해서는 알고 있는 위치에 존재한다는 가정이 필요하다. 지도의 형태는 영상 일 수도 있고, 거리정보 일 수도 있지만 모르는 환경이 아니라 알고 있는 환경이라면 자기 위치를 인식하는 것이 가능하다.

 가장 독보적인 진전과 활용을 보인 것은 아마도 독일 bonn 대학의 박물관 가이드 로봇 리노와 미네르바(Rhino & Minerva)일 것이다. 실험실에서 벗어나서 실제로 박물관에서 관객들이 있는 동적 환경에서 성공적으로 주행을 한 첫 번째 기록일 것이다. 당시로서는 로봇을 실험실이 아닌 일반 대중 앞에서 시연하는 것은 무모한 것처럼 보일 정도로 시스템의 안정성에 대한 확신이 없었더라면 힘들었을 일을 해냈다.

 1998년 8월 24일부터 9월 5일 까지 31시간 동안 44,018m를 주행한 것으로 기록되었다.

The museum tour guide robot minerva
(Photo courtesy Sebastian Thrun)

Rhino를 만져보고 있는 어린이 관람객
(Photo courtesy Sebastian Thrun)

 위치 인식 방법은 몬테카를로 확률 기반 위치 인식 방법을 사용하였다. 레이저 거리센서와 천정 카메라를 이용한 위치 인식 방법을 사용한 것으로 기록되어 있다.