Optimal Online Coverage Path Planning with Energy Constraints

Abstract

We consider the problem of covering an unknown polygonal environment possibly containing obstacles using a robot of square size $L\times L$. The environment is structured as a grid with resolution proportional to the robot size $L\times L$, imposed on it. The robot has a limited energy budget -- it has to visit a charging station before it runs out of its energy; there is a single charging station in the environment. In a single time step, the robot can move from one grid cell to one of its four adjacent cells. The energy budget B allows the robot to travel at most B distance, i.e., B grid cells. The objective of the robot is to minimize both total distance traveled to cover the environment (visit each cell of the environment not occupied by obstacles) and the number of visits to the charging station. In this paper, we present thefirst online coverage path planning algorithm that achieves O(log (B/L))-approximation for both objectives. Our bound is optimal since there exists a lower bound of Ømega(log (B/L)) for this problem for both objectives. Simulation results show the efficiency of our approach.