Growing Machines
Saul Griffith, PhD thesis. (advisor: Joe Jacobson)
Massachusetts Institute of Technology, September 2004
Full text of PhD thesis. 10.5Mb (pdf)

sgphd10MB.pdf

HIGHLIGHT VIDEOS
Abstract

Biological systems are replete with examples of high complexity structures that have “self assembled,” or more accurately, programmatically assembled from many smaller, simpler components. By comparison, the fabrication systems engineered by humans are typically top down, or subtractive, processes where systems of limited complexity are carved from bulk materials. Self-assembly to date has resembled crystallization more than it has the programmatic assembly of complex or useful structures – these systems are information limited. This thesis explores the programming of self-assembling systems by the introduction of small amounts of state to the sub-units of the assembly.

A six-state, kinematic, conformational latching component is presented that is capable of self-replicating bit strings of two shape differentiated versions of the same component where the two variants represent the 0 and 1 bits. Individual units do not assemble until a string is introduced to the assembly environment to be copied.

Electro-mechanical state machine emulators of these latching components were constructed. Operating on an air table, the units demonstrated logic limited aggregation, or error-preventing assembly, as well as autonomous self-replication of bit strings.

A new construction was developed that demonstrates that any two dimensional shape composed of square pixels can be deterministically folded from a linear string of vertex-connected square tiles. This non-intersecting series of folds implies a ‘resolution’ limit of four tiles per pixel. It is shown that four types of tiles, patterned magnetically, is sufficient to construct any shape given sequential folding. The construction was implemented to fold the letters ‘M I T’ from sequences of the 4 tile types.

An analogous construction is developed in three dimensions. It is similarly shown that right-angled tetrahedrons, when folded from an edge-connected string, can generate any three dimensional structure where the primitive pixel (or voxel) is a rhombic hexahedron. This construction suggests a concept of 3D completeness.

In combination, these pieces of work suggest that a manufacturing system based on two component tiles, with seven states per tile, is capable of self-replication of arbitrary 3D structure by copying, then folding, bit strings of those tiles where the desired structure is encoded in the tile sequence.
kinematic replication
autonomous replication
folding MIT
MORE VIDEOS
Pre-publication paper on folding arbitrary 3D shapes from linear strings of edge connected polyhedra.

Introduction.

The HowToon of Figure 1.0 perhaps best summarizes the goals and approach to this work.  We can see all around us in the natural world compelling examples of self assembly – such as the formation of floating rafts of Cheerio-crystals in our cereal bowl, and would like to exploit similar principles to build machines, mechanisms, and useful objects, similarly automatically.  The problem is one of information and system design.  What physical properties of the assembly system can be exploited as the driving forces for the assembly?  In this case menisci formed by hydrophobic and hydrophyllic interactions between chocolate and milk.  How do we encode enough information to build something interesting?  Celine shows tucker that by patterning the edges of the cereal O’s with alternating bands of chocolate that he can build crystals that resemble snowflakes.  What would be really useful technologically though, is to know how to build far more complex objects such as the one we see in the last panel.  This thesis explores how we might program  and build self-assembling systems to achieve such complexity.  Let’s not however make monsters.

Biology assembles objects of great complexity and effective design, apparently trivially, and most certainly quickly and efficiently.  Biological systems exhibit the capacity for self assembly, self repair, logic, reproduction and high complexity 1 2 . Radiolara ( Figure 1.1 ) and diatoms 3 4 . are typically 60-500 microns in largest dimension, with patterning of the silica or CaCO3 features down to 10nm.  The organisms that produce these inorganic skeletons are amongst the most plentiful vegetable matter on earth and are ubiquitous in fresh and salt water. Figure 1.2 shows artificially colored E.Coli cells dividing and replicating.  These two examples from biology exhibit behaviors hitherto unseen in human engineered systems – 3D patterning of complex structure with nm resolution, and self-replication – more impressively still, at basically ambient temperatures and in a large range of materials.  By comparison, human manufacturing typically requires high temperature or high energy processing steps, and high complexity is achieved either by top-down, computer driven control, or laborious manual assembly.

