Title: Distributed computing by mobile robots : gathering
Authors : Cieliebak, Mark
Flocchini, Paola
Prencipe, Giuseppe
Santoro, Nicola
Published in : SIAM Journal on Computing
Volume(Issue) : 41
Issue : 4
Pages : 829
Pages to: 879
Publisher / Ed. Institution : Society for Industrial and Applied Mathematics
Issue Date: 2012
License (according to publishing contract) : Licence according to publishing contract
Type of review: Peer review (Publication)
Language : German
Subjects : Distributed system; Gathering; Robot
Subject (DDC) : 004: Computer science
620: Engineering
Abstract: Consider a set of n > 2 identical mobile computational entities in the plane, called robots, operating in Look-Compute-Move cycles, without any means of direct communication. The Gathering Problem is the primitive task of all entities gathering in finite time at a point not fixed in advance, without any external control. The problem has been extensively studied in the literature under a variety of strong assumptions (e.g., synchronicity of the cycles, instantaneous movements, complete memory of the past, common coordinate system, etc.). In this paper we consider the setting without those assumptions, that is, when the entities are oblivious (i.e., they do not remember results and observations from previous cycles), disoriented (i.e., have no common coordinate system), and fully asynchronous (i.e., no assumptions exist on timing of cycles and activities within a cycle). The existing algorithmic contributions for such robots are limited to solutions for n ≤ 4 or for restricted sets of initial configurations of the robots; the question of whether such weak robots could deterministically gather has remained open. In this paper, we prove that indeed the Gathering Problem is solvable, for any n > 2 and any initial configuration, even under such restrictive conditions.
Departement: School of Engineering
Organisational Unit: Institute of Applied Information Technology (InIT)
Publication type: Article in scientific Journal
DOI : 10.1137/100796534
ISSN: 1095-7111
URI: https://digitalcollection.zhaw.ch/handle/11475/7122
Appears in Collections:Publikationen School of Engineering

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.