Smart Tile Self-Assembly and Replication

• Autorzy: Kari L. , Simjour A.

Identyfikatory

DOI

10.3233/FI-2017-1564

• Języki publikacji: EN

Abstrakty

EN

We propose the concept of self-assembly of smart tiles, i.e., tiles which possess a local computational device in addition to having edge glues that can be activated or deactivated by signals. The local tile computational device can range from its being absent, to being a counter, a simple look-up table, a finite state machine, all the way to being a Turing machine. Thus, this model offers a general framework to discuss and compare various tile self-assembly systems. We demonstrate the potential of self-assembly with smart tiles to efficiently perform robotic tasks such as the replication of convex shapes. The smart tile assembly system that we propose for convex shape replication does not make any assumption on the glues and signals of the interior tiles of the input supertile, and uses a scaffold to assemble a replica adjacent to the input supertile.

Słowa kluczowe

EN

DNA self-assembly systems; signal tile assembly model; smart tiles; robotics

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 239--260
• Opis fizyczny: Bibliogr. 23 poz., rys.

Twórcy

autor

Kari L.

• School of Computer Science, University of Waterloo
• Department of Computer Science, University of Western Ontario, Canada

autor

Simjour A.

• Department of Computer Science, University of Western Ontario, Canada

Bibliografia

• [1] Oh H, Shirazi AR, Sun C, Jin Y. Bio-inspired self-organising multi-robot pattern formation: A review. Robotics and Autonomous Systems, 2017;91:83–100. URL https://doi.org/10.1016/j.robot.2016.12.006.
• [2] Werfel J. Building blocks for multi-robot construction. In: Alami R, Chatila R, Asama H (eds.), Distributed Autonomous Robotic Systems 6. Springer Japan, Tokyo, 2007 pp. 285–294. doi:10.1007/978-4-431-35873-2_28.
• [3] Werfel J. Collective construction with robot swarms. In: Doursat R, Sayama H, Michel O (eds.), Morphogenetic Engineering, Toward Programmable Complex Systems, pp. 115–140. Springer, 2012. doi:10.1007/978-3-642-33902-8_5
• [4] Naz A, Piranda B, Bourgeois J, Goldstein SC. A distributed self-reconfiguration algorithm for cylindrical lattice-based modular robots. In: Pellegrini A, Gkoulalas-Divanis A, di Sanzo P, Avresky DR (eds.), 15th IEEE International Symposium on Network Computing and Applications, NCA 2016. IEEE Computer Society, 2016 pp. 254–263. doi:10.1109/NCA.2016.7778628.
• [5] Rubenstein M, Cornejo A, Nagpal R. Programmable self-assembly in a thousand-robot swarm. Science, 2014;345(6198):795–799. doi:10.1126/science.1254295.
• [6] Gilpin K, Rus D. A distributed algorithm for 2D shape duplication with smart pebble robots. In: Proceedings of IEEE International Conference on Robotics and Automation, ICRA 2012. IEEE, 2012 pp. 3285–3292. doi:10.1109/ICRA.2012.6225227.
• [7] Derakhshandeh Z, Gmyr R, Richa AW, Scheideler C, Strothmann T. Universal shape formation for programmable matter. In: Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, 2016 pp. 289–299. doi:10.1145/2935764.2935784.
• [8] Patitz MJ. An introduction to tile-based self-assembly and a survey of recent results. Natural Computing, 2014;13(2):195–224. doi:10.1007/s11047-013-9379-4.
• [9] Padilla JE, Liu W, Seeman NC. Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced Tile Assembly Model. Natural Computing, 2012;11(2):323–338. doi:10.1007/s11047-011-9268-7.
• [10] Padilla JE, Patitz MJ, Pena R, Schweller RT, Seeman NC, Sheline R, Summers SM, Zhong X. Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes. In: Proceedings UCNC 2013. 2013 pp. 174–185.
• [11] Jonoska N, Karpenko D. Active tile self-assembly, Part 1: universality at temperature 1. International Journal of Foundations of Computer Science, 2014;25(2):141–164. URL https://doi.org/10.1142/S0129054114500087.
• [12] Benenson Y, Gil B, Ben-Dor U, Adar R, Shapiro E. An autonomous molecular computer for logical control of gene expression. Nature, 2004;429(6990):423–429.
• [13] Komiya K, Sakamoto K, Gouzu H, Yokoyama S, Arita M, Nishikawa A, Hagiya M. Successive state transitions with I/O interface by molecules. In: Condon A, Rozenberg G (eds.), 6th International Workshop on DNA-Based Computers, DNA 2000, volume 2054 of Lecture Notes in Computer Science. Springer, 2000 pp. 17–26. doi:10.1007/3-540-44992-2_2.
• [14] Qian L, Winfree E. Scaling up digital circuit computation with DNA strand displacement cascades. Science, 2011;332(6034):1196–1201. doi:10.1126/science.1200520.
• [15] Winfree E. Algorithmic Self-Assembly of DNA. Ph.D. thesis, 1998.
• [16] Keenan A, Schweller RT, Zhong X. Exponential replication of patterns in the signal tile assembly model. Natural Computing, 2015;14(2):265–278. doi:10.1007/s11047-014-9431-z.
• [17] Chalk C, Demaine ED, Demaine ML, Martinez E, Schweller R, Vega L, Wylie T. Universal shape replicators via self-assembly with attractive and repulsive forces. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms, SODA ’17. Philadelphia, PA, USA, 2017 pp. 225–238.
• [18] Hendricks J, Patitz MJ, Rogers TA. Replication of arbitrary hole-free shapes via self-assembly with signalpassing tiles. In: Calude CS, Dinneen MJ (eds.), UCNC 2015, Proceedings, volume 9252 of Lecture Notes in Computer Science. Springer, 2015 pp. 202–214. doi:10.1007/978-3-319-21819-9_15.
• [19] Abel Z, Benbernou N, Damian M, Demaine ED, Demaine ML, Flatland RY, Kominers SD, Schweller RT. Shape replication through self-assembly and RNase enzymes. In: Charikar M (ed.), Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA. SIAM, 2010 pp. 1045–1064. URL https://doi.org/10.1137/1.9781611973075.85.
• [20] Cheng Q, Aggarwal G, Goldwasser MH, Kao MY, Schweller RT, de Espanés PM. Complexities for generalized models of self-Assembly. SIAM Journal on Computing, 2005;34:1493–1515. URL https://doi.org/10.1137/S0097539704445202.
• [21] Demaine ED, Demaine ML, Fekete SP, Ishaque M, Rafalin E, Schweller RT, Souvaine DL. Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues. Natural Computing, 2008;7(3):347–370. doi:10.1007/s11047-008-9073-0.
• [22] Brun Y. Improving efficiency of 3-SAT-solving tile systems. In: Sakakibara Y, Mi Y (eds.), DNA Computing and Molecular Programming, DNA 16, volume 6518 of Lecture Notes in Computer Science. Springer, 2010 pp. 1–12. doi:10.1007/978-3-642-18305-8_1.
• [23] Seki S. Combinatorial optimization in pattern assembly-(Extended Abstract). In: Mauri G, Dennunzio A, Manzoni L, Porreca AE (eds.), UCNC 2013, Proceedings, volume 7956 of Lecture Notes in Computer Science. Springer, 2013 pp. 220–231. doi:10.1007/978-3-642-39074-6_21.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).