Map Explorations via Dynamic Tree Structured Graph

Abstract

Map exploration in unknown environments is the key to various robotics applications (e.g., 3D reconstruction, search and rescue). However, finding the optimal path to maximize the environmental coverage is NP-hard. To overcome this problem, this research proposes a dynamic generalized cost-benefit (DGCB) algorithm to explore unknown environments via utilizing submodularity and tree-Structured routing. Moreover, the theoretical guarantees at each time step are proved via submodularity. The experiments show that the proposed method outperforms benchmark methods (e.g., FUEL, GCB, GCB-MST).