Top

Published in:

2019 | OriginalPaper | Chapter

Optimal Gathering by Asynchronous Oblivious Robots in Hypercubes

Authors : Kaustav Bose, Manash Kumar Kundu, Ranendu Adhikary, Buddhadeb Sau

Published in: Algorithms for Sensor Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider the problem of gathering a set of autonomous, identical, oblivious, asynchronous, mobile robots at a vertex of an anonymous hypercube. The robots operate in Look-Compute-Move cycles. In each cycle, a robot takes a snapshot of the current configuration (Look), then based on the perceived configuration, decides whether to stay idle or to move to an adjacent vertex (Compute), and in the later case makes an instantaneous move accordingly (Move). We have shown that the problem is unsolvable if the robots do not have multiplicity detection capability. With weak multiplicity detection capability, the problem is solvable in an oriented hypercube for any initial configuration of \(2k+1 (k > 0)\) number of robots. For \(4k (k > 0)\) number of robots, the problem is solvable under the same assumptions if and only if the group of automorphism of the configuration is trivial. Our proposed algorithms are optimal with respect to the total number of moves executed by the robots.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Mutual Visibility by Asynchronous Robots on Infinite Grid

next chapter Barrier Coverage Problem in 2D

Available only for authorised users

Agathangelou, C., Georgiou, C., Mavronicolas, M.: A distributed algorithm for gathering many fat mobile robots in the plane. In: ACM Symposium on Principles of Distributed Computing, PODC 2013, Montreal, QC, Canada, 22–24 July 2013, pp. 250–259 (2013). https://doi.org/10.1145/2484239.2484266

Barrière, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Rendezvous and election of mobile agents: impact of sense of direction. Theory Comput. Syst. 40(2), 143–162 (2007). https://doi.org/10.1007/s00224-005-1223-5MathSciNetCrossRefMATH

Bose, K., Adhikary, R., Chaudhuri, S.G., Sau, B.: Crash tolerant gathering on grid by asynchronous oblivious robots. CoRR abs/1709.00877 (2017). http://arxiv.org/abs/1709.00877

Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the robots gathering problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 1181–1196. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-45061-0_90CrossRef

Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829–879 (2012). https://doi.org/10.1137/100796534MathSciNetCrossRefMATH

Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34(6), 1516–1528 (2005). https://doi.org/10.1137/S0097539704446475MathSciNetCrossRefMATH

Czyzowicz, J., Gasieniec, L., Pelc, A.: Gathering few fat mobile robots in the plane. Theor. Comput. Sci. 410(6–7), 481–499 (2009). https://doi.org/10.1016/j.tcs.2008.10.005MathSciNetCrossRefMATH

D’Angelo, G., Stefano, G.D., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids and trees without multiplicity detection. Theor. Comput. Sci. 610, 158–168 (2016). https://doi.org/10.1016/j.tcs.2014.06.045MathSciNetCrossRefMATH

D’Angelo, G., Di Stefano, G., Navarra, A.: Gathering of six robots on anonymous symmetric rings. In: Kosowski, A., Yamashita, M. (eds.) SIROCCO 2011. LNCS, vol. 6796, pp. 174–185. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22212-2_16CrossRef

10.

D’Angelo, G., Stefano, G.D., Navarra, A.: Gathering on rings under the look-compute-move model. Distrib. Comput. 27(4), 255–285 (2014). https://doi.org/10.1007/s00446-014-0212-9MathSciNetCrossRefMATH

11.

Das, S., Mihalák, M., Šrámek, R., Vicari, E., Widmayer, P.: Rendezvous of mobile agents when tokens fail anytime. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 463–480. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92221-6_29CrossRef

12.

Dessmark, A., Fraigniaud, P., Kowalski, D.R., Pelc, A.: Deterministic rendezvous in graphs. Algorithmica 46(1), 69–96 (2006). https://doi.org/10.1007/s00453-006-0074-2MathSciNetCrossRefMATH

13.

Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Multiple agents rendezvous in a ring in spite of a black hole. In: Papatriantafilou, M., Hunel, P. (eds.) OPODIS 2003. LNCS, vol. 3144, pp. 34–46. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27860-3_6CrossRefMATH

14.

Flocchini, P., Kranakis, E., Krizanc, D., Luccio, F.L., Santoro, N., Sawchuk, C.: Mobile agents rendezvous when tokens fail. In: Královic̆, R., Sýkora, O. (eds.) SIROCCO 2004. LNCS, vol. 3104, pp. 161–172. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-27796-5_15CrossRef

15.

Flocchini, P., Kranakis, E., Krizanc, D., Santoro, N., Sawchuk, C.: Multiple mobile agent rendezvous in a ring. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 599–608. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24698-5_62CrossRef

