License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.19
URN: urn:nbn:de:0030-drops-173047
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17304/
Georgiou, Konstantinos ;
Giachoudis, Nikos ;
Kranakis, Evangelos
Evacuation from a Disk for Robots with Asymmetric Communication
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.
BibTeX - Entry
@InProceedings{georgiou_et_al:LIPIcs.ISAAC.2022.19,
author = {Georgiou, Konstantinos and Giachoudis, Nikos and Kranakis, Evangelos},
title = {{Evacuation from a Disk for Robots with Asymmetric Communication}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {19:1--19:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17304},
URN = {urn:nbn:de:0030-drops-173047},
doi = {10.4230/LIPIcs.ISAAC.2022.19},
annote = {Keywords: Communication, Cycle, Evacuation, Receiver, Sender, Mobile Agents}
}
|
Keywords: |
|
Communication, Cycle, Evacuation, Receiver, Sender, Mobile Agents |
|
Collection: |
|
33rd International Symposium on Algorithms and Computation (ISAAC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
