next->
Robust Methods of Amorphous Self-Repair

Lauren Clement (lclement@mit.edu)
UROP, Summer 2002 with Radhika Nagpal


For most recent description, see:

Lauren Clement, Radhika Nagpal, Self-Assembly and Self-Repairing Topologies (ps) in Workshop on Adaptability in Multi-Agent Systems, RoboCup Australian Open, January 2003.

Introduction

Amorphous ideas provide many insights for emerging technologies such as self-assembling systems, reconfigurable robots and smart materials, all of which try to establish global behavior from the interactions of thousands of unreliable identical parts. For such techonologies to function robustly, it is essential that they be able to adapt to changing conditions. In an amorphous computing environment it is reasonable to assume that individual agents may malfunction, perhaps losing communications ability, losing variable values, or ceasing to function entirely. It is also quite possible that large numbers of processors may be damaged or destroyed by external perturbations. In such instances it would be ideal that the system adjust to and compensate for changes in such a way that its function is preserved.

In this work, I have developed two distinct methods for the self-repair of simple amorphously created spatial patterns. Pattern formation is important in that it provides a clear way to demonstrate organization and differentiation of function. It gives us a useful way to demonstrate control over an amorphous system, in which the success of a program is very easily and visibly recognizable. But perhaps the greatest testiment to the relevance of spatial organization is the prevalence of such structure in biological systems. The fact that single cells reliably develop into highly complex physical beings suggests the great extent to which mechanisms for spatial oranization have evolved. Pattern formation is paramount to the development of any organism, and thus its significance cannot be overstated.
Daniel Coore and Radhika Nagpal have demonstrated how to program an undifferentiated set of processors, identically programmed and distributed randomly on a 2D surface, to self-organize into predetermined complex topological and geometric patterns. Moreover, these complex patterns are produced through strictly local interactions between processors. Although both Coore and Nagpal's methods for pattern creation are robust to failures that occur during the formation process, they are unable to compensate for faults that may occur later on.
By contrast, biological systems show great abilities to repair themselves. Humans and other mammals are capable of repairing many wounds, but are unable to regrow entire limbs or digits. However, cockroaches and other insects can regenerate entire limbs, as can many amphibians. Simpler organisms, such as stentor, planarian and hydra seem to demonstrate almost unlimited regenerative ablility, capable of reproducing an entire organism from a small amount of tissue. Organisms also effectively deal with constantly changing numbers and configurations of cells as they die and are replaced.
A helpful example to consider, and one which has influenced my work, is that of cockroach leg regeneration, as described by Horst Bohn in a series of three papers. In his experiments, Bohn showed that regeneration of a leg will occur when tissue that lies posterior to a leg comes into contact with tissue that lies aterior to a leg. (Such contact naturally occurs when the leg itself is missing, but in this case was induced in laboratory experiments). All that is necessary to trigger regeneration is contact between these two types of tissue, making for a very straightforward mechanism.
It is this kind of simple and elegant repair ability that we wish to bring to amorphously created structures.

Bohn,H. (1974a). Extent and properties of the regeneration field in the larval legs of cockroaches (Leucophaea maderae). I. Extirpation experiments. J. Embryol. exp. Morph. 31, 557-572

Bohn,H. (1974b). Extent and properties of the regeneration field in the larval legs of cockroaches (Leucophaea maderae). II. Confirmation by transplantation experiments. J. Embryol. exp. Morph. 32, 69-79

Bohn,H. (1974c). Extent and properties of the regeneration field in the larval legs of cockroaches (Leucophaea maderae). III. Origin of the tissues and determination of symmetry properties in the regenerates. J. Embryol. exp. Morph. 32, 81-98



The Problem
Given an existing spatial pattern, is there some way to have the pattern maintain or adapt itself if individual processors malfunction, or if a patch of processors is destroyed.
The methods used by Nagpal and Coore create complex patterns by employing a few simple primatives inspired by developmental biology. The key elements of these patterns are lines and endpoints. We believe that if we can make primitives for generating self-repairing lines and endpoints, then we will automatically make complex patterns created from these primitives self-repairing.
My first goal: To develop a mechanism for maintaining connectivity between two endpoints.
-start with 2 endpoints
-grow a line to connect them
-maintain connectivity between the endpoints even if some processors stop functioning
-evaluate the mechanism's robustness and resource usage
two endpoints (shown in red) line connecting endpoints


Solutions
I have developed two different methods for maintaining connectivity:
1)Self-Maintaining Line:
This method uses a constantly updating gradient. If processors malfunction, the gradient changes to reflect this.
The line automatically adjusts to the changing gradient; there is never any explicit detection of a break.
Before:After:


2)Self-Repairing Line:
In this method, the elements in the line monitor their neighbors. When a break is detected, a new gradient is created and the line recconects around the fault.
(note that the line segments from the 'Before' image are still present in the 'After' image, but have been reconnected by new growth)

Before:After:


Contents:

1)Creating the Line
2)Method 1: Self-Maintaining Line
3)Method 2: Self-Repairing Line
4)Future Work


next->