Aktuell:
06. Januar 2021
„Menschen sind Maschinen immer unterlegen“: Laut Experten müssen wir das in Zukunft berücksichtigen

Wie kann die Zusammenarbeit von Mensch und Maschine am besten gestaltet werden? Dieser Frage widmen sich die Paderborner ...
Publikationen
Jung, Daniel;Fischer, Matthias;Meyer auf der Heide, Friedhelm:
BibTeX in die Zwischenablage kopieren
Gathering Anonymous, Oblivious Robots on a Grid.
, CoRR abs/1702.03400, Feb. 2017Abstract
We consider a swarm of n autonomous mobile robots, distributed on a 2-dimensional grid. A basic task for such a swarm is the gathering process: all robots have to gather at one (not predefined) place. The work in this paper is motivated by the following insight: On one side, for swarms of robots distributed in the 2-dimensional Euclidean space, several gathering algorithms are known for extremely simple robots that are oblivious, have bounded viewing radius, no compass, and no "flags" to communicate a status to others. On the other side, in case of the 2-dimensional grid, the only known gathering algorithms for robots with bounded viewing radius without compass, need to memorize a constant number of rounds and need flags. In this paper we contribute the, to the best of our knowledge, first gathering algorithm on the grid, which works for anonymous, oblivious robots with bounded viewing range, without any further means of communication and without any memory. We prove its correctness and an O(n^2) time bound. This time bound matches those of the best known algorithms for the Euclidean plane mentioned above.Weblink
https://arxiv.org/abs/1702.03400Dateien
1702.03400.pdfBibtex
@techreport{hniid=9512,
author = {Jung, Daniel and Fischer, Matthias and Meyer auf der Heide, Friedhelm},
title = {Gathering Anonymous, Oblivious Robots on a Grid},
institution = {Heinz Nixdorf Institute, Paderborn University},
address = {CoRR abs/1702.03400},
month = feb,
year = {2017},
}
author = {Jung, Daniel and Fischer, Matthias and Meyer auf der Heide, Friedhelm},
title = {Gathering Anonymous, Oblivious Robots on a Grid},
institution = {Heinz Nixdorf Institute, Paderborn University},
address = {CoRR abs/1702.03400},
month = feb,
year = {2017},
}
BibTeX in die Zwischenablage kopieren