Speeded Up Elevation Map for Exploration of Large-Scale Subterranean Environments

In this paper, we address a problem of the exploration of large-scale subterranean environments using autonomous ground mobile robots. In particular, we focus on an efficient data representation of the large-scale elevation map, where it is desirable to capture the shape of the terrain to avoid areas not traversable by a robot. Subterranean environments such as mine tunnel systems can be in units of kilometers large, but only a relatively small portion of the environment represents observable parts. Therefore, uniform grid-based elevation maps with resolution in units of centimeters are not memory efficient, and more suitable are hierarchical tree-based structures. However, hierarchical structures suffer from the increased computational requirements of accessing particular grid cells needed in determination of the navigational goals or evaluation of the terrain traversability in planning safe and cost-efficient paths. We propose a speed-up technique to combine the benefits of uniform grid-based and tree-based representations. The proposed elevation map representation keeps the memory footprint low using tree structure but enables fast access to the grid cells corresponding to the robot surroundings. The efficiency of the proposed data representation is demonstrated in an experimental deployment of the autonomous exploration of outdoor and subterranean environments.