Graph-based subterranean exploration path planning using aerial and legged robots

Autonomous exploration of subterranean environments remains a major challenge for robotic systems. In response, this paper contributes a novel graph-based subterranean exploration path planning method that is attuned to key topological properties of subterranean settings, such as large-scale tunnel-like networks and complex multibranched topologies. Designed both for aerial and legged robots, the proposed method is structured around a bifurcated local- and global-planner architecture. The local planner utilizes a rapidly exploring random graph to reliably and efficiently identify paths that optimize an exploration gain within a local subspace, while simultaneously avoiding obstacles, respecting applicable traversability constraints and honoring dynamic limitations of the robots. Reflecting the fact that multibranched and tunnel-like networks of underground environments can often lead to dead-ends and accounting for the robot endurance, the global planning layer works in conjunction with the local planner to incrementally build a sparse global graph and is engaged when the system must be repositioned to a previously identified frontier of the exploration space, or commanded to return-to-home. The designed planner is detailed with respect to its computational complexity and compared against state-of-the-art approaches. Emphasizing field experimentation, the method is evaluated within multiple real-life deployments using aerial robots and the ANYmal legged system inside both long-wall and room-and-pillar underground mines in the United States and in Switzerland, as well as inside an underground bunker. The presented results further include missions conducted within the Defense Advanced Research Projects Agency (DARPA) Subterranean Challenge, a relevant competition on underground exploration.