Optimal Grid Exploration by Asynchronous Oblivious Robots - Sorbonne Université
Communication Dans Un Congrès Année : 2012

Optimal Grid Exploration by Asynchronous Oblivious Robots

Résumé

We consider deterministic terminating exploration of a grid by a team of asynchronous oblivious robots. We first consider the semi-synchronous atomic model ATOM. In this model, we exhibit the minimal number of robots to solve the problem w.r.t. the size of the grid. We then consider the asynchronous non-atomic model CORDA. ATOM being strictly stronger than CORDA, the previous bounds also hold in CORDA, and we propose deterministic algorithms in CORDA that matches these bounds. The above 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, respectively.

Dates et versions

hal-00934161 , version 1 (21-01-2014)

Identifiants

Citer

Stéphane Devismes, Anissa Lamani, Franck Petit, Pascal Raymond, Sébastien Tixeuil. Optimal Grid Exploration by Asynchronous Oblivious Robots. International Symposium on Stabilization, Safety, and Security of Distributed Systems, Oct 2012, Toronto, Canada. pp.64-76, ⟨10.1007/978-3-642-33536-5_7⟩. ⟨hal-00934161⟩
534 Consultations
0 Téléchargements

Altmetric

Partager

More