Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models
We initiate the study of a new problem on searching and fetching in a distributed environment concerning treasure-evacuation from a unit disk. A treasure and an exit are located at unknown positions on the perimeter of a disk and at known arc distance. A team of two robots start from the center of t...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2019-06-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/4884/pdf |
| _version_ | 1797270045317922816 |
|---|---|
| author | Konstantinos Georgiou George Karakostas Evangelos Kranakis |
| author_facet | Konstantinos Georgiou George Karakostas Evangelos Kranakis |
| author_sort | Konstantinos Georgiou |
| collection | DOAJ |
| description | We initiate the study of a new problem on searching and fetching in a
distributed environment concerning treasure-evacuation from a unit disk. A
treasure and an exit are located at unknown positions on the perimeter of a
disk and at known arc distance. A team of two robots start from the center of
the disk, and their goal is to fetch the treasure to the exit. At any time the
robots can move anywhere they choose on the disk, independently of each other,
with the same speed. A robot detects an interesting point (treasure or exit)
only if it passes over the exact location of that point. We are interested in
designing distributed algorithms that minimize the worst-case
treasure-evacuation time, i.e. the time it takes for the treasure to be
discovered and brought (fetched) to the exit by any of the robots.
The communication protocol between the robots is either wireless, where
information is shared at any time, or face-to-face (i.e. non-wireless), where
information can be shared only if the robots meet. For both models we obtain
upper bounds for fetching the treasure to the exit. Our main technical
contribution pertains to the face-to-face model. More specifically, we
demonstrate how robots can exchange information without meeting, effectively
achieving a highly efficient treasure-evacuation protocol which is minimally
affected by the lack of distant communication. Finally, we complement our
positive results above by providing a lower bound in the face-to-face model. |
| first_indexed | 2024-04-25T01:58:01Z |
| format | Article |
| id | doaj.art-f4b938e31dc743fb9fcea2b4a605592e |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:01Z |
| publishDate | 2019-06-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-f4b938e31dc743fb9fcea2b4a605592e2024-03-07T15:39:17ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502019-06-01Vol. 21 no. 3Distributed Computing and...10.23638/DMTCS-21-3-204884Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication ModelsKonstantinos GeorgiouGeorge KarakostasEvangelos KranakisWe initiate the study of a new problem on searching and fetching in a distributed environment concerning treasure-evacuation from a unit disk. A treasure and an exit are located at unknown positions on the perimeter of a disk and at known arc distance. A team of two robots start from the center of the disk, and their goal is to fetch the treasure to the exit. At any time the robots can move anywhere they choose on the disk, independently of each other, with the same speed. A robot detects an interesting point (treasure or exit) only if it passes over the exact location of that point. We are interested in designing distributed algorithms that minimize the worst-case treasure-evacuation time, i.e. the time it takes for the treasure to be discovered and brought (fetched) to the exit by any of the robots. The communication protocol between the robots is either wireless, where information is shared at any time, or face-to-face (i.e. non-wireless), where information can be shared only if the robots meet. For both models we obtain upper bounds for fetching the treasure to the exit. Our main technical contribution pertains to the face-to-face model. More specifically, we demonstrate how robots can exchange information without meeting, effectively achieving a highly efficient treasure-evacuation protocol which is minimally affected by the lack of distant communication. Finally, we complement our positive results above by providing a lower bound in the face-to-face model.https://dmtcs.episciences.org/4884/pdfcomputer science - data structures and algorithms |
| spellingShingle | Konstantinos Georgiou George Karakostas Evangelos Kranakis Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models Discrete Mathematics & Theoretical Computer Science computer science - data structures and algorithms |
| title | Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models |
| title_full | Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models |
| title_fullStr | Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models |
| title_full_unstemmed | Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models |
| title_short | Search-and-Fetch with 2 Robots on a Disk: Wireless and Face-to-Face Communication Models |
| title_sort | search and fetch with 2 robots on a disk wireless and face to face communication models |
| topic | computer science - data structures and algorithms |
| url | https://dmtcs.episciences.org/4884/pdf |
| work_keys_str_mv | AT konstantinosgeorgiou searchandfetchwith2robotsonadiskwirelessandfacetofacecommunicationmodels AT georgekarakostas searchandfetchwith2robotsonadiskwirelessandfacetofacecommunicationmodels AT evangeloskranakis searchandfetchwith2robotsonadiskwirelessandfacetofacecommunicationmodels |