Institute of Atomic-Scale Engineering


A Description of a Universal Assembler

 By Forrest Bishop

The following appeared in the Proceedings, IEEE International Joint Symposia on Intelligence and Systems, Nov 4-5, 1996 Rockville, MD, USA
ISBN 0-8186-7728-7 - Copyright (c) 1996, Forrest Bishop, All Rights Reserved.

Abstract

An "Active Cell Aggregate", or "Shape Shifter", is an aggregation of similar, space-filling polyhedral machines, preferably built by molecular nanotechnology methods. "Active" means each machine, or "Active Cell", has the capacity to exchange power and signals with other similar machines, and to interact with the external environment.A robot constructed in this manner can have a very large and detailed envelope of motion. By incorporating simple manipulators onto the various faces of the polyhedron, a universal assembler, or "Overtool", may be possible, for molecular, mesoscopic, and macroscopic assembly.

1. Introduction

1. The Active Cell Aggregate

An "Active Cell Aggregate" (ACA), or "Shape Shifter", is an aggregation of similar, space-filling polyhedral machines, each capable of moving with respect to its adjoining neighbors, singly or in groups, preferably built to atomic precision [1,2], {Figure 1}. "Active" means each machine, or "Active Cell", has the capacity to exchange power and signals with other similar machines, and to interact with the external environment. The cells are connected face-to-face. These cellular machines can be thought of as essentially cubical, though all space-filling polyhedral aggregates (e.g. the prisms, tetrahedra, etc.) that contain internal sliding planes are candidates. In this article, only the cubical form is considered. The scale of the cells (the "cell metric") is assumed to be on the order of 100 nanometers (mesoscopic), though much of the discussion would apply to cells of any size.

 A distinction is drawn in the method of interfacing the cells between cells that can only slide apart, and cells that can either slide or simply detach from one another. The first is a cell with mechanical interfaces on each of the six faces, that are capable of sliding two connected cubes in one of the two directions parallel to the joined faces, and parallel to the edges of those faces. The two faces of each sliding cube that are parallel to the motion and per-

pendicular to the join plane remain flush to the corresponding faces on the other cube. The cubes are unable to detach the two joined faces by movement normal to the plane of the joint. They can only move in one of the two permitted directions at a time, and must be aligned with four faces flush in order to change direction. These are "XY cubes" [2,3], {Figure 2}. Here 'XY' (and 'Z') refers to the local coordinate system of the particular face of the cell under consideration, not to any global coordinates.

The second type of cube has the same specifications as an XY cube, but with the additional capability to detach faces normally. These are "XYZ cubes" [4]. As this feature leads to a number of additional complications and failure modes, it will not be considered here. This distinction leads to a number of differences in how the cell can move in an aggregate, as well as differences in manufacture. In neither case do the cubes rotate in any way with respect to one another..

The XY cube requires a maximum of two extra moves to uncouple two faces normally as do XYZ cubes. The first move is to slide {the cube to be detached from} sideways, at which point the desired cube is free to move. The second extra move is to slide {the cube that was de-

 Figure 1 (Features)

 tached from} back to its original position. This can be seen by tracing the trajectories in the two dimension, five cube configuration space, for example {Figure 3}.

In either case, the standard active cell has, in addition to the mechanical interfaces, methods of receiving and transmitting power and signals from any face, to any face, along with the necessary interfaces for this on each face. Power and signal may be electrical, chemical, mechanical, acoustic, and so forth. Drive mechanisms on each face are required to move the cells. Cells in motion with respect to the power supply need to be able to continue receiving power in order to carry out some of the maneuvers mentioned below. This is accomplished with sliding contacts for the electrically powered type. Each active cell should have some onboard digital processing capability (just how much is a subject of current interest).

1.2 An MNT active cell

