nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Priority Evacuation from a Disk Using Mobile Robots

(Extended Abstract)

verfasst von : Jurek Czyzowicz, Konstantinos Georgiou, Ryan Killick, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, Jaroslav Opatrny, Sunil Shende

Erschienen in: Structural Information and Communication Complexity

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 \(2 + 4(\sqrt{2}-1) \frac{\pi }{n}\) for \(n \ge 4\) servants. We also demonstrate that for \(n \ge 4\) servants the queen cannot be evacuated in time less than \(2+\frac{\pi }{n}+\frac{2}{n^2}\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Formalizing Compute-Aggregate Problems in Cloud Computing

The choice of the x-axis is arbitrary since we may always rotate \(\mathcal {U}\). What is important is that a diameter of symmetry exists.

Again, these choices of search directions are arbitrary since we can reflect \(\mathcal {U}\) about the y-axis. What is important is that all servants within a group search in the same direction.

It is not guaranteed that for all \(\rho > 0\) this intercept will reach a speed of one before the queen reaches the perimeter of \(\mathcal {U}\). However, we will choose a \(\rho \) such that this does happen.

Alternatively we can say that the robots must search at a collective rate \(> n\) by the time \(t_c\). This is why we were able to ignore the “unreasonable case” in Lemma 7.

Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164–1188 (2000)MathSciNetCrossRef

Alpern, S., Gal, S.: The Theory of Search Games and Rendezvous, vol. 55. Kluwer Academic Publishers, Dordrecht (2002)MATH

Baeza Yates, R., Culberson, J., Rawlins, G., Rawlins, G.: Searching in the plane. Inf. Comput. 106(2), 234–252 (1993)MathSciNetCrossRef

Bampas, E., et al.: Linear search by a pair of distinct-speed robots. In: Suomela, J. (ed.) SIROCCO 2016. LNCS, vol. 9988, pp. 195–211. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48314-6_13CrossRef

Beck, A.: On the linear search problem. Isr. J. Math. 2(4), 221–228 (1964)MathSciNetCrossRef

Bellman, R.: An optimal search. SIAM Rev. 5(3), 274 (1963)CrossRef

Bose, P., De Carufel, J.-L.: A general framework for searching on a line. In: Kaykobad, M., Petreschi, R. (eds.) WALCOM 2016. LNCS, vol. 9627, pp. 143–153. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-30139-6_12CrossRef

Bose, P., De Carufel, J.-L., Durocher, S.: Revisiting the problem of searching on a line. In: Bodlaender, H.L., Italiano, G.F. (eds.) ESA 2013. LNCS, vol. 8125, pp. 205–216. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40450-4_18CrossRef

Brandt, S., Laufenberg, F., Lv, Y., Stolz, D., Wattenhofer, R.: Collaboration without communication: evacuating two robots from a disk. In: Fotakis, D., Pagourtzis, A., Paschos, V.T. (eds.) CIAC 2017. LNCS, vol. 10236, pp. 104–115. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-57586-5_10CrossRef

10.

Chrobak, M., Gasieniec, L., Gorry, T., Martin, R.: Group search on the line. In: Italiano, G.F., Margaria-Steffen, T., Pokorný, J., Quisquater, J.-J., Wattenhofer, R. (eds.) SOFSEM 2015. LNCS, vol. 8939, pp. 164–176. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46078-8_14CrossRef

11.

Czyzowicz, J., Dobrev, S., Georgiou, K., Kranakis, E., MacQuarrie, F.: Evacuating two robots from multiple unknown exits in a circle. In: Proceedings of the 17th International Conference on Distributed Computing and Networking, Singapore, 4–7 January 2016, pp. 28:1–28:8 (2016)

12.

Czyzowicz, J., Gąsieniec, L., Gorry, T., Kranakis, E., Martin, R., Pajak, D.: Evacuating robots via unknown exit in a disk. In: Kuhn, F. (ed.) DISC 2014. LNCS, vol. 8784, pp. 122–136. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45174-8_9CrossRef

13.

Czyzowicz, J., et al.: Evacuation from a disc in the presence of a faulty robot. In: Das, S., Tixeuil, S. (eds.) SIROCCO 2017. LNCS, vol. 10641, pp. 158–173. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72050-0_10CrossRef

14.

Czyzowicz, J., et al.: Priority evacuation from a disk using mobile robots. CoRR, abs/1805.03568 (2018)

15.

Czyzowicz, J., et al.: God save the queen. In: 9th International Conference on Fun With Algorithms (FUN18) (2018)

16.

Czyzowicz, J., Georgiou, K., Kranakis, E., Narayanan, L., Opatrny, J., Vogtenhuber, B.: Evacuating robots from a disk using face-to-face communication (extended abstract). In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 140–152. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-18173-8_10CrossRef

17.

Czyzowicz, J., Kranakis, E., Krizanc, D., Narayanan, L., Opatrny, J., Shende, S.: Wireless autonomous robot evacuation from equilateral triangles and squares. In: Papavassiliou, S., Ruehrup, S. (eds.) ADHOC-NOW 2015. LNCS, vol. 9143, pp. 181–194. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-19662-6_13CrossRef

18.

Demaine, E.D., Fekete, S.P., Gal, S.: Online searching with turn cost. Theor. Comput. Sci. 361(2), 342–355 (2006)MathSciNetCrossRef

19.

Deng, X., Kameda, T., Papadimitriou, C.: How to learn an unknown environment. In: FOCS, pp. 298–303. IEEE (1991)

20.

Feinerman, O., Korman, A., Kutten, S., Rodeh, Y.: Fast rendezvous on a cycle by agents with different speeds. Theor. Comput. Sci. 688, 77–85 (2017)MathSciNetCrossRef

21.

Fomin, F.V., Thilikos, D.M.: An annotated bibliography on guaranteed graph searching. Theor. Comput. Sci. 399(3), 236–245 (2008)MathSciNetCrossRef

22.

Georgiou, K., Karakostas, G., Kranakis, E.: Search-and-fetch with one robot on a disk (track: wireless and geometry). In: Chrobak, M., Fernández Anta, A., Gasieniec, L., Klasing, R. (eds.) ALGOSENSORS 2016. LNCS, vol. 10050, pp. 80–94. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-53058-1_6CrossRef

23.

Georgiou, K., Karakostas, G., Kranakis, E.: Search-and-fetch with 2 robots on a disk - wireless and face-to-face communication models. In: Liberatore, F., Parlier, G.H., Demange, M. (eds.) ICORES 2017, Porto, Portugal, 23–25 February 2017, pp. 15–26. SciTePress (2017)

24.

Hoffmann, F., Icking, C., Klein, R., Kriegel, K.: The polygon exploration problem. SIAM J. Comput. 31(2), 577–600 (2001)MathSciNetCrossRef

25.

Lamprou, I., Martin, R., Schewe, S.: Fast two-robot disk evacuation with wireless communication. In: Gavoille, C., Ilcinkas, D. (eds.) DISC 2016. LNCS, vol. 9888, pp. 1–15. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53426-7_1CrossRef

26.

Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. In: Ausiello, G., Dezani-Ciancaglini, M., Della Rocca, S.R. (eds.) ICALP 1989. LNCS, vol. 372, pp. 610–620. Springer, Heidelberg (1989). https://doi.org/10.1007/BFb0035787CrossRef

27.

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. In: ICDCN 2018, Varanasi, India, 4–7 January 2018, pp. 20:1–20:4 (2018)

28.

Animation of algorithm 2 for \(n=4\), 13 February 2018. https://drive.google.com/open?id=1OhmWeqFZLFLiwQalvPoZSTg9Ah860mMn

29.

Animation of algorithm 2 for \(n=8\), 13 February 2018. https://drive.google.com/open?id=10ntWmekJr5pTywEfpTNAw6uyxxrfpHsA

Titel: Priority Evacuation from a Disk Using Mobile Robots
verfasst von: Jurek Czyzowicz
Konstantinos Georgiou
Ryan Killick
Evangelos Kranakis
Danny Krizanc
Lata Narayanan
Jaroslav Opatrny
Sunil Shende
Verlag: Springer International Publishing
Buch: Structural Information and Communication Complexity
Print ISBN: 978-3-030-01324-0

Electronic ISBN: 978-3-030-01325-7

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-030-01325-7_32

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner