nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Computations by Luminous Robots

verfasst von : Paola Flocchini

Erschienen in: Ad-hoc, Mobile, and Wireless Networks

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

The study of computability issues by a system of simple, autonomous, oblivious, mobile robots, operating in the plane in Look-Compute-Move cycles, has been the object of intensive investigations. These robots do not have explicit communication mechanisms, but they implicitly cooperate towards a common goal.

This paper focuses on luminous robots, a recently introduced model where the robots are equipped with a light that can take a constant number of different colors. The light is visible to the observing robots and stays lit from a computation cycle to the next. The availability of lights, which provides little communication and memory, has clearly a great impact on the system of robots. We review the recent results, highlighting the many open problems and research directions.

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 On the Relations Between SINR Diagrams and Voronoi Diagrams

Nächstes Kapitel Online Lower Bounds and Offline Inapproximability in Optical Networks

Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829–879 (2012)MATHMathSciNetCrossRef

Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34, 1516–1528 (2005)MATHMathSciNetCrossRef

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

Das, S., Flocchini, P., Santoro, N., Yamashita, M.: Forming sequences of geometric patterns with oblivious mobile robots. Distrib. Comput. 28(2), 131–145 (2015)MathSciNetCrossRef

Das, S., Flocchini, P., Prencipe, G., Santoro, N.: Synchronized dancing of oblivious chameleons. In: Ferro, A., Luccio, F., Widmayer, P. (eds.) FUN 2014. LNCS, vol. 8496, pp. 113–124. Springer, Heidelberg (2014) CrossRef

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

Dieudonné, Y., Petit, F.: Scatter of weak mobile robots. Parallel Process. Lett. 19(1), 175–184 (2009)MathSciNetCrossRef

Dieudonné, Y., Petit, F.: Self-stabilizing gathering with strong multiplicity detection. Theor. Comput. Sci. 428(13), 47–57 (2012)MATHCrossRef

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, Heidelberg (2014)

10.

Di Luna, G.A., Flocchini, P., Poloni, F., Santoro, N., Viglietta, G.: How oblivious mobile robots can achieve mutual visibility. In: Proceedings of 26th Canadian Computational Geometry Conference (CCCG) (2014)

11.

Di Luna, G.A., Flocchini, P., Gan Chaudhuri, S., Poloni, F., Santoro, N., Viglietta, G.: Mutual visibility by luminous robots without collisions (2015). http://arxiv.org/abs/1503.04347

12.

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

13.

Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Arbitrary pattern formation by asynchronous oblivious robots. Theor. Comput. Sci. 407(1–3), 412–447 (2008)MATHMathSciNetCrossRef

14.

Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1–3), 147–168 (2005)MATHMathSciNetCrossRef

15.

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, Heidelberg (2013) CrossRef

16.

Fujinaga, N., Yamauchi, Y., Kijima, S., Yamashita, M.: Asynchronous pattern formation by anonymous oblivious mobile robots. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 312–325. Springer, Heidelberg (2012) CrossRef

17.

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) CrossRef

18.

Lin, J., Morse, A.S., Anderson, B.D.O.: The multi-agent rendezvous problem. Parts 1 and 2. SIAM J. Control Optim. 46(6), 2096–2147 (2007)MATHMathSciNetCrossRef

19.

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) CrossRef

20.

Prencipe, G.: The effect of synchronicity on the behavior of autonomous mobile robots. Theor. Comput. Syst. 38(5), 539–558 (2005)MATHMathSciNetCrossRef

21.

Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28, 1347–1363 (1999)MATHMathSciNetCrossRef

22.

Vaidyanathan, R., Busch, C., Trahan, J., Sharma, G., Rai, S.: Logarithmic-time complete visibility for robots with lights. In: 29th IEEE International Parallel and Distributed Processing Symposium (IPDPS) (2015)

23.

Viglietta, G.: Rendezvous of two robots with visible bits. In: Flocchini, P., Gao, J., Kranakis, E., der Heide, F.M. (eds.) ALGOSENSORS 2013. LNCS, vol. 8243, pp. 286–301. Springer, Heidelberg (2014) CrossRef

24.

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

Titel: Computations by Luminous Robots
verfasst von: Paola Flocchini
Verlag: Springer International Publishing
Buch: Ad-hoc, Mobile, and Wireless Networks
Print ISBN: 978-3-319-19661-9

Electronic ISBN: 978-3-319-19662-6

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-19662-6_17

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"