preprint
Asymptotically Optimal Gathering on a Grid
Andreas
Cord-Landwehr
author
Matthias
Fischer
author 146
Daniel
Jung
author 37827
Friedhelm
Meyer auf der Heide
author 15523
63
department
In this paper, we solve the local gathering problem of a swarm of $n$
indistinguishable, point-shaped robots on a two dimensional grid in
asymptotically optimal time $\mathcal{O}(n)$ in the fully synchronous
$\mathcal{FSYNC}$ time model. Given an arbitrarily distributed (yet connected)
swarm of robots, the gathering problem on the grid is to locate all robots
within a $2\times 2$-sized area that is not known beforehand. Two robots are
connected if they are vertical or horizontal neighbors on the grid. The
locality constraint means that no global control, no compass, no global
communication and only local vision is available; hence, a robot can only see
its grid neighbors up to a constant $L_1$-distance, which also limits its
movements. A robot can move to one of its eight neighboring grid cells and if
two or more robots move to the same location they are \emph{merged} to be only
one robot. The locality constraint is the significant challenging issue here,
since robot movements must not harm the (only globally checkable) swarm
connectivity. For solving the gathering problem, we provide a synchronous
algorithm -- executed by every robot -- which ensures that robots merge without
breaking the swarm connectivity. In our model, robots can obtain a special
state, which marks such a robot to be performing specific connectivity
preserving movements in order to allow later merge operations of the swarm.
Compared to the grid, for gathering in the Euclidean plane for the same robot
and time model the best known upper bound is $\mathcal{O}(n^2)$.
2016
eng
arXiv:1602.03303
1602.03303
@article{Cord-Landwehr_Fischer_Jung_Meyer auf der Heide_2016, title={Asymptotically Optimal Gathering on a Grid}, journal={arXiv:1602.03303}, author={Cord-Landwehr, Andreas and Fischer, Matthias and Jung, Daniel and Meyer auf der Heide, Friedhelm}, year={2016} }
A. Cord-Landwehr, M. Fischer, D. Jung, F. Meyer auf der Heide, ArXiv:1602.03303 (2016).
Cord-Landwehr, Andreas, et al. “Asymptotically Optimal Gathering on a Grid.” <i>ArXiv:1602.03303</i>, 2016.
Cord-Landwehr A, Fischer M, Jung D, Meyer auf der Heide F. Asymptotically Optimal Gathering on a Grid. <i>arXiv:160203303</i>. 2016.
A. Cord-Landwehr, M. Fischer, D. Jung, and F. Meyer auf der Heide, “Asymptotically Optimal Gathering on a Grid,” <i>arXiv:1602.03303</i>. 2016.
Cord-Landwehr, Andreas , Matthias Fischer, Daniel Jung, and Friedhelm Meyer auf der Heide. “Asymptotically Optimal Gathering on a Grid.” <i>ArXiv:1602.03303</i>, 2016.
Cord-Landwehr, A., Fischer, M., Jung, D., & Meyer auf der Heide, F. (2016). Asymptotically Optimal Gathering on a Grid. <i>ArXiv:1602.03303</i>.
164502020-04-07T07:20:47Z2022-01-06T06:52:50Z