© 2004 Robert A. Freitas Jr. and Ralph C. Merkle. All Rights Reserved.

Robert A. Freitas Jr., Ralph C. Merkle, Kinematic Self-Replicating Machines, Landes Bioscience, Georgetown, TX, 2004.

3.8 Macroscale Kinematic Cellular Automata (1975-present)

Rigorous research on kinematic replicators is difficult to execute, but is more useful if one is trying to create a physical working model of a self-replicating system. By contrast, cellular automata (CA), in which mere patterns of bits self-replicate, are more computationally accessible to investigators – the theoretical underpinnings are rigorous and well-understood, the start-up costs are low, and the results are often quickly transferable to software having commercial potential such as genetic algorithms, scientific visualization tools, or simulations of complex systems [711]. But CA have less direct relevance to physical models because a physical implementation would lack the ability to move in physical space, since CA are normally embedded in a fixed tessellation environment. A few researchers have tried to combine these two approaches in an attempt to capture the best of both worlds, in effect adding physical mobility to self-replicating cellular automata.

The first advocates of this approach were cellular theorists who started with cellular automata and “kinematicized” them. One of the earliest proponents was Richard Laing, who in a series of papers [559-561] during 1975-1977 proposed a “hybrid cellular-kinematic automaton” which would use strings of cells (one dimensional tessellations) to compute and construct more strings – achieving self-replication – by means of a repertoire of simple mechanical actions between the strings, e.g., sliding local shifts of contact, local changes of state, and local detections of such state changes [561]. Laing clearly envisioned the possibility of a macroscale implementation of his scheme [558] when he wrote: “I can see no reason why an electronic engineer could not easily produce the design of electronic componentry having the required properties to implement a system such as I have described....Whether such a system could be realized in terms of biological components as well I do not know.” Interestingly, Laing’s scheme is primarily a proposal for molecular machines and, as such, is discussed in more detail in Section 4.8, below.

In 1979, CA theorist Armin Hemmerling introduced a model “system of Turing automata” wherein finite automata inhabit a multidimensional tape on which the automata can move around and read and write the tape squares [797, 798]. During 1988-89, Goel and Thompson [799-802] introduced a related approach, known as “movable finite automata,” involving computational entities able to move around and interact with each other in a fixed lattice, and Lugowski [803] described a “computational metabolism” or “liquid computer” in which roving processors called tiles migrate across a tessellation environment like a liquid, recognizing and reacting to their neighbors. In the mid- and late 1990s, CA theorists continued adding new modes of “movement” to cellular automata. For example, the method of “movable cellular automata” [804-806] allows the modeling of materials properties by treating matter as composed of a 3-D array of neighboring “particle” cells with specific interaction rules; reaction-diffusion phenomena and excitable media can be similarly modeled [807]. Adamatzky and Holland [808] have computationally modeled excitable mobile agents moving on a lattice, or “lattice swarm systems.” Sipper [378-380] investigated a 5-cell non-uniform cellular automaton self-replicating loop using cells of atypically high complexity, in a model that allows state changes of neighboring cells and rule copying into them (this latter characteristic can be considered a form of cellular movement). Lohn and Reggia [369-371] introduced a model consisting of movable automata called effector automata, embedded in a cellular space, along with a new method of automata input called orientation-insensitive input, and others have investigated mobile automata [336, 809], lattice-unrestricted “graph automata” [810], and distributed assembly of 2-D shapes [811-814].

In the 1990s, a second wave of advocates appeared – robotics engineers whose training would normally predispose them to the kinematic approach for machine self-replication. Reversing the earlier approach of kinematizing the cellular automata, these engineers began proposing kinematic robotry that could be “cellularized,” in an attempt to simplify the complexities inherent in physical self-replication that von Neumann had first encountered. In his 1996 review, General Dynamics Advanced Information Systems research engineer Tihamer Toth-Fejel [711, 815] aptly termed all these attempts “kinematic cellular automata” or KCA. Such automata would consist of many identical mechatronic modules, organized into a dynamically reconfigurable system and implemented in the physical world.

