Motion planning in R 3 for multiple tethered robots.

Abstract

The problem of motion planning in three dimensions for $n$ tethered\nrobots is considered. Motivation for this problem comes from the\nneed to coordinate the motion of a group of tethered underwater\nvehicles. The motion plan must be such that it can be executed without\nthe robots' tethers becoming tangled. The simultaneous-motion plan\nis generated in three steps. First, an ordering of the robots is \nproduced that maximizes the number of robots that can move along\nstraight lines to their targets. Then paths for the robots are\ncomputed assuming they move sequentially in the given order. \nTwo methods of computing the sequential-motion plan for the \nrobots are presented. The first method is computationally\nsimple but guarantees no bound on the path length with respect\nto the optimal length; the second method guarantees nearly\noptimal paths for the given ordering at the expense of additional\ncomputation. Finally, trajectories are determined that allow the\nrobots to move simultaneously. The motion plan generated is\nguaranteed not to result in tangled tethers. The algorithms we \npresent are shown to run in $O(n^4)$ time in total in the\nworst case, which is less than the additional computation needed\nto produce the nearly optimal paths using existing approximation\nalgorithms.