2009/02/11 by Stéphane Devismes, Devismes, Stéphane, Franck Petit +3 · 1 citation
Computer Science · Decision Sciences · #Auction Theory and Applications #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Distributed #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems #Parallel #Robotics (cs.RO) #and Cluster Computing (cs.DC) #cs.CC #cs.DC #cs.DS #cs.RO
paper · pdf · doi:10.48550/arxiv.0902.1834
arxiv created 2009/02/11 · openalex publication_date 2009/02/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Θ(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.