For the purpose of illustration, a particular XY cube, Molecular Nanotechnology (MNT), active cell was designed and characterized [3]. This baseline design has a nominal edge length, or cell metric, of 167 nanometers. The structural material is of the diamondoid class, assembled by the putative methods of molecular manufac-

Figure 2 (explode)

turing [1]. Each active cell contains an embedded digital controller to perform various housekeeping functions, as well as to communicate with its neighboring cells {Figure 2}.

When two XY cubes are interfaced and aligned, some method of locking them together is desirable. The baseline design uses four tapered, retractable locking pins extending from one cell to complementary receivers in another. There are other mechanical methods of accomplishing the same thing.

The mechanical interfaces consist of orthogonal "T-slots" cut into a face of a cube. The slots are parallel to the edge of the face, and actually form "T-posts" when both sets of slots are considered. There are two complementary sets of these T-posts, and each cube has one type ("active faceplate") on three of its adjoining faces, and the other type ("passive faceplate") on its other three adjoining faces. Although the number of T-posts is somewhat arbitrary, the reference design uses nine T-posts on the active faceplate, and 16 T-posts on the passive faceplate.

The bearings between two cells consist entirely of atomically perfect, sliding surfaces sans lubrication. There is some question as to what the frictional forces would be for such surfaces (as estimated in [1]), but recent experiments [5] yield results in a usable range. The simplicity of this design produces a cell with no breaches in its walls, and reduces or eliminates the chances of jamming from foreign material. This method of construction may produce a machine that does not ever wear out.

These features of an XY cube introduce a chirality to the aggregate, and a specific orientation for mutual interfacing. As there are no permitted modes of rotation, this internal orientation is maintained regardless of the configuration of the aggregate. An active face is therefore always adjoining a passive face.

There is, in addition to the controller, an internal electromechanical "interface switch" for power and signals. Energy is delivered to the cell electrically, via roller contacts. The drive system for this particular design is a type of linear electrostatic motor, in which dielectric material is successively drawn into the gaps between the two plates of a switched row of capacitors.

As the electrical lead and contact resistances cannot be fully characterized, a programmable voltage multiplier is incorporated to keep the cell-to-cell energy transfer at the nominal voltage. This imposes a major signal propagation delay, which might be decreased, even to the theoretical limit (with superconductors), in a more refined design.

The interface switches, by permitting a variety of conduction paths, can be used to set up a multiple path, parallel power distribution network within the ACA. The high resistance of small diameter wires is then somewhat mitigated. The additional programming to accomplish this has not been investigated.

 A "Motion Primitive" is a single cell move of one cell length in an allowed manner, or a connected group of cells moving by one cell length [2]. The cell(s) begins and ends in the aligned rest position.

There are two different cases of interest here, owing to the chirality of the aggregate. In one case, a cell with an active face is moved by one cell length from a rest position on one passive face, to a rest position on an adjacent passive face. The passive-faced cells are assumed at rest with respect to the power supply and central controller (if there is one). In the other case, it is a passive face moving across two active faces which are at rest. In general, there can be "fixed" cells connected to the three other sides of the moving cell that are parallel to the desired displacement. This will not be considered in the following analysis, which is simply to look at what is minimally involved in moving a cell.

In the first case, the cell (or connected group of cells) to be moved might be interrogated to establish handshaking and verify its functionality. Instructions are sent (in this simple case) to the active-faced cell to move over by one cell. The moving cell is providing the motive force, which requires (in this design there is no dedicated onboard energy storage) receiving power from the fixed passive face via two of its retracting pins. To move, the two pins not involved in energy transfer are fully retracted. The first set of drive plates is charged, and then the two contacting pins are withdrawn in a controlled fashion. It is necessary for the cell to begin its displacement before these two pins are completely withdrawn from the holes in the passive faceplate to prevent jamming the cell. Note that this is not strictly necessary if there are fixed cells on either side of the moving cell.

When the moving cell determines, via its position feedback system, that it has moved as far as possible with its first set of drive plates, it then applies power to the next applicable set, and grounds the first set. This procedure is then repeated as the cell moves toward its new rest position.

When a spring-loaded locking pin/contact reaches an undesired receiver, it has to be actively prevented from dropping. This may be done with "clearing pins" in the passive faceplate. The layout of the conductors is such that one pin is always in contact with the interface conductors on one of the two involved passive faceplates.

As the cell approaches the aligned rest position, the tapered locking pins will drop into their receivers. There is a position where no power is being delivered to the moving cell, as the pins are dropping. This does not seem to be a problem, as there is energy stored in the drive system and the voltage boosters.

In the second case, two active-faced cells are moving a passive-faced cell, which does not have to do anything.

2. Modeling and programming

2.1 Figure games

For any given number of connected cells (an aggregate), there is a finite number of possible configurations. This set is referred to here as "configuration space" [2]. For any give initial configuration [A], there are one or more possible paths to transform the cell aggregate into a final configuration [B]. This is the [A]-> [B] problem. Note that different orientations of the same configuration are treated as separate entities. This is because the aggregate is assumed to be operating in the real world, where this matters.

These paths are trajectories in the configuration space, or "figure games" {Figure 3}. The line connecting one figure to another is a "motion primitive", consisting of a single cell move (light lines) or a single block move (heavier lines). So then, a connected sequence of motion primitives forms a figure game.

As can be seen from figure (3), there can be many possible figure games to get from [A] to [B], but only a small subset of these are minimal. It may be that at between 100 and 200 cells in an aggregate, the total number of possible figure games exceeds the number of possible chess games.

This type of analysis is therefore intractable for even relatively small numbers of cells. It can however provide some insight and guidance into partial solutions to the general problem. It would simplify the master software to establish "artificial termini", or "rest configurations", which the cell aggregate has to pass through Although this may cause certain configurations to no longer be attainable, it also decreases the permissible number of figure games.

These configuration space diagrams can also be of use in discerning rules for generating minimal figure games. As a simple example,figure (3) shows that to move from squarelike to rodlike, the block move should be made first. This principle may be extensible to the general case, and is used implicitly below.

Figure 3 (fivecube)

If these solvable configuration diagrams are applied to the entire aggregate, a constrained general solution of [A]-> [B] might proceed as follows: (this is [A]-> [X]-> [B])

1) Use the figure games for 8 cells (this is a solvable set) to assemble 2x2x2 cubes, then 4x4x4 cubes, etc. (these are artificial termini, or "composite cells"). This requires an additional choosing algorithm to decide which cells should go to which composite cell. The issue should be computable at the current local level. Cells that are already in larger composites do not participate until the process reaches the scale of their composite cell.

In addition, there is the connectivity problem: which surfaces of which composite cells should mate? This may solves itself on the way up to [X], but there are extra moves {out of the 8 cell figure game and then back in to the same point} in order for XY composite cells to effect the joining. These extra moves often require sending a request, or "ping", down a line for a single row, slab, or block move.

Let the excess cells remain on exterior surfaces. Slab move or block move them as and when needed to finish other large cells. This requires a more global programming approach, but again at a level commensurate with the current operating scale.

2) At the point where this produces a solvable (meaning a complete set of figure games is available), arbitrary configuration of large composite cells ( [X] ), reconfigure the aggregate in the most [B]-like shape. This may be done with a 3D pattern matching program. Slab or block move the remainder cells to enhance the [B]-ness (this is carried out at all applicable scales in turn also).

3) Again, use the figure games for 8 cells to refine the structure at smaller scales. At each scale, refer to the [B] configuration file to select configurations most like [B]’s morphology at that scale. Connectivity of the composite cells is more computation intensive in this phase of the transformation, as [B] is not arbitrary.

This description doesn't include such details as larger embedded structures, internal voids, and pixels. These would require application specific software. There may be less brutish ways to determine trajectories than the figure game analysis given above, perhaps based on search algorithms and interaction rules.

