SLAM 추정 효율성에 대한 고찰 - Rosen 2021 - Advances in Inference and Representation for Simultaneous Localization and Mapping

Posted on Edited on In , ,

시작하기 전…

1저자인 David Rosen은 Northeastern 대학의 조교수이며, John Leonard 교수님, Frank Dellaert 교수님, Luca Carlone 교수님과 함께 다수의 논문을 집필하셨다. SLAM 문제에 대해 수학적으로 파고드는 연구가 많으며, 주로 Certifiable algorithm 연구를 진행하셨다. 대표적인 작업물로는 Juric 2021 논문리뷰에도 나왔던 SE-Sync 라이브러리이다.

2저자 중 한명인 Kevin Doherty는 Semantic SLAM 분야에서 data association 관련 연구를 많이 진행하는 연구자이다.

이 논문은 2가지 파트로 나눌 수 있는데, 저자들이 각각 한 파트씩 적은 것 같다.

  1. 효율적인 SLAM의 representation과 inference 방법 (아마 Rosen이 적으신듯?)
  2. Semantic SLAM과 learned representation (아마 Doherty가 적으신듯?)

이번 글에서는 파트 1인 ‘효율적인 SLAM의 representation과 inference 방법’에 대해 적으려고 한다.

파트 2는 다음 글에서 적으려고 한다.

 

기본적인 SLAM 문제의 구성

Thrun의 확률론적 로보틱스 책, Stachniss의 Handbook of robotics 책 중 SLAM 챕터, Dellaert & Kaess의 Factor graphs for robot perception 논문이나 모두 입을 모아 이야기하고 있다.

“SLAM은 local observation을 모아 global model을 만드는 것이다“.

여기서 local observation은 특정 시점의 센서 데이터 (e.g. 이미지, 라이다 스캔)을 의미하고, global model은 3D scene geometry와 trajectory 정보를 의미하는 것이다.

Local observation을 의미하는 Y 데이터와 global model X가 있을 때, Joint likelihood인 을 작은 conditional likelihood로 표현하면 아래와 같은 식이 된다. 결국 작은 likelihood를 모아 확률론적으로 가장 정확한 global model을 찾는다는 말이 된다.

그리고 SLAM 문제를 잘 표현하기 위해 우리는 probabilistic graphical model을 사용한다. 사실 이렇게 길게 잘 표현하지는 않고, factor graph라고 부르는 경우가 더 많다.

Factor graph를 통해 우리는 수많은 state 사이의 conditional dependency 및 joint distribution을 표현할 수 있다.

이렇게 joint distribution을 찾아낸 후, joint optimization을 통해 최적의 global model을 찾는게 SLAM이라고 볼 수 있다. Joint optimization을 위해 iSAM, GTSAM, g2o, Ceres-solver와 같은 비선형 최적화 라이브러리를 사용한다.

그러면 이제 질문을 해보자.

“가장 효율적인 SLAM은 무엇일까?”

가장 효율적인 SLAM을 하기 위해서는 2가지 고려할 점이 생긴다.

첫째는 Representation - ‘시스템 모델 X는 어떤 정보를 담고 있어야하는가? 이 정보는 인풋 데이터 Y와 어떤 관계를 가지고 있는가?“

둘째는 Inference - ‘X와 Y 사이의 Joint probability distribution을 풀기 위해 어떤 방법을 사용해야하는가?“ 이다.

 

SLAM이 풀기 어려운 이유와 Nonconvexity에 대한 문제

SLAM 문제에 대한 매니폴드를 그려보면, 굉장히 큰 고차원의 non-convex한 모양을 가질 것이다. 이 non-convex한 state space를 라고 해보자. 이런 매니폴드에서 global minimum (i.e. 에러가 가장 낮은, 가장 정답에 가까운 파라미터들의 조합)을 찾기란 굉장히 어렵다.

초창기 SLAM에서는 간단하지만 추적이 가능한 인퍼런스 방법을 사용해서 문제를 풀었다. 예를 들어, Extended Kalman Filter (EKF)나 Monte Carlo sampling 방법 같은 방법으로 말이다.

하지만 2016년 발표된 Past, Present and future of SLAM에서 새로운 SLAM의 기준을 maximum likelihood estimation (MLE)로 푸는 방법을 제안하면서 판도가 바뀌게 되었다. MLE 방법은 이론적으로 최적의 값을 찾을 수 있다. 이 때문에 SLAM 문제의 성향은 사실 Maximum-a-posteriori (MAP)문제에 가깝지만, 여러 테크닉을 사용해서 MLE 문제로 치환해 최적의 값을 찾는 문제로 방향을 바꾼다. 또, SLAM 문제의 특징 중 하나인 sparsity를 이용한다. Sparsity는 간단하게 설명하면 ‘state들끼리 연결되지 않은 경우가 많다’ 라고 할 수 있는데, 예시를 들면 SLAM을 수행하면서 이동하다보면 SLAM을 막 실행한 첫 시점에 보였던 랜드마크가 더 이상 보이지 않아 현재의 위치와 보이지 않는 랜드마크 간에 conditional probability를 연결할 수 없는 경우가 있다. Sparsity를 이용한 1차 또는 2차 미분을 이용해서 최적화를 수행하면, 모든 매니폴드를 탐색하지 않고 빠르게 critical point를 찾아 최적 값을 탐색할 수 있다는 장점이 있다. Gauss-Newton이나 Levenberg-Marquardt 최적화 기법이 여기에 해당하며, 이러한 알고리즘을 충분히 빨리 동작할 수 있게 만들어 실시간으로 동작시킨게 현재까지의 SLAM이다.

