2026-07-26T02:16:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12767 2024-03-06T10:49:08Z ddc:004 open_access

Finding Water on Poleless Using Melomaniac Myopic Chameleon Robots Bramas, Quentin Lafourcade, Pascal Devismes, Stéphane Luminous Robots Grid Infinite Exploration Treasure Search Problem 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Quentin Bramas and Pascal Lafourcade and Stéphane Devismes 2020 Is Part Of LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2021.6 urn:nbn:de:0030-drops-127674 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.6 eng https://creativecommons.org/licenses/by/3.0/legalcode