Growing Machines – Why?

This thesis was born of a frustration with existing construction techniques at the nm-micron scale, and through a fascination with the elegance of the methods for fabrication seen in biology.  The work was set out as a design challenge:  design a ‘minimum’ set of components capable of arbitrary 3D structure formation, and of self-replication, by ‘self-assembly’ – that is assembly without directed human intervention.

Particularly as technologists pursue smaller, more complex, and three dimensional structures, traditional manufacturing schemes will likely not scale to meet the demands.  The ability to have self assembling systems perform error-prevention, error-correction, logic, self replication, and self-repair, is what will enable new modes of manufacture such as exponential manufacture by replication of part assemblies.  As the polymerase chain reaction (PCR) has proved of incredibly high value to biologists in amplifying the production of DNA, it would be similarly valuable to micro and nano-technologists to be able to amplify non-biological components where the production of the first is laborious, and of subsequent copies simple and automatic.

Serial vs. Parallel assembly

We traditionally associate a serial process with the concept of assembly - a human hand or robot grasping a component or a sub-assembly and affixing it to another component or assembly until an entire device or machine is furnished.  Assembly by this mode either requires 1) a highly intelligent robot (or human) to find parts, orient the parts, place them correctly, and fasten them, or 2) highly constrained input components or assemblies where the orientation and position is fixed relative to the assembly co-ordinate system and therefore the control problem of placement and fixing is simplified.  The cost of adding more hands, or robots, is often prohibitive.  Inherently this type of assembly process is serial, or stepwise, and parallelism is limited to the number of manipulators.

Self assembling processes on the other hand can be seen to have two core properties amenable to parallelisation of the assembly process.

1. Random or pseudo-random interactions between large numbers of components.

2. Asynchronous formation of assemblies in parallel.

These properties imply that parallelism is limited not by the number of manipulators, but by the number of parts in the bin, and by the number of components that act as the nuclei for construction.  We will see these properties in the assemblies formed in chapters 4,5,6.

3 Dimensions

At the macro scale, or scales larger than that of human fingers, many techniques have been developed for the fabrication of complex 3 dimensional (3D) machines.  Subassemblies are ganged.  The modern motor vehicle has as many as 100,000 individual components and is an inherently three dimensional machine.  Below the scale of millimeters however, very few techniques have been developed for assembling complex 3 dimensional structure, and in the micro and nanometer domain human fabricated structures are almost exclusively 2 dimensional, or at best 3D where the third dimension is achieved by the stacking of 2.5 dimensional layers.  This is the domain of micro-lithography processes and the inherently constrained geometries that they produce.  Recent work by Clark 5 (2001) has demonstrated 3-dimensional assemblies of thousands of micron scale parts.  The complexity of these assemblies is low, in that they are periodic crystals, and the errors are high – as crystal defects, but the number of components is impressive, and it illustrates parallel assembly into ordered structure from random interactions.

Replication

We routinely copy, or replicate, digital information.  It enables convenient and fast manufacture of computer programs or data.  Can this methodology be extended to manufacturing where it would be a convenient method for making complex devices where the first is prototyped and debugged at great length before being copied for manufacture.  There are many philosophical, environmental, ethical, and other debates surrounding both the definition and the implementation of replicating machines, which I shall avoid here – merely pointing out that replication as a manufacturing process is already in wide use today.  PCR, or the Polymerase Chain Reaction, is a method by which strands of DNA may be artificially replicated by cycling through a denaturing, annealing, and extension cycle.  

A model system for studying biological assembly?

Perhaps in building a replicating, structure forming hierarchy from the ground up we will also learn something about biology and the ‘choices’ it made to do things the way it does.  The work in this thesis is not slavish to biological methods for fabrication, quite the opposite.  Rather it looks at how we might achieve similar functionality given the constraints of manufacture that we have in inorganic systems.  

Self Assembly

