What is Self-Replication?
The definition of self-replication is not trivial.
Adams and Lipson (2003) have produced a 'domain independent metric of self-replication', They define a function RS that "looks at how present a configuration S becomes when it was at one point specifically in the environment, compared to its presence without being in that environment. If RS is zero, then the inclusion of S neither adds nor detracts from the future presence of S. A positive value of RS indicates that including the system results in a higher presence of the system in the future, i.e. the system appears to be self-replicating." Intuitively this is satisfying. We would like to call an object self-replicating to the extent that it produces more copies similar to itself in a given environment, compared to the case where no copies of itself were initially present in an otherwise identical environment. The application of the formal method is limited by being able to define what is meant by "similar to itself".
Classificiations of Artificial Self-Replication.
Artificial self-replication has been classified by Sipper, who gives the publication phylogeny shown below, taken from Sipper (1998).
Self-Replication and Limited Heredity in a Stochastic 1D System.
Even after 48 years, this 1957 paper stands out. Roger and Lional Penrose published in Nature, describing the simple stochastic self-replicating system shown below, (Figure 1).
A and B are 2D shapes cut out of plywood. They are placed on a thin rack and shaken horizontally, resulting in collisions with the sides of the track and with adjacent pieces. If the AB complex is assembled by hand and placed into the rack, further AB complexes form. Similarly, if a BA complex is assembled and placed into the rack, further BA complexes form. If an AB complex hits an A piece on its left, the A piece rotates anti-clockwise exposing its binding site which if a B piece is to its left, it can attach onto, so forming another AB complex. If a B piece is on the right of an AB complex then it also rotates anti-clockwise but it has no binding site exposed.
The system is of very limited heredity since only two types of complex can be replicated faithfully, AB and BA.
Self-Replication and Less Limited Heredity in a Stochastic 2D System.
Unfortunately, the work of Jarle Breivik is not widely known (Breivik, 2001). It does not feature in any references given in the Artificial Life literature. Yet, his work is a natural extension of the work of the Penroses, and is the only model of template polymerization in artificial systems that has been implemented. Figures from his paper are shown below.
Self-Replication in Cellular Automata
A self-replicating structure in cellular automata is a contiguous configuration of active cells that goes through a sequence of steps to construct a copy of itself. The copy must be displaced and may be rotated, compared to the parent. Trivial self-replicating structures are possible, and may be excluded by specifying that the self-replicating configuration must consist of more than one active cell, and that intermediate configuration changing steps must be involved.
Early models consisted of logical non-physical machines, replicating in a cellular space (Von Neumann, 1966). Von Neumann designed a self-replicating automaton capable of unlimited heredity. Chris Langton (1984) invented a simpler self-replicating automaton, based on a component of Von Neumann's machine. Indeed, Langton's work seeded the field of Artificial Life.
Lohn and Reggia (2000) used a GA to discover self-replicating rules in cellular automata. The design of the explicit fitness function is crucial. The unit of selection was a rule set for an orientation sensitive or orientation insensitive CA, and the initial seed configuration. The input to the fitness function consisted of statistics extracted from the state of the CA over only the first 15 time steps. These statistics were i. the quantity of each component type, ii. the relative positions of each component, iii. and an isolated replicant count (i.e. the number of configurations surrounded by quiescent cells). Self-replicating structrues are expected to have increasing numbers of each component type, the same relative positions of each component type over the 15 time steps as in the seed configuration, and increasing numbers of isolated components. Several self-replicating structures were evolved, see figure 1a. below. Debis forms inside the expanding colony.
Figure 1a. From Lohn and Reggia (2000). Evolved self-replicating cellular automata, leaving debris in the central wake.
Arbib, M. A. (1966), "Simple Self-Reproducing Universal Automata," Information and Control, vol. 9, pp. 177{189.
Byl, J. (1989), "Self-Reproduction in Small Cellular Automata," Physica D, vol. 34, North-Holland, pp. 295{299.
Chou, H. H. , Reggia, J. A. (1997), "Emergence of Self-Replicating Structures in a Cellular Automata Space," Physica
D, in press.
Chou, H. H., Reggia, J.A. (1997), \Problem Solving During Artifcial Selection of Self-Replicating Loops," Physica D, in
press.
Holland, J. H. (1976), "Studies of the Spontaneous Emergence of Self-Replicating Systems Using Cellular Automata and Formal Grammars," in Automata, Languages, Development, A. Lindenmayer and G. Rozenberg, Eds., North-Holland, pp. 385-404.
Langton, C.G. (1984), "Self-Reproduction in Cellular Automata," Physica D, vol. 10, pp. 135-144.
J.D. Lohn, J.A. Reggia, "Exploring the Design Space of Artificial Self-Replicating Structures," Evolution of Engineering and Information Systems and Their Applications, L.C. Jain (Ed), CRC Press, 2000, pp. 67-103. Download pdf.
Moore, E.F. (1962), "Machine Models of Self-Reproduction," Proc. Fourteenth Symp. on Applied Mathematics, pp. 17-33.
Penrose, L. (1958), "Mechanics of Self-Reproduction," Ann. Human Genetics, vol. 23, pp. 59{72.
Pesavento, U. (1995), "An Implementation of von Neumann's Self-Reproducing Machine," Arti cial Life, vol. 2 no. 4, pp. 337{
354.
Ray, T.S. (1992), "Evolution, Ecology and Optimization of Digital Organisms," Santa Fe Institute Working Paper 92-08-042.
T. S. Ray (1991), "An Approach to the Synthesis of Life," in [22], pp. 371{408.
Smith, A.R. (1991), "Simple Nontrivial Self-Reproducing Machines," in [22], pp. 709{725.
Vit anyi, P. M. B. (1973), "Sexually Reproducing Cellular Automata," Mathematical Biosciences, vol. 18, pp. 23{54.
von Neumann, J. (1966), Theory of Self-Reproducing Automata, A. Burks, Ed., University of Illinois Press.
Self-Replication in Non-Uniform Cellular Automata
Moshe Sipper invented non-uniform cellular automata, which are cellular automata in which the CA-rules are local to each cell and can be copied onto neighbouring cells. Non-uniform CA rules can be designed to model conservation of mass.
Self-Replication in Tierra
Self-Replication in Avida
Self-Replication of Molecube Objects.
Hod Lipson's team at Cornell have recently produced a mechanical self-replicating object, see figure 2 below. A range of experiments have been conducted using the physical structure of the molecube as a basis. Mytilinaios et al (2004) have evolved controllers for a self-replicating molecube modular robot, in simulation using a domain specific fitness function. The use of explicit fitness functions in genetic algorithms to select for self-replication, has previously been explored by Lohn and Reggia (2000) using a fitness function which has more general applicability.
Figure 2. From Zykov et al (2005). The molecube is a 10cm cube, split along its diagonal and able to swival. Each cube contains electromagnets that can form attachments to other cubes, so that when swivelling occurs, the attached cubes may move. If cubes are added by hand to replenishment sites on the floor at the right times, the initial stucture is able to self-replicate.
Self-Replication in a Molecube Based Non-uniform Automaton.
Greg Studer (2005) has produced a non-uniform CA model of the molecube in 2D, and shown that in a 2D world in which CA rules are passed between contacting blocks, that when random stochastic mutation of rules is introduced, CA rules capable of producing stable aggregates of blocks evolves. If aggregate formation is prevented by introducing an extra rule that prevents arms consisting of more than 10 blocks from swiveling, then the system does not reach a stable state and appears to produce rules capable of self-replication, although this has not been conclusively demonstrated in their paper. The type of mutation, global (random location) or overwrite (i.e. occuring at first contact) effects the 'ecology' of the system, see figure 3 below.
Figure 3. From Greg Studer and Hod Lipson. Molecubes in a large 2D world. Different colours represent different rule sets. (Top) Overwrite-mutations. (Bottom) Global mutations.
Self-Assembly in Stochastic Self-Reconfigurable Cellular 'Robots'.
White et al (2004) describes how many deterministic modular robots such as Lipson's exist. For example, Polybot, Rus and Vona's modular robots, Rus' Robot 'Molecules', Fracta, MTRANIII and Shape Memory Alloy Robots, however, none of these systems demonstrate the sort of stochastic self-assembly shown by Penrose's 'robots'. The stochastic microscale and nanoscale self-assembly systems that do exist are not reconfigurable (Jackman et al 1998), (Winfree et al 1998), and do not self-replicate. White's aim has been to produce microscale reconfigurable machines acting under stochastic brownian motion. They have achieved this for simple shapes in simulation, but have only produced 3 body L shapes and lines in the a real system. Diffusion limitiation is a problem for stochastic assembly of large components.
Penrose's plywoods.
Non-Uniform Cellular Automata.
Tierra
Avida
Physical Molecube
Studer Molecube Model.
TABLE 1. Comparing artificial self-replicating objects.
Bibliography.
Breivik, J. Self-Organization of Template-Replicating Polymers and the Spontaneous Rise of Genetic Information. (2001). Entropy, 3, 273-279. Download pdf.
Bryant Adams, Hod Lipson. A Universal Framework for Self-Replication. Download pdf.
Hod Lipson & Jordan B. Pollack. Automatic design and manufacture of robotic lifeforms. Download pdf.
Efstathios Mytilinaios, David Marcus, Mark Desnoyer and Hod Lipson, (2004) “Designed and Evolved Blueprints For Physical Self-Replicating Machines”, Ninth Int. Conference on Artificial Life (ALIFE IX), pp. 15-20 Download pdf.
L. S. Penrose & R. Penrose. A Self-reproducing Analogue. Nature 4571:1183 (June 8, 1957). view here.
Sipper, M. Fifty Years of Research of Self-Replication: An Overview .Artif?icial Life 4: 237–257 (1998). Download pdf.
Studer G, Lipson H., (2005) "Spontaneous emergence of self-replicating, competing cube species in physical cube automata", GECCOLate Breaking Paper, to appear. Download pdf.
White P. J., Kopanski K., Lipson H. (2004), “Stochastic Self-Reconfigurable Cellular Robotics”, IEEE International Conference on Robotics and Automation (ICRA04), pp. 2888-2893. Download pdf.
Zykov V., Mytilinaios E., Adams B., Lipson H. (2005) "Self-reproducing machines", Nature Vol. 435 No. 7038, pp. 163-164 Download pdf.