nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Constant-Time Complete Visibility for Asynchronous Robots with Lights

verfasst von : Gokarna Sharma, Ramachandran Vaidyanathan, Jerry L. Trahan

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

We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move cycles and communicate with other robots using colored lights following the robots with lights model. We study the fundamental Complete Visibility problem of repositioning N autonomous robots on a plane so that each robot is visible to all others in this model. We assume obstructed visibility where a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. There exists an \(\mathcal{O}(\log N)\) time, \(\mathcal{O}(1)\) color algorithm for this problem in the asynchronous setting. In this paper, we provide the first, asymptotically optimal, \(\mathcal{O}(1)\) time, \(\mathcal{O}(1)\) color algorithm for this problem in the asynchronous setting. The proposed algorithm is collision-free – robots do not share positions and their paths do not cross. We also introduce a technique, called Beacon-Directed Curve Positioning, for moving robots in an asynchronous setting, that may be of independent interest.

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 A Self-stabilizing General De Bruijn Graph

Nächstes Kapitel On Security Analysis of Proof-of-Elapsed-Time (PoET)

The simulation technique of Das et al. [7] shows that any algorithm (for any problem) in the robots with lights model with \(k>1\) colors in the semi-synchronous setting can be simulated in the asynchronous setting with 5k colors (without a time bound on the simulation).

Agathangelou, C., Georgiou, C., Mavronicolas, M.: A distributed algorithm for gathering many fat mobile robots in the plane. In: PODC, pp. 250–259 (2013)

Ando, H., Suzuki, I., Yamashita, M.: Formation and agreement problems for synchronous mobile robots with limited visibility. In: ISIC, pp. 453–460 (1995)

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

Cord-Landwehr, A., et al.: A new approach for analyzing convergence algorithms for mobile robots. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 650–661. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22012-8_52CrossRef

Cord-Landwehr, A., Fischer, M., Jung, D., auf der Heide, F.M.: Asymptotically optimal gathering on a grid. In: SPAA, pp. 301–312 (2016)

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

Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: Autonomous mobile robots with lights. Theor. Comput. Sci. 609, 171–184 (2016)MathSciNetCrossRef

Degener, B., Kempkes, B., Langner, T., auf der Heide, F.M., Pietrzyk, P., Wattenhofer, R.: A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. In: SPAA, pp. 139–148 (2011)

D’Emidio, M., Frigioni, D., Navarra, A.: Characterizing the computational power of anonymous mobile robots. In: ICDCS, pp. 293–302 (2016)

10.

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

11.

Di Luna, G.A., Flocchini, P., Gan Chaudhuri, S., Santoro, N., Viglietta, G.: Robots with lights: overcoming obstructed visibility without colliding. In: Felber, P., Garg, V. (eds.) SSS 2014. LNCS, vol. 8756, pp. 150–164. Springer, Cham (2014). doi:10.1007/978-3-319-11764-5_11CrossRef

12.

Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by oblivious mobile robots. Synth. Lect. Distrib. Comput. Theory 3(2), 1–185 (2012)CrossRef

13.

Izumi, T., Potop-Butucaru, M.G., Tixeuil, S.: Connectivity-preserving scattering of mobile robots with limited visibility. In: Dolev, S., Cobb, J., Fischer, M., Yung, M. (eds.) SSS 2010. LNCS, vol. 6366, pp. 319–331. Springer, Heidelberg (2010). doi:10.1007/978-3-642-16023-3_27CrossRef

14.

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

15.

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

16.

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

17.

Sharma, G., Vaidyanathan, R., Trahan, J.L., Busch, C., Rai, S.: Logarithmic-time complete visibility for asynchronous robots with lights. In: IPDPS, pp. 513–522 (2017)

18.

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

19.

Yamashita, M., Suzuki, I.: Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theor. Comput. Sci. 411(26–28), 2433–2453 (2010)MathSciNetCrossRef

Titel: Constant-Time Complete Visibility for Asynchronous Robots with Lights
verfasst von: Gokarna Sharma
Ramachandran Vaidyanathan
Jerry L. Trahan
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_18

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