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

Bramas, Quentin ; Lafourcade, Pascal ; Devismes, Stéphane

Finding Water on Poleless Using Melomaniac Myopic Chameleon Robots

pdf-format:
LIPIcs-FUN-2021-6.pdf (0.5 MB)

Abstract

In 2042, the exoplanet exploration program, launched in 2014 by NASA, finally discovers a new exoplanet so-called Poleless, due to the fact that it is not subject to any magnetism. A new generation of autonomous mobile robots, called M2C (for Melomaniac Myopic Chameleon), have been designed to find water on Poleless. To address this problem, we investigate optimal (w.r.t., visibility range and number of used colors) solutions to the infinite grid exploration problem (IGE) by a small team of M2C robots. Our first result shows that minimizing the visibility range and the number of used colors are two orthogonal issues: it is impossible to design a solution to the IGE problem that is optimal w.r.t. both parameters simultaneously. Consequently, we address optimality of these two criteria separately by proposing two algorithms; the former being optimal in terms of visibility range, the latter being optimal in terms of number of used colors. It is worth noticing that these two algorithms use a very small number of robots, respectively six and eight.

BibTeX - Entry

@InProceedings{bramas_et_al:LIPIcs:2020:12767,
  author =	{Quentin Bramas and Pascal Lafourcade and St{\'e}phane Devismes},
  title =	{{Finding Water on Poleless Using Melomaniac Myopic Chameleon Robots}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{6:1--6:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Martin Farach-Colton and Giuseppe Prencipe and Ryuhei Uehara},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12767},
  URN =		{urn:nbn:de:0030-drops-127674},
  doi =		{10.4230/LIPIcs.FUN.2021.6},
  annote =	{Keywords: Luminous Robots, Grid, Infinite Exploration, Treasure Search Problem}
}

Keywords: Luminous Robots, Grid, Infinite Exploration, Treasure Search Problem
Collection: 10th International Conference on Fun with Algorithms (FUN 2021)
Issue Date: 2020
Date of publication: 16.09.2020
Supplementary Material: https://doi.org/10.5281/zenodo.3606387

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