It would take a relatively large number of identical KCA cells to make up a physical replicator. With conventional cellular automata, the individual cells cannot move and can only change state, and patterns move across a static array. In contrast, the KCA mechatronic design allows individual physical cells – not just patterns – to move with respect to each other, permitting the physical swarm to change shape just like the virtual patterns in cellular automata. Because they are derived from the CA field, KCA aggregates have the advantage of being more naturally fault tolerant and more flexible than non-modular or unitary kinematic robots, and the KCA are more structured in the interactions between individual cells. (Principal disadvantages are that the individual KCA cells must be fairly complex, compared to the typical unitary kinematic machine “part,” and that in most designs the KCA aggregate is not capable of manufacturing its own component cells from more primitive parts.)

Proposals for KCA replicators typically envision a very large number of basic cell units operating in parallel, that can replicate a given geometric or lattice arrangement of those same cell units. Confirmed early design proposals (many of them apparently independently conceived without direct knowledge of the others’ work) include Kokaji’s “fractal mechanism” work at AIST in 1988 [817], Hall’s well-known utility fog* with 100-micron “foglet” robots (Figure 3.16) in 1993-1995 [818-820], Chirikjian’s “metamorphic” robots [1281] in 1993-1994, the “Fractum” self-repairing machine at AIST during 1994-1999 [821-823], Michael’s fractal robots or “programmable matter” (Figure 3.17) in 1994-1995 [816, 824], Hasslacher and Tilden’s “self-assembling colonies of micron-scale biomorphic machines” in 1994-1995 [185], Bishop’s XY active cell aggregates or ACA (Figure 3.18) in 1995-1996 [825-828] (Section 4.12), Toth-Fejel’s KCA cells in 1995-1996 [815], Freitas’ programmable surfaces in 1995-1996 [2886], and the replicating swarm of Globus et al [224] in 1997-1998 (Figure 3.19), plus one unconfirmed report that Thorson [829] described “assemblies of tiny machines that flexibly coordinate to form human-scale objects” in 1991.** Only one of these proposals, by Bishop [828] (Section 4.12), envisioned additionally the assembly of individual KCA cells from more primitive parts (Figure 3.20), thus extending the capability of the KCA replicator concept beyond the mere replication of selfsame building-block patterns. However, Yim et al [830] have alleged that microscale KCA systems built from cubical modules (as in the schemes of Michael and Bishop) might have significant disadvantages, for example, in that “rolling/rotational motions are preferable to sliding motions because they can have less friction, which becomes very important as systems scale down in size.” Chen [831-833] also studied modular reconfigurable robotic system assembly configurations in the early 1990s.

* The American inventor Thomas Alva Edison apparently anticipated at least a part of the functionality of utility fog at a dinner talk [834] as long ago as 1890: “...as if out of a great revery, saying what a great thing it would be if a man could have all the component atoms of himself under complete control, detachable and adjustable at will. ‘For instance,’ he explained, ‘then I could say to one particular atom in me – call it atom No. 4320 – “Go and be part of a rose for a while.” All the atoms could be sent off to become parts of different minerals, plants, and other substances. Then, if by just pressing a little button they could be called back together again, they would bring back their experiences while they were parts of those different substances, and I should have the benefit of the knowledge.’” Following this, Landers [835] discussed modular building block based robots in 1966, Erber et al [836] studied pattern replication in arrays of magnetic blocks in 1969, Toffoli and Margolus [332] in 1987 and Rasmussen et al [368] in 1992 wrote of “programmable matter” in a slightly different context, and Okuma and Todo [837, 838] analyzed assembly methods using cubic blocks as primitives at least as early as 1993.

** Toth-Fejel [815] speculates that the use of microscopic KCA cells could explain some of the capabilities of the sometimes human-shaped, liquidlike, evidently nanotechnology-based [825, 839] fictional T-1000 robot in the science fiction movie Terminator 2 [840] – who, Toth-Fejel opines [815] (after discussions with Bishop [825]), could have survived its fall into the vat of molten steel in the final scene by making fuller use of its own technology, as follows:

(1) Balance-sensors and accelerometers in undamaged areas of the robot sense that it is about to fall, causing a pre-programmed panic sequence to order a lowering of the center of balance and an extrusion of micro or macro hooks from the feet into the floor.

(2) The same sensors detect the weightlessness of falling, and the pre-programmed panic sequence orders the KCA cells to form into a parachute; hot air rising from the molten steel lifts the robot out of harm’s way.

(3) Depending on the degree of central control required (given that the T-1000 was damaged and degrading fast), the robot could have sprouted wings and glided to safety.

(4) Upon contact with molten steel, temperature sensors actuate a pre-programmed panic sequence to quickly reconfigure refractory-material cells at its surface into a foamy air-trapping structure, providing the same heat insulation qualities as space shuttle tiles; since molten steel is quite dense, and the machine appears not to be made of solid polymetal (otherwise its weight would have broken through most transportation vehicles, second-story floors, elevators, etc.), the robot could have simply walked across the surface of the vat, to safety.

(5) Force sensors keep interconnection mechanisms between cells from damage by ordering cells to disconnect whenever the strain gets too high, thus dissipating the energy of bullets over time and distance (something like shooting at gelatin) rather than allowing bullet impacts and deformations as shown in the movie.

(6) Miniaturized radar systems (already available today) detect the incoming explosive bullet with enough accuracy to predict its trajectory, allowing portions of the T-1000 along that path to slide aside so the bullet passes unimpeded through the robot, eliminating the need to dissipate the kinetic energy of the bullet.

(7) An onboard cell-fabricating facility allows the robot to exploit the existing industrial infrastructure to make more KCA cells, both for self-repair (by replacing damaged cells) and for self-replication (thus overwhelming any non-replicating opponent).

The experimental field of modular robotics (that could enable the physical realization of the aforementioned theoretical KCA replicators) has exploded in recent years, with many new designs proposed and a number of prototypes built in hardware, starting in the late 1980s and early 1990s. One of the earliest examples was the cellular robotic system (CEBOT) pursued by Fukuda’s group [841-849] in Japan, starting in 1987. CEBOT is a dynamically reconfigurable robotic system composed of diverse robotic cells combined in different configurations. Each cell-robot is autonomous and mobile, able to seek and physically join other appropriate cells. Fukuda has used CEBOT (and more recently MARS or micro autonomous robotic system [850]) to investigate multi-purpose end-effector systems, self-organization, self-evaluation of robot cells, communication among robots, and control strategies for group behavior [603].

Mark Yim and colleagues [853] designed and built multi-robot polypods [851, 854] at Stanford in 1993-1994 (Figure 3.21(A)), continuing in 1998-2001 with polybots [852] for DARPA at Xerox PARC (Figure 3.21(B)). Yim’s polybots are capable of significant physical reconfiguration with some teleoperation assistance from human operators (Figure 3.22), though of course they cannot build new primitive units from smaller components. In between these efforts, Yim’s group briefly pursued “a self-assembling robotic system capable of approximating arbitrary three dimensional shapes utilizing repeated rhombic dodecahedron shaped modules,” and demonstrated algorithms which, at least in simulations, transformed a square plate of 441 modules into a teacup shape in 1808 steps and 625 modules into a hollow sphere in 3442 steps [830]. Hardware prototypes of these “polymorphic cytokinetic quasi-fluid crystallic robots” [855] (so-named somewhat tongue-in-cheek, according to the researchers) were reportedly under construction in 1997,* with each robot module to have 48 shape memory alloy actuators including 24 for edge motion rotations and 24 in six groups of four to achieve dynamic shape modification [830].

* According to Tad Hogg [856], this design turned out to be too complicated (needing actuators for 12 faces) and was not continued to any functional hardware, although a few passive devices with magnets were built that a person could manually reconfigure to illustrate how such robots would work if they were ever built. Hristo Bojinov was instrumental in simulations involving local controls, as opposed to a high level controller that told each module where to go. The simulation results with these robots, e.g., making branching structures, growing around objects, etc., are described in Bojinov et al [857], and nicely illustrate the contrast between broadcast control and local control.

