Advanced Automation for Space Missions/Appendix 5H
Appendix 5H: Hierarchical System Architecture For Automated Design, Fabrication, And Repair
The desire to create the self-replicating telefactor (Bekey and Naugle, 1980; Heer, unpublished draft notes of the Pajaro Dunes Goal Setting Workshop, 1980) leads to a number of interesting systems design problems. Early theoretical work by von Neumann (1966) showed that selfreplicating machines could in principle be built. Laing (1975, 1977) has further elaborated this theme in a novel approach to the problem. Practical considerations in the creation of self-replicating machines have been treated by von Tiesenhausen and Darbro (1980). Freitas (1980) and Valdes and Freitas (1980) have dealt with the application of self-replicating machines to the exploration of deep space.
This appendix presents an architecture for a system which can perform automated design, fabrication, and repair of complex systems. This methodology should be a useful component of any self-replicating system.
5H.1 System Level Architecture
This section describes the architecture of a hierarchical fabrication system which starts with raw materials and outputs finished products. At the system level, each layer or "rank" of the hierarchy looks just like any other rank; however, the internal details of the various ranks may be entirely different. The present approach was inspired by Miller (1978). Figure 5.46 shows the basic system architecture which consists, from left to right, of rank upon rank of fabricators. Adjacent ranks of fabricators are separated by a transportation and communication subsystem. Ultimately, final products issue from the system at the extreme right.
For generality, the transportation and communication subsystems for each rank are shown to be disjoint. Indeed, it is evident that the subsystem T1 which handles raw materials, such as ores, will no doubt differ in detail from the subsystem TL which handles electronic parts, such as electronic circuits. Furthermore, they will both differ from the system TN which handles major subassemblies, such as complete power plants or complete computer systems. However, at the system level, each transportation and communication subsystem performs the same function: TL handles the transfer of information and material between the fabricators at rank L and those at rank L+1 as shown in figure 5.47.
Although the internal details of the transportation and communication subsystem, TL, need not concern us here, we shall consider how they appear logically to their adjacent ranks of fabricators. To the fabricators they look like a random-access, nonblocking switching network for information (e.g., our telephone system), and like a network of roads and delivery trucks for products. In other words, each message or product is dispatched from a fabricator with a unique address (e.g., telephone number or street address) attached to it. It is the function of TL to see that the messages and products reach their specified destinations
In figure 5.47, it will be seen that a fabricator at rank L+1 can request (via the status links) information on the types of product and their availability from each of the fabricators at rank L. Then the fabricator at rank L+1 transmits orders to the rank L fabricators for those products it requires as inputs to its process. The fabricators at rank L respond with order verifications which include expected time of shipment (to aid scheduling at rank L+1). Physical transportation of product through TL is expected to be slow compared to information transfer; therefore, provision has been made for the transmission of shipping notices. Although this is logically redundant it can aid error recovery if the physical transport of materials goes awry. When the product arrives at its rank L+1 destination a receipt is returned to the rank L shipper to complete the transaction.
It may appear that the complexity of this interrank interface is not absolutely necessary. While strictly speaking this may be so, it is intended to aid in error recovery and to facilitate adaptive multipurpose behavior throughout the entire system. Indeed the multiple hierarchical feedback loops are borrowed both from living organisms and from human industrial economies (Miller, 1978).
Although some modest amount of diversity is expected in the transportation and communication subsystems, the fabricators are expected to be extremely diverse. They will range from ore smelters, to rolling mills, to high precision lithography for integrated circuits, to final assembly of complex products. The next section of this appendix will show, however, that at the system level all fabricators are essentially similar.
5H.2 Fabricator Morphology
Although great diversity of fabricators is envisioned, relatively few subsystem level primitives are required regardless of the rank L of the fabricator and these primitives are common to all ranks L.
A basic (Morph I) fabricator node appears as figure 5.48. It consists of six subdivisions which correspond to the production oriented parts of a business. The arrows are intended to denote material flow. Associated with each arrow, but not shown, are bi-directional information exchanges analogous to those associated with interfabricator communication in figure 5.47. The intrafabricator communications can in many instances be simpler because of tighter coupling between the communicating entities. Feedback and ability to manage error recovery should be preserved, however.
Material enters a rank L+1 fabricator node through a receiver which places orders for those rank L products which have been requested by the kitter. The receiver handles the shipping protocol for interface with transportation and communication subsystem TL.
The kitter is driven by the parts list for whatever product the fabricator is to produce. The kitter orders the parts (through the receiver) and provides complete kits to the producer.
The producer converts the kitted parts with which it is provided into the output product of the fabricator node. This conversion could be a chemical process such as ore smelting or a mechanical process such as milling or PCB assembly .
After the product is produced by the producer, it is tested by the tester. In the basic Morph I, fabricator node product which does not pass the test is simply expelled as waste. Product which passes the test is sent to the stocker which accumulates it for shipment.
The shipper handles the protocol with the rank L+1 transportation and communication subsystem. It transmits status information, receives orders, and ships product.
Communication between the transportation and communication subsystems of adjacent ranks can be provided by degenerate fabricator nodes as shown in figure 5.49. Such a fabricator node might consist, as a minimum, of only a receiver and a shipper. This is sufficient to interface the protocols of the two different transportation and communication systems. In the simplest case it only provides a buffer. In a slightly more complex case, perhaps a repackaging or aggregation of product is performed. Kitters and/or stockers could be added, to perform these functions. Note that a Morph IIB fabricator node provides a material flow from higher to lower ranks. This capability is useful in dealing with recyclable scrap.
Figure 5.50 shows how a fabricator node could deal with product which fails its test, but which can profitably be recycled at some lower rank. The additional stocker and shipper can send the failed product, through a series of Morph IIB nodes, to an appropriate rank for recycling. This could be applied, for instance, to a milled part which is out of tolerance and can be recycled at less cost than producing an equivalent amount of material from raw ore.
If, on the other hand, the production process is reversible (such as putting a number of printed circuit cards into a card cage) then a more advantageous approach is shown (fig. 5.51). The disassembler performs the inverse of the production process. The subassemblies are then returned whence they came to be re-tested as subassemblies. Also shown in the lower right hand corner of the figure are a receiver and stocker for returned (potentially faulty) product from the next higher rank.
One could conceive of doing incoming inspection at the receiver: however, this does not seem to be the best approach. It seems more effective to associate production and test together in the same node (and thus the same rank) since they use much the same information. Furthermore, it seems wasteful to test product both after production and after shipment. This is especially true because the test capability would have to be duplicated at several receivers. Accordingly, for this architecture, test is uniquely associated with production, and suspect product is sent back to its producer for re-test.
We now consider a further embellishment of the fabricator node. Rather than entirely disassembling a faulty product, it may be profitable to rework it. Rework is in general much harder than simple disassembly because it can entail fairly complex diagnosis and repair. We deal here with a simple form of rework, namely, part exchange, as shown in figure 5.52.
In a Morph IV fabricator node, product which fails tests (again a cage full of printed circuit cards is a good example) has its parts replaced one at a time. After each replacement the product is tested again. If it passes it goes to the stock and the faulty part is recycled or becomes waste. If the product fails again, a different part is exchanged, and so on until the culprit is identified. The decision of which part to exchange can be made on the basis of diagnostic tests, or can be made at random.
5H.3 Automated Repair
The above has described a system level architecture of an automated fabrication facility. That architecture incorporated a test function after each production function as a way to catch errors as close to the source as possible and to prevent wasted effort. The architecture included paths for recycling product which failed its test. This also was to promote economy. A side effect of this architecture (which was designed only for efficient fabrication) is that it also perform automated repair. Depending on circumstances this repair call be effected by selective disassembly or selective rework.
First consider selective disassembly for a suspect computer system that needs repair. For the purposes of example it is assumed that the final product is a computer item consisting of four racks of card cages and that each card cage contains 32 printed circuit boards. The PCBs are populated by 11 integrated circuit (IC) types. In order to simplify the discussion, inter-rack cabling, the card cages themselves (with back planes). and power supplies are not considered. Clearly, these can be accommodated in the same way as the components explicitly considered. We further assumed that plugging ICs into PCBs, plugging PCBs into card cages, placing card cages into racks (with interconnection), and cabling the racks together are reversible processes. Furthermore, since the Morph IV fabricator node is the simplest which can accept suspect product from a higher rank source, it is assumed that Morph IV fabricator nodes are used to perform the aforementioned assembly operations. Since IC manufacture is inherently nonreversible (one does not get useful subassemblies by disassembling a finished chip), ICs are assumed produced by a somewhat degenerate Morph IV fabricator node which simply scraps product which fails test rather than disassembling it. Finally, it is also assumed that the entire production facility is idle, there being no current need for additional finished computers.
The repair process begins when the suspect computer is presented to the fabricator node which produced it. This is node F5,1 of figure 5.53. In this figure only those parts of the fabrication network which actually participate in the repair are shown. At node F5,1 the computer is tested and determined to indeed be faulty. It is then disassembled into four component racks, each of which is sent to the node which produced it. At these nodes the individual racks are tested and in the example the third one is found to be faulty. Then this rack is disassembled into card cages, etc.
The selective disassembly proceeds until finally at node F1,3 a faulty IC is found. With say, 100 ICs per card, 32 cards per cage, 10 cages per rack, and 4 racks per computer, this process has in rather straightforward manner isolated the one out of 128,000 ICs that was faulty. Node F1,3, provides another IC of that type and scraps the faulty one.
Meanwhile, node F5,1, having tested a computer which failed, has placed orders with nodes F4,1 through F4,4 for a set of racks from which to fabricate a replacement computer. Nodes F4,1, F4,2, and F4,4 return their racks to node F5,1. Node F4,3, however, places orders for a set of card cages from which to fabricate a replacement for the third rack. Cages 1, and 3 through 10, are returned to node F4,3 after testing, while cage 2 is disassembled. The PCBs from cage 2 are pulled out and sent to their respective fabrication nodes. Boards 1 through 12 and 14 through 32 are returned to node F3,2. Meanwhile, board 13 is disassembled and the ICs are tested at nodes F1,1 through F1,11. (It is assumed here that of the roughly 100 ICs per card there are only eleven different types.)
Now final reassembly can commence as shown in figure 5.54. The heavy lines in the figure trace the path of the replacement 1C back into a repaired computer. When the replacement IC reaches node F2,13, PCB 13 is reassembled. When the PCB rack reaches node F3,2, card cage 2 is reassembled. When this card cage reaches node F4,3 rack 3 is reassembled. And, finally, when rack 3 reaches node F5,1 the original computer reappears with the one faulty IC replaced.
If, on the other hand, the production facility had been in use when the suspect computer was presented to node F5,1, then the original computer would not reemerge at node F5,1. Instead, one more new computer would be produced. The subassemblies obtained by the selective disassembly of the failed computer would be incorporated into many different new computers. However, the failed computer plus one new IC will have resulted in the construction of one new computer to replace the failed one.
In either case, the replacement of the faulty computer is automatic - a consequence of the fabrication system architecture. No additions to the architecture were required to obtain the repair function. Similar arguments hold true if Morph V fabricator nodes are used, but selective rework, rather than selective disassembly, occurs.
5H.4 Automated Design
The system architecture described above readily lends itself to top-down modular design techniques. Using this discipline, at each level of detail, a designer (usually human) receives a specification for the product he is to design. He then consults a catalog of available lower products and selects those to be incorporated into the design. If he needs a lower level product which is not available, he generates specifications for that lower level product. The designer also generates assembly instructions for his product and a parts list. The assembly instructions go to the production department and the parts list to the procurement department. The original specification is used as the test department to verify that the product is what was originally requested.
Figure 5.55 shows how such a design function is added to a fabricator node. The designer in this node functions in a capacity analogous to that of a human designer. Automated design is a function which requires a fairly intelligent machine. Indeed, this is a topic of active current interest in the machine intelligence community.
Although the figure does not show the details of the interface, it is intended that the designer of rank L checks the nodes of rank L-1 to ascertain what rank L-1 products are available, in much the same way as the kitter does. If the designer finds it needs a product which is not available, it chooses a free node at rank L-1 and sends to it the specification for the required product. If there are no free nodes, then the system as configured is not large enough to produce the desired final product. As the system architecture presently stands, outside intervention is required at this point.
5H.5 Utility of Node Morph Architecture
The node morphs enumerated in this paper are not meant to be exhaustive. Compound node morphs may be made by combining elements of two or more morphs. Degenerate morphs from which some functions have been deleted can also be useful. Those morphs enumerated are the ones found useful in the exposition of the system architecture. Additional stocker functions may be desirable in an actual physical system. Potentially useful locations are between the kitter and producer and between the producer and the tester. Also, multiple stockers may be required following a disassembler to handle the number and diversity of components. Redundant transportation and communication subsystems at each rank would make the overall system more robust, as would redundant fabricator nodes. This could be readily incorporated into a physical system.
This appendix has described the architecture of an automated system which has the following interesting properties:
- If it is presented with a final product specification (within its capabilities) it will do the detailed design (all the way down to raw materials if necessary) and then manufacture that product.
- If the system is presented with a faulty final product, it will repair it.
Interesting extensions of this architecture would be the ability to add additional fabricator nodes when required and the ability to add entire additional ranks when needed. This is presently under consideration (Cliff, 1981).
The similarities between the system described herein and the industrial complex of a developed nation are fairly obvious and indeed intentional. There are some significant differences, however. The automated system presented here is much more regular: The interrank transportation and communication systems are disjoint, one from another, and any one fabricator node makes only one product. The result is that the graph of the system is a lattice, rather than a random network. Furthermore, one could expand the number of nodes in each rank in such a way that the graph of the system becomes a tree. This should facilitate mathematical analysis of the system.
The idea (borrowed from top-down structured programming) is to produce a system which is at once extremely large and complex, but is still both understandable by humans and rigorously analyzable mathematically. This will be especially useful when growth by addition of nodes and ranks is studied.
5H.6 References
Bekey, Ivan; and Naugle, John E.: Just Over the Horizon in Space. Astronautics and Aeronautics, vol. 18, May 1980, pp.64-76.
Cliff, Podger, A.: An Hierarchical System Architecture for Automated Design, Fabrication, and Repair. Paper presented at the 5th Princeton/AIAA/SSI Conference on Space Manufacturing, 18-21 May 1981, Princeton, NJ.
Freitas, Robert A., Jr.: A Self-Reproducing Interstellar Probe. J. Brit. Interplan. Society, vol. 33, July 1980, pp.251-264
Laing, Richard: Some Alternative Reproductive Strategies in Artificial Molecular Machines. J. Theoret. Biol., vol. 54, Oct. 1975, pp. 63-84.
Laing, Richard: Automation Models of Reproduction Self-inspection. J. Theoret. Biol., vol. 66, June 7, 19pp. 437-456.
Miller, James G.: Living Systems. McGraw-Hill Book Company, N.Y., 1978
Valdes, Francisco; and Freitas, Robert A., Jr.: Comparison of Reproducing and Nonreproducing Starprobe Strategies for Galactic Exploration. J. of the Brit. Interplan. Soc. vol. 33, November 1980, pp. 402-408.
Von Neumann, John: Theory of Self-Reproducing Automata, A. W. Burks, ed., Univ. of Illinois Press, Urbana, Illinois, 1966.
Von Tiesenhausen, Georg; and Darbro, Wesley A.: Replicating Systems - A Systems Engineering Approach. NASA TM-78304, July 1980.