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.24
URN: urn:nbn:de:0030-drops-118103
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11810/
Go to the corresponding LIPIcs Volume Portal

Das, Shantanu ; Di Luna, Giuseppe A. ; Flocchini, Paola ; Santoro, Nicola ; Viglietta, Giovanni ; Yamashita, Masafumi

Oblivious Permutations on the Plane

pdf-format:
LIPIcs-OPODIS-2019-24.pdf (3 MB)

Abstract

We consider a distributed system of n identical mobile robots operating in the two dimensional Euclidian plane. As in the previous studies, we consider the robots to be anonymous, oblivious, dis-oriented, and without any communication capabilities, operating based on the Look-Compute-Move model where the next location of a robot depends only on its view of the current configuration. Even in this seemingly weak model, most formation problems which require constructing specific configurations, can be solved quite easily when the robots are fully synchronized with each other. In this paper we introduce and study a new class of problems which, unlike the studied formation problems, cannot always be solved even in the fully synchronous model with atomic and rigid moves. This class of problems requires the robots to permute their locations in the plane. In particular, we are interested in implementing two special types of permutations - permutations without any fixed points and permutations of order n. The former (called Move-All) requires each robot to visit at least two of the initial locations, while the latter (called Visit-All) requires every robot to visit each of the initial locations in a periodic manner. We provide a characterization of the solvability of these problems, showing the main challenges in solving this class of problems for mobile robots. We also provide algorithms for the feasible cases, in particular distinguishing between one-step algorithms (where each configuration must be a permutation of the original configuration) and multi-step algorithms (which allow intermediate configurations). These results open a new research direction in mobile distributed robotics which has not been investigated before.

BibTeX - Entry

@InProceedings{das_et_al:LIPIcs:2020:11810,
  author =	{Shantanu Das and Giuseppe A. Di Luna and Paola Flocchini and Nicola Santoro and Giovanni Viglietta and Masafumi Yamashita},
  title =	{{Oblivious Permutations on the Plane}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{24:1--24:16},
  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/11810},
  URN =		{urn:nbn:de:0030-drops-118103},
  doi =		{10.4230/LIPIcs.OPODIS.2019.24},
  annote =	{Keywords: Distributed Algorithms, Mobile Robots, Fully synchronous, Oblivious, Permutations, Chirality, Sequence of configurations}
}

Keywords: Distributed Algorithms, Mobile Robots, Fully synchronous, Oblivious, Permutations, Chirality, Sequence of configurations
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