Priority evacuation from a disk: The case of n = 1,2,3

Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Sunil Shende

Research output: Contribution to journalArticle

Abstract

An exit (or target) is at an unknown location on the perimeter of a unit disk. A group of n+1 robots (in our case, n=1,2,3), initially located at the centre of the disk, are tasked with finding the exit. The robots have unique identities, share the same coordinate system, move at maximum speed 1 and are able to communicate wirelessly the position of the exit once found. Among them there is a distinguished robot called the queen and the remainder of the robots are referred to as servants. It is known that with two robots searching, the room can be evacuated (i.e., with both robots reaching the exit) in [Formula presented] time units and this is optimal [11]. Somewhat surprisingly, in this paper we show that if the goal is to have the queen reach the exit, not caring if her servants make it, there is a slightly better strategy for the case of one servant. We prove that this “priority” version of evacuation can be solved in time at most 4.81854. Furthermore, we show that any strategy for saving the queen with one servant requires time at least 3+π/6+3/2≈4.3896 in the worst case. If more servants are available, we show that the time bounds can be improved to 3.8327 for two servants, and 3.3738 for three servants which are better than the known lower bound for the corresponding problems of evacuating three or four robots. Finally, we show lower bounds for these cases of 3.6307 (two servants) and 3.2017 (three servants). The case of more than three servants uses substantially different techniques and is discussed in a separate paper [13].

Original languageEnglish (US)
JournalTheoretical Computer Science
DOIs
StateAccepted/In press - Jan 1 2019

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Disk
  • Evacuation
  • Exit
  • Group search
  • Mobile robots
  • Priority
  • Queen
  • Servants
  • Wireless communication

Fingerprint Dive into the research topics of 'Priority evacuation from a disk: The case of n = 1,2,3'. Together they form a unique fingerprint.

  • Cite this

    Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., & Shende, S. (Accepted/In press). Priority evacuation from a disk: The case of n = 1,2,3. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2019.09.026