Multi-Robot Active Graph Exploration with Reduced Pose-SLAM Uncertainty via Submodular Optimization

This paper considers the multi-robot active graph exploration problem, where robots need to collaboratively cover a graph environment while maintaining reliable pose estimation in collaborative Simultaneous Localization and Mapping (SLAM). Considering both objectives presents challenges for multi-robot pathfinding, as it involves the expensive covariance propagation for SLAM uncertainty evaluation, especially when considering various combinations of robots’ paths. To reduce the computational complexity, we propose an efficient two-stage strategy where exploration paths are first generated for quick coverage, and then enhanced by adding informative loop-closing actions along the paths for reliable pose estimation. We formulate the latter problem as a non-monotone submodular maximization problem by relating SLAM uncertainty with pose graph topology, which (1) facilitates a more efficient evaluation of SLAM uncertainty than covariance inference, and (2) allows the employment of approximation algorithms in submodular optimization to provide suboptimality guarantees. We further introduce ordering heuristics to improve the objective values while preserving the optimality bound. Simulation experiments over randomly generated graph environments verify the effectiveness of our methods to achieve quick coverage and enhanced pose graph reliability, and benchmark the performance of the approximation algorithms and the greedy-based algorithm in the loop edge selection problem. Our implementations will be open-source at https://github.com/bairuofei/CGE.