Optimal grid exploration by asynchronous oblivious robots - Sorbonne Université Access content directly
Reports Year : 2011

Optimal grid exploration by asynchronous oblivious robots

Stéphane Devismes
Franck Petit
  • Function : Author
  • PersonId : 778299
  • IdRef : 050783238
Pascal Raymond


We consider a team of {\em autonomous weak robots} that are endowed with visibility sensors and motion actuators. Autonomous means that the team cannot rely on any kind of central coordination mechanism or scheduler. By weak we mean that the robots are devoid of (1) any (observable) IDs allowing to differentiate them (anonymous), (2) means of communication allowing them to communicate directly, and (3) any way to remember any previous observation nor computation performed in any previous step (oblivious). Robots asynchronously operate in cycles of three phases: Look, Compute, and Move. Furthermore, the network is an anonymous unoriented grid. In such settings, the robots must collaborate to solve a collective task, here the terminating grid exploration (exploration for short), despite being limited with respect to input from the environment, asymmetry, memory, etc. Exploration requires that robots explore the grid and stop when the task is complete. We propose optimal (w.r.t. the number of robots) solutions for the deterministic terminating exploration of a grid shaped network by a team of $k$ asynchronous oblivious robots in the fully asynchronous and non-atomic model, so called CORDA. In more details, we first assume the ATOM model in which each Look-Compute-Move cycle execution is executed atomically, ie every robot that is activated at instant t instantaneously executes a full cycle between t and t+1. ATOM being strictly stronger than CORDA, all impossibility results in ATOM also hold in CORDA. We show that it is impossible to explore a grid of at least three nodes with less than three robots in ATOM. (This first result holds for both deterministic and probabilistic settings.) Next, we show that it is impossible to deterministically explore a (2,2)-Grid with less than 4 robots, and a (3,3)-Grid with less than 5 robots, respectively. Then, we propose deterministic algorithms in CORDA to exhibit the optimal number of robots allowing to explore of a given grid. Our results show that except in two particular cases, 3 robots are necessary and sufficient to deterministically explore a grid of at least three nodes. The optimal number of robots for the two remaining cases is: 4 for the (2,2)-Grid and 5 for the (3,3)-Grid.
Fichier principal
Vignette du fichier
Report.pdf (385.03 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-00591963 , version 1 (11-05-2011)
hal-00591963 , version 2 (23-01-2012)
hal-00591963 , version 3 (07-03-2012)



Stéphane Devismes, Anissa Lamani, Franck Petit, Pascal Raymond, Sébastien Tixeuil. Optimal grid exploration by asynchronous oblivious robots. [Research Report] ???. 2011. ⟨hal-00591963v3⟩
578 View
615 Download



Gmail Mastodon Facebook X LinkedIn More