Origami Programmable Cell Sheet
Radhika Nagpal
Amorphous
Computing Group
MIT Artificial Intelligence Lab
(Dec 2000)
|
The objective is to produce a language for describing global shape
that can be compiled to local interactions amongst a large number of
cells that work robustly inspite of imprecise positioning and
individual cell limitations and failures. The long term goal is to
contribute to the understanding of engineered
self-organisation, i.e. rather
than observing emergent global behavior from given local rules, how
does one derive local rules for a particular global goal? What
are the high level languages for describing global goals, and what are
the primitives for constructing local rules? |
 |
Here I describe a global language for describing shape, based on
Origami,
and a means for compiling from that description to a
sequence of actions or local rules to execute on each cell. The global
structures need not be origami art but any desired structure that can
be achieved by folding and the language could be extended to include
other operations such as cuts or dynamic shapes.
The physical structure is modeled after epithelial cell sheets. An individual cell
can deform its shape by contracting fibers in its membrane (see activecells). The programmable material
is composed of identically programmed active cells, distributed
randomly but densely in a sheet. The sheet has an apical (top) and
basal (bottom) surface and cells can coordinate to fold the sheet by
contracting the appropriate fibers. Each cell can communicate locally
with other cells within some small distance (communication radius) and
can detect when another cell physically touches it.
An Origami Program
Origami as a language has several key features.
-
Origami is an example of a language that constructively describes
global structures.
-
Using a small set of axioms (called Huzita's
axioms) and only
two types of folds (mountain
and valley), one can construct a very wide variety
of complex shapes.The initial conditions are very simple and always
the same.
-
The methods of combination are very simple. Axioms generate new creases
from existing points and creases and new points can be formed only by the
intersection of previous folds.
-
Origami is a scale-independent language
- i.e. the sequence of folds for a particular shape is independent of the
size of the sheet.
-
The axioms have some very interesting parallels to straight-edge and compass
constructions. Not only can one do euclidean geometry, but also solve problems
of degree three, such as angle trisections and cube doubling. In general
the axioms have significant constructive power.
To describe the formation of a global shape, we use the Huzita axioms of
origami.
Huzita's Origami Axioms:
-
Given two points p1 and p2, we can fold a line through them
-
Given two points p1 and p2, we can fold p1 onto p2 (make
a crease that bisects the line p1p2 at right angles)
-
Given two lines L1 and L2 we can fold L1 onto L2 (crease
is a bisector of the angle between L1 and L2)
-
Given p1 and L1 we can make a fold through p1 perpendicular
to L1
-
Given p1 and p2 and line l1, we can make a fold that places
p1 on l1 and passes through p2
-
Given p1 and p2 and lines l1 and l2, we can make a fold that
places p1 on l1 and p2 on l2.
Axioms 1-3 are the most commonly used. Applying axioms creates new crease
lines and new points are created at the intersection of crease lines. Initially
the sheet starts out with four corner points and four edges (boundery).
One can specify whether or not to fold along the crease line and whether
the fold is a mountain or valley fold.
Deriving Local Rules for the Cell Sheet
At the local level, origami exploits biologically-inspired amorphous
computing primitives, such as gradients, tropisms,
seepthru
and induction,
to organize the cells. Gradients are an analog to chemical gradients secreted
by cells - the chemical concentration provides a estimate of distance from
the source of the chemical (which may be a single cell, small group of
cells, line of cells, etc). Tropism implies ability to sense the
direction of the chemical gradient by comparing neighboring chemical values.
Both of these primitives have been explored in many different contexts
within amorphous computing (GPL language, self organising coordinate systems,
cellular computing language). The primitives are are robust, insensitive
to processor placement and trade off precision for reliability. Contact
and Seepthru use mechanical sensing in the cell sheet - cells make contact
with neighbors they touch as a result of a fold operation and gradient
values can seep through contact neighbors. Induction implies that one group
of cells can induce their polarity on another group of cells through contact.
Using these primitive operations, each axiom can be translated to a
set of local rules. For example axiom 2 creates a crease line such that
any point on the line is equidistant from points p1 and p2. Therefore if
points p1 and p2 (which are not single cells but rather groups of cells)
generate two chemical gradients then all cells can compare if the gradient
levels are the same - if so then they are equidistant and lie on the new
crease line. Seepthru allows a folded cell sheet to behave as a single
sheet so that the same local rules to work by changing the context
or shape in which the axiom applies.
Thus the local program for creating the crease pattern from the global
origami description consists of sequencing the local rules corresponding
to each axiom. Each fold happens with high reliability since the
primitives are robust and there is never any dependence on a single processor,
and since the gradients always travel over the whole sheet the axioms are
to a large extent self-synchronizing.
Contents
The origami based language provides a mechanism for generating global shape
at the local level robustly and could be applied to ideas such as self-configuring
physical structures and reconfigurable robots. More importantly it provides
interesting insights into the general problem of deriving local interactions
from global descriptions of behavior. Not only can one construct
complex global behavior (shape) from a few primitive local behaviors
but also the same shape can be created at many
different scales with no modification of the local program (dna)
of each cells even though the number of cells involved may vary significantly.
We derive local rules for a particular global goal, provide a language
for describing global shapes and primitives for organisation at the local
level. This differs from previous work, such as cellular automata and reaction
diffusion, where the local rules create emergent patterns and how one creates
these local rules is poorly understood.