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.DISC.2018.13
URN: urn:nbn:de:0030-drops-98029
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9802/
Go to the corresponding LIPIcs Volume Portal

Brandt, Sebastian ; Uitto, Jara ; Wattenhofer, Roger

A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration

pdf-format:
LIPIcs-DISC-2018-13.pdf (0.5 MB)

Abstract

Recently, there has been a growing interest in grid exploration by agents with limited capabilities. We show that the grid cannot be explored by three semi-synchronous finite automata, answering an open question by Emek et al. [TCS'15] in the negative.
In the setting we consider, time is divided into discrete steps, where in each step, an adversarially selected subset of the agents executes one look-compute-move cycle. The agents operate according to a shared finite automaton, where every agent is allowed to have a distinct initial state. The only means of communication is to sense the states of the agents sharing the same grid cell. The agents are equipped with a global compass and whenever an agent moves, the destination cell of the movement is chosen by the agent's automaton from the set of neighboring grid cells. In contrast to the four agent protocol by Emek et al., we show that three agents do not suffice for grid exploration.

BibTeX - Entry

@InProceedings{brandt_et_al:LIPIcs:2018:9802,
  author =	{Sebastian Brandt and Jara Uitto and Roger Wattenhofer},
  title =	{{A Tight Lower Bound for Semi-Synchronous Collaborative Grid Exploration}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{13:1--13:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9802},
  URN =		{urn:nbn:de:0030-drops-98029},
  doi =		{10.4230/LIPIcs.DISC.2018.13},
  annote =	{Keywords: Finite automata, Graph exploration, Mobile robots}
}

Keywords: Finite automata, Graph exploration, Mobile robots
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

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