Priority evacuation from a disk: the case of \(n \geq 4\). (English) Zbl 1464.68401
Summary: 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 from a unit disk. Namely, we propose an algorithm specifying the trajectories of the robots which guarantees evacuation of the queen in time always better than \(2 + 4(\sqrt{ 2} - 1) \frac{ \pi}{ n}\) for \(n \geq 4\) servants. We also demonstrate that for \(n \geq 4\) servants the queen cannot be evacuated in time less than \(2 + \frac{ \pi}{ n} + \frac{ 2}{ n^2} \).
Keywords:
mobile robots; priority evacuation; group search; evacuation from a disk; wireless communicationReferences:
| [1] | Albers, S.; Henzinger, M. R., Exploring unknown environments, SIAM J. Comput., 29, 4, 1164-1188 (2000) · Zbl 0947.68165 |
| [2] | Alpern, S.; Gal, S., The Theory of Search Games and Rendezvous, Vol. 55 (2002), Kluwer Academic Publishers |
| [3] | Baeza Yates, R.; Culberson, J.; Rawlins, G., Searching in the plane, Inf. Comput., 106, 2, 234-252 (1993) · Zbl 0781.68044 |
| [4] | Bampas, E.; Czyzowicz, J.; Gasieniec, L.; Ilcinkas, D.; Klasing, R.; Kociumaka, T.; Pajak, D., Linear search by a pair of distinct-speed robots, (SIROCCO. SIROCCO, LNCS (2016), Springer), 195-211 · Zbl 1410.68055 |
| [5] | Beck, A., On the linear search problem, Isr. J. Math., 2, 4, 221-228 (1964) · Zbl 0168.39502 |
| [6] | Bellman, R., An optimal search, SIAM Rev., 5, 3, 274 (1963) |
| [7] | Bose, P.; De Carufel, J.-L., A general framework for searching on a line, (WALCOM 2016 (2016)), 143-153 · Zbl 1380.68452 |
| [8] | Bose, P.; De Carufel, J.-L.; Durocher, S., Revisiting the problem of searching on a line, (ESA 2013, Sophia Antipolis, France, September 2-4, 2013. Proceedings (2013)), 205-216 · Zbl 1394.68166 |
| [9] | Brandt, S.; Laufenberg, F.; Lv, Y.; Stolz, D.; Wattenhofer, R., Collaboration without communication: evacuating two robots from a disk, (Algorithms and Complexity - 10th International Conference, CIAC 2017, Athens, Greece, May 24-26, 2017. Proceedings (2017)), 104-115 · Zbl 1487.68241 |
| [10] | Chrobak, M.; Gasieniec, L.; Gorry, T.; Martin, R., Group search on the line, (SOFSEM 2015 (2015), Springer), 164-176 · Zbl 1410.68159 |
| [11] | 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) |
| [12] | Czyzowicz, J.; Dobrev, S.; Georgiou, K.; Kranakis, E.; MacQuarrie, F., Evacuating two robots from multiple unknown exits in a circle, (Proceedings of the 17th International Conference on Distributed Computing and Networking. Proceedings of the 17th International Conference on Distributed Computing and Networking, Singapore, January 4-7, 2016 (2016)), 28:1-28:8 |
| [13] | 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, (DISC 2014 (2014), Springer: Springer Austin, Texas), 122-136 · Zbl 1393.68164 |
| [14] | 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, (SIROCCO 2017, 19-22 June 2017, Porquerolles, France (2017)), 158-173 · Zbl 1496.68046 |
| [15] | 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 |
| [16] | Czyzowicz, J.; Georgiou, K.; Killick, R.; Kranakis, E.; Krizanc, K.; Narayanan, L.; Opatrny, J.; Shende, S., God save the queen, (9th International Conference on Fun with Algorithms (FUN’18) (2018)) · Zbl 1489.68348 |
| [17] | Czyzowicz, J.; Georgiou, K.; Kranakis, E.; Narayanan, L.; Opatrny, J.; Vogtenhuber, B., Evacuating robots from a disk using face-to-face communication (extended abstract), (Algorithms and Complexity, CIAC 2015, Paris, France, May 20-22, 2015. Proceedings (2015)), 140-152 · Zbl 1459.68212 |
| [18] | Czyzowicz, J.; Kranakis, E.; Krizanc, D.; Narayanan, L.; Opatrny, J.; Shende, S., Wireless autonomous robot evacuation from equilateral triangles and squares, (ADHOC-NOW (2015)), 181-194 |
| [19] | Demaine, E. D.; Fekete, S. P.; Gal, S., Online searching with turn cost, Theor. Comput. Sci., 361, 2, 342-355 (2006) · Zbl 1097.68031 |
| [20] | Deng, X.; Kameda, T.; Papadimitriou, C., How to learn an unknown environment, (FOCS (1991), IEEE), 298-303 |
| [21] | Feinerman, Ofer; Korman, Amos; Kutten, Shay; Rodeh, Yoav, Fast rendezvous on a cycle by agents with different speeds, Theor. Comput. Sci., 688, 77-85 (2017) · Zbl 1371.68035 |
| [22] | Fomin, F. V.; Thilikos, D. M., An annotated bibliography on guaranteed graph searching, Theor. Comput. Sci., 399, 3, 236-245 (2008) · Zbl 1160.68007 |
| [23] | Georgiou, Konstantinos; Karakostas, George; Kranakis, Evangelos, Search-and-fetch with one robot on a disk - (track: Wireless and geometry), (ALGOSENSORS 2016 (2016)), 80-94 · Zbl 1403.68297 |
| [24] | Georgiou, Konstantinos; Karakostas, George; Kranakis, Evangelos, Search-and-fetch with 2 robots on a disk - wireless and face-to-face communication models, (Liberatore, Federico; Parlier, Greg H.; Demange, Marc, ICORES 2017, Porto, Portugal, February 23-25, 2017 (2017), SciTePress), 15-26 · Zbl 1416.68191 |
| [25] | Hoffmann, F.; Icking, C.; Klein, R.; Kriegel, K., The polygon exploration problem, SIAM J. Comput., 31, 2, 577-600 (2001) · Zbl 0994.68163 |
| [26] | Lamprou, I.; Martin, R.; Schewe, S., Fast two-robot disk evacuation with wireless communication, (International Symposium on Distributed Computing (2016)), 1-15 · Zbl 1393.68166 |
| [27] | Papadimitriou, C. H.; Yannakakis, M., Shortest paths without a map, (ICALP (1989), Springer), 610-620 |
| [28] | 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, (ICDCN 2018, Varanasi, India, January 4-7, 2018 (2018)), 20:1-20:4 |
| [29] | Animation of Algorithm 2 for \(n = 4\) (Feb. 13, 2018) |
| [30] | Animation of Algorithm 2 for \(n = 8\) (Feb. 13, 2018) |
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.
