1 Search Results for "Okumura, Takashi"

Document

DOI: 10.4230/LIPIcs.OPODIS.2018.24

Optimal Rendezvous L-Algorithms for Asynchronous Mobile Robots with External-Lights

Authors: Takashi Okumura, Koichi Wada, and Xavier Défago

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract

We study the Rendezvous problem for two autonomous mobile robots in asynchronous settings with persistent memory called light. It is well known that Rendezvous is impossible in a basic model when robots have no lights, even if the system is semi-synchronous. On the other hand, Rendezvous is possible if robots have lights of various types with a constant number of colors. If robots can observe not only their own lights but also other robots' lights, their lights are called full-light. If robots can only observe the state of other robots' lights, the lights are called external-light. This paper focuses on robots with external-lights in asynchronous settings and a particular class of algorithms called L-algorithms, where an L-algorithm computes a destination based only on the current colors of observable lights. When considering L-algorithms, Rendezvous can be solved by robots with full-lights and three colors in general asynchronous settings (called ASYNC) and the number of colors is optimal under these assumptions. In contrast, there exist no L-algorithms in ASYNC with external-lights regardless of the number of colors. In this paper, extending the impossibility result, we show that there exist no L-algorithms in so-called LC-1-Bounded ASYNC with external-lights regardless of the number of colors, where LC-1-Bounded ASYNC is a proper subset of ASYNC and other robots can execute at most one Look operation between the Look operation of a robot and its subsequent Compute operation. We also show that LC-1-Bounded ASYNC is the minimal subclass in which no L-algorithms with external-lights exist. That is, Rendezvous can be solved by L-algorithms using external-lights with a finite number of colors in LC-0-Bounded ASYNC (equivalently LC-atomic ASYNC). Furthermore, we show that the algorithms are optimal in the number of colors they use.

Cite as

Takashi Okumura, Koichi Wada, and Xavier Défago. Optimal Rendezvous L-Algorithms for Asynchronous Mobile Robots with External-Lights. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{okumura_et_al:LIPIcs.OPODIS.2018.24,
  author =	{Okumura, Takashi and Wada, Koichi and D\'{e}fago, Xavier},
  title =	{{Optimal Rendezvous L-Algorithms for Asynchronous Mobile Robots with External-Lights}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.24},
  URN =		{urn:nbn:de:0030-drops-100843},
  doi =		{10.4230/LIPIcs.OPODIS.2018.24},
  annote =	{Keywords: Autonomous mobile robots, Rendezvous, Lights, L-algorithms}
}

Refine by Author
1 Défago, Xavier
1 Okumura, Takashi
1 Wada, Koichi

Refine by Classification
1 Computing methodologies → Self-organization
1 Theory of computation → Distributed algorithms

Refine by Keyword
1 Autonomous mobile robots
1 L-algorithms
1 Lights
1 Rendezvous

Refine by Type
1 document

Refine by Publication Year
1 2019

1 Search Results for "Okumura, Takashi"

Optimal Rendezvous L-Algorithms for Asynchronous Mobile Robots with External-Lights

Abstract

Cite as

Thanks for your feedback!

Could not send message