An Efficient Coverage Method for Irregularly Shaped Terrains

Abstract

In mobile robotics, effectively covering known terrains is essential. While grid-based methods surpass exact cell decomposition in path length and multi-robot scalability, they face challenges in irregular areas. Here we develop a model for shortening coverage paths in arbitrary environments using grid-based methods, which redefines the path optimization problem as finding the largest Hamiltonian sub-graph of a given grid graph. Additionally, we present a Hamiltonian cycle expansion strategy to simplify the resolution process and propose a low-repetitive coverage path planner based on the strategy. Our path planner enables the quick finding of an efficient full coverage path in any region. Simulation results show that our algorithm consistently produces efficient coverage paths across diverse settings and demonstrates its adaptability in multi-robot systems.