Factor Graph
- 카테고리: State estimation & navigation › Localisation
- 태그: state-estimation, slam, probabilistic-inference, optimization, sensor-fusion
확률 분포를 팩터들의 곱으로 표현하는 이분 그래프로, 자세와 랜드마크 같은 미지 변수를 그것을 제약하는 측정 및 사전 분포와 연결한다.
정의
팩터 그래프(factor graph)에는 두 종류의 노드가 있다. 변수 노드는 로봇 자세, 속도, 센서 바이어스, 랜드마크 위치처럼 추정해야 할 미지량을 나타낸다. 팩터 노드는 사전 분포, 두 자세 사이의 주행거리 측정, 랜드마크에 대한 카메라 관측처럼 그 미지량에 관한 정보 조각을 나타내며, 각 팩터는 자신이 관여하는 변수에만 연결된다. 그래프는 모든 팩터의 곱과 같은 결합 분포를 기술하며, 이로써 문제의 구조, 즉 어떤 미지량들이 연결되어 있고 어떤 측정이 희소하고 국소적인 제약인지가 명시적으로 드러난다.
팩터 그래프는 Kschischang, Frey, Loeliger(2001)가 추론을 위한 일반적인 틀로 제시했으며, 주로 평활화와 매핑에 관한 Dellaert와 Kaess의 연구를 통해 로봇공학에 널리 채택되었다. 가우시안 잡음 모델에서, 모든 팩터가 주어졌을 때 모든 변수의 가장 가능성 높은 값을 찾는 것은 비선형 최소제곱 문제이다. 각 팩터는 정보 행렬로 가중된 잔차를 기여한다. 풀이기는 잔차를 선형화하고, 그래프의 희소성을 활용해 결과로 나온 선형 시스템을 효율적으로 분해하며, Gauss-Newton이나 Levenberg-Marquardt로 반복한다. iSAM2 같은 점진적 풀이기는 새 팩터가 들어올 때 처음부터 다시 풀지 않고 해를 갱신한다. GTSAM은 팩터 그래프를 직접 구현하며, g2o와 Ceres 같은 범용 최소제곱 라이브러리도 같은 종류의 문제에 쓰인다.
실용적인 주된 매력은 모듈성이다. 새 센서는 자체 잔차와 잡음 모델을 갖는 새로운 팩터 유형이 되므로, IMU 사전적분, GPS, 휠 주행거리, LiDAR 스캔 매칭, 루프 클로저, 학습된 측정 모델이 모두 하나의 추정기 안에 들어갈 수 있다. 포즈 그래프 최적화(pose graph optimization)는 모든 변수가 자세이고 모든 팩터가 상대 자세 제약인 특수한 경우이다. 일반적인 팩터 그래프는 랜드마크, 속도, 바이어스, 보정 파라미터도 담을 수 있다. 고정 지연 평활기는 계산량을 제한하기 위해 오래된 변수를 주변화하며, 그 대가로 일부 선형화 지점이 고정된다. 잘못된 루프 클로저 같은 이상치에는 강인 비용 함수나 전환 가능 제약이 필요하다. 일반적인 최소제곱 해는 잘못된 팩터 하나에도 크게 끌려갈 수 있기 때문이다.
중요한 이유
팩터 그래프는 현대 SLAM과 다중 센서 상태 추정의 공통 언어이다. 엔지니어는 추정기를 다시 설계하지 않고도 센서, 사전 분포, 제약을 추가할 수 있으며, 각 측정이 어떤 잡음 및 독립성 가정을 담고 있는지가 명시적으로 드러난다.
주요 응용
- LiDAR, 시각, 시각 관성 시스템을 위한 SLAM 백엔드
- IMU, GPS, 휠 주행거리, 비전의 다중 센서 융합
- 카메라, LiDAR, IMU 외부 파라미터 보정
- Structure from Motion과 번들 조정
- 확률적 추론으로 정식화한 궤적 최적화
- 공유 제약을 이용한 다중 로봇 매핑
실제 사례
한 지상 차량이 미리 기록한 지하 지도에 대해 지표 투과 레이더(GPR)로 위치를 추정한다. 각 시간 단계마다 자세 변수가 추가되고, 관성 또는 휠 주행거리가 연속한 자세 사이에 팩터를 추가하며, 사전 지도에 대한 레이더 정합이 현재 자세에 팩터를 추가한다. 레이더용 센서 모델을 손으로 작성하는 대신, GPR 위치 추정을 위한 학습된 팩터 그래프 모델에 관한 연구에서처럼 측정 팩터를 데이터로부터 학습할 수 있다. 팀은 최신 자세를 실시간으로 얻을 수 있도록 점진적 평활기를 실행하며, 매 시험 주행 뒤에 팩터 잔차를 살펴 잡음 모델이 너무 빡빡하거나 너무 느슨하게 설정된 측정 유형을 찾는다.
흔한 오해
- 팩터 그래프는 풀이기이다 — 팩터 그래프는 문제의 표현이다. 일괄 Gauss-Newton이나 점진적 평활화 같은 풀이기는 별개의 선택이다
- 팩터 그래프는 포즈 그래프만 기술한다 — 랜드마크, 속도, 바이어스, 보정 파라미터, 임의의 측정 모델도 담을 수 있다
- 팩터를 더 추가하면 추정이 언제나 좋아진다 — 잡음 모델이 틀린 팩터나 이상치 측정은 강인 비용을 쓰지 않으면 해 전체를 오염시킬 수 있다
알아야 할 사람
- SLAM 및 상태 추정 엔지니어
- 센서 융합 및 내비게이션 개발자
- 로봇공학에서 확률적 추론을 연구하는 연구자
- 자율 주행 차량 위치 추정 팀
관련 기술
- GTSAM
- iSAM2
- g2o
- Ceres Solver
- 번들 조정(Bundle Adjustment)
- Levenberg-Marquardt 알고리즘(Levenberg-Marquardt Algorithm)
관련 용어
관련 프로젝트
- LingBot-Map: Streaming 3D reconstruction from one camera: pose and depth for every frame, live
- oomwoo: Open-source DIY robot vacuum: 3D-printed, ROS2 + 2D LiDAR, fully local.
- Cartographer: Google's real-time 2D and 3D SLAM system for multi-platform robotics
- FAST-LIVO2: Fast, direct LiDAR-inertial-visual odometry from HKU-MARS, published in IEEE T-RO
- DimOS: Python robotics runtime with agents, SLAM and teleop, no ROS required
- evo: De-facto standard tool for evaluating and plotting odometry/SLAM trajectories
동영상
- Factor Graph - 5 Minutes with Cyrill: Cyrill Stachniss
- MIT Robotics - Frank Dellaert - Factor Graphs for Perception and Action: MIT Robotics