Planar Curve Routing for Tethered-Robot Motion Planning

The following problem appears in robotics. A number of small, circular robots live in a common planar workspace. Each is attached by a flexible cable of finite length to a point on the boundary of this workspace. Each robot has a target point in the workspace it must reach. When a robot has reached its target, its cable will have been dragged out into the workspace and possibly pushed and bent by other robots. The cables remain taut at all times and may not overlap, but may bend around other robots. When only the target points are specified for the robots, their motion can produce arbitrarily complex cable configurations. The more complex a cable configuration is, the more restrictive it is to the motion of the robots. To keep restrictions on the robots' motions at a minimum, it is necessary to specify, in addition to the target points, a configuration of the cables that is as simple as possible but allows all robots to reach their targets. The problem of finding the simplest cable con..