We consider the problem of covering an unknown planar environment possibly containing obstacles using a robot of square size
D × D attached to a fixed point S by a cable of finite length L. The
environment is structured as a cell layout with resolution proportional to the robot size D × D, imposed on it. Starting at S, the task
for the robot is to visit each cell of the environment (not occupied by obstacles) and return to S with the cable fully retracted. In a single time step, the robot can move from one cell to one of its four adjacent cells. The cable length of L allows the robot to visit a cell that is at distance at most L (i.e., ⌊L/D⌋ cells in the environment at increasing distance) from S. Our goal is to minimize the total
distance traveled by the robot to fully cover the unknown environment avoiding tangling the cable. In this paper, we present the first
online tethered coverage path planning algorithm that achieves 2- approximation for the total distance traveled by the robot compared to the distance traveled using an optimal offline algorithm. Our algorithm guarantees that the cable never tangles. Moreover, our algorithm significantly improves the 2L/D-approximation achieved by the best previously known algorithm designed for this problem.
Furthermore, we show that there are instances for which no on- line algorithm achieves better than 2-approximation, which implies
that our algorithm is essentially optimal. Simulation experiments illustrate the usefulness and efficiency of our proposed algorithm.