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
|
