A Continuous, Local Strategy for Constructing a Short Chain of Mobile Robots

We are given an arbitrarily shaped chain of

n

robots with fixed end points in the plane. We assume that each robot can only see its two neighbors in the chain, which have to be within its viewing range. The goal is to move the robots to the straight line between the end points. Each robot has to base the decision where to move on the relative positions of its neighbors only. Such

local

strategies considered until now are based on discrete rounds, where a round consists of a movement of each robot. In this paper, we initiate the study of continuous local strategies: The robots may perpetually observe the relative positions of their neighbors, and may perpetually adjust their speed and direction in response to these observations. We assume a speed limit for the robots, that we normalize to one, which corresponds to the viewing range. Our contribution is a continuous, local strategy that needs time

${\mathcal O}(min\{n, (OPT+d) \log(n)\})$

. Here

d

is the distance between the two stationary end points, and

OPT

is the time needed by an optimal global strategy. Our strategy has the property that the robot which reaches its destination last always moves with maximum speed. Thus, the same bound as above also holds for the distance travelled.