Self-assembly enables nature to build complex forms, from multicellular organisms to complex animal structures such as flocks of birds, through the interaction of vast numbers of limited and unreliable individuals. Creating this ability in engineered systems poses challenges in the design of both algorithms and physical systems that can operate at such scales. We report a system that demonstrates programmable self-assembly of complex two-dimensional shapes with a thousand-robot swarm. This was enabled by creating autonomous robots designed to operate in large groups and to cooperate through local interactions and by developing a collective algorithm for shape formation that is highly robust to the variability and error characteristic of large-scale decentralized systems. This work advances the aim of creating artificial swarms with the capabilities of natural ones.
Complex systems are characterized by many independent components whose low-level actions produce collective high-level results. Predicting high-level results given low-level rules is a key open challenge; the inverse problem, finding low-level rules that give specific outcomes, is in general still less understood. We present a multi-agent construction system inspired by mound-building termites, solving such an inverse problem. A user specifies a desired structure, and the system automatically generates low-level rules for independent climbing robots that guarantee production of that structure. Robots use only local sensing and coordinate their activity via the shared environment. We demonstrate the approach via a physical realization with three autonomous climbing robots limited to onboard sensing. This work advances the aim of engineering complex systems that achieve specific human-designed goals.
The predominantly hexagonal cell pattern of simple epithelia was noted in the earliest microscopic analyses of animal tissues1, a topology commonly thought to reflect cell sorting into optimally packed honeycomb arrays2. Here we use a discrete Markov model validated by time-lapse microscopy and clonal analysis to demonstrate that the distribution of polygonal cell types in epithelia is not a result of cell packing, but rather a direct mathematical consequence of cell proliferation. On the basis of in vivo analysis of mitotic cell junction dynamics in Drosophila imaginal discs, we mathematically predict the convergence of epithelial topology to a fixed equilibrium distribution of cellular polygons. This distribution is empirically confirmed in tissue samples from vertebrate, arthropod and cnidarian organisms, suggesting that a similar proliferation-dependent cell pattern underlies pattern formation and morphogenesis throughout the metazoa.
Termites construct complex mounds that are orders of magnitude larger than any individual and fulfil a variety of functional roles. Yet the processes through which these mounds are built, and by which the insects organize their efforts, remain poorly understood. The traditional understanding focuses on stigmergy, a form of indirect communication in which actions that change the environment provide cues that influence future work. Termite construction has long been thought to be organized via a putative ‘cement pheromone’: a chemical added to deposited soil that stimulates further deposition in the same area, thus creating a positive feedback loop whereby coherent structures are built up. To investigate the detailed mechanisms and behaviours through which termites self-organize the early stages of mound construction, we tracked the motion and behaviour of major workers from two Macrotermes species in experimental arenas. Rather than a construction process focused on accumulation of depositions, as modelsbased on cement pheromone would suggest, our results indicated that the primary organizing mechanisms were based on excavation. Digging activity was focused on a small number of excavation sites, which in turn provided templates for soil deposition. This behaviour was mediated by a mechanism of aggregation, with termites being more likely to join in the work at an excavation site as the number of termites presently working at that site increased. Statistical analyses showed that this aggregation mechanism was a response to active digging, distinct from and unrelated to putative chemical cues that stimulate deposition. Agent-based simulations quantitatively supported the interpretation that the early stage of de novo construction is primarily organized by excavation and aggregation activity rather than by stigmergic deposition.
Harold Abelson, Don Allen, Daniel Coore, Chris Hanson, George Homsy, Thomas Knight, Radhika Nagpal, Erik Rauch, Gerald Sussman, and Ron Weiss. 2000. “Amorphous Computing.” Communications of the ACM, 43, 5. (pdf)