nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Connected Reconfiguration of Lattice-Based Cellular Structures by Finite-Memory Robots

verfasst von : Sándor P. Fekete, Eike Niehs, Christian Scheffer, Arne Schmidt

Erschienen in: Algorithms for Sensor 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 provide algorithmic methods for reconfiguration of lattice-based cellular structures by finite-state robots, motivated by large-scale constructions in space. We present algorithms that are able to detect and reconfigure arbitrary polyominoes, while also preserving connectivity of a structure during reconfiguration; we also provide mathematical proofs and performance guarantees. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.

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 VectorTSP: A Traveling Salesperson Problem with Racetrack-Like Acceleration Constraints

Nächstes Kapitel On Efficient Connectivity-Preserving Transformations in a Grid

Abdel-Rahman, A., et al.: Space ants: constructing and reconfiguring large-scale structures with finite automata. In: Symposium on Computational Geometry (SoCG), pp. 73:1–73:7 (2020). https://www.ibr.cs.tu-bs.de/users/fekete/Videos/SoCG/2020/Space_final.mp4

Bender, M.A., Slonim, D.K.: The power of team exploration: two robots can learn unlabeled directed graphs. In: Symposium on Foundations of Computer Science (FOCS), pp. 75–85 (1994)

Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: Symposium on Foundations of Computer Science (FOCS), pp. 132–142 (1978)

Brass, P., Cabrera-Mora, F., Gasparri, A., Xiao, J.: Multirobot tree and graph exploration. IEEE Trans. Robot. 27(4), 707–717 (2011)CrossRef

Czyzowicz, J., Dobrev, S., Gasieniec, L., Ilcinkas, D., Jansson, J., Klasing, R., Lignos, I., Martin, R., Sadakane, K., Sung, W.-K.: More efficient periodic traversal in anonymous undirected graphs. Theor. Comput. Sci. 444, 60–76 (2012)MathSciNetCrossRef

D’Angelo, G., D’Emidio, M., Das, S., Navarra, A., Prencipe, G.: Leader election and compaction for asynchronous silent programmable matter. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pp. 276–284 (2020)

Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theor. Comput. Sci. 385(1), 34–48 (2007)MathSciNetCrossRef

Daymude, J.J., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Improved leader election for self-organizing programmable matter. In: Fernández Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 127–140. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72751-6_10CrossRef

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

10.

Derakhshandeh, Z., Gmyr, R., Porter, A., Richa, A.W., Scheideler, C., Strothmann, T.: On the runtime of universal coating for programmable matter. In: Rondelez, Y., Woods, D. (eds.) DNA 2016. LNCS, vol. 9818, pp. 148–164. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-43994-5_10CrossRef

11.

Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: An algorithmic framework for shape formation problems in self-organizing particle systems. In: International Conference on Nanoscale Computing and Communication (NANOCOM), pp. 21:1–21:2 (2015)

12.

Derakhshandeh, Z., Gmyr, R., Richa, A.W., Scheideler, C., Strothmann, T.: Universal coating for programmable matter. Theor. Comput. Sci. 671, 56–68 (2017)MathSciNetCrossRef

13.

Derakhshandeh, Z., Gmyr, R., Strothmann, T., Bazzi, R., Richa, A.W., Scheideler, C.: Leader election and shape formation with self-organizing programmable matter. In: International Conference on DNA Computing and Molecular Programming (DNA), pp. 117–132 (2015)

14.

Di Luna, G.A., Flocchini, P., Santoro, N., Viglietta, G., Yamauchi, Y.: Shape formation by programmable particles. Distrib. Comput. 33(1), 69–101 (2019). https://doi.org/10.1007/s00446-019-00350-6MathSciNetCrossRefMATH

15.

Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. J. Algorithms 51(1), 38–63 (2004)MathSciNetCrossRef

16.

Fekete, S.P., Gmyr, R., Hugo, S., Keldenich, P., Scheffer, C., Schmidt, A.: CADbots: algorithmic aspects of manipulating programmable matter with finite automata. In: Morales, M., Tapia, L., Sánchez-Ante, G., Hutchinson, S. (eds.) WAFR 2018. SPAR, vol. 14, pp. 727–743. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-44051-0_42CrossRef

