|   | 
Details
   web
Record
Author D'Angelo, G.; Di Stefano, G.; Navarra, A.; Nisse, N.; Suchan, K.
Title Computing on Rings by Oblivious Robots: A Unified Approach for Different Tasks Type
Year 2015 Publication Algorithmica Abbreviated Journal Algorithmica
Volume 72 Issue 4 Pages 1055-1096
Keywords Distributed computing; Exploration; Searching; Gathering; Oblivious anonymous robots; Asynchronous anonymous networks; Look-Compute-Move
Abstract A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled (that is, the ring is anonymous). We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual clearing, and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often while avoiding that two robots occupy a same node (exclusivity property); in exclusive perpetual clearing (also known as graph searching), the team of robots aims at clearing the whole ring infinitely often (an edge is cleared if it is traversed by a robot or if both its endpoints are occupied); and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the Look-Compute-Move model where the robots cannot communicate but can perceive the positions of other robots. Each robot is equipped with visibility sensors and motion actuators, and it operates in asynchronous cycles. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it eventually moves to this neighbor (Move). Moreover, robots are endowed with very weak capabilities. Namely, they are anonymous, asynchronous, oblivious, uniform (execute the same algorithm) and have no common sense of orientation. In this setting, we devise algorithms that, starting from an exclusive and rigid (i.e. aperiodic and asymmetric) configuration, solve the three above problems in anonymous ring-topologies.
Address [D'Angelo, Gianlorenzo] Gran Sasso Sci Inst GSSI, Laquila, Italy, Email: gianlorenzo.dangelo@gssi.infn.it;
Corporate Author Thesis
Publisher Springer Place of Publication Editor
Language English Summary Language Original Title
Series Editor Series Title Abbreviated Series Title
Series Volume Series Issue Edition (up)
ISSN 0178-4617 ISBN Medium
Area Expedition Conference
Notes WOS:000356461400008 Approved
Call Number UAI @ eduardo.moreno @ Serial 504
Permanent link to this record