toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author D'Angelo, G.; Di Stefano, G.; Navarra, A.; Nisse, N.; Suchan, K. pdf  doi
  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:;  
  Corporate Author Thesis  
  Publisher Springer Place of Publication Editor  
  Language English Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title (up)  
  Series Volume Series Issue Edition  
  ISSN 0178-4617 ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000356461400008 Approved  
  Call Number UAI @ eduardo.moreno @ Serial 504  
Permanent link to this record
Select All    Deselect All
 |   | 

Save Citations:
Export Records: