nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Optimum Algorithm for Mutual Visibility Among Asynchronous Robots with Lights

verfasst von : Subhash Bhagat, Krishnendu Mukhopadhyaya

Erschienen in: Stabilization, Safety, and Security of Distributed Systems

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

This paper addresses the constrained version of the mutual visibility problem for a set of asynchronous, opaque robots in the Euclidean plane. The mutual visibility problem asks the robots to form a configuration, within finite time and without collision, in which no three robots are collinear. The constrained mutual visibility problem in addition aims to minimize the maximum number of movements by a single robot. One of the implications of this constrained version of mutual visibility problem is that it also addresses issue of energy efficiency. The robots have a constant amount of persistent memory and they are equipped with externally visible lights which can assume a constant number of predefined colors. The colors represent different states of the robots and are used both for internal memory and communication. The colors of the lights do not change automatically. A distributed algorithm is proposed to solve the constrained mutual visibility problem for a set of asynchronous robots using only seven colors. The proposed algorithm does not impose any other restriction on the capability of the robots and guarantees collision-free movements for the robots.

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 Universally Optimal Gathering Under Limited Visibility

Nächstes Kapitel Brief Announcement: ZeroBlock: Timestamp-Free Prevention of Block-Withholding Attack in Bitcoin

Défago, X., Gradinariu, M., Messika, S., Raipin-Parvédy, P.: Fault-tolerant and self-stabilizing mobile robots gathering. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 46–60. Springer, Heidelberg (2006). doi:10.1007/11864219_4CrossRef

Agathangelou, C., Georgiou, C., Mavronicolas, M.: A distributed algorithm for gathering many fat mobile robots in the plane. In: Proceedings of the 32nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 250–259 (2013)

Di Luna, G.A., Flocchini, P., Poloni, F., Santoro, N., Viglietta, G.: The mutual visibility problem for oblivious robots. In: Proceedings of 26th Canadian Conference on Computational Geometry (CCCG 2014) (2014)

Ando, H., Oasa, Y., Suzuki, I., Yamashita, M.: Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. Robot. Autom. 15, 818–828 (1999)CrossRef

Bolla, K., Kovacs, T., Fazekas, G.: Gathering of fat robots with limited visibility and without global navigation. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., Zurada, J.M. (eds.) EC/SIDE -2012. LNCS, vol. 7269, pp. 30–38. Springer, Heidelberg (2012). doi:10.1007/978-3-642-29353-5_4CrossRef

Cohen, R., Peleg, D.: Local spreading algorithms for autonomous robot systems. Theoret. Comput. Sci. 399, 71–82 (2008)MathSciNetCrossRef

Czyzowicz, J., Gasieniec, L., Pelc, A.: Gathering few fat mobile robots in the plane. Theoret. Comput. Sci. 410(6–7), 481–499 (2009)MathSciNetCrossRef

Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: The power of lights: synchronizing asynchronous robots using visible bits. In: Proceedings of the 32nd International Conference on Distributed Computing Systems (ICDCS), pp. 506–515 (2012)

Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: Synchronized dancing of oblivious chameleons. In: Ferro, A., Luccio, F., Widmayer, P. (eds.) FUN 2014. LNCS, vol. 8496, pp. 113–124. Springer, Heidelberg (2014). doi:10.1007/978-3-319-07890-8_10CrossRef

10.

Bhagat, S., Gan Chaudhuri, S., Mukhopadhyaya, K.: Formation of general position by asynchronous mobile robots under one-axis agreement. In: Kaykobad, M., Petreschi, R. (eds.) WALCOM 2016. LNCS, vol. 9627, pp. 80–91. Springer, Cham (2016). doi:10.1007/978-3-319-30139-6_7CrossRef

11.

Vaidyanathan, R., Busch, C., Trahan, J.L., Sharma, G., Rai, S.: Logarithmic-time complete visibility for robots with lights. In: Proceedings of Parallel and Distributed Processing Symposium (IPDPS), pp. 375–384 (2015)

12.

Sharma, G., Vaidyanathan, R., Trahan, J.L., Busch, C., Rai, S.: O(log N)-time complete visibility for asynchronous robots with lights. In: Proceedings of Parallel and Distributed Processing Symposium (IPDPS), pp. 513–522 (2017)

13.

Sharma, G., Vaidyanathan, R., Trahan, J.L., Busch, C., Rai, S.: Complete visibility for robots with lights in O(1) time. In: Bonakdarpour, B., Petit, F. (eds.) SSS 2016. LNCS, vol. 10083, pp. 327–345. Springer, Cham (2016). doi:10.1007/978-3-319-49259-9_26CrossRef

14.

Efrima, A., Peleg, D.: Distributed models and algorithms for mobile robot systems. In: Leeuwen, J., Italiano, G.F., Hoek, W., Meinel, C., Sack, H., Plášil, F. (eds.) SOFSEM 2007. LNCS, vol. 4362, pp. 70–87. Springer, Heidelberg (2007). doi:10.1007/978-3-540-69507-3_5CrossRefMATH

15.

Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Morgan & Claypool, San Rafael (2012)CrossRef

16.

Flocchini, P., Santoro, N., Viglietta, G., Yamashita, M.: Rendezvous of two robots with constant memory. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol. 8179, pp. 189–200. Springer, Cham (2013). doi:10.1007/978-3-319-03578-9_16CrossRef

17.

Peleg, D.: Distributed coordination algorithms for mobile robot swarms: new directions and challenges. In: Pal, A., Kshemkalyani, A.D., Kumar, R., Gupta, A. (eds.) IWDC 2005. LNCS, vol. 3741, pp. 1–12. Springer, Heidelberg (2005). doi:10.1007/11603771_1CrossRef

18.

Sharma, G., Busch, C., Mukhopadhyay, S.: Mutual visibility with an optimal number of colors. In: Bose, P., Gąsieniec, L.A., Römer, K., Wattenhofer, R. (eds.) ALGOSENSORS 2015. LNCS, vol. 9536, pp. 196–210. Springer, Cham (2015). doi:10.1007/978-3-319-28472-9_15CrossRef

19.

Sharma, G., Busch, C., Mukhopadhyay, S.: Bounds on mutual visibility algorithms. In: Proceedings of 27th Canadian Conference on Computational Geometry (CCCG 2015) (2015)

20.

Di Luna, G.A., Flocchini, P., Gan Chaudhuri, S., Poloni, F., Santoro, N., Viglietta, G.: Mutual visibility by luminous robots without collisions. Inf. Comput. 254, 392–418 (2017)MathSciNetCrossRef

21.

Bhagat, S., Gan Chaudhuri, S., Mukhopadhyaya, K.: Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement. J. Discrete Algorithms 36, 50–62 (2016)MathSciNetCrossRef

22.

Viglietta, G.: Rendezvous of two robots with visible bits. In: Flocchini, P., Gao, J., Kranakis, E., Meyer auf der Heide, F. (eds.) ALGOSENSORS 2013. LNCS, vol. 8243, pp. 291–306. Springer, Heidelberg (2014). doi:10.1007/978-3-642-45346-5_21CrossRef

Titel: Optimum Algorithm for Mutual Visibility Among Asynchronous Robots with Lights
verfasst von: Subhash Bhagat
Krishnendu Mukhopadhyaya
Verlag: Springer International Publishing
Buch: Stabilization, Safety, and Security of Distributed Systems
Print ISBN: 978-3-319-69083-4

Electronic ISBN: 978-3-319-69084-1

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-69084-1_24

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