TY - JOUR

T1 - Priority evacuation from a disk

T2 - The case of n = 1,2,3

AU - Czyzowicz, Jurek

AU - Georgiou, Konstantinos

AU - Killick, Ryan

AU - Kranakis, Evangelos

AU - Krizanc, Danny

AU - Narayanan, Lata

AU - Opatrny, Jaroslav

AU - Shende, Sunil

N1 - Funding Information:
Research supported in part by NSERC of Canada.Research supported in part by the Ontario Graduate Scholarship (OGS) Program.Research partially supported by NSF grant no. AF-1813940.
Publisher Copyright:
© 2019 Elsevier B.V.

PY - 2020/2/2

Y1 - 2020/2/2

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

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

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=85072833013&partnerID=8YFLogxK

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

U2 - 10.1016/j.tcs.2019.09.026

DO - 10.1016/j.tcs.2019.09.026

M3 - Article

AN - SCOPUS:85072833013

VL - 806

SP - 595

EP - 616

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -