License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2019.27
URN: urn:nbn:de:0030-drops-118139
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11813/
Go to the corresponding LIPIcs Volume Portal

Kamei, Sayaka ; Lamani, Anissa ; Ooshita, Fukuhito ; Tixeuil, Sébastien ; Wada, Koichi

Gathering on Rings for Myopic Asynchronous Robots With Lights

pdf-format:
LIPIcs-OPODIS-2019-27.pdf (2 MB)

Abstract

We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: M_{init}, which denotes the number of nodes between two border nodes, and O_{init}, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if M_{init} or O_{init} is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.

BibTeX - Entry

@InProceedings{kamei_et_al:LIPIcs:2020:11813,
  author =	{Sayaka Kamei and Anissa Lamani and Fukuhito Ooshita and S{\'e}bastien Tixeuil and Koichi Wada},
  title =	{{Gathering on Rings for Myopic Asynchronous Robots With Lights}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{27:1--27:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11813},
  URN =		{urn:nbn:de:0030-drops-118139},
  doi =		{10.4230/LIPIcs.OPODIS.2019.27},
  annote =	{Keywords: LCM robot system, ASYNC schedulers, myopic, luminous, ring networks}
}

Keywords: LCM robot system, ASYNC schedulers, myopic, luminous, ring networks
Collection: 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)
Issue Date: 2020
Date of publication: 11.02.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI