nach oben

Erschienen in:

2015 | OriginalPaper | Buchkapitel

Leader Election and Shape Formation with Self-organizing Programmable Matter

verfasst von : Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida Bazzi, Andréa W. Richa, Christian Scheideler

Erschienen in: DNA Computing and Molecular Programming

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

In this paper we consider programmable matter consisting of simple computational elements, called particles, that can establish and release bonds and can actively move in a self-organized way, and we investigate the feasibility of solving fundamental problems relevant for programmable matter. As a model for such self-organizing particle systems, we will use a generalization of the geometric amoebot model first proposed in [21]. Based on the geometric model, we present efficient local-control algorithms for leader election and line formation requiring only particles with constant size memory, and we also discuss the limitations of solving these problems within the general amoebot model.

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 New Geometric Algorithms for Fully Connected Staged Self-Assembly

Nächstes Kapitel Leakless DNA Strand Displacement Systems

For a simulation video of the Line Formation Algorithm please see http://sops.cs.upb.de.

Adleman, L.M.: Molecular computation of solutions to combinatorial problems. Science 266(11), 1021–1024 (1994)CrossRef

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)

Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M.J., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235–253 (2006)CrossRef

Arbuckle, D., Requicha, A.: Self-assembly and self-repair of arbitrary shapes by a swarm of reactive robots: algorithms and simulations. Auton. Robots 28(2), 197–211 (2010)CrossRef

Awerbuch, B., Ostrovsky, R.: Memory-efficient and self-stabilizing network RESET (extended abstract). In: Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 254–263 (1994)

Barriere, L., Flocchini, P., Mesa-Barrameda, E., Santoro, N.: Uniform scattering of autonomous mobile robots in a grid. Int. J. Found. Comput. Sci. 22(3), 679–697 (2011)MathSciNetCrossRef

Bhattacharyya, A., Braverman, M., Chazelle, B., Nguyen, H.L.: On the convergence of the hegselmann-krause system. In: Proceedings of the 4th Innovations in Theoretical Computer Science (ITCS), pp. 61–66 (2013)

Boneh, D., Dunworth, C., Lipton, R.J., Sgall, J.: On the computational power of DNA. Discrete Appl. Math. 71, 79–94 (1996)MathSciNetCrossRef

Bonifaci, V., Mehlhorn, K., Varma, G.: Physarum can compute shortest paths. In: Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 233–240 (2012)

10.

Butler, Z.J., Kotay, K., Rus, D., Tomita, K.: Generic decentralized control for lattice-based self-reconfigurable robots. Int. J. Robot. Res. 23(9), 919–937 (2004)CrossRef

11.

B. Chazelle. Natural algorithms. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 422–431 (2009)

12.

Chen, H.-L., Doty, D., Holden, D., Thachuk, C., Woods, D., Yang, C.-T.: Fast algorithmic self-assembly of simple shapes using random agitation. In: Murata, S., Kobayashi, S. (eds.) DNA 2014. LNCS, vol. 8727, pp. 20–36. Springer, Heidelberg (2014)

13.

Chen, M., Xin, D., Woods, D.: Parallel computation using active self-assembly. In: Soloveichik, D., Yurke, B. (eds.) DNA 2013. LNCS, vol. 8141, pp. 16–30. Springer, Heidelberg (2013) CrossRef

14.

Cheung, K.C., Demaine, E.D., Bachrach, J.R., Griffith, S.: Programmable assembly with universally foldable strings (moteins). IEEE Trans. Robot. 27(4), 718–729 (2011)CrossRef

15.

Chirikjian, G.: Kinematics of a metamorphic robotic system. In: Proceedings of the 1994 International Conference on Robotics and Automation (ICRA), pp. 449–455 (1994)

16.

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

17.

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

18.

Das, S., Flocchini, P., Santoro, N., Yamashita, M.: On the computational power of oblivious robots: forming a series of geometric patterns. In: Proceedings of 29th ACM Symposium on Principles of Distributed Computing (PODC) (2010)

19.

Defago, X., Souissi, S.: Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity. Theor. Comput. Sci. 396(1–3), 97–112 (2008)MathSciNetCrossRef

20.

Demaine, E.D., Patitz, M.J., Schweller, R.T., Summers, S.M.: Self-assembly of arbitrary shapes using rnase enzymes: meeting the kolmogorov bound with small scale factor (extended abstract). In: Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, pp. 201–212 (2011)

21.

Derakhshandeh, Z., Dolev, S., Gmyr, R., Richa, A., Scheideler, C., Strothmann, T.: Brief announcement: amoebot – a new model for programmable matter. In: Proceedings of the 26th ACM Symposium on Parallelism in Algorithms and Architectures, (SPAA), pp. 220–222 (2014)

