SLAMDUNK Cartographer Review

  • 2022/08/09
  • 4-minute read

참고 원본 - SLAMDUNK Cartographer

참고 원본 - 오로카 Cartographer

Table of Contents

Abstract 및 Contribution

  • We present the approach used in our backpack mapping platform which achieves real-time mapping and loop closure at 5cm resolution
  • 본 논문에서는 5cm의 해상도를 가지는 지도를 실시간으로 Mapping 및 Loop 탐지를 할 수 있는 알고리즘을 제안하고 있습니다.
  • To achieve real-time loop closure, we use a branch-and-bound approach for computing scan-to-submap matches as constraints.
  • 이와 같은 실시간 Loop 탐지를 위해서, LiDAR 데이터와 SubMap(Local Map) 사이의 매칭을 제약조건으로 계산하기 위해 Branch-and-Bound라는 방식을 제안하고 있습니다.

Graph SLAM?

  • Graph SLAM은 크게 Local SLAM (Frontend)과 Global SLAM (Backend)로 구성됩니다.
  • Local SLAM
    • Local SLAM은 입력으로 로봇의 움직임에 해당하는 정보(Pose)와 주변 환경에 대한 정보(Observation)를 받습니다.
      • 대표적인 움직임에 해당하는 정보는 IMU, Odometry, GPS 등이 있습니다.
      • 대표적인 주변 환경에 해당하는 정보는 LiDAR, Vision, Depth-Camera 등이 있습니다.
    • Local SLAM은 크게 2가지 역할이 있습니다.
      • Pose와 Observation 이용하여 Pose Trajectory를 생성합니다.
      • 생성된 Pose Trajectory와 Observation을 이용하여 Local Map을 생성합니다. (Occupancy Grid Map)
    • Local Map과 Pose Trajectory 사이에는 위치 정보에 대한 Constraint가 존재합니다.
  • Global SLAM
    • Global SLAM은 입력으로 Local Map들과 Pose에 대한 Observation 정보를 받습니다.
    • Global SLAM은 Loop Closure Detection을 수행합니다.
      • $T_1$에서 생성된 Local Map과 $T_{1000}$에서 얻은 Observation을 매칭하는 역할을 수행합니다.
      • 이를 기반으로 Loop Closure Constraint를 생성합니다.
  • Local SLAM 및 Global SLAM을 통해 얻은 Node(Robot Pose, Landmark)와 Edge(Constraint)를 이용하여, Graph형태로 나타내고, 각 Node의 위치를 최적화하는 것이 Graph SLAM

Local Mapping

  • Occupancy Grid Map 형태의 Local Map 생성
  • 각 Cell은 log Odds를 기반으로 기록
  • N개(파라미터로 조절 가능)의 연속된 Observation을 이용하여, 하나의 Local Map을 구성
  • 각각의 Local Map은 생성 시점에서는 서로 독립적이며, 따라서 Local Map의 Quality는 Pose 정보의 정확도(Motion Model)에 달려있음.
  • Local Map생성 시, Noise 보정에 두 가지 알고리즘을 적용
    • Real-time correlated scan matcher 알고리즘은 Pose의 정확도가 높으면, 필요없으며, 정확도가 낮을수록, 성능에 큰 영향을 미침 (속도는 느린편)
    • Ceres scan matcher 알고리즘은 수학적인 최적화가 있으며, 더 높은 정확도가 필요할 때 fine tuning을 위해 사용
  • 아래 이미지의 [X]부분은 실제로 Observation이 측정된 위치이며, 회색 Cell은 Observation 되었지만, 측정값은 존재되지 않은 영역을 의미한다. local_map

Loop Closure Detection

  • Cartographer에 대해 알아보기 전에, Loop Closure Detection에 대해 이해해야한다.
  • Loop Closure Detection은 쉽게 말하면, 현재 Pose 및 Observation을 이용했을 때, 과거에 방문한 지역에 대한 재방문(과거의 Local Map)인지 아닌지를 판단하는 것을 의미한다.
  • 위에서 설명한 Global SLAM에서 수행하는 것처럼, 기존에 존재하는 Local Map과 현재의 Pose의 Observation을 비교하여, 유사한 정도를 파악하고, 이를 기반으로 방문 여부를 결정한다.
  • 당연하게도 Local Map의 개수가 늘어날 수록(전체 지도 크기가 커질수록), 지도의 해상도가 높을수록 계산량이 늘어난다.
  • 또한 이는 NP Hard문제이다. (모든 경우의 수를 일일이 다 확인해보는 것 외에는 풀 수 없는 문제) Loop_Closure

