  This paper considers the collaborative graph exploration problem in
GPS-denied environments, where a group of robots are required to cover a graph
environment while maintaining reliable pose estimations in collaborative
simultaneous localization and mapping (SLAM). Considering both objectives
presents challenges for multi-robot pathfinding, as it involves the expensive
covariance inference for SLAM uncertainty evaluation, especially 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 and
distance-efficient loop-closing actions, called loop edges, 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 more efficient evaluation of SLAM uncertainty
than covariance inference, and (2) allows the application of approximation
algorithms in submodular optimization to provide optimality guarantees. We
further introduce the ordering heuristics to improve objective values while
preserving the optimality bound. Simulation experiments over randomly generated
graph environments verify the efficiency of our methods in finding paths for
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.
