---
res:
bibo_abstract:
- "In this paper, we solve the local gathering problem of a swarm of $n$\r\nindistinguishable,
point-shaped robots on a two dimensional grid in\r\nasymptotically optimal time
$\\mathcal{O}(n)$ in the fully synchronous\r\n$\\mathcal{FSYNC}$ time model. Given
an arbitrarily distributed (yet connected)\r\nswarm of robots, the gathering problem
on the grid is to locate all robots\r\nwithin a $2\\times 2$-sized area that is
not known beforehand. Two robots are\r\nconnected if they are vertical or horizontal
neighbors on the grid. The\r\nlocality constraint means that no global control,
no compass, no global\r\ncommunication and only local vision is available; hence,
a robot can only see\r\nits grid neighbors up to a constant $L_1$-distance, which
also limits its\r\nmovements. A robot can move to one of its eight neighboring
grid cells and if\r\ntwo or more robots move to the same location they are \\emph{merged}
to be only\r\none robot. The locality constraint is the significant challenging
issue here,\r\nsince robot movements must not harm the (only globally checkable)
swarm\r\nconnectivity. For solving the gathering problem, we provide a synchronous\r\nalgorithm
-- executed by every robot -- which ensures that robots merge without\r\nbreaking
the swarm connectivity. In our model, robots can obtain a special\r\nstate, which
marks such a robot to be performing specific connectivity\r\npreserving movements
in order to allow later merge operations of the swarm.\r\nCompared to the grid,
for gathering in the Euclidean plane for the same robot\r\nand time model the
best known upper bound is $\\mathcal{O}(n^2)$.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: 'Andreas '
foaf_name: 'Cord-Landwehr, Andreas '
foaf_surname: Cord-Landwehr
- foaf_Person:
foaf_givenName: Matthias
foaf_name: Fischer, Matthias
foaf_surname: Fischer
foaf_workInfoHomepage: http://www.librecat.org/personId=146
- foaf_Person:
foaf_givenName: Daniel
foaf_name: Jung, Daniel
foaf_surname: Jung
foaf_workInfoHomepage: http://www.librecat.org/personId=37827
- foaf_Person:
foaf_givenName: Friedhelm
foaf_name: Meyer auf der Heide, Friedhelm
foaf_surname: Meyer auf der Heide
foaf_workInfoHomepage: http://www.librecat.org/personId=15523
dct_date: 2016^xs_gYear
dct_language: eng
dct_title: Asymptotically Optimal Gathering on a Grid@
...