Branch-and-Bound

  • 앞서 얘기했던 것처럼, Loop Closure Detection은 NP Hard문제이므로, 실시간 처리가 힘들다.
  • 이를 Cartographer에서는 Branch-and-Bound 기법을 통해, 실시간 수준으로 계산한다고 한다.
  • Branch-and-Bound는 Local Map 사이의 최적의 위치를 계산하기 위한 Tree 자료구조 기반의 탐색 알고리즘이며, 특정 Local Map 1개와 특정 Pose 1개에 대해, 최적의 위치를 찾는 알고리즘이다.
  • Tree 자료구조의 각 Node는 위치 후보점들이며, Height가 깊어질수록 더 정밀한 위치가 된다.
  • 즉, 저해상도의 지도를 통해 대략적인 Pose를 먼저 확인한 후, 점점 고해상도의 지도를 이용하여 정확한 Pose를 찾는 방식
  • 아래의 그림을 보면 Brute Force를 통해 전체를 다 찾는 방법에 비해, 더 빠른 결과를 얻을 것을 예상할 수 있다. Branch-and-Bound Branch-and-Bound2

Cartographer

  • 논문 이외의 오픈 소스 Cartographer에서 확인할 수 있는 내용
  • ROS Independent하며, ROS Node도 제공하고 있다.
  • ROS Independent하게 사용하려면, 센서 및 움직임에 대한 인터페이스의 구현이 필요
  • 로봇에서 여러 개의 센서를 사용하더라도 다중 센서를 지원! (일반적인 다른 SLAM은 단일 센서를 지원하는 경우가 많음)
  • 다중 로봇 지원 (Multi-Trajectory)
  • 실내, 실외 구분 없이 사용 가능
  • IMU가 있는 Mobile Robot에서는 3D SLAM도 사용 가능
  • Localization Only 기능 사용 가능
    • 일반적인 AMCL과 같은 방식이 아닌 Cartographer Mapping과 동일한 방식을 통해 Localization에 사용 가능
    • 생성되는 Pose Node의 길이를 windowing방식으로 제한하여, 실시간 최적화 가능 (Pose Node가 커지면, 계산량이 점점 늘어나기 때문)
    • Pose Graph의 업데이트 없이(Frozen Pose Graph), 현재 로봇의 Pose Graph와의 비교를 통해 inter trajectory constraint 또는 global constraint를 찾는 방식
  • Life-long Mapping 제공 (Continuous Mapping)
  • Cloud Mapping 제공 (다수의 로봇을 둔 Server에서 Pose Graph Optimization을 진행)
    • GRPC 기반으로 동작
    • 각 로봇에서는 Localization only처럼 한정된 Pose Node만 유지
    • Cloud에서 Local Map(Frozen Pose Graph)를 로봇에게 지속적으로 업데이트
    • Local Map Trimmer를 통해, 겹치는 Local Map을 지워주는 방식을 통해, Pose Graph의 크기에 비례하지 않고, 실제 공간의 크기에 비례하도록 함
  • TSDF(Truncated Signed Distance Function) 지도 형식 제공 (KinectFusion을 통해 유명해졌다고 함)
  • 3D Lidar Mapping의 경우, Voxel이 아닌 Hybrid Grid를 통해, 2.5D Mapping을 하며, Visualization이 까다롭다고 함

Review

  • Cartographer를 실제로 돌려본 것은 오래되었으나, 실질적인 동작에 대해 확인하니, 더 대단하게 느껴지는 것 같다.
  • Hector Mapping에서도 Branch-and-Bound와 같이, 낮은 해상도의 지도부터 비교하여, 높은 해상도까지 정밀하게 위치 추정을 하는 방법을 사용하는데, 추후에는 이에 해당하는 내용도 확인해봐야할 것 같다.
  • 개인적으로 튜닝이 좀 까다로운 편이라, Gmapping을 좋아하는 편이긴한데, 코드 및 상세한 내용을 조금 더 이해하면 좋을 것 같다.
  • 실제 논문과 코드와의 비교를 통해서, 구현 부분과 이론 부분이 어떻게 연결되는 지 확인하면 좋을 것 같다.
  • DFS등의 알고리즘 문제풀이에 사용되는 알고리즘이 실제 적용되는 것을 보니, 쓸데 없는 것을 하고 있지는 않았다(?)는 생각이 든다. cartographer_overview

comments