×

Priority evacuation from a disk: the case of \(n = 1,2,3\). (English) Zbl 1437.68173

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 + \frac{2 \pi}{3} + \sqrt{3} \approx 4.8264\) time units and this is optimal [the first author et al., Lect. Notes Comput. Sci. 8784, 122–136 (2014; Zbl 1393.68164)]. 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 + \pi / 6 + \sqrt{3} / 2 \approx 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 [the first author et al., Lect. Notes Comput. Sci. 11085, 392–407 (2018; Zbl 1436.68370)].

MSC:

68T40 Artificial intelligence for robotics
68M14 Distributed systems
Full Text: DOI

References:

[1] Ahlswede, R.; Wegener, I., Search Problems (1987), Wiley-Interscience · Zbl 0647.90023
[2] Alpern, S.; Gal, S., The Theory of Search Games and Rendezvous, vol. 55 (2002), Kluwer Academic Publishers
[3] (Alpern, Steve; Fokkink, Robbert; Gasieniec, Leszek; Lindelauf, Roy; Subrahmanian, V. S., Ten Open Problems in Rendezvous Search (2013), Springer NY: Springer NY New York, NY), 223-230 · Zbl 1263.91001
[4] Baeza Yates, R.; Culberson, J.; Rawlins, G., Searching in the plane, Inf. Comput., 106, 2, 234-252 (1993) · Zbl 0781.68044
[5] Baeza-Yates, R.; Schott, R., Parallel searching in the plane, Comput. Geom., 5, 3, 143-154 (1995) · Zbl 0839.68104
[6] Beck, A., On the linear search problem, Isr. J. Math., 2, 4, 221-228 (1964) · Zbl 0168.39502
[7] Bellman, R., An optimal search, SIAM Rev., 5, 3, 274 (1963)
[8] Brandt, S.; Laufenberg, F.; Lv, Y.; Stolz, D.; Wattenhofer, R., Collaboration without communication: evacuating two robots from a disk, (Proceedings of Algorithms and Complexity - 10th International Conference. Proceedings of Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017 (2017)), 104-115 · Zbl 1487.68241
[9] Chuangpishit, H.; Georgiou, K.; Sharma, P., Average case - worst case tradeoffs for evacuating 2 robots from the disk in the face-to-face model, (ALGOSENSORS’18 (2018), Springer)
[10] Czyzowicz, J.; Dobrev, S.; Georgiou, K.; Kranakis, E.; MacQuarrie, F., Evacuating two robots from multiple unknown exits in a circle, Theor. Comput. Sci., 709, 20-30 (2018) · Zbl 1382.68239
[11] Czyzowicz, J.; Gasieniec, L.; Gorry, T.; Kranakis, E.; Martin, R.; Pajak, D., Evacuating robots from an unknown exit located on the perimeter of a disc, (Proceedings DISC. Proceedings DISC, Austin, TX (2014), Springer), 122-136 · Zbl 1393.68164
[12] Czyzowicz, J.; Georgiou, K.; Godon, M.; Kranakis, E.; Krizanc, D.; Rytter, W.; Wlodarczyk, M., Evacuation from a disc in the presence of a faulty robot, (Proceedings SIROCCO 2017. Proceedings SIROCCO 2017, 19-22 June 2017, Porquerolles, France (2018)), 158-173 · Zbl 1496.68046
[13] Czyzowicz, J.; Georgiou, K.; Killick, R.; Kranakis, E.; Krizanc, D.; Narayanan, L.; Opatrny, J.; Shende, S., Priority evacuation from a disk using mobile robots, (SIROCCO (2018), Springer) · Zbl 1436.68370
[14] Czyzowicz, J.; Georgiou, K.; Kranakis, E.; Narayanan, L.; Opatrny, J.; Vogtenhuber, B., Evacuating robots from a disk using face-to-face communication (extended abstract), (Proceedings of Algorithms and Complexity. Proceedings of Algorithms and Complexity, CIAC 2015, Paris, France, May 20-22, 2015 (2015)), 140-152 · Zbl 1459.68212
[15] Czyzowicz, J.; Kranakis, E.; Krizanc, D.; Narayanan, L.; Opatrny, J.; Shende, S., Wireless autonomous robot evacuation from equilateral triangles and squares, (Proceedings of Ad-hoc, Mobile, and Wireless Networks, ADHOC-NOW. Proceedings of Ad-hoc, Mobile, and Wireless Networks, ADHOC-NOW, Athens, Greece, June 29-July 1, 2015 (2015)), 181-194
[16] Lamprou, I.; Martin, R.; Schewe, S., Fast two-robot disk evacuation with wireless communication, (Proceedings DISC. Proceedings DISC, Paris, France (2016)), 1-15 · Zbl 1393.68166
[17] Pattanayak, D.; Ramesh, H.; Mandal, P. S.; Schmid, S., Evacuating two robots from two unknown exits on the perimeter of a disk with wireless communication, (Proceedings of the 19th International Conference on Distributed Computing and Networking. Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN 2018, Varanasi, India, January 4-7, 2018 (2018)), Article 20 pp.
[18] Stone, L., Theory of Optimal Search (1975), Academic Press: Academic Press New York · Zbl 0343.90030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.