Jurek Czyzowicz ; Konstantinos Georgiou ; Evangelos Kranakis ; Lata Narayanan ; Jarda Opatrny et al. - Evacuating Robots from a Disk Using Face-to-Face Communication

dmtcs:6198 - Discrete Mathematics & Theoretical Computer Science, August 27, 2020, vol. 22 no. 4 - https://doi.org/10.23638/DMTCS-22-4-4
Evacuating Robots from a Disk Using Face-to-Face CommunicationArticle

Authors: Jurek Czyzowicz ; Konstantinos Georgiou ; Evangelos Kranakis ; Lata Narayanan ; Jarda Opatrny ; Birgit Vogtenhuber

    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.


    Volume: vol. 22 no. 4
    Section: Distributed Computing and Networking
    Published on: August 27, 2020
    Accepted on: July 31, 2020
    Submitted on: March 13, 2020
    Keywords: Computer Science - Data Structures and Algorithms
    Funding:
      Source : OpenAIRE Graph
    • Funder: Natural Sciences and Engineering Research Council of Canada

    1 Document citing this article

    Consultation statistics

    This page has been seen 552 times.
    This article's PDF has been downloaded 307 times.