Shortest path planning for a tethered robot

We consider the problem of finding the shortest path for a tethered robot in a planar environment with polygonal obstacles of n total vertices. The robot is attached to an anchor point by a tether of finite length. The robot can cross the tether; i.e., the tether can be self-intersecting. Neither the robot nor the tether may enter the interior of any obstacle. The initial tether configuration is given as a polyline of k vertices.If the tether is automatically retracted and kept taut, we present an O(kn2log⁡n)O(kn2log⁡n) time algorithm to find the shortest path between the source and the destination point. This improves the previous O(lkn3)O(lkn3) time algorithm [24], where l   is the number of loops in the initial tether configuration. If the tether can only be retracted while the robot backtracks along the tether, we present an algorithm to find the shortest path in O((n+log⁡k)log⁡n)O((n+log⁡k)log⁡n) time.