2.2 Digital vector space

Because the cells do not rotate or change their relative orientation, a Cartesian coordinate system will remain valid for all aggregate configurations.

To specify the position of a standard active cell, relative to some origin, it is natural to use an ordered binary integer triple, or digital vector. This obviates the need for floating point processors, and allows full hardware implementation of arithmetic operations. As the cells can move about in an arbitrary way, this vector also serves as the temporary identification of the standard cell. As the cell moves, one (and only one) of the vector components is updated. There may not be any need of a separate serial ID for standard cells, only for pixels and other special structures.

When a global control computer (mother ship) issues instructions for movement, it can now do so with a second binary integer triple in conjunction with the digital vector. Since the cells in this design only move on one axis at a time, this second "triple" can be compressed into a single integer, plus three bits for sign and axis. This combination of two ordered triples forms a digital vector field.

As the integers can be positive or negative, a sign bit is required. This, along with the bit count of the digital vector, sets the maximum dimensions of the cell aggregate, which can only be attained by setting the origin at the midpoint of the aggregate. For this reason, and others, it is desirable to employ a multiplicity of origins on an ad hoc basis. A third ordered triple specifies a particular origin. This hierarchy might be extensible to many levels. Implementing it requires either a global approach, or a method of voting.

2.3 Cellular automata modeling

Cellular Automata provide an ideal environment for modeling and optimizing the movements of an Active Cell Aggregate, and the additions to it mentioned below. The aggregated cubical Active Cells can be mapped one-to-one (or one-to-eight, etc.) onto the cells of a three-dimensional cubicle CA with geometric congruence. The number of bits required per cell may be as few as four, although more would yield a richer model.

Consider the simple case of moving a row of cells lengthwise by one unit cell. A cell at the leading edge of the row (the ‘initiator’) might send a signal, or ‘ping’, down the row to notify the other cells of an impending move (it may be simply set to this condition by the programmer for this example). The cell at the end of the row (the ‘reflector’) might return the ping forward. As the cells in the row register this return pulse, they release their latches to the perpendicular, neighboring cells and engage their drive systems (in a real device a time lag would be required here). When the return pulse reaches the initiator, the row move can then be made. In this simple model, the cells either detach normally, then reattach after each one moves, or ‘overlap’ for one clock.

For a slab move, consisting of a set of connected rows moving as a group, the initiators would have to mutually ping perpendicular to the desired slab move to establish the leading surface of the slab. Then a parallel, rearward ping (‘slab ping’) is made. Latches are conditionally set or released depending on the perpendicular neighbor’s cell state (pinged or not pinged), and the move proceeds as above.

By means of a genetic algorithm operating on the initial state of the CA, as well as at certain time steps, it should be possible to locally optimize the number of moves required to change from one particular configuration to another, i.e. to find a minimal path figure game. The final desired configuration [B] is applied to the CA as an overlay (a 3D, one bit bitmap). Some initial row or slab move is made, until the surface of [B] is ‘felt’. Next perpendicular moves are made until a [B] surface is felt, and so forth. A counter tracks the total number of moves, for use as a fitness parameter. The resulting sequences are then selected and bred.

A CA platform is also quite amenable to other kinds of modeling solutions for the ACA, such as adaptations of the methods presented in [6].

When studies of the movements of the ACA are sufficiently refined, one can then turn to CA modeling a system such as the one presented below.

3. A Universal Assembler

3.1 The Overtool

 The essential features of this concept include the "MNT Active Cell" {Figure 2}, and a manipulator mounted on the active cell. An aggregate of these devices provides the necessary functionality, variability, and means of transport to form the core of a universal assembler, for macroscopic assembly as well as for positionally controlled chemical synthesis.

As any space-filling polyhedral aggregate with internal sliding planes can form an ACA construct, the general concept of an active cell aggregate with manipulators on the faces of some of these cells would apply here. Again, for illustration, a particular design is looked at.

