Robustness

The programs executed so far have proven to be very robust and work on completely random distributions as well as smoothed distributions.
The primitive behaviors are robust to imprecise cell placement, asynchronous behavior,  occasional communication failures and random cell death. Robustness is achieved by depending on average behavior, not individual behavior, trading precision for reliability and by composing primitives in a way that minimizes error.
 

Robustness is achieved in the following ways:

Points and Creases : Points and creases are always represented by groups of cells, all of which are equal (no leaders). This provides robustness to random cell death. The width of the points and creases are approx twice the local communication distance, so that a point on average contains a neighborhood and creases tend to have several cells along its width. It is important that the cells be dense enough; we use an average neighborhood size of 15 which works well.

Gradients : Gradients produce good (but not error-free) estimates of euclidean distance, in spite of random cell placement, when the average neighborhood size is above 15.  Average neighborhoods above 20 provide diminishing returns on gradient accuracy. My paper on global coordinate systems gives a detailed theoretical as well as experimental basis for this. Gradients are an extremely robust mechanism. They are robust to occasional message loss, due to the high redundancy of messages. They do not depend on synchronicity of cells. They are insensitive to the number of cells in the source.The errors in the distance estimates are on average radially symmetric and not correlated with distance from the source. Because gradient values are averaged over local neighborhoods, small errors by single cells, failures in cell-to-cell contact, and variations in the shape of points and width of creases tend not to have a significant effect.

Axioms and Composition of Primitives : The axioms are robust to small errors in the gradients because they depend only on relative comparisons, not absolute values. Axioms are tolerant to imperfections in the inputs, such as variable numbers of cells in points and creases, non-circular points and non-uniform width of creases. This is because gradients tend to average out small variations in the source shape, so locality (point) and approximate shape (crease) are sufficient.  In addition, the axioms attempt to produce creases with sufficient cell width, independent of the inputs. Hence imperfections in creases rarely propagate.

Interestingly, axioms 2 and 3 actually compose gradients in a manner that minimizes error. In a single gradient the error is radially symmetric, but when two gradients overlap the interference causes spatial variation in error, with the minimum error along the bisector of the line between the two sources (see figure below) Axioms 2 and 3 operate only along this minimal error region. As a result, even when the processors are placed completely randomly, the creases formed are surprisingly straight as is seen in the grid.  (note: can i prove that the composition has gain?).

Many Gradients: Overall the cell program achieves error tolerance by using many gradients. Errors in a single gradient have limited effect and each axiom creates new gradients to minimize error specifically in the area where the fold will occur. In developmental biology, it also seems that many gradients are used, with genes responding to only one or two thresholds in a single gradient and patterns being generated through the ``combinational regulation'' of many gradients. One might ask if it is for the same reason of robustness.

LEFT: In the top row, processors are placed randomly and independently. In the bottom row, processors are assumed to have some size and the attempt is made not overlap, thus smoothing the distribution.  RIGHT: Shows the intereference between gradients from two points A and B (from AI Memo 1666).

All of the above ensure that a fold happens with high probability. This is important given the nature of origami. A complete failure in one early fold can lead to an abort of the whole structure. The axioms are designed with this in mind - it is imperative that the axioms be extremely robust in the sense that they should not completely fail. On the other hand they may have many imperfections and the composition of the axioms must be able to tolerate imperfections.  Hence the primitives and axioms concentrate on producing acceptable (rather than accurate) answers with very high probability.

Still there is the possibility of failure of a fold. For example a point may have no cells if there are no cells at the intersection of two creases.
Or a fold may fail for mechanical reasons. The assumption is that this will need to be covered at a higher level, i.e. in the origami program.
Also we do not cover malicious cells that may incorrectly emit a gradient at the precise time when the gradient is being used. Somewhat analogous to drosophila double head effect (emit some chemical from the incorrect pole) - could be catastrophic.  It may be possible to  could do some sort of weighted average over the all srcs to avoid this (build up of chemical...)

TODO

• Explain how using relative values vs absolute increases robustness.
• Explain what density is sufficient to ensure points ahve enough cells (high probability that no area has is empty)
• Explain (and PROVE) robustness of axioms to random cell death (axioms 2 and 3 cell autonomous i.e. each cell independently making a decision, axiom 1 the locus of activity keeps shifting each step and each cell makes best decision even if it loses some neighbor messages).
• Explain robustness of the FOLD operation: robustness of folding to malfunctions in some cells, width of cells taking part in the fold, so individual cell is less likely to have an effect on the overall deformation. General  idea - strength in numbers.
• Prove axiom2 composition has gain?
• Prove robustness of region definition to death of cells in creases (or missing sections of the crease)