Catalyzing Inquiry at the Interface of Computing and Biology

266 CATALYZING INQUIRY

•A population of candidate solutions to the problem. For example, these candidate solutions may
be a sequence of amino acids that can fold into some protein, a computer program, some encoding of the
design for something, or some set of rules in a production system.
•A “fitness” metric by which the “goodness” of a candidate solution can be evaluated. For ex-
ample, if the program was intended to model the output of some designer circuit, the fitness metric
might be based on the performance of a candidate program acting on a test case. That is, given the test
case, the fitness metric would be the deviation of the output of the program from a known, appropriate
answer. Programs that minimized this deviation would be more fit.

Box 8.1

Pattern Formation Using Identical Autonomous Agents

In a 2001 Ph.D. thesis, Nagpal describes a language for instructing a sheet of identically programmed, flexi-

ble, and randomly but densely distributed autonomous agents (“cells’’) to assemble themselves into a prede-

termined global shape, using only local interactions. A wide variety of global shapes and patterns can be

synthesized (patterns including flat layered shapes, all plane Euclidean constructions, and a variety of tessel-

lation patterns) using only local interactions between identically programmed deformable cells. That is, the

global shape results from a coordinated set of local shape changes in individual cells. Despite being pro-

grammed identically, each cell deforms in its own individualized manner, depending on the behavior and

state of its neighbors. (The governing structural metaphor is that of epithelial cells, which generate a wide

variety of structures: skin, capillaries, and many embryonic structures (gut, neural tube) through the coordinat-

ed effect of many cells changing their individual shape.)

The global shape is specified as a folding construction on a continuous sheet, using a small set of axioms, simple

initial conditions (edges and corners of the sheet), and two types of folds. From an engineering standpoint, the

significance of global shape description is that a process that is inherently local can be harnessed to produce a

shape of known configuration. This differs significantly from approaches based on cellular automata, in which

the local-to-global relationship is not well understood and there is no framework for constructing local rules to

obtain any desired pattern (and patterns “emerge” in a non-obvious way from the local interactions).

In this formalism, the specific global shape desired uniquely determines the program executed by all cells. The

cellular program is based on several (biologically inspired) primitives for interacting with the cell’s local

environment. A cell can change the local environment in ways that create the equivalent of chemical gradi-

ents, query its local neighborhood and collect information about the state of local companions (e.g., collect

neighboring values of a gradient), broadcast messages to all the cells in its local neighborhood, invert its

polarity, connect with neighbors in physical contact to establish communication (thus allowing multiple

layers of the sheet to act as a single fused layer), and fold itself along a particular orientation by calling the

local fold within its program with two arguments: a pair of neighbors and a cell surface.

Each cell has limited resources and reliability. All cells execute the same program and differ only in a small

amount of local dynamic state. The cell program does not rely on regular cell placement, global coordinates,

or synchronous operation. Robustness against a small amount of random cell death is achieved by depending

on large and dense cell populations, using average behavior rather than individual behavior, trading off

precision for reliability, and avoiding any centralized control. Further, global coordinates are not required,

because cells are able to “discover” positional information. An average cell neighborhood of 15 is sufficient

to reliably self-assemble complex shapes and geometric patterns on randomly distributed cells.

SOURCE: R. Nagpal, “Programmable Self-assembly: Constructing Global Shape Using Biologically-inspired Local Interactions and

Origami Mathematics,” Ph.D. thesis, MIT Department of Electrical Engineering and Computer Science, June 2001.