Adapting swarm intelligence for the self-assembly of prespecified artificial structures.

摘要

The self-assembly problem involves designing individual behaviors that a collection of agents can follow in order to form a given target structure. An effective solution would potentially allow self-assembly to be used as an automated construction tool, for example, in dangerous or inaccessible environments. However, existing methodologies are generally limited in that they are either only capable of assembling a very limited range of simple structures, or only applicable in an idealized environment having few or no constraints on the agents' motion. The research presented here seeks to overcome these limitations by studying the self-assembly of a diverse class of non-trivial structures (building, bridge, etc.) from different-sized blocks, whose motion in a continuous, three-dimensional environment is constrained by gravity and block impenetrability. These constraints impose ordering restrictions on the self-assembly process, and necessitate the assembly and disassembly of temporary structures such as staircases. It is shown that self-assembly under these conditions can be accomplished through an integration of several techniques from the field of swarm intelligence. Specifically, this work extends and incorporates computational models of distributed construction, collective motion, and communication via local signaling. These mechanisms enable blocks to determine where to deposit themselves, to effectively move through continuous space, and to coordinate their behavior over time, while using only local information. Further, an algorithm is presented that, given a target structure, automatically generates distributed control rules that encode individual block behaviors. It is formally proved that under reasonable assumptions, these rules will lead to the emergence of correct system-level coordination that allows self-assembly to complete in spite of environmental constraints. The methodology is also verified experimentally by generating rules for a diverse set of structures, and testing them via simulations. Finally, it is shown that for some structures, the generated rules are able to parsimoniously capture the necessary behaviors. This work yields a better understanding of the complex relationship between local behaviors and global structures in non-trivial self-assembly processes, and presents a step towards their use in the real world.