Abstract References

Distributed Computing by Mobile Robots: Expanding the Horizon

Paola Flocchini ORCID University of Ottawa, Canada
Abstract

Extensive research focus within distributed computing has been spent on the computational and complexity issues arising in systems of mobile computational entities (called robots) operating in the Euclidean space in Look-Compute-Move cycles. In the classical 𝒪⁢ℬ⁢ℒ⁢𝒪⁢𝒯 model, the robots are homogeneous, having no distinguishing features and running the same algorithm. Moreover, they are silent, having no explicit means of communication, and oblivious, meaning that, whenever activated, they forget everything they have seen and done in previous cycles.

The research focus has been in determining the impact that internal capabilities (e.g., memory, communication) and external conditions (e.g. synchrony, type of the activation scheduler) have on the computability power of these robots (e.g., see [8] and chapters therein). Over the years, various enhancement of the basic model have been studied in regards to memory and communication under the different activation schedules (e.g., [3, 4, 5, 9, 10, 11]). At the same time, the computational landscape has been broadened by examining aspects typically explored in other areas of distributed computing that have not yet been investigated in these systems. One such aspect is the concept of robots possessing identifiers (which need not be identical), diverging from the usual assumption of homogeneity (e.g., [1, 2, 6, 7, 12]).

In this talk, I will first discuss some of the recent results shaping the overall computational landscape. I will then describe some recent explorations on the impact of introducing non-homogeneity of the robots.

Keywords and phrases:
Mobile Robots, Look-Compute-Move, Computability, Moving and Computing
Category:
Invited Talk
Funding:
Paola Flocchini: Discovery Grant (Natural Science and Engineering Council)
Copyright and License:
[Uncaptioned image] © Paola Flocchini; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation → Algorithm design techniques ; Theory of computation → Computability ; Theory of computation → Distributed computing models
DOI:
10.4230/LIPIcs.OPODIS.2024.2
Event:
28th International Conference on Principles of Distributed Systems (OPODIS 2024)
Editors:
Silvia Bonomi, Letterio Galletta, Etienne Rivière, and Valerio Schiavoni
Series and Publisher:
LIPIcs Logo Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

References

  • [1] Y. Asahiro and M. Yamashita. Minimum algorithm sizes for self-stabilizing gathering and related problems of autonomous mobile robots (extended abstract). In 25th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 312–327, 2023.
  • [2] S. Bhagat, P. Flocchini, K. Mukhopadhyaya, and N. Santoro. Weak robots performing conflicting tasks without knowing who is in their team. In 21st International Conference on Distributed Computing and Networking (ICDCN), pages 29:1–29:6, 2020.
  • [3] K. Buchin, P. Flocchini, I. Kostitsyna, T. Peters, N. Santoro, and K. Wada. Autonomous mobile robots: refining the computational landscape. In IEEE International Parallel and Distributed Processing Symposium Workshops, pages 576–585, 2021.
  • [4] K. Buchin, P. Flocchini, I. Kostitsyna, T. Peters, N. Santoro, and K. Wada. On the computational power of energy-constrained mobile robots: algorithms and cross-model analysis. In 29th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 42–61, 2022.
  • [5] S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. Autonomous mobile robots with lights. Theoretical Computer Science, 609:171–184, 2016. doi:10.1016/J.TCS.2015.09.018.
  • [6] P. Flocchini, D. Pattanayak, F. Piselli, N. Santoro, and Y. Yamauchi. Asynchronous separation of unconscious colored robots. In 16th International Workshop on Parallel and Distributed Algorithms and Applications, 2024.
  • [7] P. Flocchini, D. Pattanayak, N. Santoro, and M. Yamashita. The minimum algorithm size of k-grouping by silent oblivious robots. In 35th International Workshop on Combinatorial Algorithms (IWOCA), pages 472–484, 2024.
  • [8] P. Flocchini, G. Prencipe, and N. Santoro, editors. Distributed Computing by Mobile Entities. Springer, 2019.
  • [9] P. Flocchini, N. Santoro, Y. Sudo, and K. Wada. On asynchrony, memory, and communication: separations and landscapes. In 27th Int. Conf. on Principles of Distributed Systems (OPODIS), pages 28:1–28:23, 2023. doi:10.4230/LIPIcs.OPODIS.2023.28.
  • [10] P. Flocchini, N. Santoro, G. Viglietta, and M. Yamashita. Rendezvous with constant memory. Theoretical Computer Science, 621:57–72, 2016. doi:10.1016/J.TCS.2016.01.025.
  • [11] Paola Flocchini, Nicola Santoro, and Koichi Wada. On Memory, Communication, and Synchronous Schedulers When Moving and Computing. In Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller, editors, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019), volume 153 of Leibniz International Proceedings in Informatics (LIPIcs), pages 25:1–25:17, Dagstuhl, Germany, 2020. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2019.25.
  • [12] H. Seike and Y. Yamauchi. Separation of unconscious colored robots. In 25th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 328–343, 2023.