Today I read a paper titled “Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots”
The abstract is:
We consider a team of $k$ identical, oblivious, asynchronous mobile robots that are able to sense i.e., view) their environment, yet are unable to communicate, and evolve on a constrained path
Previous results in this weak scenario show that initial symmetry yields high lower bounds when problems are to be solved by deterministic robots
In this paper, we initiate research on probabilistic bounds and solutions in this context, and focus on the exploration problem of anonymous unoriented rings of any size
It is known that $\Theta(\log n)$ robots are necessary and sufficient to solve the problem with $k$ deterministic robots, provided that $k$ and $n$ are coprime
By contrast, we show that four identical probabilistic robots are necessary and sufficient to solve the same problem, also removing the coprime constraint
Our positive results are constructive