Programmable Self-Assembly: Bio-inspired, Modular Robotics, and Swarms

Cells with identical DNA cooperate to create complex structures, from fruitflies to humans, with incredible reliability in the face of cell death, variations in cell numbers, and changes in the environment. Even after development, multicellular organisms show amazing abilities to repair and regenerate. Yet colonies of cells are not the only living things that create complex structure. Even colonies of social insects ("superorganisms") show the ability to create complex large-scale structures that is self-repairing, for example millimeter size termites cooperate to create mounds with complex architecture that are 2-5 meters high, weaver ants create bridges and pulling chains to fold leaves, and army ants create nests (bivouacs) out of their own bodies.

Our group uses inspiration from these systems to understand how global structure, repair and adaptation can be achieved through simple local behaviors. We are interested in programmable self-assembly and its application to the design of programmable materials, self-reconfiguring modular robots, and coordinating robot swarms. A key focus of our work is the design of global-to-local compilers, where the goal is described using a high-level shape language and the compiler automatically translates the user-specified global goal into a provable agent ("cell") program. Our work in this area is algorithmic and theory-oriented, but also in many cases tied closely to robotic implementations. Below are several of the self-assembly related themes we pursue and have pursued:

Self-assembling and Self-reconfigurable Modular Robots: Modular robots are a type of robot composed of many connected smart modules with computation, sensors, and actuators ("cells"); the modules can cooperate to allow a single robot to flexibly assume many shapes and functions similar to a multicellular organism. An important challenge is the design and analysis of decentralized and robust algorithms for module cooperation. Our group has developed several "global-to-local" algorithmic approaches for 2D and 3D self-assembly, including self-reconfiguration on lattice-style modular robots and self-assembly for bipartite modular robots. These global-to-local algorithms rely on simple, decentralized, purely local agent rules and are robust to variable timing and behavior of agents. At the same time they are provably correct for large classes of shapes. More recently, we have been developing a common framework for studying self-assembly algorithms, to show how algorithms can translate to different agent models, and how algorithms developed in different domains can be compared on a common ground.

See the movie to the right for an overview of many different kinds of shapes that can be self-assembled. Programmable modular self-assembly is closely related to other areas we study, such as collective construction and formation control by mobile robots.

Bio-inspired Self-assembly using Global-to-local Compilers: [2000-2005] Cells with identical DNA cooperate to form complex structures, from fruitflies to humans. As part of the Amorphous Computing project, we used inspiration from multicellular development to create several models of self-assembly: (1) pattern formation on amorphous cellular automata (2) an origami-inspired foldable programmable surface (3) a directed growth model inspired by cell growth/death. Together, this work was one of the first demonstrations of how one can build global-to-local compilers for many models of agents: in each case the goal is described using a high-level shape language, and the compiler automatically translates the user-specified global goal into a provable agent ("cell") program, by composing a small set of bio-inspired primitives. We also showed how biological phenomena, such as scale-invariance and regeneration can be directly encoded into the compilation process. Our more recent work in this area focuses on adapting these ideas to robotics and developing a global-to-local theory for pattern-formation. (Origami-shape language old website)

Self-repairing Formation Control for Mobile Agent Swarms: [2004-2006] Birds and fish exploit simple local interactions to form and move in complex formations; these formations do not depend on knowing how many agents there are in advance and easily adapt to the agent error, addition, and removal. Many multicellular organisms show similar properties during development. We combine ideas from flocking and self-assembly to show how a group of mobile agents can coordinate in a decentralized manner, without an external coordinate system, to create arbitrary user-specified formation shapes. In one approach (shapebugs), agents use gas-like behaviors to spread within the confines of the desired shape: this approach compensates for individual agent movement and sensing error but also allows the formation to automatically self-repair when large numbers of agents are added or removed. Other approaches rely on distributed sensing of scale, and such approaches may even allow formations to move through complex obstacle fields. Most recently, we are working on a new hardware project ("kilobot" project) to design extremely low-cost robots capable of executing the formation control algorithms and demonstrating the power of scale.