Czyzowicz, Jurek; Georgiou, Konstantinos; Kranakis, Evangelos; Narayanan, Lata; Opatrny, Jarda; Vogtenhuber, Birgit Evacuating robots from a disk using face-to-face communication. (English) Zbl 1459.68213 Discrete Math. Theor. Comput. Sci. 22, No. 4, Paper No. 4, 22 p. (2020). Summary: 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 [Lect. Notes Comput. Sci. 8784, 122–136 (2014; Zbl 1393.68164)] the first author et al. 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. Cited in 1 ReviewCited in 6 Documents MSC: 68T40 Artificial intelligence for robotics 68W40 Analysis of algorithms Keywords:disk; evacuation; face-to-face model Citations:Zbl 1393.68164 PDFBibTeX XMLCite \textit{J. Czyzowicz} et al., Discrete Math. Theor. Comput. Sci. 22, No. 4, Paper No. 4, 22 p. (2020; Zbl 1459.68213) Full Text: DOI Link References: [1] Springer, 2015a. ISBN 978-3-319-18172-1. [2] Springer, 2014. ISBN 978-3-662-43950-0. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.