Evacuating Robots from a Disk Using Face-to-Face Communication
Assume that two robots are located at the centre of a unit disk. Their goal is to evacuate from the disk through an exit at an unknown location on the boundary of the disk. At any time the robots can move anywhere they choose on the disk, independently of each other, with maximum speed $1$. The robo...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2020-08-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/6198/pdf |
| _version_ | 1827323722699112448 |
|---|---|
| author | Jurek Czyzowicz Konstantinos Georgiou Evangelos Kranakis Lata Narayanan Jarda Opatrny Birgit Vogtenhuber |
| author_facet | Jurek Czyzowicz Konstantinos Georgiou Evangelos Kranakis Lata Narayanan Jarda Opatrny Birgit Vogtenhuber |
| author_sort | Jurek Czyzowicz |
| collection | DOAJ |
| description | Assume that two robots are located at the centre of a unit disk. Their goal
is to evacuate from the disk through an exit at an unknown location on the
boundary of the disk. At any time the robots can move anywhere they choose on
the disk, independently of each other, with maximum speed $1$. The robots can
cooperate by exchanging information whenever they meet. We study algorithms for
the two robots to minimize the evacuation time: the time when both robots reach
the exit.
In [CGGKMP14] the authors gave an algorithm defining trajectories for the two
robots yielding evacuation time at most $5.740$ and also proved that any
algorithm has evacuation time at least $3+ \frac{\pi}{4} + \sqrt{2} \approx
5.199$. We improve both the upper and lower bound on the evacuation time of a
unit disk. Namely, we present a new non-trivial algorithm whose evacuation time
is at most $5.628$ and show that any algorithm has evacuation time at least $3+
\frac{\pi}{6} + \sqrt{3} \approx 5.255$. To achieve the upper bound, we
designed an algorithm which proposes a forced meeting between the two robots,
even if the exit has not been found by either of them. We also show that such a
strategy is provably optimal for a related problem of searching for an exit
placed at the vertices of a regular hexagon. |
| first_indexed | 2024-04-25T01:57:01Z |
| format | Article |
| id | doaj.art-0854650aed7b40179ab735437581b121 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:01Z |
| publishDate | 2020-08-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-0854650aed7b40179ab735437581b1212024-03-07T15:43:24ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502020-08-01vol. 22 no. 4Distributed Computing and...10.23638/DMTCS-22-4-46198Evacuating Robots from a Disk Using Face-to-Face CommunicationJurek CzyzowiczKonstantinos GeorgiouEvangelos KranakisLata NarayananJarda OpatrnyBirgit VogtenhuberAssume that two robots are located at the centre of a unit disk. Their goal is to evacuate from the disk through an exit at an unknown location on the boundary of the disk. At any time the robots can move anywhere they choose on the disk, independently of each other, with maximum speed $1$. The robots can cooperate by exchanging information whenever they meet. We study algorithms for the two robots to minimize the evacuation time: the time when both robots reach the exit. In [CGGKMP14] the authors gave an algorithm defining trajectories for the two robots yielding evacuation time at most $5.740$ and also proved that any algorithm has evacuation time at least $3+ \frac{\pi}{4} + \sqrt{2} \approx 5.199$. We improve both the upper and lower bound on the evacuation time of a unit disk. Namely, we present a new non-trivial algorithm whose evacuation time is at most $5.628$ and show that any algorithm has evacuation time at least $3+ \frac{\pi}{6} + \sqrt{3} \approx 5.255$. To achieve the upper bound, we designed an algorithm which proposes a forced meeting between the two robots, even if the exit has not been found by either of them. We also show that such a strategy is provably optimal for a related problem of searching for an exit placed at the vertices of a regular hexagon.https://dmtcs.episciences.org/6198/pdfcomputer science - data structures and algorithms |
| spellingShingle | Jurek Czyzowicz Konstantinos Georgiou Evangelos Kranakis Lata Narayanan Jarda Opatrny Birgit Vogtenhuber Evacuating Robots from a Disk Using Face-to-Face Communication Discrete Mathematics & Theoretical Computer Science computer science - data structures and algorithms |
| title | Evacuating Robots from a Disk Using Face-to-Face Communication |
| title_full | Evacuating Robots from a Disk Using Face-to-Face Communication |
| title_fullStr | Evacuating Robots from a Disk Using Face-to-Face Communication |
| title_full_unstemmed | Evacuating Robots from a Disk Using Face-to-Face Communication |
| title_short | Evacuating Robots from a Disk Using Face-to-Face Communication |
| title_sort | evacuating robots from a disk using face to face communication |
| topic | computer science - data structures and algorithms |
| url | https://dmtcs.episciences.org/6198/pdf |
| work_keys_str_mv | AT jurekczyzowicz evacuatingrobotsfromadiskusingfacetofacecommunication AT konstantinosgeorgiou evacuatingrobotsfromadiskusingfacetofacecommunication AT evangeloskranakis evacuatingrobotsfromadiskusingfacetofacecommunication AT latanarayanan evacuatingrobotsfromadiskusingfacetofacecommunication AT jardaopatrny evacuatingrobotsfromadiskusingfacetofacecommunication AT birgitvogtenhuber evacuatingrobotsfromadiskusingfacetofacecommunication |