Yim and colleagues in the Xerox PARC modular robotics group have also produced 3-D “telecube” modules (Figure 3.23) [858-865] which are cube-shaped modules 5 cm on a side with faces that can telescope outward by 36-40 mm, thus doubling the length of any dimension while applying a thrust force of ~12 N. Each face can contract (Figure 3.24(A)) or expand (Figure 3.24(B)) independently, with a reversible magnetic latching mechanism to attach or detach from any other face of a neighboring module with a holding force of ~25 N, sufficient to resist a torque of 0.75 N-m between adjacent cubes. To reconfigure a telecube lattice (Figure 3.24(C)), a module at one site on a virtual grid detaches from all modules except one. By extending (or contracting) the faces that are attached to it, the module moves to the neighboring site.

Chirikjian [1281-1283] and Murata et al [821] have separately simulated and built planar hexagonal robots that roll around each other. While neither addressed experimentally the decentralized self-assembly of arbitrary 3-D shapes [830], Chirikjian’s vision of self-reconfigurable [867] or “metamorphic” [1281] robots (at the Johns Hopkins University Robot Kinematics and Motion Planning Lab [868]) clearly anticipates this: “A metamorphic robotic system is a collection of mechatronic modules, each of which has the ability to connect, disconnect, and climb over adjacent modules. A change in the macroscopic morphology results from the locomotion of each module over its neighbors. That is, a metamorphic system can dynamically self-reconfigure. Metamorphic systems can therefore be viewed as a large swarm of physically connected robotic modules which collectively act as a single entity.” (Freitas’ “metamorphic surfaces” concept (Nanomedicine [228], Chapter 5) in the medical nanorobotics field is similar.) Michael [869] has constructed several simple operating prototypes of his cubical “fractal robots” design, using blocks 12 inches and 5 inches in size. The “Fractum” machine developed at AIST [823] is claimed to be the first modular mechanical system to demonstrate self-repairing capability using more than ten modules. Other modular mechatronic robotic systems include:

• CONRO (Figure 3.25) at USC/ISI [866];
• the Crystal Robot [871-874], Molecule Robot [875, 876], and the “desktop mobile manipulators” [877] at the Dartmouth Robotics Lab [878];
• 3-D modular units for self-assembly of desired shapes (Figure 3.26) at the Mechanical Engineering Laboratory in Japan [822, 870], a kind of macroscale utility fog (cf. Figure 3.16);
• the LEGO®-based autonomous robot teams (MinDART) at the University of Minnesota [879];
• the tetrobot modular reconfigurable robot at Rensselaer Polytechnic Institute [880-884];
• the reconfigurable modular manipulator system (RMMS) of the Advanced Mechatronics Laboratory at Carnegie Mellon University [885];
• the DARPA Microrobot Project at Michigan State University [886];
• the modular self-reconfigurable robot M-TRAN or Modular TRANSformer [887-889] (Figure 3.27) from the Intelligent Systems Institute, National Institute of Advanced Science and Technology (AIST);
• a miniaturized modular machine system using shape memory alloy, also at AIST [890-892];
• the European Swarm-bots Project [893];
• the Linux radio robot, solarbot, and ant-like robots of the Intelligent Autonomous Systems Engineering Laboratory of the University of the West of England [894];
• the HYDRA Project of the Artificial Intelligence Laboratory at the University of Zurich [895];
• the Amoeba Robot project at the Autonomous Systems Engineering Laboratory at Hokkaido University [896];
• the Random Morphology Robot Project at the University of Dortmund, Germany [897], and the self-reconfiguring robots for morphogenesis of Hosokawa et al [898];
• the PIRAIA Project at the Swedish Institute of Computer Science [43];
• a large number of other modular snake [899-901] and segmented [902] robots; and
• the ICES Cubes or I-Cubes system (Figure 3.28) at the CMU Robotics Institute, a collection of independently controlled mechatronic modules (links) and passive connection elements (cubes) [903-905].

