Ring Exploration by Oblivious Agents with Local Vision

Abstract : The problem of exploring a discrete environment by identical oblivious asynchronous agents (or robots) devoid of direct means of communication has been well investigated so far. The (terminating) exploration requires that starting from a configuration where no two agents occupy the same node, every node needs to be visited by at least one agent, with the additional constraint that all agents eventually stop moving. Agents have sensors that allow them to see their environment and move accordingly. The previous works on this problem assume agents having an unlimited visibility, that is, they can sense the agents on every node of the ring, whatever the ring size. In this paper, we address deterministic exploration in an anonymous, unoriented ring using oblivious, and myopic agents. By myopic, we mean that their visibility is limited in terms of sensing distance. We consider the strongest possible myopia that is, an agent can only sense agents located at its own and at its immediate neighboring nodes. Our contribution is threefold. We first prove that within such settings, no deterministic exploration is possible in the semi-synchronous model. The result is also valid for the (fully) asynchronous model and holds for any k < n where k is the number of agents and n is the number of nodes in the ring. Next, we address the synchronous model and show that no deterministic exploration protocol solves the problem with less than five agents when n > 6. Finally, we provide optimal (in terms of number of agents) deterministic algorithms in the fully synchronous model for both cases 2 < n < 7 and n > 6.
Type de document :
Communication dans un congrès
33rd International Conference on Distributed Computing (ICDCS), Jul 2013, Philadelphia, United States. pp.347-356, 2013, 〈10.1109/ICDCS.2013.55〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00933909
Contributeur : Franck Petit <>
Soumis le : mardi 21 janvier 2014 - 12:05:55
Dernière modification le : vendredi 31 août 2018 - 09:25:54

Identifiants

Collections

Citation

Ajoy Datta, Anissa Lamani, Lawrence Larmore, Franck Petit. Ring Exploration by Oblivious Agents with Local Vision. 33rd International Conference on Distributed Computing (ICDCS), Jul 2013, Philadelphia, United States. pp.347-356, 2013, 〈10.1109/ICDCS.2013.55〉. 〈hal-00933909〉

Partager

Métriques

Consultations de la notice

284