iMCB-PGO : Incremental Minimum Cycle Basis Construction and Application to Online Pose Graph Optimization

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Journal / PublicationIEEE Robotics and Automation Letters
Online published7 Aug 2024
Publication statusOnline published - 7 Aug 2024

Abstract

Pose graph optimization (PGO) is a fundamental technique for robot localization. It is typically encoded with a sparse graph. The recent work on the cycle-based PGO reveals the merits of solving PGOs in the graph cycle space, which brings the computation of the minimum cycle basis (MCB) into the robotics community. However, due to batch-MCB's inability to handle the graph topology changes, it is hard for its use in real-time applications. In practice, PGOs are constructed incrementally, which requires us to solve MCB problems in an incremental setting. In this letter, we propose an exact method to solve MCB problem in an incrementally constructed graph. Methodology-wise, we first compute a tight superset called isometric set which contains an MCB, and then apply independence tests to evaporate redundant cycles to form an MCB. Our main contribution is the construction of an effective algorithm to update the superset, namely the isometric set, in an incremental setting. Our update rules preserve the optimality, thus yielding an exact incremental MCB algorithm, which is termed as iMCB. We integrate our iMCB algorithm into the cycle-based PGO, forming the iMCB-PGO approach. We validate the superior performance of our iMCB-PGO on a range of simulated and real-world datasets. © 2024 IEEE.

Research Area(s)

  • Approximation algorithms, Cycle-based Pose Graph Optimization, Incremental Minimum Cycle Basis, Lenses, Optimization, Real-time systems, Simultaneous localization and mapping, SLAM Back-end, Sun, Vectors