Coverage With Self-Induced Obstacles on Grids

Abstract

Modelling environments as grids is a common approach in robotics, particularly for coverage path planning tasks, where the goal is to fully traverse an area or visit key points. In this paper, we introduce a new variant of coverage planning, inspired by applications such as open-pit mining, harvesting, and painting, where the robot's own actions modify the environment. Specifically, self-induced obstacles arise as a result of task execution, e.g. piles of rubble from drilling, and must be avoided in all future motion planning. We formally model these constraints by assuming that once a vertex is visited, it becomes non-traversable, and define an obstacle as self-induced if its existence depends on the set of previously visited vertices. This situation has not been addressed in existing formulations, which assume static obstacle placement. We provide a formal analysis of how the existence of solutions is affected by geometric constraints, such as vertex distances and robot turning radius, as defined by the Dubins vehicle. We also propose modelling the problem using self-deleting graphs based on the line graph of the grid. This provides a sufficient representation that captures the problem's dynamics and enables the use of general graph search algorithms. Our experimental evaluation demonstrates that our approach outperforms classical coverage path algorithms in terms of computation time and solution quality.