preprint
Gathering a Closed Chain of Robots on a Grid
Sebastian
Abshoff
author
Andreas
Cord-Landwehr
author
Matthias
Fischer
author 146
Daniel
Jung
author 37827
Friedhelm
Meyer auf der Heide
author 15523
63
department
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.
2015
eng
arXiv:1510.05454
1510.05454
Abshoff, S., Cord-Landwehr, A., Fischer, M., Jung, D., & Meyer auf der Heide, F. (2015). Gathering a Closed Chain of Robots on a Grid. <i>ArXiv:1510.05454</i>.
Abshoff, Sebastian, Andreas Cord-Landwehr, Matthias Fischer, Daniel Jung, and Friedhelm Meyer auf der Heide. “Gathering a Closed Chain of Robots on a Grid.” <i>ArXiv:1510.05454</i>, 2015.
S. Abshoff, A. Cord-Landwehr, M. Fischer, D. Jung, F. Meyer auf der Heide, ArXiv:1510.05454 (2015).
@article{Abshoff_Cord-Landwehr_Fischer_Jung_Meyer auf der Heide_2015, title={Gathering a Closed Chain of Robots on a Grid}, journal={arXiv:1510.05454}, author={Abshoff, Sebastian and Cord-Landwehr, Andreas and Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm}, year={2015} }
S. Abshoff, A. Cord-Landwehr, M. Fischer, D. Jung, and F. Meyer auf der Heide, “Gathering a Closed Chain of Robots on a Grid,” <i>arXiv:1510.05454</i>. 2015.
Abshoff S, Cord-Landwehr A, Fischer M, Jung D, Meyer auf der Heide F. Gathering a Closed Chain of Robots on a Grid. <i>arXiv:151005454</i>. 2015.
Abshoff, Sebastian, et al. “Gathering a Closed Chain of Robots on a Grid.” <i>ArXiv:1510.05454</i>, 2015.
164492020-04-07T07:20:46Z2022-01-06T06:52:50Z