The essence of this proposal is to reduce the number of individual parts (the cells) to a small set of identical components governed by a few simple rules of interaction. A collection, or aggregate, of these cells then form a device of arbitrary size which can change its configuration to fit the desired task..

The active cells and nanomanipulators are further broken down into a set of standardized parts. The assembler may be capable of making and assembling all of these parts, thereby replicating itself. The atomically precise version of this, operating in vacuo, is called the "Overtool" [7,8].

The "active cells" of the study design are essentially cubicle, and thus constrained to relative movement in only one of the three perpendicular directions at a time. A second type of cell has much the same functionality as the "standard cell", except that one of the facesplates of the cell is replaced by an "XYZ gantry", similar to a contemporary Coordinate Measuring Machine, to permit the fine control and generate the forces needed for positional control chemistry. This simple type of three-dimensional manipulator may seem to be too restricted in its motion to perform the many necessary maneuvers. However, when incorporated into an active cell aggregate, and programmed to work in concert with others of its kind, this machine can indeed execute a large class of rotational and translational movements for both the workpiece and the tool holder.

The tip of this mechanical arm may have a holder for interchangeable tools, or perhaps a dedicated tool. As there are six faces on a cube, there are six possible orientations for this "Gantry Cell". This means a number of Gantry Cells can be simultaneously engaged in a particular process. Some of the cells can be holding, straining, and rotating an arbitrary workpiece, while others fetch reactive species or perform abstraction reactions[9].

Although is not strictly necessary to use the XYZ gantry, a number of advantages incur. Its geometry is quite compatible with the cubicle active cell, simplifying the design. In addition, the Cartesian kinematics are trivial,

Figure 4 (allover)

for both forward and backward solutions. This means the development time, as well as the real-time computation, are significantly less than what would be required for a more elaborate robot arm, such as proposed in [1] and [10].

In figure (4), the workpiece is shown rotated through two (or three Euler) angles. This is done by moving the gantries in synchrony, which of course requires real time cooperation and accounting for signal and processing delays. This is one of the tradeoffs between a system of this type, and an elaborate single arm.

A secondary feature is the "Moiety Palette" {Figure 4}, which is based on a passive faceplate. What would be the interior surface of this component is made flat, with receptors incorporated for the desired molecules. These may be as simple as a single crystal Au(111) surface, for self assembling monolayers, or more specifically tailored receptors. A similar device is used for waste removal.

These pallets can be brought together to form a flat surface, or a box, of nearly any size. For the atomically precise case, the resulting surface might be gastight. This provides one (of several) means of bulk processing of precursor molecules, by chemical vapor deposition (CVD), for example. The pallets can then be separated and sent to the various assembly stations. In practice, this path should be kept quite short for energy efficiency considerations, that is the molecular assembly should be done at a dedicated station near the supply station.

The advantage of this scheme is that the pallets do not need active controllers onboard, that is, they are monolithic objects. The possible disadvantage is that only three (of six) orientations are available. In this event, the active faceplates could also be used as pallets.

The external environment for the universal assembler may be a liquid solution and vacuum-tight vessel, as outlined in [11], or perhaps simply outer space.

It is interesting to note the similarities between, and extensions to, von Neumann’s original, self-replicating "Universal Constructor", which was grounded in cellular automata (also his invention), and this proposal [12].

3.1 Macroscopic assembly methods

The fractal-like nature of an ACA allows a sort of "scale and repeat" software re-use, as with the 8-cell figure games above. The gantry cell, for example, can be physically emulated at larger scales by the ACA itself. From a software perspective then, a fractal-like end product may be the easiest to produce, as often is the case in biology.

The reference design produces an estimated, nominal 10^4 N force per square meter of engaged, sliding plane. This force can be made arbitrarily large, within the material constraints, by making the sliding plane longer than one meter in the direction of the force to be applied {Figure 5}. By interleaving stationary and moving layers of active cells in all six directions, a somewhat arbitrary stress can be applied to the workpiece. There are additional limitations here due to the resultant strain of the workpiece.