하지만 문제가 있다. 1차/2차 미분 값을 이용한다는건 ‘초기값’이 존재하며 최적화 수행 시 초기값 기준으로 1차/2차 미분값을 기반으로 더 좋은 값을 찾아가는 로컬 탐색을 한다는 것인데, 로컬 탐색을 ‘초기값 주변의 critical point’를 찾게 해주는 기능이지, MLE 문제의 전역 최적변수를 찾는 것이 아니다 (i.e. Global minimum이 아닌 local minima를 찾는 것이다). 물론 로컬 탐색으로 찾은 변수가 global minimum일 확률이 아예 없는건 아니지만, SLAM을 해본 사람들은 대부분 최적화 실패로 인한 소위 ‘망한 값’을 본 적이 있을 것이고, 최적화가 성공했다고 해도 은근히 에러가 많이 쌓인 값을 본 적이 있을 것이다. 로컬 탐색은 이처럼 전역 최적 변수를 보장할 수 없다.

그러면 MLE 문제의 전역 최적 변수는 어떻게 찾는 것일까? SLAM 문제처럼 고차원의 non-convex 공간에서 최적점을 찾는 것은 NP-hard 문제이기 때문에, 모든 경우의 수를 검토하는 것은 좋은 방법이 아니다. 근데 또 생각해봐야하는건, 로컬 탐색이 항상 실패하는건 아니다. 우리가 만족할 만큼 꽤나 잘 동작했으니 또 SLAM이 연구개발되온 것일텐데, 그러면 ‘잘된 SLAM’과 ‘안된 SLAM’의 경계가 무엇인지도 생각해봐야한다.

이렇게 SLAM inference 방법을 개발하고 평가할 때는 다음과 같은 2가지 기준으로 평가해야한다.

  1. 알고리즘 - 어떤 조건에서 MLE 전역 최적점을 찾을 수 있을 것인가?
  2. 통계 - MLE 전역 최적점을 찾을 수 있다면, 그 확률이 어떻게 되는가?

 

Certifiable Correct SLAM

Certifiably correct method라는 분야는 전역 최적점을 찾았다는 것을 보장할 수 있는 알고리즘을 연구하는 분야이다. 1/2차 미분으로 로컬 탐색을 하는 보통의 SLAM과는 다르게, convex relaxation 기반으로 전역 최적점을 찾는 연구이다. Convex relaxation은 간단하게 설명하자면, non-convex 문제를 convex 문제로 근사한 후, convex 문제의 최적점을 찾는 방법이다.

Carlone et.al. 2015 - Lagrangian duality in 3D SLAM: Verification techniques and optimal solutions에서는 Lagrangian duality를 이용해서 SLAM 문제를 2차 함수 프로그램으로 변환해 최적점을 찾았다. 이는 결국 semidefinite program의 해를 찾는 것과 같은데, 당시에는 아쉽게도 해를 찾기 위해 로컬 탐색 기법을 사용하긴 했다.

하지만 이런 duality 관련 연구가 발전하면서, Rosen et.al. 2016 - A certifiably correct algorithm for synchronization over the special Euclidean group 연구를 통해 3D pose의 조합에서 해를 찾는 방법이 개발되었고, 이는 곧 3년 후 알고리즘이 몇개 더 추가된 후 SE-Sync 라이브러리가 되었다.

3D pose에 대해 certified algorithm이 개발되었다는건, rotation averaging, two-view registration, sensor extrinsic calibration, 3D registration, shape reconstruction, SLAM에서 사용될 수 있다는 것을 의미한다.

 

Robust estimation

기존 SLAM의 최적화 방식에는 또 다른 큰 문제가 있다. 바로 MLE 알고리즘의 전제가 ‘모든 데이터가 통계적으로 올바를 때 최적점을 보장한다’ 라는 점인데, 모든 센서 데이터가 SLAM에 유용한 데이터를 제공하는게 아니기 때문이다. SLAM을 해본 사람들은 알겠지만, 센서 데이터 속에서 SLAM에 유용한 데이터를 솎아주는 frontend 설계하는 부분은 굉장히 섬세하고 어려운 작업이라 많은 피,땀,눈물을 필요로 한다. 통계적으로 유용한 데이터는 inlier, 유용하지 않은 데이터는 outlier라고 칭하는데, 주로 outlier는 SLAM에서 세워둔 물리적인 모델을 따르지 않는 데이터가 된다. 그리고 MLE 문제를 풀 때, outlier가 몇개 끼어있기만해도 아주 잘못된 결과가 나오는 일이 태반이다.