16.

Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1–3), 147–168 (2005). https://doi.org/10.1016/j.tcs.2005.01.001MathSciNetCrossRefMATH

17.

Godsil, C., Royle, G.F.: Algebraic Graph Theory. GTM, vol. 207. Springer Science & Business Media, New York (2001). https://doi.org/10.1007/978-1-4613-0163-9CrossRefMATH

18.

Haba, K., Izumi, T., Katayama, Y., Inuzuka, N., Wada, K.: On gathering problem in a ring for 2n autonomous mobile robots. In: Proceedings of the 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), poster (2008)

19.

Izumi, T., Izumi, T., Kamei, S., Ooshita, F.: Mobile robots gathering algorithm with local weak multiplicity in rings. In: Patt-Shamir, B., Ekim, T. (eds.) SIROCCO 2010. LNCS, vol. 6058, pp. 101–113. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13284-1_9CrossRef

20.

Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection. In: Kosowski, A., Yamashita, M. (eds.) SIROCCO 2011. LNCS, vol. 6796, pp. 150–161. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22212-2_14CrossRef

21.

Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Gathering an even number of robots in an odd ring without global multiplicity detection. In: Rovan, B., Sassone, V., Widmayer, P. (eds.) MFCS 2012. LNCS, vol. 7464, pp. 542–553. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32589-2_48CrossRefMATH

22.

Klasing, R., Kosowski, A., Navarra, A.: Taking advantage of symmetries: gathering of many asynchronous oblivious robots on a ring. Theor. Comput. Sci. 411(34–36), 3235–3246 (2010). https://doi.org/10.1016/j.tcs.2010.05.020MathSciNetCrossRefMATH

23.

Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci. 390(1), 27–39 (2008). https://doi.org/10.1016/j.tcs.2007.09.032MathSciNetCrossRefMATH

24.

Koreń, M.: Gathering small number of mobile asynchronous robots on ring. Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne 18, 325–331 (2010)

25.

Kranakis, E., Krizanc, D., Markou, E.: Deterministic symmetric rendezvous with tokens in a synchronous torus. Discrete Appl. Math. 159(9), 896–923 (2011). https://doi.org/10.1016/j.dam.2011.01.020MathSciNetCrossRefMATH

26.

Kranakis, E., Santoro, N., Sawchuk, C., Krizanc, D.: Mobile agent rendezvous in a ring. In: 23rd International Conference on Distributed Computing Systems, ICDCS 2003, Providence, RI, USA, 19–22 May 2003, pp. 592–599 (2003). https://doi.org/10.1109/ICDCS.2003.1203510

27.

Di Luna, G.A., Flocchini, P., Pagli, L., Prencipe, G., Santoro, N., Viglietta, G.: Gathering in dynamic rings. In: Das, S., Tixeuil, S. (eds.) SIROCCO 2017. LNCS, vol. 10641, pp. 339–355. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72050-0_20CrossRef

28.

Marco, G.D., Gargano, L., Kranakis, E., Krizanc, D., Pelc, A., Vaccaro, U.: Asynchronous deterministic rendezvous in graphs. Theor. Comput. Sci. 355(3), 315–326 (2006). https://doi.org/10.1016/j.tcs.2005.12.016MathSciNetCrossRefMATH

29.

Pagli, L., Prencipe, G., Viglietta, G.: Getting close without touching: near-gathering for autonomous mobile robots. Distrib. Comput. 28(5), 333–349 (2015). https://doi.org/10.1007/s00446-015-0248-5MathSciNetCrossRefMATH

30.

Prencipe, G.: Impossibility of gathering by a set of autonomous mobile robots. Theor. Comput. Sci. 384(2–3), 222–231 (2007). https://doi.org/10.1016/j.tcs.2007.04.023MathSciNetCrossRefMATH

31.

Stefano, G.D., Navarra, A.: Gathering of oblivious robots on infinite grids with minimum traveled distance. Inf. Comput. 254, 377–391 (2017). https://doi.org/10.1016/j.ic.2016.09.004MathSciNetCrossRefMATH

32.

Stefano, G.D., Navarra, A.: Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings. Distrib. Comput. 30(2), 75–86 (2017). https://doi.org/10.1007/s00446-016-0278-7MathSciNetCrossRefMATH

33.

Tel, G.: Network orientation. Int. J. Found. Comput. Sci. 5(1), 23–57 (1994). https://doi.org/10.1142/S0129054194000037CrossRefMATH

Title: Optimal Gathering by Asynchronous Oblivious Robots in Hypercubes
Authors: Kaustav Bose
Manash Kumar Kundu
Ranendu Adhikary
Buddhadeb Sau
Publisher: Springer International Publishing
Book: Algorithms for Sensor Systems
Print ISBN: 978-3-030-14093-9

Electronic ISBN: 978-3-030-14094-6

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-14094-6_7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner