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

4 Citations (Scopus)

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

Fingerprint

Evacuation
Mobile Robot
Mobile robots
Robot
Robots
Perimeter
Unit Disk
Upper and Lower Bounds
Trajectories
Trajectory
Demonstrate

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

Cite this

Czyzowicz, J., Georgiou, K., Killick, R., Kranakis, E., Krizanc, D., Narayanan, L., ... 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
Czyzowicz, Jurek ; Georgiou, Konstantinos ; Killick, Ryan ; Kranakis, Evangelos ; Krizanc, Danny ; Narayanan, Lata ; Opatrny, Jaroslav ; Shende, Sunil. / Priority evacuation from a disk using mobile robots. 25th International Colloquium, SIROCCO 2018, Revised Selected Papers. editor / Zvi Lotker ; Boaz Patt-Shamir. Springer Verlag, 2018. pp. 392-407 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{776c20b283fd4f92936881e2ba906d01,
title = "Priority evacuation from a disk using mobile robots",
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).",
keywords = "Disk, Evacuation, Exit, Group search, Mobile robots, Priority, Queen, Servants, Wireless communication",
author = "Jurek Czyzowicz and Konstantinos Georgiou and Ryan Killick and Evangelos Kranakis and Danny Krizanc and Lata Narayanan and Jaroslav Opatrny and Sunil Shende",
year = "2018",
month = "1",
day = "1",
doi = "10.1007/978-3-030-01325-7_32",
language = "English (US)",
isbn = "9783030013240",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "392--407",
editor = "Zvi Lotker and Boaz Patt-Shamir",
booktitle = "25th International Colloquium, SIROCCO 2018, Revised Selected Papers",
address = "Germany",

}

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. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11085, Springer Verlag, pp. 392-407, 25th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2018, Ma’ale HaHamisha, Israel, 6/18/18. https://doi.org/10.1007/978-3-030-01325-7_32

Priority evacuation from a disk using mobile robots. / Czyzowicz, Jurek; Georgiou, Konstantinos; Killick, Ryan; Kranakis, Evangelos; Krizanc, Danny; Narayanan, Lata; Opatrny, Jaroslav; Shende, Sunil.

25th International Colloquium, SIROCCO 2018, Revised Selected Papers. ed. / Zvi Lotker; Boaz Patt-Shamir. Springer Verlag, 2018. p. 392-407 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11085).

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

TY - GEN

T1 - Priority evacuation from a disk using mobile robots

AU - Czyzowicz, Jurek

AU - Georgiou, Konstantinos

AU - Killick, Ryan

AU - Kranakis, Evangelos

AU - Krizanc, Danny

AU - Narayanan, Lata

AU - Opatrny, Jaroslav

AU - Shende, Sunil

PY - 2018/1/1

Y1 - 2018/1/1

N2 - 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).

AB - 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).

KW - Disk

KW - Evacuation

KW - Exit

KW - Group search

KW - Mobile robots

KW - Priority

KW - Queen

KW - Servants

KW - Wireless communication

UR - http://www.scopus.com/inward/record.url?scp=85061131544&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85061131544&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-01325-7_32

DO - 10.1007/978-3-030-01325-7_32

M3 - Conference contribution

AN - SCOPUS:85061131544

SN - 9783030013240

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 392

EP - 407

BT - 25th International Colloquium, SIROCCO 2018, Revised Selected Papers

A2 - Lotker, Zvi

A2 - Patt-Shamir, Boaz

PB - Springer Verlag

ER -

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