Optimal Rendezvous L-Algorithms for Asynchronous Mobile Robots with External-Lights

Authors Takashi Okumura, Koichi Wada, Xavier Défago



PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2018.24.pdf
  • Filesize: 0.48 MB
  • 16 pages

Document Identifiers

Author Details

Takashi Okumura
  • Graduate School of Science and Engineering, Hosei University, Tokyo, 184-8485, Japan
Koichi Wada
  • Faculty of Science and Engineering, Hosei University, Tokyo, 184-8485, Japan, http://ai.k.hosei.ac.jp/staff/wada
Xavier Défago
  • School of Computing, Tokyo Institute of Technology, Tokyo, Japan

Cite AsGet BibTex

Takashi Okumura, Koichi Wada, and Xavier Défago. Optimal Rendezvous L-Algorithms for Asynchronous Mobile Robots with External-Lights. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.OPODIS.2018.24

Abstract

We study the Rendezvous problem for two autonomous mobile robots in asynchronous settings with persistent memory called light. It is well known that Rendezvous is impossible in a basic model when robots have no lights, even if the system is semi-synchronous. On the other hand, Rendezvous is possible if robots have lights of various types with a constant number of colors. If robots can observe not only their own lights but also other robots' lights, their lights are called full-light. If robots can only observe the state of other robots' lights, the lights are called external-light. This paper focuses on robots with external-lights in asynchronous settings and a particular class of algorithms called L-algorithms, where an L-algorithm computes a destination based only on the current colors of observable lights. When considering L-algorithms, Rendezvous can be solved by robots with full-lights and three colors in general asynchronous settings (called ASYNC) and the number of colors is optimal under these assumptions. In contrast, there exist no L-algorithms in ASYNC with external-lights regardless of the number of colors. In this paper, extending the impossibility result, we show that there exist no L-algorithms in so-called LC-1-Bounded ASYNC with external-lights regardless of the number of colors, where LC-1-Bounded ASYNC is a proper subset of ASYNC and other robots can execute at most one Look operation between the Look operation of a robot and its subsequent Compute operation. We also show that LC-1-Bounded ASYNC is the minimal subclass in which no L-algorithms with external-lights exist. That is, Rendezvous can be solved by L-algorithms using external-lights with a finite number of colors in LC-0-Bounded ASYNC (equivalently LC-atomic ASYNC). Furthermore, we show that the algorithms are optimal in the number of colors they use.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Computing methodologies → Self-organization
Keywords
  • Autonomous mobile robots
  • Rendezvous
  • Lights
  • L-algorithms

Metrics

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

References

  1. N. Agmon and D. Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput., 36(1):56-82, 2006. Google Scholar
  2. Z. Bouzid, S. Das, and S. Tixeuil. Gathering of mobile robots tolerating multiple crash Faults. In 33rd ICDCS, pages 334-346, 2013. Google Scholar
  3. M. Cieliebak, P. Flocchini, G. Prencipe, and N. Santoro. Distributed computing by mobile robots: Gathering. sicomp, 41(4):829-879, 2012. Google Scholar
  4. S. Das, P. Flocchini, G. Prencipe, N. Santoro, and M. Yamashita. Autonomous mobile robots with lights. Theoretical Computer Science, 609:171-184, 2016. Google Scholar
  5. X. Défago, M. Gradinariu Potop-Butucaru, J. Clément, S. Messika, and P. Raipin Parvédy. Fault and Byzantine tolerant self-stabilizing mobile robots gathering - Feasibility study. CoRR abs/1602.05546, arXiv, 2016. Google Scholar
  6. B. Degener, B. Kempkes, T. Langner, F. Meyer auf der Heide, P. Pietrzyk, and R. Wattenhofer. A tight run-time bound for synchronous gathering of autonomous robots with limited visibility. In 23rd ACM SPAA, pages 139-148, 2011. Google Scholar
  7. Y. Dieudonné and F. Petit. Self-stabilizing gathering with strong multiplicity detection. tcs, 428(13):47-57, 2012. Google Scholar
  8. P. Flocchini, G. Prencipe, and N. Santoro. Distributed Computing by Oblivious Mobile Robots. Morgan &Claypool, 2012. Google Scholar
  9. P. Flocchini, G. Prencipe, N. Santoroand, and P. Widmayer. Gathering of asynchronous robots with limited visibility. tcs, 337(1-3):147-169, 2005. Google Scholar
  10. P. Flocchini, N. Santoro, G. Viglietta, and M. Yamashita. Rendezvous with Constant Memory. tcs, 621:57-72, 2016. Google Scholar
  11. A. Hériban, X. Défago, and S. Tixeuil. Optimally gathering two robots. In 19th ICDCN:3, pages 1-10, 2018. Google Scholar
  12. T. Izumi, Z. Bouzid, S. Tixeuil, and K. Wada. Brief Announcement: The BG-simulation for Byzantine mobile robots. In 25th DISC, pages 330-331, 2011. Google Scholar
  13. T. Izumi, Y. Katayama, N. Inuzuka, and K. Wada. Gathering Autonomous Mobile Robots with Dynamic Compasses: An Optimal Result. In 21st DISC, pages 298-312, 2007. Google Scholar
  14. T. Izumi, S. Souissi, Y. Katayama, N. Inuzuka, X. Défago, K. Wada, and M. Yamashita. The gathering problem for two oblivious robots with unreliable compasses. sicomp, 41(1):26-46, 2012. Google Scholar
  15. S. Kamei, A. Lamani, F. Ooshita, and S. Tixeuil. Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection. In 18th SIROCCO, pages 150-161, 2011. Google Scholar
  16. J. Lin, A.S. Morse, and B.D.O. Anderson. The multi-agent rendezvous problem. parts 1 and 2. sicomp, 46(6):2096-2147, 2007. Google Scholar
  17. T. Okumura, K. Wada, and Y. Katayama. Brief Announcement: Optimal asynchronous Rendezvous for mobile robots with lights. In 19th SSS, pages 484-488, 2017. Google Scholar
  18. G. Prencipe. Impossibility of gathering by a set of autonomous mobile robots. tcs, 384(2-3):222-231, 2007. Google Scholar
  19. S. Souissi, X. Défago, and M. Yamashita. Using eventually consistent compasses to gather memory-less mobile robots with limited visibility. ACM Transactions on Autonomous and Adaptive Systems, 4(1):1-27, 2009. Google Scholar
  20. I. Suzuki and M. Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. sicomp, 28:1347-1363, 1999. Google Scholar
  21. G. Viglietta. Rendezvous of two robots with visible bits. In ALGOSENSORS 2013, pages 291-306, 2014. 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