Shortest path planning for a tethered robot or an anchored cable

Abstract

We consider the problem of planning shortest paths for a tethered robot with a finite length tether in a 2D environment with polygonal obstacles. We present an algorithm that runs in time O((k/sub l/+1)/sup 2/n/sup 4/) and finds the shortest path or correctly determines that none exists that obeys the constraints, where n is the number obstacle vertices, and k/sub l/ is the number loops in the initial configuration of the tether. The robot may cross its tether but nothing can cross obstacles, which cause the tether to bend. The algorithm can also be applied to planning a shortest path for the free end of an anchored cable.