# Optimal Torus Exploration by Oblivious Robots

3 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
4 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : We consider autonomous robots that are endowed with motion actuators and visibility sensors. The robots we consider are weak, i.e., they are anonymous, uniform, unable to explicitly communicate, and oblivious (they do not remember any of their past actions). In this paper, we propose an optimal (w.r.t. the number of robots) solution for the terminating exploration of a torus-shaped network by a team of $k$ such robots. In more details, we first show that it is impossible to explore a simple torus of arbitrary size with (strictly) less than four robots, even if the algorithm is probabilistic. If the algorithm is required to be deterministic, four robots are also insufficient. This negative result implies that the only way to obtain an optimal algorithm (w.r.t. the number of robots participating to the algorithm) is to make use of probabilities. Then, we propose a probabilistic algorithm that uses four robots to explore all simple tori of size $\ell \times L$, where $7 \leq \ell \leq L$. Hence, in such tori, four robots are necessary and sufficient to solve the (probabilistic) terminating exploration. As a torus can be seen as a 2-dimensional ring, our result shows, perhaps surprisingly, that increasing the number of possible symmetries in the network (due to increasing dimensions) does not come at an extra cost w.r.t. the number of robots that are necessary to solve the problem.
Keywords :
Type de document :
Communication dans un congrès
NETYS 2015 - Third International Conference on Networked Systems, May 2015, Agadir, Morocco. Springer, 9466, pp.183-199, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-319-26850-7_13〉
Domaine :
Liste complète des métadonnées

Littérature citée [17 références]

https://hal.inria.fr/hal-00926573
Contributeur : Stéphane Devismes <>
Soumis le : vendredi 13 juin 2014 - 11:46:48
Dernière modification le : jeudi 22 novembre 2018 - 14:25:28
Document(s) archivé(s) le : samedi 13 septembre 2014 - 11:05:20

### Fichier

torus.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Stéphane Devismes, Anissa Lamani, Franck Petit, Sébastien Tixeuil. Optimal Torus Exploration by Oblivious Robots. NETYS 2015 - Third International Conference on Networked Systems, May 2015, Agadir, Morocco. Springer, 9466, pp.183-199, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-319-26850-7_13〉. 〈hal-00926573v3〉

### Métriques

Consultations de la notice

## 580

Téléchargements de fichiers