22.

Doty, D.: Theory of algorithmic self-assembly. Commun. ACM 55(12), 78–88 (2012)CrossRef

23.

Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Computing without communicating: ring exploration by asynchronous oblivious robots. Algorithmica 65(3), 562–583 (2013)MathSciNetCrossRef

24.

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

25.

Fukuda, T., Nakagawa, S., Kawauchi, Y., Buss, M.: Self organizing robots based on cell structures - cebot. In: Proceedings of the International Conference on Intelligent Robots and Systems, (IROS), pp. 145–150 (1988)

26.

Hendricks, J., Patitz, M.J., Rogers, T.A.: Replication of arbitrary hole-free shapes via self-assembly with signal-passing tiles (2015). arXiv preprint arXiv:1503.01244

27.

Hsiang, T.-R., Arkin, E., Bender, M., Fekete, S., Mitchell, J.: Algorithms for rapidly dispersing robot swarms in unknown environments. In: Proceedings of the 5th Workshop on Algorithmic Foundations of Robotics (WAFR), pp. 77–94 (2002)

28.

Itai, A., Rodeh, M.: Symmetry breaking in distributive networks. In: 22nd Annual Symposium on Foundations of Computer Science, (FOCS), pp. 150–158 (1981)

29.

Itkis, G., Levin, L.: Fast and lean self-stabilizing asynchronous protocols. In: 35th Annual Symposium on Foundations of Computer Science, (FOCS), pp. 226–239 (1994)

30.

Kernbach, S. (ed.): Handbook of Collective Robotics - Fundamentals and Challanges. Pan Stanford Publishing, Singapore (2012)

31.

Kling, P., Meyer auf der Heide, F.: Convergence of local communication chain strategies via linear transformations. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures, (SPAA), pp. 159–166 (2011)

32.

Li, K., Thomas, K., Torres, C., Rossi, L., Shen, C.-C.: Slime mold inspired path formation protocol for wireless sensor networks. In: Dorigo, M., Birattari, M., Di Caro, G.A., Doursat, R., Engelbrecht, A.P., Floreano, D., Gambardella, L.M., Groß, R., Şahin, E., Sayama, H., Stützle, T. (eds.) ANTS 2010. LNCS, vol. 6234, pp. 299–311. Springer, Heidelberg (2010) CrossRef

33.

McLurkin, J.: Analysis and implementation of distributed algorithms for multi-robot systems. Ph.D. thesis, Massachusetts Institute of Technology (2008)

34.

Patitz, M.J.: An introduction to tile-based self-assembly and a survey of recent results. Nat. Comput. 13(2), 195–224 (2014)MathSciNetCrossRef

35.

Rubenstein, M., Cornejo, A., Nagpal, R.: Programmable self-assembly in a thousand-robot swarm. Science 345(6198), 795–799 (2014)CrossRef

36.

Walter, J.E., Welch, J.L., Amato, N.M.: Distributed reconfiguration of metamorphic robot chains. Distrib. Comput. 17(2), 171–189 (2004)CrossRef

37.

Winfree, E., Liu, F., Wenzler, L.A., Seeman, N.C.: Design and self-assembly of two-dimensional dna crystals. Nature 394(6693), 539–544 (1998)CrossRef

38.

Woods, D.: Intrinsic universality and the computational power of self-assembly. In: Neary, T., Cook, M. (eds) Proceedings of the 6th Conference on Machines, Computations and Universality 2013, (MCU), EPTCS, vol. 128, pp. 16–22 (2013)

39.

Woods, D., Chen, H., Goodfriend, S., Dabby, N., Winfree, E., Yin, P.: Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS, pp. 353–354 (2013)

40.

Yim, M., Shen, W.-M., Salemi, B., Rus, D., Moll, M., Lipson, H., Klavins, E., Chirikjian, G.S.: Modular self-reconfigurable robot systems. IEEE Robot. Autom. Mag. 14(1), 43–52 (2007)CrossRef

Titel: Leader Election and Shape Formation with Self-organizing Programmable Matter
verfasst von: Zahra Derakhshandeh
Robert Gmyr
Thim Strothmann
Rida Bazzi
Andréa W. Richa
Christian Scheideler
Verlag: Springer International Publishing
Buch: DNA Computing and Molecular Programming
Print ISBN: 978-3-319-21998-1

Electronic ISBN: 978-3-319-21999-8

Copyright-Jahr: 2015
DOI: https://doi.org/10.1007/978-3-319-21999-8_8

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"