Closely related research areas such as distributed robotic systems [906, 907], multirobot systems [906, 908], and swarm robotics generally [909-913] may also be relevant but are beyond the scope of this book.

Another interesting project in 1995-1996 was the development of a computer-controlled LEGO® factory – itself made entirely of LEGO® components – that could build LEGO® cars. The LEGO® factory project was conducted at the CODES Lab in the Electrical and Computer Engineering Department at the University of Massachusetts [914] and began as an Electrical Engineering senior design project inspired by a similar project at Linkoping University, Sweden. The effort was supported by an NSF grant and involved at least 7 students and 5 professors from the University of Massachusetts, Boston University, and Harvard University. The factory (Figure 3.29) was computer-controlled, incorporated up to 16 sensors and a number of motors, and assembled the LEGO® cars in 7 steps. The factory is “an interesting demonstration of a simple, small-scale system capable of handling and assembling the same type of parts that make up the system.” [915] The students’ future plan [914] was to add “decision-making functionality and the ability to flexibly manufacture multiple products,” although the explicit pursuit of self-replication was never stated as a goal before the project ended. The factory itself was not capable of self-replication.* A LEGO® model of a steel production factory has also been done in the “Lego Lab” at the University of Aarhus [916].

* The first mention of this possibility in the literature appears to have been made by Mitchel Resnick, who concluded his 1987 discussion [917] of LEGO®-based robotic simulated animals with the following comment: “Eventually (and more speculatively), LEGO®/Logo could evolve into a type of universal constructor. One can imagine a LEGO®-based automated factory, in which LEGO® machines construct and program new LEGO® animals – and new LEGO® factory machines. Or, perhaps, the factory machines and the animals should not be viewed as separate categories; perhaps the factory machines are the animals. Obviously, such projects would require complex programs and new types of building materials, including specialized pieces outside of the LEGO® repertoire. Such projects will probably not be feasible for many years – if ever.” Just 14 years later, this “not...feasible...ever” project was accomplished experimentally (Section 3.18).

LEGO® is becoming popular for mechatronics hobbyists [918]. Other LEGO®-based replicator projects are currently underway (Sections 3.22 and 3.23) and one of these has succeeded in building the first LEGO®-based self-replicating machines (Section 3.23). The authors are unaware of any similar efforts using other popular minimal parts-set construction toys* such as Erector® [919] or Meccano® [920], although in 1975 a mechanical computer that could play tic-tac-toe was constructed at MIT [921] using Tinkertoys® [922].

* There have been over 500 imitations of Erector® and Meccano® in over 40 countries [923] (with at least 10 still being made today), including [923-926] American Model Builder, Ami-Lac (Italy), Bing’s Structator (Germany), BRAL (Italy), Buildo, Construction C10, Construct-O-Craft, Elektromehaniskais konstructors (Russia), Exacto (Argentina), Ezy-Bilt (Australia), FAC (Sweden), Junior, Lyons, Make Your Own Toys, Marklin Mehanotehnika (Slovenia), Metall (Germany), Mekanik (Sweden), Mek-Struct (China), Merkur (Czech., renamed Cross), Metallus, Mini Meta-Build (India), Modern Morecraft, Necobo, Palikit, Pioneer, Primus Engineering Outfits (England), Schefflers, Stabil (Germany), Steel Engineering (U.S.), Steel Tec (China), Stokys (Switzerland), Structo (U.S.), Structomode, TECC (Czech.), Teknik, Takno (Norway & Denmark), TemSi (Netherlands), Thale Stahlbau Technik (E. Germany), The Constructioneer, The Engineer (Canada), ToyTown, TRIX (Germany), Trumodel (U.S.), Vogue (England), Wisdom/Sagesse (China), and ZigZag. Other less-popular construction toys [926] include American Plastic Bricks, Anker, Bayko, BILOFIX, Blockmen, Brik-O-Built, Brio, Bristle Blocks, Builderific, Cuburo, CoinStruction, Constux, Easy Fit, Eitech, Fiddlestix, Fischer Technik, Fractiles, Frontier Log Building, GEOMAG, Hexlo, Expandagon, ImagiBRICKSTM, JOVO, KAPLA, Knex, LASY, Liberty Logs, Lincoln Logs, Lokon, Manetico, MegaBloks, Nice-Dice, Plastikant, PlayMobile, Quadro, Rhomblocks, Richter’s Anchor Blocks, Robotix, Rokenbok, Stanlo, Steelbuilder, Toobers & Zots, Zolo, and Zome System.

