Document Open Access Logo

On the Transformation Capability of Feasible Mechanisms for Programmable Matter

Authors Othon Michail, George Skretas, Paul G. Spirakis

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.136.pdf
  • Filesize: 0.5 MB
  • 15 pages

Document Identifiers

Author Details

Othon Michail
George Skretas
Paul G. Spirakis

Cite As Get BibTex

Othon Michail, George Skretas, and Paul G. Spirakis. On the Transformation Capability of Feasible Mechanisms for Programmable Matter. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 136:1-136:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.136

Abstract

In this work, we study theoretical models of programmable matter systems. The systems under consideration consist of spherical modules, kept together by magnetic forces and able to perform two minimal mechanical operations (or movements): rotate around a neighbor and slide over a line. In terms of modeling, there are n nodes arranged in a 2-dimensional grid and forming some initial shape. The goal is for the initial shape A to transform to some target shape B by a sequence of movements. Most of the paper focuses on transformability questions, meaning whether it is in principle feasible to transform a given shape to another. We first consider the case in which only rotation is available to the nodes. Our main result is that deciding whether two given shapes A and B can be transformed to each other is in P. We then insist on rotation only and impose the restriction that the nodes must maintain global connectivity throughout the transformation. We prove that the corresponding transformability question is in PSPACE and study the problem of determining the minimum seeds that can make feasible otherwise infeasible transformations. Next we allow both rotations and slidings and prove universality: any two connected shapes A,B of the same number of nodes, can be transformed to each other without breaking connectivity. The worst-case number of movements of the generic strategy is Theta(n^2). We improve this to O(n) parallel time, by a pipelining strategy, and prove optimality of both by matching lower bounds. We next turn our attention to distributed transformations. The nodes are now distributed processes able to perform communicate-compute-move rounds. We provide distributed algorithms for a general type of transformation.

Subject Classification

Keywords
  • programmable matter
  • transformation
  • reconfigurable robotics
  • shape formation
  • complexity
  • distributed algorithms

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Greg Aloupis, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Robin Flatland, John Iacono, and Stefanie Wuhrer. Efficient reconfiguration of lattice-based modular robots. Computational geometry, 46(8):917-928, 2013. Google Scholar
  2. Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. Computation in networks of passively mobile finite-state sensors. Distributed Computing, 18(4):235-253, March 2006. Google Scholar
  3. Dana Angluin, James Aspnes, David Eisenstat, and Eric Ruppert. The computational power of population protocols. Distributed Computing, 20(4):279-304, November 2007. Google Scholar
  4. Zack Butler, Keith Kotay, Daniela Rus, and Kohji Tomita. Generic decentralized control for lattice-based self-reconfigurable robots. The International Journal of Robotics Research, 23(9):919-937, 2004. Google Scholar
  5. Xuli Chen, Li Li, Xuemei Sun, Yanping Liu, Bin Luo, Changchun Wang, Yuping Bao, Hong Xu, and Huisheng Peng. Magnetochromatic polydiacetylene by incorporation of Fe3O4 nanoparticles. Angewandte Chemie International Edition, 50(24):5486-5489, 2011. Google Scholar
  6. Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Solving the robots gathering problem. In International Colloquium on Automata, Languages, and Programming, pages 1181-1196. Springer, 2003. Google Scholar
  7. Alejandro Cornejo, Fabian Kuhn, Ruy Ley-Wild, and Nancy Lynch. Keeping mobile robot swarms connected. In Proceedings of the 23rd international conference on Distributed computing, DISC'09, pages 496-511, Berlin, Heidelberg, 2009. Springer-Verlag. Google Scholar
  8. Shantanu Das, Paola Flocchini, Nicola Santoro, and Masafumi Yamashita. Forming sequences of geometric patterns with oblivious mobile robots. Distributed Computing, 28(2):131-145, April 2015. Google Scholar
  9. Erik D. Demaine. Playing games with algorithms: Algorithmic combinatorial game theory. In International Symposium on Mathematical Foundations of Computer Science, pages 18-33. Springer, 2001. Google Scholar
  10. Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Brief announcement: amoebot-a new model for programmable matter. In Proceedings of the 26th ACM symposium on Parallelism in algorithms and architectures (SPAA), pages 220-222, 2014. Google Scholar
  11. Zahra Derakhshandeh, Robert Gmyr, Alexandra Porter, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. On the runtime of universal coating for programmable matter. In International Conference on DNA-Based Computers, pages 148-164. Springer, 2016. Google Scholar
  12. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. An algorithmic framework for shape formation problems in self-organizing particle systems. In Proceedings of the Second Annual International Conference on Nanoscale Computing and Communication, page 21. ACM, 2015. Google Scholar
  13. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Universal shape formation for programmable matter. In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, pages 289-299. ACM, 2016. Google Scholar
  14. David Doty. Theory of algorithmic self-assembly. Communications of the ACM, 55:78-88, 2012. Google Scholar
  15. David Doty. Timing in chemical reaction networks. In Proc. of the 25th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pages 772-784, 2014. Google Scholar
  16. Adrian Dumitrescu and János Pach. Pushing squares around. In Proceedings of the twentieth annual symposium on Computational geometry, pages 116-123. ACM, 2004. Google Scholar
  17. Adrian Dumitrescu, Ichiro Suzuki, and Masafumi Yamashita. Formations for fast locomotion of metamorphic robotic systems. The International Journal of Robotics Research, 23(6):583-593, 2004. Google Scholar
  18. Adrian Dumitrescu, Ichiro Suzuki, and Masafumi Yamashita. Motion planning for metamorphic systems: Feasibility, decidability, and distributed reconfiguration. IEEE Transactions on Robotics and Automation, 20(3):409-418, 2004. Google Scholar
  19. Yuval Emek and Jara Uitto. Dynamic networks of finite state machines. In International Colloquium on Structural Information and Communication Complexity, pages 19-34. Springer, 2016. Google Scholar
  20. Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed computing by oblivious mobile robots. Synthesis lectures on distributed computing theory, 3(2):1-185, 2012. Google Scholar
  21. Kyle Gilpin, Ara Knaian, and Daniela Rus. Robot pebbles: One centimeter modules for programmable matter through self-disassembly. In Robotics and Automation (ICRA), 2010 IEEE International Conference on, pages 2485-2492. IEEE, 2010. Google Scholar
  22. Robert A. Hearn and Erik D. Demaine. PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoretical Computer Science, 343(1-2):72-96, 2005. Google Scholar
  23. Ara N. Knaian, Kenneth C. Cheung, Maxim B. Lobovsky, Asa J. Oines, Peter Schmidt-Neilsen, and Neil A. Gershenfeld. The milli-motein: A self-folding chain of programmable matter with a one centimeter module pitch. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 1447-1453. IEEE, 2012. Google Scholar
  24. Evangelos Kranakis, Danny Krizanc, and Euripides Markou. The mobile agent rendezvous problem in the ring. Synthesis Lectures on Distributed Computing Theory, 1(1):1-122, 2010. Google Scholar
  25. Yunfeng Lu, Yi Yang, Alan Sellinger, Mengcheng Lu, Jinman Huang, Hongyou Fan, Raid Haddad, Gabriel Lopez, Alan R. Burns, Darryl Y. Sasaki, John Shelnutt, and C. Jeffrey Brinker. Self-assembly of mesoscopically ordered chromatic polydiacetylene/silica nanocomposites. Nature, 410(6831):913-917, 2001. Google Scholar
  26. Othon Michail and Paul G. Spirakis. Simple and efficient local codes for distributed stable network construction. Distributed Computing, 29(3):207-237, 2016. URL: http://dx.doi.org/10.1007/s00446-015-0257-4.
  27. Othon Michail and Paul G. Spirakis. Elements of the theory of dynamic networks. Communications of the ACM, 2017. Accepted: 6th April 2017, To appear. Google Scholar
  28. Paul W. K. Rothemund. Folding DNA to create nanoscale shapes and patterns. Nature, 440(7082):297-302, 2006. Google Scholar
  29. Paul W. K. Rothemund and Erik Winfree. The program-size complexity of self-assembled squares. In Proceedings of the 32nd annual ACM symposium on Theory of computing (STOC), pages 459-468, 2000. URL: http://dx.doi.org/10.1145/335305.335358.
  30. Michael Rubenstein, Alejandro Cornejo, and Radhika Nagpal. Programmable self-assembly in a thousand-robot swarm. Science, 345(6198):795-799, 2014. Google Scholar
  31. Masahiro Shibata, Toshiya Mega, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Uniform deployment of mobile agents in asynchronous rings. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 415-424. ACM, 2016. Google Scholar
  32. Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. Comput., 28(4):1347-1363, March 1999. URL: http://dx.doi.org/10.1137/S009753979628292X.
  33. Erik Winfree. Algorithmic Self-Assembly of DNA. PhD thesis, California Institute of Technology, June 1998. Google Scholar
  34. Damien Woods, Ho-Lin Chen, Scott Goodfriend, Nadine Dabby, Erik Winfree, and Peng Yin. Active self-assembly of algorithmic shapes and patterns in polylogarithmic time. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 353-354. ACM, 2013. Google Scholar
  35. Yukiko Yamauchi, Taichi Uehara, and Masafumi Yamashita. Brief announcement: pattern formation problem for synchronous mobile robots in the three dimensional euclidean space. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 447-449. ACM, 2016. Google Scholar
  36. Mark Yim, Wei-Min Shen, Behnam Salemi, Daniela Rus, Mark Moll, Hod Lipson, Eric Klavins, and Gregory S. Chirikjian. Modular self-reconfigurable robot systems [grand challenges of robotics]. IEEE Robotics &Automation Magazine, 14(1):43-52, 2007. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact