Document Open Access Logo

Evacuation from a Disk for Robots with Asymmetric Communication

Authors Konstantinos Georgiou, Nikos Giachoudis , Evangelos Kranakis

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.19.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Konstantinos Georgiou
  • Department of Mathematics, Toronto Metropolitan University, Canada
Nikos Giachoudis
  • Department of Mathematics, Toronto Metropolitan University, Canada
Evangelos Kranakis
  • School of Computer Science, Carleton University, Ottawa, Canada

Funding

  • Georgiou, Konstantinos: Research supported in part by NSERC.
  • Giachoudis, Nikos: Research supported in part by the Fields Institute and the Faculty of Science, Ryerson University.
  • Kranakis, Evangelos: Research supported in part by NSERC.

Cite AsGet BibTex

Konstantinos Georgiou, Nikos Giachoudis, and Evangelos Kranakis. Evacuation from a Disk for Robots with Asymmetric Communication. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.19

Abstract

We consider evacuation of two robots from an Exit placed at an unknown location on the perimeter of a unit (radius) disk. The robots can move with max speed 1 and start at the center of the disk at the same time. We consider a new communication model, known as the SR model, in which the robots have communication faults as follows: one of the robots is a Sender and can only send wirelessly at any distance, while the other is a Receiver in that it can only receive wirelessly from any distance. The communication status of each robot is known to the other robot. In addition, both robots can exchange messages when they are co-located, which is known as Face-to-Face (F2F) model. There have been several studies in the literature concerning the evacuation time when both robots may employ either F2F or Wireless (WiFi) communication. The SR communication model diverges from these two in that the two robots themselves have differing communication capabilities. We study the evacuation time, namely the time it takes until the last robot reaches the Exit, and show that the evacuation time in the SR model is strictly between the F2F and the WiFi models. The main part of our technical contribution is also an evacuation algorithm in which two cooperating robots accomplish the task in worst-case time at most π+2. Interesting features of the proposed algorithm are the asymmetry inherent in the resulting trajectories, as well as that the robots do not move at full speed for the entire duration of their trajectories.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Communication
  • Cycle
  • Evacuation
  • Receiver
  • Sender
  • Mobile Agents

Metrics

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

References

  1. Sebastian Brandt, Felix Laufenberg, Yuezhou Lv, David Stolz, and Roger Wattenhofer. Collaboration without communication: Evacuating two robots from a disk. In International Conference on Algorithms and Complexity, pages 104-115. Springer, 2017. Google Scholar
  2. J. Czyzowicz, L. Gasieniec, T. Gorry, E. Kranakis, R. Martin, and D. Pajak. Evacuating robots from an unknown exit located on the perimeter of a disc. In DISC 2014, pages 122-136. Springer, Austin, Texas, 2014. Google Scholar
  3. Jurek Czyzowicz, Konstantinos Georgiou, Maxime Godon, Evangelos Kranakis, Danny Krizanc, Wojciech Rytter, and Michał Włodarczyk. Evacuation from a disc in the presence of a faulty robot. In International Colloquium on Structural Information and Communication Complexity, pages 158-173. Springer, 2017. Google Scholar
  4. Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Lata Narayanan, Jaroslav Opatrny, and Sunil M. Shende. Energy consumption of group search on a line. In 46th International Colloquium on Automata, Languages, and Programming, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 137:1-137:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  5. Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, and Sunil Shende. Search on a line by byzantine robots. International Journal of Foundations of Computer Science, pages 1-19, 2021. Google Scholar
  6. Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Lata Narayanan, Jaroslav Opatrny, and Birgit Vogtenhuber. Evacuating robots from a disk using face-to-face communication. Discret. Math. Theor. Comput. Sci, 22(4), 2020. Google Scholar
  7. Jurek Czyzowicz, Kostantinos Georgiou, and Evangelos Kranakis. Group search and evacuation. In Distributed Computing by Mobile Entities, pages 335-370. Springer, 2019. Google Scholar
  8. Jurek Czyzowicz, Maxime Godon, Evangelos Kranakis, and Arnaud Labourel. Group search of the plane with faulty robots. Theoretical Computer Science, 792:69-84, 2019. Google Scholar
  9. Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Denis Pankratov, and Sunil Shende. Group evacuation on a line by agents with different communication abilities. ISAAC 2021, pages 57:1-57:24, 2021. Google Scholar
  10. Jurek Czyzowicz, Ryan Killick, Evangelos Kranakis, and Grzegorz Stachowiak. Search and evacuation with a near majority of faulty agents. In SIAM Conference on Applied and Computational Discrete Algorithms (ACDA21), pages 217-227. SIAM, 2021. Google Scholar
  11. Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, and Jaroslav Opatrny. Search on a line with faulty robots. Distributed Computing, 32(6):493-504, 2019. Google Scholar
  12. Yann Disser and Sören Schmitt. Evacuating two robots from a disk: a second cut. In International Colloquium on Structural Information and Communication Complexity, pages 200-214. Springer, 2019. Google Scholar
  13. Konstantinos Georgiou, Evangelos Kranakis, Nikos Leonardos, Aris Pagourtzis, and Ioannis Papaioannou. Optimal circle search despite the presence of faulty robots. In International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pages 192-205. Springer, 2019. Google Scholar
  14. Ioannis Lamprou, Russell Martin, and Sven Schewe. Fast two-robot disk evacuation with wireless communication. In Cyril Gavoille and David Ilcinkas, editors, Distributed Computing, pages 1-15, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. Google Scholar
  15. Nikos Leonardos, Aris Pagourtzis, and Ioannis Papaioannou. Byzantine fault tolerant symmetric-persistent circle evacuation. In Leszek Gąsieniec, Ralf Klasing, and Tomasz Radzik, editors, Algorithms for Sensor Systems, pages 111-123, Cham, 2021. Springer International Publishing. Google Scholar
  16. X. Sun, Y. Sun, and J. Zhang. Better upper bounds for searching on a line with byzantine robots. In Complexity and Approximation, pages 151-171. Springer, 2020. 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 Imprint Privacy Contact