Evolutionary optimization of self-assembly in a swarm of bio-micro-robots

ABSTRACT

This paper deals with the programmability of a swarm of bio-micro-robots in order to display self-assembling behaviors into specific shapes. We consider robots that are DNA-functionalized micro-beads capable of sensing and expressing signals as well as self-assembling. We describe an in vitro experimentation with a million of micro-beads conditionally aggregating into clusters. Using a realistic simulation, we then address the question of how to automatically design the reaction networks that define the micro-robots' behavior, to self-assemble into a specific shape at a specific location. We use bioNEAT, an instantiation of the famous NEAT algorithm capable of handling chemical reaction networks, and CMA-ES to optimize the behavior of each micro-bead. As in swarm robotics, each micro-bead shares the same behavioral rules and the general outcome depends on interactions between neighbors and with the environment. Results obtained on four different target functions show that solutions optimized with evolutionary algorithms display efficient self-assembling behaviors, improving over pure hand-designed networks provided by an expert after a week-long trials and errors search. In addition, we show that evolved solutions are able to self-repair after damage, which is a critical property for smart materials.

References

1. M Rubenstein, A Cornejo, and R Nagpal. Programmable self-assembly in a thousand-robot swarm. Science, 345(6198):795--799, 2014.
2. R O'Grady, AL Christensen, and M Dorigo. Swarmorph: multirobot morphogenesis using directional self-assembly. IEEE Transactions on Robotics, 25(3):738--743, 2009.
3. E Tuci, R Groß, V Trianni, F Mondada, M Bonani, and M Dorigo. Cooperation through self-assembly in multi-robot systems. ACM Transactions on Autonomous and Adaptive Systems (TAAS), 1(2):115--150, 2006.
4. R Groß, M Bonani, F Mondada, and M Dorigo. Autonomous self-assembly in swarm-bots. IEEE transactions on robotics, 22(6):1115--1130, 2006.
5. R Groß and M Dorigo. Self-assembly at the macroscopic scale. Proceedings of the IEEE, 96(9):1490--1508, 2008.
6. N Aubert, C Mosca, T Fujii, M Hagiya, and Y Rondelez. Computer-assisted design for scaling up systems based on dna reaction networks. Journal of The Royal Society Interface, 11(93):20131167, 2014.
7. K O Stanley and R Miikkulainen. Evolving neural networks through augmenting topologies. Evolutionary computation, 10(2):99--127, 2002.
8. N Hansen. The CMA evolution strategy: a comparing review. In Towards a new evolutionary computation, pages 75--102. Springer, 2006.
9. L M Adleman. Molecular computation of solutions to combinatorial problems. Science, 266(5187):1021--1024, 1994.
10. L Qian and E Winfree. Scaling up digital circuit computation with DNA strand displacement cascades. Science, 332(6034):1196--1201, 2011.
11. L Qian, E Winfree, and J Bruck. Neural network computation with DNA strand displacement cascades. Nature, 475(7356):368--372, 2011.
12. N C Seeman. Dna in a material world. Nature, 421(6921):427--431, 2003.
13. A Padirac, T Fujii, and Y Rondelez. Bottom-up construction of in vitro switchable memories. Proceedings of the National Academy of Sciences, 109(47):E3212--E3220, 2012.
14. A Padirac, T Fujii, A Estevez-Torres, and Y Rondelez. Spatial waves in synthetic biochemical networks. Journal of the American Chemical Society, 135(39):14586--14592, 2013.
15. K Montagne, R Plasson, Y Sakai, T Fujii, and Y Rondelez. Programming an in vitro dna oscillator using a molecular networking strategy. Molecular systems biology, 7(1):466, 2011.
16. M Hagiya, N Aubert-Kato, S Wang, and S Kobayashi. Molecular computers for molecular robots as hybrid systems. Theoretical Computer Science, 632:4--20, 2016.
17. G Gines, A Zadorin, JC Galas, Teruo Fujii, A Estevez-Torres, and Y Rondelez. Microscopic agents programmed by dna circuits. Nature Nanotechnology, advance online publication, 2017.
18. W Benjamin Rogers and Vinothan N Manoharan. Programming colloidal phase transitions with dna strand displacement. Science, 347(6222):639--642, 2015.
19. M Hadorn, E Boenzli, K T Sørensen, H Fellermann, P E Hotz, and M M Hanczyc. Specific and reversible dna-directed self-assembly of oil-in-water emulsion droplets. Proceedings of the National Academy of Sciences, 109(50):20320--20325, 2012.
20. A J Genot, A Baccouche, R Sieskind, N Aubert-Kato, N Bredeche, JF Bartolo, V Taly, T Fujii, and Y Rondelez. High-resolution mapping of bifurcations in nonlinear biochemical circuits. Nature Chemistry, pages 760--767, 2016.
21. N Aubert, H Q Dinh, M Hagiya, H Iba, T Fujii, N Bredeche, and Y Rondelez. Evolving cheating dna networks: a case study with the rock-paper-scissors game. In Advances in Artificial Life, ECAL, volume 12, pages 1143--1150, 2013.
22. H Q Dinh, N Aubert, N Noman, T Fujii, Y Rondelez, and H Iba. An effective method for evolving reaction networks in synthetic biochemical systems. Evolutionary Computation, IEEE Transactions on, 19(3):374--386, 2014.
23. R P Wool. Self-healing materials: a review. Soft Matter, 4(3):400--418, 2008.
24. A Devert, N Bredeche, and M Schoenauer. Robustness and the halting problem for multicellular artificial ontogeny. IEEE Transactions on Evolutionary Computation, 15(3):387--404, 2011.
25. A Baccouche, K Montagne, A Padirac, T Fujii, and Y Rondelez. Dynamic dna-toolbox reaction circuits: a walkthrough. Methods, 67(2):234--249, 2014.

Index Terms

• Applied computing

  • Life and medical sciences

    • Systems biology

  • Physical sciences and engineering

    • Chemistry

• Computer systems organization

  • Embedded and cyber-physical systems

    • Robotics

• Computing methodologies

  • Artificial intelligence