# Presentation: 173853

##  AMORPHOUS AND CELLULAR COMPUTING

- Hal Abelson
- Jake Beal
- Lauren Clement
- Chris Hanson
- Attila Kondacs
- Tom Knight

- Radhika Nagpal
- Randy Rettberg
- Erik Rauch
- Gerald Jay Sussman
- Ron Weiss

## A scientific and technological effort to identify

- Methods for obtaining coherent behavior from the cooperation of vast numbers of unreliable parts, that are interconnected in unknown, irregular, and time-varying ways
- Organizational principles
- Algorithms
- Programming models
- Compilation technology targeted to appropriate substrates
- New computing substrates, both from traditional silicon technology and from molecular biology

## Slide 3

## Why is this interesting?

- Physically feasible at any scale
- Forces robustness of design
- Potentially extremely inexpensive
- Provides the possibility of *bulk computation*
- smart paints
- smart gels
- concrete by the Megaflops
- vast sensor networks
*Our programming models run out when there are too many elements to program individually, *_*or even to name*_*.*

## "It is unlikely that we could construct automata of a much higher complexity than the ones we now have, without possessing a very advanced and subtle theory of automata and information.  This intellectual inadequacy certainly prevents us from getting much farther than we are now...A simple manifestation of this factor is our present relation to error checking...

- With our artificial automata we are moving much more in the dark than nature appears to be with its organisms.  We are, and apparently, at least at present, have to be much more `scared' by the occurrence of an isolated error and by the malfunction which must be behind it. Our behavior is clearly that of overcaution, generated by ignorance.“
- -- John von Neumann (1948)

## Example of an Amorphous Computing Medium

- An amorphous medium has independent computational particles, all identically programmed.  Each particle is represented by a spot in the picture, and different states are shown by different colors.

## Our amorphous computing model

- Computing elements sprinkled on a surface or in a volume
- Too many to individually program or even to name
- Each talks to a few neighbors, but not reliably
- Not synchronous, nor regularly arranged

## Crude local coordinate systems can be constructed by intersecting countdown waves radiating from several loci.

- Crude local coordinate systems can be constructed by intersecting countdown waves radiating from several loci.

## How can we program amorphous stuff?

- We can look to biology for organizational metaphors, although we need not try to duplicate actual biological mechanisms
- We’ll take examples from pattern formation to illustrate the point, and produce cartoon caricatures of biological morphogenesis

## Bifurcating Tubes: an example of emergent behavior

- This is an amorphous physical simulation of a weak membrane
- bounding a pressure vessel.  When a bulge appears, the membrane
- thins and the bulge expands. (by Radhika Nagpal)

## Suppose we wanted to make something with a precisely specified geometry?

- from Frank Netter
*Atlas of Human Anatomy*

## Differentiation

**Differentiation**

- To make a “spine”, the elements in an initial polarized tube must differentiate into bands of alternating C and D type segments.

## Local SIMD paradigm for programming differentiation and growth (Weiss)

-  Each computing element’s state includes some binary markers.  Each computing element’s program has many independent rules.
-  Rules are triggered when messages are received.  A rule is applicable if a certain boolean combination of markers is satisfied.
-  When a rule is applied it may set markers and send further messages.
-  Messages have hop counts that determine how far they will diffuse.
-  Markers may have lifetimes after which they expire.

##  A program for creating segments:

-  *A program for creating segments:*

**(start**
** ****Crest**
** ****((send (make-seg C 1) 3)))**
**((make-seg seg-type seg-index)**
** ****(and Tube (not C) (not D))**
** ****((set seg-type)**
**  ****(set seg-index)**
**  ****(send created 3)))**
**(((make-seg) (= 0))**
** ****Tube**
** ****((set Bottom)))**
**(((make-seg) (> 0))**
** ****Tube**
** ****((unset Bottom)))**

- Microbial Colony Language (MCL): Ron Weiss

**(created**
** ****(or C D)**
** ****((set Waiting 10)))**
**(* **
** ****(and Bottom C 1 (Waiting (= 0)))**
** ****((send (make-seg D 1) 3)))**
**(* **
** ****(and Bottom D 1 (Waiting (= 0)))**
** ****((send (make-seg C 2) 3)))**
**(* **
** ****(and Bottom C 2 (Waiting (= 0)))**
** ****((send (make-seg D 2) 3)))**
**(* **
** ****(and Bottom D 2 (Waiting (= 0)))**
** ****((send (make-seg C 3) 3)))**

## Deleting Hox genes in mice

- from Wolpert, *Principles of Development, *Oxford University Press, 2002, p. 124

## A botanical metaphor for pattern generation:  (Daniel Coore)

- Organize the process in terms of “growing points.”
- Growing points are abstract structures that exhibit “tropisms” toward particular “chemical gradients.”
- The growing points may lay down materials.
- Materials may secrete pheromones that attract or repel other growing points.
- Growing points may split, die off, or join.
- Support for this abstraction may be programmed as a uniform state machine in each computational particle.

## Start with “Vdd”, “Vss”, and a “Poly” Contact

## The poly contact sprouts a growing point that bifurcates and then grows toward the pheromones secreted  by Vdd and Vss.

## When the growing poly gets close to Vdd and Vss it is stopped by a short-range inhibition

## The poly growing points die off, but first they sprout P and N transistor diffusion growing points, which grow toward Vdd and Vss, where they drop contacts.

## The diffusions also grow toward each other.  When they hit they form a new poly contact and poly growing point.

## The process then repeats, growing the next inverter.

## This process repeats to make an arbitrarily long chain of ugly, but topologically correct inverters.

- This process repeats to make an arbitrarily long chain of ugly, but topologically correct inverters.

- This demonstrates totally local control of precision topology.

## The growing points provide a serial locus of control, even though the implementation is in terms of a uniform state machine in each computational particle

**(define-growing-point ((poly from-input-contact) Q-id)**
**  ****(material poly)**
**  ****(tropism constant Vdd-long Vss-long)**
**  ****(initialize lifetime 5)**
**  ****(secrete (poly-short inhibitor) Q-id)**
**  ****(when (= lifetime 0)**
**   ****(start-growing-point (poly up) Q-id)**
**   ****(start-growing-point (poly down) Q-id)**
**   ****(terminate)))**

## Capabilities of GPL

## Robustness and regeneration 

- Newt

- Starfish

- Hydra

- from Wolpert, *Principles of Development, *Oxford University Press, 2002, pp. 447, 450

## Active gradients and self-repairing linesLauren Clement and Radhika Nagpal

- Active gradients and self-repairing linesLauren Clement and Radhika Nagpal

## 10

- 9

- 9

## 10

- 9

- 9

## 10

- 9

- 9

- 9

- 9

- 9

- 9

- 9

- 9

## 10

- 9

- 9

- 9

- 9

- 9

- 9

**X**

**X**

- 9

- 9

## 10

- 9

- 9

- 9

- 9

- 9

- 9

## 10

- 9

- 9

- 9

- 9

- 9

- 9

- 8

- 8

- 8

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 6

- 5

- 5

- 6

- 6

- 5

- 4

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 6

- 5

- 5

- 6

- 6

- 5

- 4

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 6

- 5

- 5

- 6

- 6

- 5

- 4

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 6

- 5

- 5

- 6

- 6

- 5

- 4

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 6

- 5

- 5

- 6

- 6

- 5

- 4

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 5

- 5

- 6

- 6

- 5

- 4

**?**

**?**

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 5

- 5

- 6

- 6

- 5

- 4

**?**

**?**

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 5

- 5

- 6

- 6

- 5

- 4

**?**

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 5

- 5

- 6

- 6

- 5

- 4

**?**

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 5

- 5

- 6

- 6

- 5

- 4

**?**

## 9

- 10

- 8

- 8

- 8

- 7

- 7

- 7

- 6

- 5

- 5

- 6

- 6

- 5

- 4

## Self-repairing line

## Languages for programmable materials

- (Nagpal, 2001)

- An amorphous sheet of programmable cells folds itself to form prespecified shapes

## Programmable  Cell sheet

- Randomly and densely distributed cells

## Inspiration: Epithelial cell tissues

- Cell Model by Odell et al.

## Programmable cells

## Biologically-inspired primitives

- Gradients

- Tropism                        Bounded

**Notes:**
First primitive is gradients:
inspired by chemical concentration gradients during development believed to fundamental to patterning embryo. Drosophila variety of gradeints
In our model the way a gradient works is 
- count up (estimate of distance)
- local average to improve integral distance estimate
- gradient has a name
- multiple sources may emit gradient same name (shortest distance to any) 
   (almost always case)
      ?? time (away from), redundancy, asynchornicity issues ??

The gradient values are used in one of three ways:
- comparison of scalar values g1=g2 within tolerance
- tropism (gradients also provide sense of direction relative source)
     daniel coore showed many complex patterns based on different types of tropisms, we just use very simple case 
     cells locally detect vector of gradient, 
     locus of control moves along vector field and leaves a trail behind
- create gradients that are bounded by an impassable boundery
    simply detecting presence of gradient

No absolute thresholding

## More biologically-inspired primitives

- Seepthru
- Flexible Folding
- Polarity Induction

- cell-to-cell
-    contact

- ==> new nbrhood

**Notes:**
Second primitive is called seepthru
   based on cell-to-cell contact, cell can detect when a new cell comes into direct contact, 
Modifies local neighborhood of the cell.
Modifying neighborhood affects how gradients propogate
gradients seepthrough - example

Flexible folding - 
from cell model discussed earlier, but extended to non rectangular cell. 
     assume apical basal surface have a random dense network of fibers 
     given some orientation a cell can contract all fibers  lie along
     (note effect is perpendicular to orientation)

Polarity Induction -
cells original apical basal polarity, but this is not fixed
can be induced to reverse polarity.

## Folding a cell sheet

## Origami

- Origami as a *constructive* shape language
- Huzita's Axioms of Origami [1989]

-    sequence of
-   straight flat folds

- (1) fold-lbp

- (2) fold-p2p

- (4) fold-l2self

- (5) fold-p2l

- (3) fold-l2l

- (6) fold-pp2ll

**Notes:**
Origami can be thought of as a constructive language for describing global
sequence of staright flat folds,  on a piece of paper with some initial fixed boundery conditions, no cuts or glue is allowed.

Humiaki Huzita came up with an elegant set of 6 axioms that describe most origami folds . Each axiom shows how to construct a new crease line from current set of points and creases.

1-3 most commonly used

Axioms by themselves are not sufficient,
Two fold types (mountain and valley), choice to fold, partial layers

staright line
bisector  line p1p2
angle bisector or parallel line
perpendicular to l1 thru p1
5 and 6 less commonly used

## Approach

- Global Shape
-    Program

- compiled

-  Cell Program

- Programmable
-   Cell Sheet

- autonomous
- flexible cell

- executed

**Notes:**
This slide gives an overview of how it works
The global shape is constructively described as a folding seuqnce on a sheet, the language for which is inspired by huzita
The global shape description is then automatically compiled into a program run on a single cell, simple computing element that is inspired by epithelial cell. The cell has simple actuators that allow it to modify its own shape, limited resources limited reliability, 
constrained locally with neoghbors

Executed on a sheet of thousands cells, all identically programmed. Some initial conditions, No global position, no global clock, 
Cells on sheet coordinate to self assemble sheet into the desired global shape

## Implementing the axioms

## GPL-like code for axiom 2

## Origami-based formation of global shapefrom biologically-inspired local interactions

- An language for self assembling predetermined global shape from a sheet of identically-programmed flexible autonomous cells
- A means of compiling that language into programs for the cells, using biologically-inspired primitives

## Origami Shape Language

_** **__**Origami Cup Program**_
- (define d1 (fold-p2p c3 c1))
- (define-region front(c3 d1))
- (define-region back (c1 d1))
- (execute-fold d1 apical mark=c3)
- (define d2 (fold-l2l e23 d1))
- (define p1 (intersect d2 e34))
- (define d3 (fold-p2p c2 p1))
- (execute-fold d3 apical mark=c2)

- (define p2 (intersect d3 e23))
- (define d4 (fold-p2p c4 p2))
- (execute-fold d4 apical mark=c4)
- (define l1 (fold-lbp p1 p2))
- (within-region front
-  (execute-fold l1 apicl mark=c3))
- (within-region back
-  (execute-fold l1 basal mark=c1))

**Notes:**
Using simple example, origami cup, illustrate how write program to describe origami sequence. Cup is a good example because simple folding seuqnce that touches subtle points.

I will explain this slide in DETAIL

Basic elements: points and line
Start with initial conditions: c1-c4, e12-e41
Axioms generate new creases (lines)
Intersect creases generates new points

1. crease divide into two regions
two ways of folding (apiocal basal) - make implicit top explicit
2. Intermediate crease, not a permanent fold
fold goes through all layers (not always)
3. 
4. axiom 1 - partial layers : use notion of region 

## Cup Example: 1

**       **_**Origami Cup Program**_
- (define **d1** (fold-p2p c1 c3 "green"))
- (define-region front(c3 d1))
- (define-region back (c1 d1))
- (execute-fold **d1** apical landmark=c3)

**Notes:**
Illustrate how this all works on an example
same OSL program from before

c1 cells emits gradient g1, 
when arrives at c3, c3 cells emit g2
cells in between compare g1 g2 to see if they lie along line
when gradient rrives at c1 waits some time 
sends final gradeitn to mark end

c1 cells emit gradient that can not pass through d1
all cells that received d1 set bit local state to say that they are part of this fron region

execute-fold
c1 generates a different gradient mark region reverse apical
 when arrives at d1, cells contract and fold sheet
 cells on one side reverse polarity 
( think of color gray=original polarity, black reversed)
 new contact neighborhoods are formed

## Cup Example:2

- (define **d2** (fold-l2l e23 d1 "cyan"))
- (define p1 (intersect d2 e34))
- (define **d3** (fold-p2p c2 p1 "magenta"))
- (execute-fold **d3** apical landmark=c2)

**Notes:**
axiom 3 form next crease
cells part of e23 and d1 emit gradients

cells are both d2 and e34 become p1

axiom2 p1 and c2 cells emit gradients and cells equidistant d3
execute-fold d3 same as before

## Cup Example:3

- (define p2 (intersect d3 e23))
- (define **d4** (fold-p2p c4 p2 "magenta"))
- (execute-fold **d4** apical landmark=c4)

**Notes:**
same thing on the other side

## Cup Example:4

- (define **l1** (fold-lbp p1 p2 "yellow"))
- (**within-region** **front**
-   (execute-fold **l1** apical landmark=c3))
- (**within-region** **back**
-   (execute-fold **l1** basal landmark=c1))

- unfold

**Notes:**
Now use axiom1 to generate crease from p1 cells to p2 cells, 
p2 emits a gradeint
when arrives at p1, p1 cells compete to start tropism and then grow crease towards p2
when arrives at any p2 cell, cell sedns out final gradient indicating craese complete

Now fold affects only ceratin layers, by restricting within a region
- execute-apical-fold using only l1 cells that are also in front region
- execute-basal-fold using only l1 cells that in back region

If we unfold the sheet and look at the states of the cells
see creases are generally very straight, see which cells reversed polarity as a result of folds.

## Examples: Origami Shapes

- CUP

- Samurai Hat

- Rouge Container

- Airplane

- Puzzle

**Notes:**
Examples of flat folding shapes
- partially folded airplane (hard to see fully), traditional folding samurai hat, rouge container used as a gift wrapping

each shapes formed with high reliabilty, but they are not perfect, but functional

EDIT: need slide explain why can't do crane or traditional BASE

## The origami shape language is well-suited for amorphous systems 

- Wide variety of predetermined global shapes, with only **local** communication and local computation
- Local rules are** ****automatically derived**
- Small set of biologically-inspired primitives
**Robust**** **in the face of** **irregular cell placement, asynchronous cells, random cell death, etc
- Programs** are scale independent**

**Notes:**
Wide variety of shapes and patterns can be described using this system - origami shapes, geometric patterns, tesselllations, biologically inspired.
all acheved using control algorithms that based on local interactions

High level language for globally describing a particular goal,
This description compiled into Local Rules executed on each cell.
This approach is significantly different  from bottom-up and empirical approach of cellular automata , emergent phenomena, ittle understanding of how to design local rules for specific goal shape. 
Also different from genetic algorithms, where local rules are derived from a description of final goal but little understanding of how and why local rules work 
By contrast I provide a small set of biologically-inspired primitives for organisation at the local level. and the local rules are compositions, well understand the relationship between global and local

An important focus of this work is achieving global robustness even though individuals may be unreliable and have no global info. I show that the primitives do not depend on .... I show possible to understand, reason and analyze why 

Robustness achieved through combination of depending on large and dense populations, average behavior, trading off precision for relability and avoiding any centralized control (leaders, depend on group behavior)

## Programs are scale independent

- Same shape at different scales

- Program remains same, irrespective of number of cells

- 8000

- 2000

- 4000

- pattern

*scales*

-  with number of cells

## Similar programs produce homologous structures

- Ridley (1997) *Evolution*

## Cells as a programming substrate

**=**

- Biochemical Logic circuit

- Environment

- sensors

- actuators

**Notes:**
I’m going to tell you today about the work I’ve done to create a new engineering discipline that makes it possible to use living cells as a substrate for engineering design 
Like the first days of designing electrical circuits
Biological systems as substrates for engineering
Mapping of logic circuits to biochemical substrates
Use biological substrates to engineer behavior

--------------------------------------------------------------------------------
I’m going to tell you today about the work I’ve done to create a new engineering discipline that makes it possible to use living cells as a substrate for engineering design 
This research, which we’re calling cellular robotics, is at a point similar to the first days of integrated circuit design:  We have to create elementary devices and ways of using them as mix and match components, we have to figure out how to control signals to obtain reliable behavior, and we have to create levels of language that span the gap from the elementary physical devices we create, to high-level behaviors that we want to engineer.
This is all a familiar story to electrical engineers and computer scientists, and today I’m going to tell you how I’ve been carrying out that same program, only this time using living cells, rather than semiconductor devices.

## Vision

- A new substrate for engineering: living cells
- interface to the chemical world
- cell as a factory / robot
- possible biomedical applications
- Challenge: engineer complex, predictable behavior

**Notes:**
Cells are a novel substrate for engineering design -- providing an outstanding interface to the worlds of chemistry and nanotechnology.

Analogously to the development of a new silicon process, the challenge here is to come up with a new family of components and standard ways combining them so that the combinations have predictable behavior

A cell is like a machine shop, with proteins as the molecular scale machine tools.  I am working toward a future where we get to write the “tapes” (as DNA) that control these tools to do useful work for us.
In my engineering model, developed with Tom Knight and Gerald Sussman, the control signals are the concentrations of biochemicals and the primitive components are segments of genetic material (DNA) that conditionally code for some signalling molecules, controlled by the concentrations of other molecules.

Add physical properties to computers / robots

Enable 

## Programming Cells

- plasmid = “user program”

- Compile logic circuits into pieces of DNA that encode genetic regulatory networks
- Logic signals are represented as concentrations of   proteins (mRNA)
- Action of the genetic regulatory network in a living cell implements the desired logic function

## Biochemical Inverter

- signal = concentration of specific proteins (mRNA)
- computation = regulated protein synthesis + decay

## A More In-Depth Model of the Inverter: I

- promoter

*translation*

*transcription*

- RNAp

- ribosome

- protein

## from Becker, Reece, and Poenie, The World of the Cell, Benjamin/Cummings, 1996, p. 559

- from Becker, Reece, and Poenie, *The World of the Cell, *Benjamin/Cummings, 1996, p. 559

## A More In-Depth Model of the Inverter: II

- promoter

*translation*

*transcription*

- RNAp

- mRNA

- ribosome

- protein

- operator

- repressor protein

## Inducers

- Use as a logical *Implies* gate:                 (NOT R) OR I

- operator

- promoter

- gene

- RNAP

- active
- repressor

- operator

- promoter

- gene

- RNAP

- inactive
- repressor

- inducer

- no transcription

- transcription

## BioCircuit Computer-Aided Design

- SPICE

- BioSPICE

-  BioSPICE: a prototype biocircuit CAD tool
-  simulates protein and chemical concentrations
-  intracellular circuits, intercellular communication
-  single cells, small cell aggregates

## “Proof of Concept” Circuits

- Work in BioSPICE simulations [Weiss, Homsy, Nagpal, 1998]
- They work in vivo
- Flip-flop [Gardner & Collins, 2000],  Ring oscillator [Elowitz & Leibler, 2000]
- Models poorly predict their behavior

- time (x100 sec)

- [A]

- [**C**]

- [B]

**B**

**_**
- S

**_**
- R

**A**

**_**
- [R]

- [**B**]

**_**
- [S]

- [**A**]

- time (x100 sec)

- time (x100 sec)

- RS-Latch (“flip-flop”)

- Ring oscillator

## Measurements of a Ring Oscillator

- [Elowitz & Leibler, 2000]

## Genetic Process Engineering(Ron Weiss)

## BioBricks: Future Data Book for Cellular Robotics?(Randy Rettberg and Tom Knight)

| BB Device Number | Description |
| --- | --- |
| *BBa D0001  | Base Plasmid for Structured Assembly |
| BBa D0001  | Inverter |
| *BBa D0002  | Inverter |
| *BBa D0003  | Inverter |
| BBa D0004  | Inverter |
| *BBa D0001  | Green Fluorescence Output |
| BBa D0002  | Cyan Fluorescence Output |
| *BBa D0003  | Yellow Fluorescence Output |
| ... | ... |

## Putting it all together?

- Origami Shape Language
- (Nagpal)

- Low-level languages (e.g. MCL)

- Growing Point Language
- (Coore)

- Robust gradients?

## The Challenge of Amorphous Computing

- To reliably obtain a desired behavior by engineering the cooperation of myriads of computing elements, without assuming any precision interconnect or precision geometrical arrangement of the elements.
- To invent the computational substrates that can support this kind of engineering

## The Old-fashioned Way

## The Amorphous Way

## END

## Chemical mechanism for inverter

## Intercellular Communications

- Certain inducers useful for communications:
- A cell produces inducer
- Inducer diffuses outside the cell
- Inducer enters another cell
- Inducer interacts with repressor/activator  change signal

## Logic Circuits based on Inverters

- Proteins are the wires/signals
- Promoter + decay implement the gates
- NAND gate is a universal logic element:
- any (finite) digital circuit can be built!

- X

- Y

- R1

- Z

**R****1**

**R****1**

**X**

**Y**

**Z**

**=**

- gene

- gene

- gene

- NAND

- NOT