LIPIcs.FUN.2021.6.pdf
- Filesize: 0.5 MB
- 19 pages
Document
Finding Water on Poleless Using Melomaniac Myopic Chameleon Robots
Authors
Quentin Bramas 
,
Pascal Lafourcade ,
Stéphane Devismes
-
Part of:
Volume:
10th International Conference on Fun with Algorithms (FUN 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-09-16
File
Document Identifiers
Author Details
Cite As Get BibTex
Quentin Bramas, Pascal Lafourcade, and Stéphane Devismes. Finding Water on Poleless Using Melomaniac Myopic Chameleon Robots. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FUN.2021.6
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.
Subject Classification
ACM Subject Classification
- Theory of computation → Distributed algorithms
Keywords
- Luminous Robots
- Grid
- Infinite Exploration
- Treasure Search Problem
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Ranendu Adhikary, Kaustav Bose, Manash Kumar Kundu, and Buddhadeb Sau. Mutual visibility by asynchronous robots on infinite grid. In Algorithms for Sensor Systems - 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers, pages 83-101, 2018.
- Roberto Baldoni, François Bonnet, Alessia Milani, and Michel Raynal. Anonymous graph exploration without collision by mobile robots. Inf. Process. Lett., 109(2):98-103, 2008. URL: https://doi.org/10.1016/j.ipl.2008.08.011.
- François Bonnet, Alessia Milani, Maria Potop-Butucaru, and Sébastien Tixeuil. Asynchronous exclusive perpetual grid exploration without sense of direction. In Antonio Fernández Anta, editor, Proceedings of International Conference on Principles of Distributed Systems (OPODIS 2011), number 7109 in Lecture Notes in Computer Science (LNCS), pages 251-265, Toulouse, France, December 2011. Springer Berlin / Heidelberg. URL: http://www.springerlink.com/content/9l3v424157681707/.
-
Kaustav Bose, Ranendu Adhikary, Manash Kumar Kundu, and Buddhadeb Sau. Arbitrary pattern formation on infinite grid by asynchronous oblivious robots. In WALCOM: Algorithms and Computation - 13th International Conference, WALCOM 2019, Guwahati, India, February 27 - March 2, 2019, Proceedings, pages 354-366, 2019.
- Quentin Bramas, Stéphane Devismes, and Pascal Lafourcade. Infinite grid exploration by disoriented robots. In Michele Flammini Keren Censor-Hillel, editor, Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, L'Aquila, Italy, July 1-4, 2019, Proceedings, volume 11639 of Lecture Notes in Computer Science, pages 340-344. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-24922-9_25.
- Quentin Bramas, Stéphane Devismes, and Pascal Lafourcade. Poleless Exploration with Melomaniac Myopic Chameleon Robots: The Animations, January 2020. URL: https://doi.org/10.5281/zenodo.3606387.
- Sebastian Brandt, Jara Uitto, and Roger Wattenhofer. A tight lower bound for semi-synchronous collaborative grid exploration. In Ulrich Schmid and Josef Widder, editors, 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15-19, 2018, volume 121 of LIPIcs, pages 13:1-13:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.DISC.2018.13.
- Shantanu Das, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Masafumi Yamashita. Autonomous mobile robots with lights. Theor. Comput. Sci., 609(P1):171-184, January 2016. URL: https://doi.org/10.1016/j.tcs.2015.09.018.
- Stéphane Devismes, Anissa Lamani, Franck Petit, Pascal Raymond, and Sébastien Tixeuil. Terminating Exploration Of A Grid By An Optimal Number Of Asynchronous Oblivious Robots. The Computer Journal, March 2020. URL: https://doi.org/10.1093/comjnl/bxz166.
-
Durjoy Dutta, Tandrima Dey, and Sruti Gan Chaudhuri. Gathering multiple robots in a ring and an infinite grid. In Distributed Computing and Internet Technology - 13th International Conference, ICDCIT 2017, Bhubaneswar, India, January 13-16, 2017, Proceedings, pages 15-26, 2017.
- Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, and Roger Wattenhofer. How many ants does it take to find the food? Theor. Comput. Sci., 608(P3):255-267, December 2015. URL: https://doi.org/10.1016/j.tcs.2015.05.054.
- Giuseppe Antonio Di Luna, Paola Flocchini, Sruti Gan Chaudhuri, Federico Poloni, Nicola Santoro, and Giovanni Viglietta. Mutual visibility by luminous robots without collisions. Inf. Comput., 254:392-418, 2017. URL: https://doi.org/10.1016/j.ic.2016.09.005.
-
Fukuhito Ooshita and Ajoy K. Datta. Brief announcement: Feasibility of weak gathering in connected-over-time dynamic rings. In Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Tokyo, Japan, November 4-7, 2018, Proceedings, pages 393-397, 2018.
- David Peleg. Distributed coordination algorithms for mobile robot swarms: New directions and challenges. In Proceedings of the 7th International Conference on Distributed Computing, IWDC'05, pages 1-12, Berlin, Heidelberg, 2005. Springer-Verlag. URL: https://doi.org/10.1007/11603771_1.
- Gabriele Di Stefano and Alfredo Navarra. Gathering of oblivious robots on infinite grids with minimum traveled distance. Inf. Comput., 254:377-391, 2017. URL: https://doi.org/10.1016/j.ic.2016.09.004.