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

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

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2020-02, Vol.806, p.595-616
Main Authors: Czyzowicz, Jurek, Georgiou, Konstantinos, Killick, Ryan, Kranakis, Evangelos, Krizanc, Danny, Narayanan, Lata, Opatrny, Jaroslav, Shende, Sunil
Format: Article
Language:English
Subjects:
Disk
Evacuation
Exit
Group search
Mobile robots
Priority
Queen
Servants
Wireless communication
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 1+2π3+3≈4.8264 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].
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2019.09.026