Priority evacuation from a disk using mobile robots

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Scopus citations

Abstract

We introduce and study a new search-type problem with (n+1)-robots on a disk. The searchers (robots) all start from the center of the disk, have unit speed, and can communicate wirelessly. The goal is for a distinguished robot (the queen) to reach and evacuate from an exit that is hidden on the perimeter of the disk in as little time as possible. The remaining n robots (servants) are there to facilitate the queen’s objective and are not required to reach the hidden exit. We provide upper and lower bounds for the time required to evacuate the queen. Namely, we propose an algorithm specifying the trajectories of the robots which guarantees evacuation of the queen in time always better than (formula presented) for n ≥ 4 servants. We also demonstrate that for n ≥ 4 servants the queen cannot be evacuated in time less than (formula presented).

Original languageEnglish (US)
Title of host publication25th International Colloquium, SIROCCO 2018, Revised Selected Papers
EditorsZvi Lotker, Boaz Patt-Shamir
PublisherSpringer Verlag
Pages392-407
Number of pages16
ISBN (Print)9783030013240
DOIs
StatePublished - Jan 1 2018
Event25th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2018 - Ma’ale HaHamisha, Israel
Duration: Jun 18 2018Jun 21 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11085
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2018
CountryIsrael
CityMa’ale HaHamisha
Period6/18/186/21/18

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 using mobile robots'. Together they form a unique fingerprint.

  • Cite this

    Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., & Shende, S. (2018). Priority evacuation from a disk using mobile robots. In Z. Lotker, & B. Patt-Shamir (Eds.), 25th International Colloquium, SIROCCO 2018, Revised Selected Papers (pp. 392-407). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11085). Springer Verlag. https://doi.org/10.1007/978-3-030-01325-7_32