Efficient Sampling-Based Planning for Subterranean Exploration

Abstract

The paper proposes a path planning solution for autonomous robotic exploration of complex subterranean environments. The work contributes to the family of graph-based planners by bringing the following improvements. Firstly, an occupancy grid-based sample-and-project solution to terrain-assessment is proposed instead of building an explicit elevation map of the environment. Secondly, the solution-search method is formulated as a constraint-satisfaction problem to obtain a good-enough solution instead of optimizing for a single objective function parametrized by penalty gains. This method is shown to significantly improve the computational efficiency of the planner. Thirdly, a coordination solution is proposed that relies on the position histories of the robots instead of merged-maps or merged-graphs, therefore, making the planning solution resilient to inter-robot map misalignments, while also reducing the communication bandwidth required to carry out coordination. Finally, the planner also takes into account changes in the environment such as blocked passages that are initially open. The proposed planning solution is demonstrated at the DARPA Subterranean Challenge final event by team MARBLE, the third place finisher of the challenge.