There is a growing body of work in self assembly 6 7 8 ..  As the reader contemplates the state of the art presented in that work they will see the extremely limited structures available in existing self-assembly schemes.  We can look at biology and the natural world for many inspirational examples of self assembly, and it is precisely this look at biological self assembly that illuminates the limited nature of human made self-assemblies, and of the requirement for more study and invention in this arena to enable higher complexity articles.  It is too soon to determine whether self assembly outside of organic or biological systems will ever prove useful.  Studying this process however is a natural extension of the human desire to understand the structure and function of the world around us, and as well as providing new perspectives on biological self assembly it may well inspire new directions in manufacturing.

The Problem:  Information in Structure

The problem which I seek to address may perhaps be best described as the effort to rationally design for symmetry breaking in self-assembly.  By rationally I mean apriori design of a fixed, repeatable entity.  By symmetry breaking I mean a non-trivial structure, an arbitrary 3D object as opposed to a regular, repeating, crystal structure.  This problem might also be described as the following series of questions that seek to outline the relationship between information and structure in physically assembling systems:

“How does one encode enough information within an assembly of parts to specify (exactly) the resulting structure?

“What is the minimum amount of information, and hence the number of unique part types, and the amount of state, or information within each of those parts, to specify a desired structure or type of structural behaviour?

“How does one implement this information, and the logical steps of assembly it implies, in an autonomously proceeding assemblage?

“Can interesting assembly protocols be implemented in logic simple enough to be executed without microprocessor control, ie. in systems too small or numerous to consider digital computation or on-board power?”

Solution:  Programmable Assembly

To date all designed self-assemblies have effectively been crystallizations, or ordered arrays of similar components.  These ordered arrays tend also to be imperfect crystals.  For self-assembly to be a practical manufacturing device for anything more than arrays (such as photonic crystals) symmetry needs to be broken.  A system that relies purely on pre-patterned edge interactions of tiles or components will require a very large number of different components 9 to construct an object of any complexity.  This realisation has led to the approach taken in this work: to develop a system based on a minimal part set that can achieve the behaviour that is desired: replication and arbitrary 3D structure.  The approach taken is the addition of state to individual tiles in order to implement longer range ordering and patterning.  State can also be used to prevent detrimental errors in the assembly.

One issue tantamount to programming assembly is that the instruction set or data must be stored in memory somewhere.  One approach is that each component in the assembly carries all of the instructions for the entire assembly in a similar way that every cell contains the complete DNA code.  The approach I explore here is storing the code in the structure itself similar to DNA, or proteins.  This implies that to make multiples of a given assembly, one must copy the instructions directly from the structure, not just transfer the information from some digital memory.  This leads to questions of assembly analogs to subcellular processes.

Why not purely simulate?

An immediate criticism of this work to the casual reader could be ‘why not just simulate programmable assembly?”  Indeed this is a good question.  There are even software packages such as SWARM, specifically designed to simulate asynchronous agent based computation.  It is my assertion, and a brief reading of the literature cited in chapter 2 should give the reader a similar perspective, that although a good deal of work has been done in simulating systems such as these, they are generally underconstrained as simulations, and therefore are not modeling real, implementable, systems for assembly. I would anticipate that this thesis will inform future simulation work and suggest how the existing simulation and design tools need to change to reflect the ever so harsh constraints of implementation in the physical world.

Architecture of this thesis.

Chapter 2 of this thesis will introduce enough previous work across fields from DNA computation to meso-scale self assembly and mechanical engineering, to ground the reader in the state of the art and suggest why this piece of work is new and (hopefully) interesting.

In chapter 3 I will define programmed assembly for the purposes of this thesis, and use this chapter to lay out what role small amounts of state could have in programmed assembly.  I will examine the constraints that make physical assembly different from cellular automaton models, and other constraints relevant to implementation.

In chapter 4 I develop a construction that demonstrates that non-intersecting folding of a 2D string of vertex connected squares can produce any 2D pixilated structure (where a pixel is one of the connected squares).  I then show that a similar construction demonstrates that the folding of an edge connected string of right-angled tetrahedral can produce an arbitrary 3D voxelated structure.  These constructions imply a resolution limit to the structure, and a concept of ‘3D completeness’ for a manufacturing system.

