Enabling Ring Exploration with Myopic Oblivious Robots

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.