Toth-Fejel [711] envisions a self-replicating system composed primarily of a robot arm made up of KCA cells. A well-defined grid of KCA components would surround the replicator, with each cell containing sensors, actuators, and a central processor, all of which could be simulated at a kinematic level. The next step would be to build a working prototype, using stereolithography or similar rapid prototyping techniques [927-933]. To achieve further cost reductions, off-the-shelf parts would be used whenever possible to build physical prototypes. Toth-Fejel recommends starting a KCA development effort with simulations involving a very rich environment of parts. In other words, the entropy of the surroundings, the number of parts that make up the replicator, and the number and complexity of the assembly steps should all be minimized, while the complexity of the parts themselves should be maximized. After success is achieved using the initial replicator in a rich environment, the number of parts and assembly steps should be doubled in the replicator, while the complexity of each part in the environment should be halved, and self-replication again attempted. This iterative process should then be continued (in the manner of Moore’s Law in semiconductor chip design), until either complete success is achieved or insurmountable obstacles are encountered, with the goal of working toward complete KCA autotrophy in which the replicator can assemble itself from the most primitive KCA cell components. Once such componential autotrophy is achieved, the next task would be to find molecular analogs for all the components, and work towards true molecular autotrophy while respecting public safety guidelines (Section 5.11). In keeping with the idea of approximating the real world with greater detail, the amount of disorder in the environment should also be increased as the experiments progress.

Much like the ideal array of individual nanorobots comprising the programmable dermal display proposed in 1999 by Freitas (Nanomedicine [228], Section 7.4.6.7), Tilden and Lowe [936] have suggested that “it is potentially feasible to manufacture nanorobots that are capable of sophisticated symmetric behaviors, either through independent function or by assembling themselves into collective units....for example, high-resolution video screens that can repair themselves simply by having a microscopic robot at each screen element. These ‘pixelbots’ would be capable of producing light, but smart enough to remove themselves from the video array should they ever fail. Other pixelbots would sense the vacancy left by any defective device and reorganize themselves to fill the hole.” Such arrays could replicate patterns in the manner of cellular automata.

Hasslacher, Tilden, J. Moses and M. Moses [185, 937-940] have investigated “autonomous self-assembling robotic mechanisms” in the context of groups of robots of various different species that vie for control of energy resources in order to “survive.” In 1994, Hasslacher and Tilden [185] (Section 5.1.3) operated a Robot Jurassic Park (Figure 3.30) “where over 40 robots of 12 different solar powered species have been running continuously for over 6 months....There has been evidence of flocking, fighting, cooperative group battles against particularly aggressive forms, even pecking-order dominance, but little in the way of true cooperation that would indicate hive structure stability for such devices....Further work would have to be done in sensor technology so that like creatures would be able to recognize others of their own hive.” During 1995-6, Tilden (with Moses) [937-939] operated their own version of the robotic Jurassic Park in which “new control systems have been devised to allow these devices to power-mine their environment exploiting the available light-energy sources without having to resort to internal batteries. Future work will examine and promote the development of these mobile machine components so that they may act as coordinating organs in sophisticated robots for application-specific tasks, creating a form of ‘living LEGO®’ with inherent self-repair and self-optimization characteristics.” More recent work has found some evidence of primitive territory formation in populations of mobile robots [941].

Last updated on 1 August 2005