In chapter 5 I build on the work of Lionel Penrose in the development of kinematic self-replicating machines and demonstrate that a self replicating system capable of copying arbitrary ‘bit strings’ can be implemented in 6 states.  I shall the difficulties in designing such systems to proceed autonomously.  In Chapter 6 I describe the design and building of ‘electromechanical emulators’ for the study of small program state machines in self assembly.  These emulators are assembled in a 2D air-bearing (air hockey table) environment.  Finally in Chapter 7 I will draw all of these pieces together in conclusion and suggest the further work that may bring some of these ideas closer to reality.

1  Thompson, D. A. W. and L. L. Whyte (1942). On growth and form . Cambridge Eng., The University Press.

2  Bard, J. (1990). Morphogenesis : the cellular and molecular basis of developmental anatomy . Cambridge England ; New York, Cambridge University Press.

3  Flachentragwerke, I. f. l., Ed. (1984). IL28 Diatoms 1, Shells in Nature and Technics , Universitat Stuttgart.

4  Flachentragwerke, I. f. l., Ed. (1990). IL33 Radiolaria , Universitat Stuttgart.

5  Clark, T. D., J. Tien, et al. (2001). "Self-assembly of 10-mu m-sized objects into ordered three-dimensional arrays." Journal of the American Chemical Society   123 (31): 7677-7682.

6  Terfort, A., N. Bowden, et al. (1997). "Three-dimensional self-assembly of millimetre-scale components." Nature   386 (6621): 162-164.

7  Bowden, N., I. S. Choi, et al. (1999). "Mesoscale self-assembly of hexagonal plates using lateral capillary forces: Synthesis using the "capillary bond"." Journal of the American Chemical Society   121 (23): 5373-5391.

8  Oliver, S. R. J., T. D. Clark, et al. (2001). "Three-dimensional self-assembly of complex, millimeter-scale structures through capillary bonding." Journal of the American Chemical Society   123 (33): 8119-8120.

9  Private communications with Erik Winfree and Joe Jacobson.

Figure 1.0.  Conceptual cartoon of programmed self-assembly.
Figure 11 . The predominantly silica skeleton of a radiolara.
Figure 12 E.Coli. cell division and replication
The videos below are excerpts from the experimental work of this thesis. They are all quicktime movies.
Conceptual video that describes some of the motivation for this work. How to make complex machinery and mechanisms that assemble themselves from many parts. (This video by Honda corporation). The information complexity problem is illustrated here. How does one code all the individual parts to achieve this type of behaviour?
Mechanical 5-state state machines capable of bit-string replication are demonstrated by hand. It is only once an input string is created from the 2 types of basic units that the string may replicate. Both blue and white parts run identical mechanical state machine logic with a shape recognition / differentiation aspect.
Dynamics tracking and control experiment. Demonstrates system dynamics of air table. Three coloured components (white, blue, yellow) are monitored for position and rotational orientation.
Detail of magnetically actuated latching mechanism for electromechanical assembling units.
Control experiment 1: no logic, purely irreversible bonds, demonstrates the error prone nature of logicless self assembly.
Control experiment 2: no logic, purely irreversible bonds, demonstrates the error prone nature of logicless self assembly.
Coloured lines assembling (green and yellow) addition of new tiles at both ends of line.
Coloured lines assembling with timed break-up (at 15 minutes all bonds are broken).
Exponential replication of a 3-mer. Begin with one, end with 8.
Replication of a G:G:Y:Y:G 5-mer autonomously.
Accelerated video of assembling checker-board pattern.
Error preventing crystal formation with counter of number of parts in crystal. Could be described as logic limited aggregation.
Movie showing formation of crystal, infection by outside unit, break apart, and reformation into lines.
Another example of programmed structure from predicated folding strings of polyhedra.
First example of programmed structure from predicated folding strings of polyhedra.
Folding MIT from a linear string of parts. The order of the 4 magnetically encoded tile types uniquely specifies the resulting structure provided that the folding proceeds sequentially down the string.