Paper Info
Title
Gathering Anonymous, Oblivious Robots on a Grid
Abstract
We consider a swarm of n autonomous mobile robots distributed on a 2-dimensional grid. A basic task for such a swarm is to perform the gathering process: All robots have to gather at one not predefined place. On the grid there are configurations which, due to symmetry, cannot be gathered at a single point. Such configurations are 2×2 squares. Therefore, we say that the swarm is gathered if all robots are located inside of a 2×2 square. We assume the fully synchronous FSYNC time model and the following very simple so-called Basic&Plain robot model: The robots are oblivious, only have a constant viewing radius, are autonomous and indistinguishable, do not have a common compass, and cannot communicate. This implies that a robot's decision about its next action can only be based on the current relative positions of the robots in its viewing range. We consider connected swarms. We say two robots are connected if they are located in horizontally or vertically neighboring grid cells. We present the first gathering algorithm on the grid for this simple robot model and show that it gathers in time O(n2). Known algorithms for gathering on the grid need much stronger robot models: Either they have a common compass, or they have a finite memory and can communicate (via lights or flags) with robots in their viewing range. Finally, we extend our algorithm to the case where one of the robots is stationary, i.e. does not move.
Year
DOI
Venue
2020
10.1016/j.tcs.2020.02.018
Theoretical Computer Science
Keywords
DocType
Volume
Gathering problem,Autonomous robots,Stationary robots,Distributed algorithms,Local algorithms,Mobile agents,Runtime bound,Swarm formation problems
Journal
815
Issue
ISSN
Citations 
C
0304-3975
0
PageRank 
References 
Authors
0.34
0
5
Name
Order
Citations
PageRank
Jannik Castenow102.03
Matthias Fischer200.34
Jonas Harbig301.01
Daniel Jung493.27
Friedhelm Meyer auf der Heide51744238.01