Document Open Access Logo

Gathering on Rings for Myopic Asynchronous Robots With Lights

Authors Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, Koichi Wada

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2019.27.pdf
  • Filesize: 2.19 MB
  • 17 pages

Document Identifiers

Author Details

Sayaka Kamei
  • Graduate School of Engineering, Hiroshima University, Japan
Anissa Lamani
  • Ecole internationale des sciences du traitement de l'information, Cergy, France
Fukuhito Ooshita
  • Graduate School of Science and Technology, Nara Institute of Science and Technology, Japan
Sébastien Tixeuil
  • Sorbonne University, Paris, France
Koichi Wada
  • Faculty of Science and Engineering, Hosei University, Japan

Funding

Supported in part by JST SICORP Grant Number JPMJSC1806, Japan.
  • Kamei, Sayaka: Supported in part by JSPS KAKENHI No. 19K11828.
  • Ooshita, Fukuhito: Supported in part by JSPS KAKENHI No. 18K11167.
  • Tixeuil, Sébastien: Supported in part by Hiroshima University and by project ESTATE (Ref. ANR-16-CE25-0009-03).
  • Wada, Koichi: Supported in part by JSPS KAKENHI No. 17K00019.

Cite As Get BibTex

Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, and Koichi Wada. Gathering on Rings for Myopic Asynchronous Robots With Lights. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.OPODIS.2019.27

Abstract

We investigate gathering algorithms for asynchronous autonomous mobile robots moving in uniform ring-shaped networks. Different from most work using the Look-Compute-Move (LCM) model, we assume that robots have limited visibility and lights. That is, robots can observe nodes only within a certain fixed distance, and emit a color from a set of constant number of colors. We consider gathering algorithms depending on two parameters related to the initial configuration: M_{init}, which denotes the number of nodes between two border nodes, and O_{init}, which denotes the number of nodes hosting robots between two border nodes. In both cases, a border node is a node hosting one or more robots that cannot see other robots on at least one side. Our main contribution is to prove that, if M_{init} or O_{init} is odd, gathering is always feasible with three or four colors. The proposed algorithms do not require additional assumptions, such as knowledge of the number of robots, multiplicity detection capabilities, or the assumption of towerless initial configurations. These results demonstrate the power of lights to achieve gathering of robots with limited visibility.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • LCM robot system
  • ASYNC schedulers
  • myopic
  • luminous
  • ring networks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Z. Bouzid, M. G. Potop-Butucaru, and S. Tixeuil. Optimal Byzantine-resilient convergence in uni-dimensional robot networks. Theor. Comput. Sci., 411(34-36):3154-3168, 2010. Google Scholar
  2. Q. Bramas, S. Devismes, and P. Lafourcade. Infinite Grid Exploration by Disoriented Robots. In SIROCCO, 2019. Google Scholar
  3. G. D'Angelo, A. Navarra, and N. Nisse. A unified approach for gathering and exclusive searching on rings under weak assumptions. Distributed Computing, 30(1):17-48, 2017. Google Scholar
  4. G. D'Angelo, G. D. Stefano, R. Klasing, and A. Navarra. Gathering of robots on anonymous grids and trees without multiplicity detection. Theor. Comput. Sci., 610:158-168, 2016. Google Scholar
  5. G. D'Angelo, G. D. Stefano, and A. Navarra. Gathering on rings under the Look-Compute-Move model. Distributed Computing, 27(4):255-285, 2014. Google Scholar
  6. S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. Autonomous mobile robots with lights. Theor. Comput. Sci., 609:171-184, 2016. Google Scholar
  7. A. K. Datta, A. Lamani, L. L. Larmore, and F. Petit. Enabling Ring Exploration with Myopic Oblivious Robots. In IPDPS, pages 490-499, 2015. Google Scholar
  8. P. Flocchini, G. Prencipe, and N. Santoro, editors. Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of LNCS. Springer, 2019. Google Scholar
  9. S. Guilbault and A. Pelc. Gathering asynchronous oblivious agents with local vision in regular bipartite graphs. Theor. Comput. Sci., 509:86-96, 2013. Google Scholar
  10. S. Guilbault and A. Pelc. Gathering Asynchronous Oblivious Agents with Restricted Vision in an Infinite Line. In SSS, volume 8255, pages 296-310, 2013. Google Scholar
  11. T. Izumi, T. Izumi, S. Kamei, and F. Ooshita. Time-Optimal Gathering Algorithm of Mobile Robots with Local Weak Multiplicity Detection in Rings. IEICE Transactions, 96-A(6):1072-1080, 2013. Google Scholar
  12. S. Kamei, A. Lamani, and F. Ooshita. Asynchronous Ring Gathering by Oblivious Robots with Limited Vision. In WSSR, pages 46-49, 2014. Google Scholar
  13. S. Kamei, A. Lamani, F. Ooshita, S. Tixeuil, and K. Wada. Gathering on Rings for Myopic Asynchronous Robots with Lights. arXiv:1911.04757, 2019. Google Scholar
  14. R. Klasing, A. Kosowski, and A. Navarra. Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring. Theor. Comput. Sci., 411(34-36):3235-3246, 2010. Google Scholar
  15. G. A. D. Luna and G. Viglietta. Robots with Lights. In Distributed Computing by Mobile Entities, Current Research in Moving and Computing., volume 11340 of LNCS, pages 252-277. Springer, 2019. Google Scholar
  16. S. Nagahama, F. Ooshita, and M. Inoue. Ring Exploration of Myopic Luminous Robots with Visibility More than One. In SSS, 2019. Google Scholar
  17. F. Ooshita and S. Tixeuil. Ring Exploration with Myopic Luminous Robots. In SSS, pages 301-316, 2018. Google Scholar
  18. I. Suzuki and M. Yamashita. Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. SIAM Journal on Computing, 28(4):1347-1363, 1999. Google Scholar
  19. G. Viglietta. Rendezvous of Two Robots with Visible Bits. In ALGOSENSOR, pages 291-306, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact