A 2-Approximation Algorithm for the Online Tethered Coverage Problem
Gokarna Sharma, Pavan Poudel, Ayan Dutta, Vala Zeinali, Tala Talaei Khoei, Jonghoon Kim · 2019
We consider the problem of covering a planar environment, possibly containing unknown 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 discretized into 4-connected grid cells with resolution proportional to the robot size.Starting at S, the task of the robot is to visit each cell in the environment that are not occupied by obstacles and return to S with the cable fully retracted.Our goal is to minimize the total distance traveled by the robot to fully cover the unknown environment while avoiding tangling of the cable.In this paper, we present a novel online algorithm to solve this problem that achieves 2-approximation for the total distance traveled by the robot compared to the minimum distance that needs to be traveled.Our algorithm significantly improves the 2L/D-approximation achieved by the best previously known online algorithm designed for this problem.The approximation bound is also validated using rigorous simulated experiments.• Condition (a): Each path π i (a sequence of cells) starts and ends at S, • Condition (b): At the end of each path π i , the cable is fully retracted, and • Condition (c): The paths in Π collectively cover the environment P , i.e., ∪ p i=1 π i = P .We will show that any algorithm satisfying simultaneously