Abstract
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 [9] 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 bounds 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 non-intuitively proposes a forced meeting between the two robots, even if the exit has not been found by either of them.
This work was partially supported by NSERC grants.
This work was initiated during the \(13^{th}\) Workshop on Routing held in July 2014 in Querétaro, México.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahlswede, R., Wegener, I.: Search problems. Wiley-Interscience (1987)
Alpern, S., Beck, A.: Asymmetric rendezvous on the line is a double linear search problem. Mathematics of Operations Research 24(3), 604–618 (1999)
Alpern, S., Gal, S.: The theory of search games and rendezvous, vol. 55. Springer, New York (2003)
Yates, R.B., Culberson, J., Rawlins, G.: Searching in the plane. Information and Computation 106(2), 234–252 (1993)
Beck, A.: On the linear search problem. Israel Journal of Mathematics 2(4), 221–228 (1964)
Bellman, R.: An optimal search. Siam Review 5(3), 274–274 (1963)
Benkoski, S., Monticino, M., Weisinger, J.: A survey of the search theory literature. Naval Research Logistics (NRL) 38(4), 469–494 (1991)
Bonato, A., Nowakowski, R.: The game of cops and robbers on graphs. American Mathematical Soc. (2011)
Czyzowicz, J., Gasieniec, L., Gorry, T., Kranakis, E., Martin, R., Pajak, D.: Evacuating robots via unknown exit in a disk. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 122–136. Springer, Heidelberg (2014)
Czyzowicz, J., Georgiou, K., Kranakis, E., Narayanan, L., Opatrny, J., Vogtenhuber, B.: Evacuating using face-to-face communication. CoRR, abs/1501.04985 (2015)
Dobbie, J.: A survey of search theory. Operations Research 16(3), 525–537 (1968)
Emek, Y., Langner, T., Uitto, J., Wattenhofer, R.: Solving the ANTS problem with asynchronous finite state machines. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014, Part II. LNCS, vol. 8573, pp. 471–482. Springer, Heidelberg (2014)
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theoretical Computer Science 337(1), 147–168 (2005)
Lenzen, C., Lynch, N., Newport, C., Radeva, T.: Trade-offs between selection complexity and performance when searching the plane without communication. In: Proceedings of PODC, pp. 252–261 (2014)
López-Ortiz, A., Sweet, G.: Parallel searching on a lattice. In: Proceedings of CCCG, pp. 125–128 (2001)
Nahin, P.: Chases and Escapes: The Mathematics of Pursuit and Evasion. Princeton University Press (2012)
Stone, L.: Theory of optimal search. Academic Press, New York (1975)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Czyzowicz, J., Georgiou, K., Kranakis, E., Narayanan, L., Opatrny, J., Vogtenhuber, B. (2015). Evacuating Robots from a Disk Using Face-to-Face Communication (Extended Abstract). In: Paschos, V., Widmayer, P. (eds) Algorithms and Complexity. CIAC 2015. Lecture Notes in Computer Science(), vol 9079. Springer, Cham. https://doi.org/10.1007/978-3-319-18173-8_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-18173-8_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18172-1
Online ISBN: 978-3-319-18173-8
eBook Packages: Computer ScienceComputer Science (R0)