Paper Info
Title
Optimal exploration of small rings
Abstract
In [4], the authors look at probabilistic bounds and solutions for the exploration of anonymous unoriented rings of any size by a cohort of robots. Considering identical, oblivious, and probabilistic robots, they show that at least four of them are necessary to solve the problem. Moreover, they give a randomized protocol for four robots working in any ring of size more than eight. Here we close the question of optimal (w.r.t. the cohort size) ring exploration by probabilistic robots. Indeed, we propose a protocol for four robots working in any ring of size less or equal to eight. Composing this protocol with the one in [4], we obtain a protocol for any ring-size.
Year
DOI
Venue
2010
10.1145/1953563.1953571
WRAS
Keywords
Field
DocType
small ring,probabilistic bound,cohort size,randomized protocol,probabilistic robot,anonymous unoriented ring,optimal exploration,ring exploration,mobile robots,mobile robot,probabilistic algorithm
Randomized algorithm,Theoretical computer science,Probabilistic logic,Robot,Mobile robot,Mathematics
Conference
Citations 
PageRank 
References 
5
0.46
11
Authors
1
Name
Order
Citations
PageRank
Stéphane Devismes119225.74