Designing Sparse Reliable Pose-Graph SLAM: A Graph-Theoretic Approach
This work addresses the problem of improving computational efficiency and reliability in SLAM for robotics, though it appears incremental as it builds on existing graph-theoretic approaches.
The paper tackled the open problem of designing sparse D-optimal pose-graph SLAM by characterizing graphs with maximum weighted spanning trees, establishing new theoretical results like monotone log-submodularity, and developing near-optimal approximation algorithms with provable guarantees, validated on random graphs and a public dataset.
In this paper, we aim to design sparse D-optimal (determinantoptimal) pose-graph SLAM problems through the synthesis of sparse graphs with the maximum weighted number of spanning trees. Characterizing graphs with the maximum number of spanning trees is an open problem in general. To tackle this problem, several new theoretical results are established in this paper, including the monotone log-submodularity of the weighted number of spanning trees. By exploiting these structures, we design a complementary pair of near-optimal efficient approximation algorithms with provable guarantees. Our theoretical results are validated using random graphs and a publicly available pose-graph SLAM dataset.