For fully rotating objects, there seem to be two methods: either some of the cells circulate about a fixed group, or some additional module has to be added, much like the wheels that come with LEGOs â .

The ACA itself can emulation other structures, jigs, conveyor belts, and the other accouterments of production. Existing types of tools, e.g. welders, could be handled in the manner of today’s industrial robots.

The architecture of an active cell aggregate is eminently scaleable, from the assembly of mesoscopic systems, to the "machine-phase synthesis" and assembly of quite large structures, using the same cell family. The diameter of the shell in {Figure 5} is intentionally omitted. It may be 1700 nanometers, or perhaps 1700 kilometers

Figure 5 (strain)

{space-based) [13]. It would be necessary to build such a large structure of something very strong and cheap, like diamond.

4. Conclusion

The Feynman Grand Prize [14] has been offered in the spirit of the bounties for the chronometer and for human-powered flight. The winner will have constructed a nanomanipulator capable of "pick and place" of single atoms or molecules. The specifications for this device exceed what is required for the Gantry Cell manipulator. If this prize is claimed, a Universal Assembler cannot be far behind.

The confluence of evolvable hardware and software, self-organizing neural networks, positional-control molecular synthesis, and so on, may lead to systems resembling, and exceeding, biological life in their capabilities. These new classes of machinery are difficult to characterize at this epoch.

References

[1] Drexler, K. Eric, "Nanosystems: Molecular Machinery, Manufacturing, and Computation" (1992) John Wiley & Sons, ISBN 0-471-57547-X

[2] Bishop, Forrest, "The Construction and Utilization of Space Filling Polyhedra for Active Mesostructures" (1995), http://www.speakeasy.org/~forrestb

[3] Bishop, Forrest, "A Proposed MNT Active Cell", (1996), http://www.speakeasy.org/~forrestb

[4] Michael, Joseph, "Shape Changing Robot Construction Theory & Application Notes", (1995), ftp.demon.co.uk /pub /ibmpc/dos/apps/graphics/pm as file pm5.zip

[5] Luethi, R, "Sled-Type Motion on the Nanometer Scale: Determination of Dissipation and Cohesive Energies of C60", *Science*, Vol. 266, pp. 1979-1981 (1994)

[6] Adamatzky A,. Identification of Cellular Automata, London: Taylor and Francis, (1994).

[7] Bishop, Forrest, "The Overtool: A Proposed Universal Assembler", (1996), at: http://www.speakeasy.org/~forrestb

[8] Bishop, Forrest, "A Top Down Approach to a Universal Assembler", (1996), at: http://www.speakeasy.org/~forrestb

[9] Musgrave, Charles M., et al, "Theoretical Studies of a Hydrogen Abstraction Tool for Nanotechnology", (1992), journal Nanotechnology*

[10] Merkle, Ralph, draft of "Design Considerations for an Assembler", presented at the Fourth Foresight Conference on Molecular Nanotechnology, No 10, 1995

[11] Merkle, Ralph C., "Self-Replicating Systems and Molecular Manufacturing", (1992), *Journal of the British Interplanetary Society*, Vol. 45, pp. 407-413

[12] von Neumann, John, "Theory of Self Reproducing Automata", (1966), (edited by Arthur W. Burks), University of Illinois Press

[13] McKendree, Tom, "Implications of Molecular Nanotechnology Technical Performance Parameters on Previously Defined Space Systems Architectures", (1995), presented at the Fourth Foresight Conference on Molecular Nanotechnology, No 11, 1995

[14] Feynman Grand Prize, http://www. Foresight.org/ GrandPrize.1.html

[Home] [Articles] [Contact] [Images]
Copyright ©1967-2004, Forrest Bishop, All Rights Reserved