오늘은 ROS SLAM 기본 패키지인 Gmapping 논문 리뷰를 해볼 생각이다.
이 논문은 아래 링크에서 다운로드 받을 수 있다.
https://openslam-org.github.io/gmapping.html
OpenSLAM.org
Papers Describing the Approach Giorgio Grisetti, Cyrill Stachniss, and Wolfram Burgard: Improved Techniques for Grid Mapping with Rao-Blackwellized Particle Filters, IEEE Transactions on Robotics, Volume 23, pages 34-46, 2007 (link) Giorgio Grisetti, Cyril
openslam-org.github.io
Gmapping 사이트에서는 아래와 같이 한 줄로 요약하고 있다.
오늘 리뷰할 논문은 "Improved Techniques for Grid Mapping with Rao-Blackwellized Particle Filters"이다.
GMapping is a highly efficient Rao-Blackwellized particle filer to learn grid maps from laser range data.
: Gmapping은 높은 효율을 갖는 Rao-Blackwellized 파티클 필터이고, 이것은 레이저 데이터로부터 grid map을 형성하기 위함이다.
여기서 나는 처음 들어보는 키워드로써 "Rao-Blackwellized particle filter" 였다.
논문에서는 Rao-Blackwellized particle filter는 SLAM 문제에서 많이 쓰이고 있다고 소개한다. 이 파티클 필터에서 중요한 부분은 각각의 파티클들이 환경의 맵을 수반한다는 점이다.여기서 제일 핵심은 이 "Rao-Blackwellized particle filter의 파티클들을 얼마나 잘 줄여야 하는지?"이다.
그래서 이 논문에서는 adaptive하게 Rao-Blackwellized particle filter 파티클들을 그리드 맵에서 줄일 수 있는지에 대한 방법론을 제안한다. 이 방법은 로봇의 움직임 뿐만 아니라 최근 관측한 데이터도 고려한다. 필터의 prediction 과정에서 불확실성이 감소했다. 게다가 파티클 필터의 핵심이라고 할 수 있는 리샘플링 과정도 선별적으로 하는 방법론도 제안한다. 이전의 방법론보다 향상된 결과를 낳았다.
I. INTRODUCTION
SLAM이 어려운 이유는 두 가지를 동시에 수행해야 하기 때문이다.
1. localization을 위해서는 로봇이 맵을 필요로 한다.2. 맵을 생성하기 위해서는 로봇이 스스로의 위치를 잘 추정할 수 있어야 한다.
정말 유감스럽게도 이 두 문제는 서로에게 영향이 있으며, 서로에게 종속적인 관계이기 때문에 어려운 문제이다.
[기존 연구의 문제점]
Rao-Blackwellized particle filter[6, 32] 는 SLAM 문제에 있어서 큰 효과를 보였다. 하지만 이 Rao-Blackwellized particle filter의 문제점은 정확한 맵을 그리기 위해서는 "복잡도(=연산량)"가 요구된다. 게다가 resampling 과정에서 정확한 파티클들을 제거하기도 한다.
[제안하는 방법]
따라서 이번 연구에서는 그리드 맵에서 적용할 수 있는 Rao-Blackwellized particle filter 성능을 향상시킨 두 가지 접근 방법을 제안할 것이다.
1. *제안 분포(proposal distribution) : 센서의 정확도를 고려하고 우리가 파티클들을 그릴 수 있도록 허용함.
오도메트리 정보를 결합한 scan-matching 과정을 사용한 likelihood를 평가한다.
2. 적응형 리샘플링 과정(adaptive resampling technique) : 파티클 연소의 위험을 줄이고 정확한 맵을 그릴 수 있도록 합리적인 파티클(=로봇의 위치를 잘 추정하는)들은 유지시킨다.
*여기서 제안 분포란 쉽게 샘플을 생성할 수 있도록 임의의 분포를 만들어 주는 것을 "제안 분포(Proposal distribution)"라고 한다. 아래 링크에 가시면 잘 설명되어 있다. 기각 샘플링을 설명할 때 필요한 개념인 것 같다. 제안 분포는 uniform distribution, normal distribution 등이 이용될 수 있다고 하고 가능하면 원래의 분포와 흡사하게 만드는 것이 좋다고 한다.
[머신 러닝] 기각 샘플링 (Rejection Sampling)
Rejection sampling (또는 acceptance-rejection method)은 어떠한 주어진 확률 분포에서 효율적으로 샘플을 생성하기 위해 많이 이용되는 알고리즘이다. 우리가 샘플을 추출하고자 하는 확률 분포 $p$에 대
untitledtblog.tistory.com
II. MAPPING WITH RAO-BLACKWELLIZED PARTICLE FILTERS
Murphy[32] 에 따르면 SLAM을 위한 Rao-Blackwellized particle filter 핵심 아이디어는 맵 m과 로봇의 궤적 x에 대해서 joint posterior를 추정하는 것이다.
*notation은 다음과 같다.
- x : 로봇의 궤적
- z : 관측기
- u : 모바일 로봇의 odometry 측정치
이 추정기(estimator)는 observation과 odometry measurement를 이용하여 만들어진다. Rao-Blackwellized particle filter는 SLAM을 쓰이기 위해 다음 수식을 따른다.
위 수식을 해석하면 다음과 같다.
우선, 로봇의 궤적을 추정하고, 그런 다음 주어진 궤적으로부터 맵을 계산한다. 맵은 아주 강력하게 로봇의 추정기에 의존하기 때문에 이 접근 방법은 아주 효율적인 계산을 제공한다. 이 테크닉은 Rao-Blackwellization 에 잘 기술되어 있다.https://en.wikipedia.org/wiki/Rao%E2%80%93Blackwell_theorem
Rao–Blackwell theorem - Wikipedia
Statistical theorem In statistics, the Rao–Blackwell theorem, sometimes referred to as the Rao–Blackwell–Kolmogorov theorem, is a result which characterizes the transformation of an arbitrarily crude estimator into an estimator that is optimal by the
en.wikipedia.org
단어 기본 지식
*prior : 사전확률
*posterior : 사후확률
전형적으로 위 (1) 식은 사후확률을 효율적으로 계산할 수 있다. 왜냐하면 p(m | x1:t, z1:t) 은 분석적으로(analytically) 궤적과 관측을 알고 있는 상황에서 맵을 알아내는 것이기 때문이다 [31].
사후확률 p(x1:t | z1:t, u1:t−1)은 파티클 필터를 적용할 수 있다. 각각의 파티클들은 로봇의 가능성 있는 궤적을 나타낸다. 게다가 각각의 샘플은 맵과 관련이 있다. 그 맵은 관측기와 궤적(=파티클)으로부터 만들어진다.
가장 흔한 파티클 필터링 알고리즘은 sampling importance resampling(SIR)이다. 맵핑을 위한 A Rao-Blackwellized SIR filter는 sensor observation과 odometry 정보를 처리한다. 이 알고리즘은 맵과 로봇의 궤적을 나타내는 사후확률을 나타내는 파티클들을 업데이트한다.
다음 네 가지 단계로 요약할 수 있다.
1. Sampling
다음 파티클인 {x(i) t}은 {x(i) t−1}로부터 획득된다. 바로 제안 분포 π를 샘플함으로써!
2. Imprtance Weighting
각각의 importance weight인 w(i)t가 각각의 파티클에 할당된다. 바로 importance sampling principle에 의하여!
이 가중치는 다음 사실을 설명해준다.
사실 : 제안 분포 π는 successor state의 목표 분포(target distribution)과 일반적으로 동일하지 않다.
3. Resampling
importance weight에 따라 파티클들이 그려진다. 이 단계는 파티클들이 유한하기 때문에 매우 중요하다. 게다가 샘플링은 목표 분포와 제안 분포가 다른 상황일 때 파티클 필터를 적용할 수 있다. resampling 이후에 모든 파티클들은 같은 가중치를 갖게 된다.
4. Map Estimation
각각의 파티클(맵 추정치 p(m(i) | x(i)1:t, z1:t)와 대응됨)은 관측치의 history와 로봇의 궤적을 기반으로 하여 계산된다.
이 과정을 반복하다보면 한 가지 문제가 있는데 바로 궤적이 길어질수록 계산량이 많아진다는 것이다.
따라서 Doucet et al. [7]에 따르면 우리는 재귀적으로 이를 계산할 수 있다.
다음 가정을 따르면
(2)식과 (3)식을 기반으로 해서 가중치는 다음과 같이 계산된다.
여기서 η = 1/p(zt | z1:t−1, u1:t−1) 은 정규화 요소(normalization factor)이다.
대부분의 파티클 필터는 식(6)의 구조를 따른다. 반면에 generic 알고리즘은 learning map을 위해서 다른 프레임워크를 사용한다. 이것은 제안 분포가 어떻게 계산하고 resampling 단계를 언제 수행할지에 대해서 question으로 남겨놨다. 다음 섹션부터는 정확한 제안 분포를 계산하는 방법과 적응적으로 리샘플링을 하는 방법에 대해서 소개한다.
III. RBPF WITH IMPROVED PROPOSALS AND ADAPTIVE RESAMPLING
예측 단계에서 다음 파티클을 획득하기 위해서는 제안 분포 π로부터 샘플을 그리는 것이 필요하다. 더 나은 효과를 위해서는 제안 분포가 목표 분포를 잘 근사화하는 것이고, 이는 결과적으로 더 나은 필터 결과를 낳는다.
한 예로, importance weight는 모든 파티클들에 대해서 동일하고 리샘플링 단계는 더이상 필요하지 않다. 불행히도 SLAM에서는 *사후 확률의 closed form은 일반적으로 사용하지 못한다.
*사후 확률의 closed form이 무엇일까...?
결과적으로 일반적인 파티클 필터는 제안 분포로써 odometry 모션 모델을 사용한다. 이 모션 모델은 대부분의 로봇에 쓰일 수 있도록 쉽게 계산할 수 있는 장점을 갖고 있다. 게다가 관측 모델에 따라서 importance weight를 계산할 수 있다.
(더 읽어서 정리해야 함....)
