Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Keywords |
|---|---|---|
2009 | Clinical Orthopaedics and Related Research | lower bound,data structure,cluster computing,computational complexity,mobile robot |
DocType | Volume | Citations |
Journal | abs/0902.1 | 6 |
PageRank | References | Authors |
0.66 | 12 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Devismes | 1 | 192 | 25.74 |
| Franck Petit | 2 | 736 | 60.02 |
| Sébastien Tixeuil | 3 | 978 | 93.01 |