Hierarchical coverage path planning for a multi-modal robot exploring disconnected regions

Abstract

We present a near-optimal Coverage Path Planning (CPP) approach for multi-modal robots in complex environments with multiple arbitrarily shaped disconnected regions. The problem arises in ground coverage missions conducted in unstructured terrains, such as planetary exploration or search and rescue missions, where safe regions are disconnected by areas of high slope that a robot with a single locomotion modality cannot traverse. A multi-modal robot can switch between different locomotion modalities (e.g. driving and flying) to safely navigate these challenging environments while ensuring complete coverage. The proposed method identifies both traversable and non-traversable areas based on Digital Elevation Model (DEM) meshes. The problem is then formulated as a hierarchical Traveling Salesman Problem (TSP) and solved using Mixed-Integer Linear Programming (MILP). The proposed approach is evaluated on 500 randomly generated maps and four real-world simulation scenarios constructed from Martian terrain DEM data.