Programmable Self-Assembly:
Constructing Global Shape Using Biologically-Inspired Local Interactions and Origami Mathematics

Radhika Nagpal
MIT Artificial Intelligence Lab
(June 2001)

Ph.D Thesis

Thesis (ps)

Papers

Webpages

Defense Talk Slideshow

Towards a Programmable Material

Amorphous Computing HomePage

Cells cooperate to form complex structures, such as ourselves, starting from a nearly homogeneous egg, with incredible precision and reliability. Emerging technologies like MEMs and bioengineering are making it possible to embed millions of tiny computing and sensing devices into the environment. We would like to be able to build novel applications from these technologies that achieve the kind of complexity and reliability that cells achieve. This poses the following challenges: a) How does one achieve a particular global shape or pattern from the local interactions of vast numbers of parts, in a robust and decentralized way? b) What are the appropriate local and global programming paradigms for engineering such systems?

This thesis provides an example of how programmable self-assembly can be achieved. I present a language for instructing a sheet of identically-programmed, flexible, autonomous cells to assemble themselves into a predetermined global shape. A wide variety of global shapes and patterns can be synthesized, using only local interactions between identically-programmed cells. The global shape is described as a folding construction on a continuous sheet, using a language based on Huzita's axioms of origami. The program executed by a cell is automatically compiled from the global description, which is in contrast to approaches based on cellular automata and evolution. The cell program is inspired by developmental biology and is composed from a small set of primitives. The cell programs do not rely on regular cell placement, global coordinates, unique global identifiers or synchronous operation and are robust in the face of a small amount of random cell death.

The language and simulations provide many insights into the relationship between local and global descriptions of behavior, such as the advantage of constructive languages, mechanisms for achieving global robustness, and mechanisms for achieving scale-independent shapes and related shapes from a single program. Many of these mechanisms will be applicable to programming smart matter and reconfigurable substrate applications, as well as provide a basis for directing experiments towards understanding biological morphogenesis.

Thesis Completed: June 2001
Committee: Gerald Jay Sussman, Harold Abelson, Thomas F Knight Jr