Coordinated three-dimensional robotic self-assembly

Nature has demonstrated that geometrically interesting and functionally useful structures can be built in an entirely distributed fashion. We present a biologically-inspired model and several algorithms for three-dimensional self-assembly, suitable for implementation by very simple reactive robots. The robots, which we call assembly components, have limited local sensing capabilities and operate without centralized control. We consider the problem of maintaining coordination of the assembly process over time, and introduce the concept of an assembly ordering to describe constraints on the sequence in which components may attach to a growing structure. We prove the sufficient properties of such an ordering to guarantee production of a desired end result. The set of ordering constraints can be expressed as a directed acyclic graph; we develop a graph algorithm that is able to generate ordering constraints for a wide variety of structures. We then give a procedure for encoding the graph in a set of local assembly rules. Finally, we show that our previous results for the optimization of rule sets for two-dimensional structures can be readily extended to three dimensions.