---
res:
bibo_abstract:
- "We consider a swarm of $n$ autonomous mobile robots, distributed on a\r\n2-dimensional
grid. A basic task for such a swarm is the gathering process: All\r\nrobots have
to gather at one (not predefined) place. A common local model for\r\nextremely
simple robots is the following: The robots do not have a common\r\ncompass, only
have a constant viewing radius, are autonomous and\r\nindistinguishable, can move
at most a constant distance in each step, cannot\r\ncommunicate, are oblivious
and do not have flags or states. The only gathering\r\nalgorithm under this robot
model, with known runtime bounds, needs\r\n$\\mathcal{O}(n^2)$ rounds and works
in the Euclidean plane. The underlying time\r\nmodel for the algorithm is the
fully synchronous $\\mathcal{FSYNC}$ model. On\r\nthe other side, in the case
of the 2-dimensional grid, the only known gathering\r\nalgorithms for the same
time and a similar local model additionally require a\r\nconstant memory, states
and \"flags\" to communicate these states to neighbors in\r\nviewing range. They
gather in time $\\mathcal{O}(n)$.\r\n In this paper we contribute the (to the
best of our knowledge) first\r\ngathering algorithm on the grid that works under
the same simple local model as\r\nthe above mentioned Euclidean plane strategy,
i.e., without memory (oblivious),\r\n\"flags\" and states. We prove its correctness
and an $\\mathcal{O}(n^2)$ time\r\nbound in the fully synchronous $\\mathcal{FSYNC}$
time model. This time bound\r\nmatches the time bound of the best known algorithm
for the Euclidean plane\r\nmentioned above. We say gathering is done if all robots
are located within a\r\n$2\\times 2$ square, because in $\\mathcal{FSYNC}$ such
configurations cannot be\r\nsolved.@eng"
bibo_authorlist:
- 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: 2017^xs_gYear
dct_language: eng
dct_title: Gathering Anonymous, Oblivious Robots on a Grid@
...