TY - GEN
AB - We consider the following variant of the two dimensional gathering problem
for swarms of robots: Given a swarm of $n$ indistinguishable, point shaped
robots on a two dimensional grid. Initially, the robots form a closed chain on
the grid and must keep this connectivity during the whole process of their
gathering. Connectivity means, that neighboring robots of the chain need to be
positioned at the same or neighboring points of the grid. In our model,
gathering means to keep shortening the chain until the robots are located
inside a $2\times 2$ subgrid. Our model is completely local (no global control,
no global coordinates, no compass, no global communication or vision, \ldots).
Each robot can only see its next constant number of left and right neighbors on
the chain. This fixed constant is called the \emph{viewing path length}. All
its operations and detections are restricted to this constant number of robots.
Other robots, even if located at neighboring or the same grid point cannot be
detected. Only based on the relative positions of its detectable chain
neighbors, a robot can decide to obtain a certain state. Based on this state
and their local knowledge, the robots do local modifications to the chain by
moving to neighboring grid points without breaking the chain. These
modifications are performed without the knowledge whether they lead to a global
progress or not. We assume the fully synchronous $\mathcal{FSYNC}$ model. For
this problem, we present a gathering algorithm which needs linear time. This
result generalizes the result from \cite{hopper}, where an open chain with
specified distinguishable (and fixed) endpoints is considered.
AU - Abshoff, Sebastian
AU - Cord-Landwehr, Andreas
AU - Fischer, Matthias
AU - Jung, Daniel
AU - Meyer auf der Heide, Friedhelm
ID - 16449
T2 - arXiv:1510.05454
TI - Gathering a Closed Chain of Robots on a Grid
ER -