1. How many oblivious robots can explore a line
- Author
-
Nicola Santoro, David Ilcinkas, Andrzej Pelc, Paola Flocchini, School of Information Technology and Engineering [Ottawa] (SITE), University of Ottawa [Ottawa], Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Algorithmics for computationally intensive applications over wide scale distributed platforms (CEPAGE), Université Sciences et Technologies - Bordeaux 1 (UB)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS), Département d'Informatique et d'Ingénierie (DII), Université du Québec en Outaouais (UQO), School of Computer Science [Ottawa], Carleton University, See paper for details., ANR-07-BLAN-0322,ALADDIN,Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks(2007), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), and Université Sciences et Technologies - Bordeaux 1-Inria Bordeaux - Sud-Ouest
- Subjects
Theoretical computer science ,Computer science ,Distributed computing ,[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,exploration ,01 natural sciences ,Theoretical Computer Science ,distributed computing ,oblivious ,mobile robots ,Impossibility ,asynchronous ,021103 operations research ,Mobile robot ,Computer Science Applications ,010201 computation theory & mathematics ,Asynchronous communication ,Signal Processing ,Robot ,line ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Line (text file) ,Information Systems - Abstract
International audience; We consider the problem of exploring an anonymous line by a team of k identical, oblivious, asynchronous deterministic mobile robots that can view the environment but cannot communicate. We completely characterize sizes of teams of robots capable of exploring a n-node line. For k= 5, or k=4 and n is odd. For all values of k for which exploration is possible, we give an exploration algorithm. For all others, we prove an impossibility result.
- Published
- 2011