데이터 속에서 아웃라이어를 제거하기 위해 다양한 방법들이 있다. 가장 많이 사용하는 방법은 RANSAC이며, 수많은 데이터 속에서 소수의 데이터를 샘플링 한 후 나머지 데이터들과 비교해서 적절한 모델을 선택했는지 결정해 나머지 데이터를 아웃라이어 처리하는 방법이다. 또 다른 방법으로는 RRR 전략 (Realizing, reversing, recovering)이 있는데, multiple hypothesis tracking이라고도 불리는 방법으로써 여러가지 가능성을 전부 계산하고, 시간이 지나면서 말이 안되는 가능성은 점점 버리는 방법이다. 최근에는 Pairwise consistency maximization (PCM) 방식이 루프 클로저를 할 때 안정적으로 성공시키는 방법으로 뜨고 있다.

위와 같이 특정 테크닉들을 사용하기도 하지만, 거의 모든 SLAM에 기본적으로 사용하는 기법은 robust estimator (M-estimator) 이다. 여러가지 M-estimatior 커널들이 존재하고, 각각의 커널마다 다른 방법으로 아웃라이어를 제거한다. M-estimator를 적절하게 사용하기 위해 Sunderhauf et.al. 2012 - Switchable constraints for robust pose graph SLAM 논문에서는 여러 M-estimator 커널을 상황에 따라 바꿀 수 있는 기법을 소개했고, Agarwal et.al. 2014 - Dynamic covariance scaling for robust map optimization에서는 적절히 커널의 노이즈 covariance 값을 변경하는 방법을, Olson 2013 - Inference on networks of mixtures for robust robot mapping에서는 여러개의 커널을 동시에 적용하는 max-mixture 기법을 사용했다. M-estimator는 매니폴드의 특정 부분에 non-convexity를 추가로 적용해 좋은 데이터를 섞어내는 테크닉으로써 매우 성공적이였지만, 잘못 사용할 경우 오히려 더 좋지 않은 결과가 나타날 수 있기에 일종의 튜닝의 영역으로 다뤄진다. 진정한 Robust estimation을 위해 Yang et.al. 2020 - One ring to rule them all: Certifiably robust geometric perception with outliers에서는 M-estimator와 certifiably correct optimization 기법을 혼합하는데, 조금 더 설명하자면 semidefinite relaxation을 통해 전체 매니폴드를 convex하게 풀어줌과 동시에 M-estimator를 이용해서 truncated squared-error loss를 적용해 매니폴드를 polynomial 최적화 문제로 변환한다. 이는 전체 데이터에서 아웃라이어가 50% 이상이 넘을 때도 잘 동작하며, 효율적이게 동작하는 dual problem의 해를 구하는 방식을 채택함으로써 적당한 시간 내에 연산을 끝내는 방식을 제안한다.

 

그래서 앞으로 무엇이 더 연구되어야하는가?

  1. Semidefinite programming을 효율적으로 푸는 방법이 필요하다. 엄청나게 많은 데이터를 모아두고 엄청나게 큰 문제를 푸는 방식이 아닌, 실시간으로 SLAM을 돌릴면서 풀 수 있도록 최적화된 incremental semidefinite optimization 기법이 만들어져서 iSAM이나 GTSAM 같은 라이브러리에 포함되면 좋을 것 같다.
  2. Certifiable correct perception 모델의 초창기를 보게 되었는데, 이걸 실시간으로 수행하고 검증할 수 있으면 좋을 것 같다. 왜냐하면, 100% correct한 정보만을 모아서 SLAM을 돌린다면 outlier rejection 과정을 전부 제거할 수 있기 때문이다. 100% 정확한 prior들만 가지고 연산을 한다? 벌써 심장이 뛴다.
  3. 단순히 포인트 클라우드가 아닌, 다른 형태의 맵을 사용해보면 좋을 것 같다. 포인트 클라우드에서 각각의 3D landmark들은 서로 관계가 없고, 이 때문에 서로간의 conditional probability가 전혀 없다. 언제든 랜드마크가 사라져도 할말이 없다는 것이다. 하지만 실제 환경을 보면, 동일 물체에서 나타난 포인트들은 서로 연관이 있을 확률이 굉장히 높다. 예를 들어, 하나의 line에서는 2개의 point가 나타날 것이 아닌가? line이 존재하는 한 다른 point는 절대 사라질 수 없다. 포인트를 넘어서는 representation, 예를 들어 line, plane… semantics 같은 정보를 쓸 수 있다면 더욱 안정적인 매니폴드를 구축할 수 있을 것이다.

그런 의미에서 다음 글에서는 Semantic 정보에 대해 이야기해본다.

Related Posts