Computationally-Fast Coverage Path Planning for Planetary Multi-Modal Mobility Robots Traversing Disconnected Regions

Abstract Planetary exploration missions require efficient coverage path planning methods to reliably and rapidly investigate vast areas of scientific interest. This task is particularly challenging due to strict computational limitations and complex terrain properties, with nontraversable regions separating the target area into multiple arbitrarily shaped safe regions. For covering such terrains, the proposed work presents a multi-stage heuristic coverage path planning method that utilizes multi-modal robots capable of switching between ground and aerial locomotion. Safe regions are extracted from a Digital Elevation Map (DEM) and individually covered by solving a Traveling Salesman Problem (TSP) using a Lin-Kernighan Heuristic solver. The sub-tour endpoints are then connected through an additional TSP to generate the complete coverage path. Unlike existing approaches that assume convexity, the proposed method generalizes to complex planetary scenarios and prioritizes computational efficiency. The method is evaluated on over 500 randomly generated maps, as well as scenarios derived from Martian DEM data, using a single core of a low computation power embedded computer. The experimental results demonstrate the viability and computational efficiency of the approach across various complex scenarios with arbitrarily shaped regions. When compared with state-of-the-art planners, the proposed method achieves substantially reduced computation times while producing coverage paths of comparable length.