Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots

Details Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots

2009-02-11

arxiv.org/abs/0902.1834v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider a team of $k$ identical, oblivious, asynchronous mobile robots that are able to sense (\emph{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 \emph{deterministic} robots. In this paper, we initiate research on probabilistic bounds and solutions in this context, and focus on the \emph{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 \emph{four} identical probabilistic robots are necessary and sufficient to solve the same problem, also removing the coprime constraint. Our positive results are constructive.

Affiliated with

Also associated with

No associations

Rating

Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimal Probabilistic Ring Exploration by Asynchronous Oblivious Robots will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-487413