17.

Fekete, S.P., Niehs, E., Scheffer, C., Schmidt, A.: Connected assembly and reconfiguration by finite automata. CoRR (2019)

18.

Fleischer, R., Trippen, G.: Exploring an unknown graph efficiently. In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol. 3669, pp. 11–22. Springer, Heidelberg (2005). https://doi.org/10.1007/11561071_4CrossRef

19.

Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3), 166–177 (2006)MathSciNetCrossRef

20.

Fraigniaud, P., Ilcinkas, D.: Digraphs exploration with little memory. In: Symposium on Theoretical Aspects of Computer Science (STACS), pp. 246–257 (2004)

21.

Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theor. Comput. Sci. 345(2–3), 331–344 (2005)MathSciNetCrossRef

22.

Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 585–594 (2007)

23.

Gąsieniec, L., Radzik, T.: Memory efficient anonymous graph exploration. In: Broersma, H., Erlebach, T., Friedetzky, T., Paulusma, D. (eds.) WG 2008. LNCS, vol. 5344, pp. 14–29. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92248-3_2CrossRefMATH

24.

Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C.: Shape recognition by a finite automaton robot. In: International Symposium on Mathematical Foundations of Computer Science (MFCS), pp. 52:1–52:15 (2018)

25.

Gmyr, R., Hinnenthal, K., Kostitsyna, I., Kuhn, F., Rudolph, D., Scheideler, C., Strothmann, T.: Forming tile shapes with simple robots. In: International Conference on DNA Computing and Molecular Programming (DNA), pp. 122–138 (2018)

26.

Gmyr, R., Kostitsyna, I., Kuhn, F., Scheideler, C., Strothmann, T.: Forming tile shapes with a single robot. In: European Workshop on Computational Geometry (EuroCG), pp. 9–12 (2017)

27.

Gregg, C.E., Jenett, B., Cheung, K.C.: Assembled, modular hardware architectures - what price reconfigurability? In: IEEE Aerospace Conference, pp. 1–10 (2019)

28.

Gregg, C.E., Kim, J.H., Cheung, K.C.: Ultra-light and scalable composite lattice materials. Adv. Eng. Mater. 20(9), 1800213 (2018)CrossRef

29.

Hurtado, F., Molina, E., Ramaswami, S., Sacristán, V.: Distributed reconfiguration of 2D lattice-based modular robotic systems. Auton. Robots 38(4), 383–413 (2015). https://doi.org/10.1007/s10514-015-9421-8CrossRef

30.

Jenett, B., Cellucci, D.: A mobile robot for locomotion through a 3D periodic lattice environment. In: IEEE International Conference on Robotics and Automation (ICRA), pp. 5474–5479 (2017)

31.

Jenett, B., Cellucci, D., Gregg, C., Cheung, K.: Meso-scale digital materials: modular, reconfigurable, lattice-based structures. In: ASME International Manufacturing Science and Engineering Conference (MSEC) (2016)

32.

Jenett, B., Cheung, K.: BILL-E: robotic platform for locomotion and manipulation of lightweight space structures. In: AIAA/AHS Adaptive Structures Conference, p. 1876 (2017)

33.

Kosowski, A., Navarra, A.: Graph decomposition for memoryless periodic exploration. Algorithmica 63(1–2), 26–38 (2012)MathSciNetCrossRef

34.

Niehs, E., et al.: Recognition and reconfiguration of lattice-based cellular structures by simple robots. In: IEEE International Conference on Robotics and Automation (ICRA) (2020, to appear). https://www.ibr.cs.tu-bs.de/users/fekete/hp/publications/PDF/2020-Automata_ICRA.pdf

35.

Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33(2), 281–295 (1999)MathSciNetCrossRef

36.

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

Titel: Connected Reconfiguration of Lattice-Based Cellular Structures by Finite-Memory Robots
verfasst von: Sándor P. Fekete
Eike Niehs
Christian Scheffer
Arne Schmidt
Verlag: Springer International Publishing
Buch: Algorithms for Sensor Systems
Print ISBN: 978-3-030-62400-2

Electronic ISBN: 978-3-030-62401-9

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-62401-9_5

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"