Enabling Ring Exploration with Myopic Oblivious Robots - Sorbonne Université Accéder directement au contenu
Communication Dans Un Congrès Année : 2015

Enabling Ring Exploration with Myopic Oblivious Robots

Résumé

We consider the deterministic terminating exploration of an anonymous, unoriented ring using asynchronous and oblivious robots.We address the problem of reducing the resource as much as possible in terms of number of required robots and in terms of vision capacities. We assume myopic robots, i.e., their vision is limited within a certain distance f, computed in terms of hops. It is known that assuming an infinite visibility, at least four identical (probabilistic or deterministic) robots are necessary to solve terminating exploration. It is also known that assuming f = 1, the problem can be deterministically solved with synchronous robots only. In other words, no asynchronous solution exists assuming f = 1.By contrast, we show that the terminating exploration can still be solved asynchronously using a few number of myopic robots only. Assuming f = 3, we first show that 5 robots are necessary to solve the terminating exploration deterministically in asynchronous settings. Next, we provide an asynchronous algorithm that matches this bound, but it requires that the robots start on contiguous nodes. We then give an algorithm that can start from any possible initial configuration that uses 7 asynchronous robots only. Finally, we show that the problem can also be solved assuming f = 2. We present an algorithm for 7 asynchronous robots.
Fichier non déposé

Dates et versions

hal-01347444 , version 1 (21-07-2016)

Identifiants

Citer

Ajoy K. Datta, Anissa Lamani, Lawrence Larmore, Franck Petit. Enabling Ring Exploration with Myopic Oblivious Robots. 17th Workshop on Advances in Parallel and Distributed Computational Models, in conjunction with 29th IEEE International Parallel and Distributed Processing Symposium, May 2015, Hyderabad, India. ⟨10.1109/IPDPSW.2015.137⟩. ⟨hal-01347444⟩
113 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More