Fast Autonomous Exploration with Sparse Topological Graphs in Large-Scale Environments

Exploring large-scale environments autonomously poses a significant challenge. As the size of environments increases, the computational cost becomes a hindrance to real-time operation. Additionally, while frontier-based exploration planning provides convenient access to environment frontiers, it suffers from slow global exploration speed. On the other hand, sampling-based methods effectively explore individual regions but fail to cover the entire environment. To overcome these limitations, this paper presents a hierarchical exploration strategy that integrates frontier-based and sampling-based methods. The proposed strategy consists of a local exploration stage and a global exploration stage. The local exploration stage rapidly expands the free space within environments, while the global stage guides robots to different sub-regions. In the local exploration stage, the planner uniformly samples viewpoints within a sliding window and assesses their utility based on the number of frontiers, which are continually updated as the map evolves. Once a local sub-region is fully explored, the planner initiates global planning to relocate robots to other sub-regions with frontiers. To improve the search speed of global topological graph, this paper introduces a method for constructing a sparse topological graph. During the exploration process, the planner incrementally constructs a three-dimensional sparse topological graph by dynamically capturing the spatial structure of free space through uniform sampling. In various challenging simulated environments, the proposed method demonstrates comparable exploration performance to state-of-the-art approaches. Notably, in terms of computational efficiency, our method achieves a single iteration time that is only one-tenth of the latest and most advanced methods.