Position discovery for a system of bouncing robots

Jurek Czyzowicz 1 Leszek Gasieniec 2 Adrian Kosowski 3 Evangelos Kranakis 4 Oscar Morales-Ponce 5 Eduardo Pacheco 6
1 DII - Département d'Informatique et d'Ingénierie
2 Department of Computer Science [Liverpool]
3 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
4 School of Computer Science [Ottawa]
5 Chalmers University of Technology [Göteborg]
6 School of Computer Science (Carleton, Ottawa)
Abstract : A collection of n anonymous mobile robots is deployed on a unit-perimeter ring or a unit-length line segment. Every robot starts moving at constant speed, and bounces each time it meets any other robot or segment endpoint, changing its walk direction. We study the problem of position discovery, in which the task of each robot is to detect the presence and the initial positions of all other robots. The robots cannot communicate or perceive information about the environment in any way other than by bouncing nor they have control over their walks which are determined by their initial positions and their starting directions. Each robot has a clock allowing it to observe the times of its bounces. We give complete characterizations of all initial configurations for both the ring and the segment in which no position detection algorithm exists and we design optimal position detection algorithms for all feasible configurations.
Document type :
Journal articles
Complete list of metadatas
https://hal.inria.fr/hal-01251829
Contributor : Adrian Kosowski <>
Submitted on : Wednesday, January 6, 2016 - 5:59:52 PM
Last modification on : Friday, January 4, 2019 - 5:33:21 PM

Links full text

openaccess

Identifiers

Collections

CNRS | UNIV-PARIS7 | INRIA | USPC

Citation

Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Oscar Morales-Ponce, et al.. Position discovery for a system of bouncing robots. Journal of Information and Computation, Elsevier, 2015, 244, pp.122-133. ⟨10.1016/j.ic.2015.07.005⟩. ⟨hal-01251829⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

326

 

 

Contact

archive-ouverte@inria.fr