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

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.