Programming Self-Assembling Systems via Physically Encoded Information

Abstract

Throughout nature, in both the inorganic and organic realms, complex entities emerge as a result of self-assembly from decentralised components governed by simple rules. Natural self-assembly is dictated by the morphology of the components and the environmental conditions they are subjected to, as well as the physical and chemical properties of their components and environments—their information. Components, their environment, and the interactions among them form a system, which can be described as a set of simple rules. The process of self-assembly is equivalent to a physical computation, through the interaction and transformation of physically and chemically encoded information. A critical question then arises: How does one program self-assembling systems? In the pursuit of answering this question we first use the classic Penrose physical self-assembling system as a case study. This is followed by our three-level design approach, which comprises: specifying a set of self-assembly rules, modelling these rules to determine the outcome of a system in software, and translating to a physical system by mapping the set of rules using physically encoded information. The objective of our approach is to provide a bottom-up design methodology to create scalable self-assembling systems. Two physically encoded information schemes are presented in eight experiments, to demonstrate how component interactions can be directed during the self-assembly process. The results show that the translated physical systems self-assembled into the target structures achieved by the modelling. We use rapid prototyping to construct the translated components and their environment in the latter three experiments. These successful results demonstrate how our three-level approach can be used for programming self-assembling systems via physically encoded information.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Natural self-assembly is dictated by the morphology of the components and their environmental conditions, as well as their physical and chemical properties—their information [5–8, 63]. Components, their environment, and the interactions among them form a system, which can be described as a set of simple rules. One could view entities in nature constituting programs that are based on the rules present in a given system [76]. These programs are the interaction and transformation of physically and chemically encoded information in a given environment. The process of self-assembly has been shown to being equivalent to performing a physical computation [71, 72, 74, 75], as information is compared and exploited to build larger structures.

Organic entities in nature self-repair, self-reproduce, and in many instances are capable of morphogenesis. They are products of parallel construction processes. Their designs are autonomous, robust, and adaptive. Creating new technologies with these defining characteristics of nature is the goal of Morphogenetic Engineering (ME) [29]. In order to reach this elusive goal, understanding the central issue between programmability/controllability and self-organisation is required [28]. The ability to design self-assembling systems is one of the keys to realising this new paradigm of ME. However, designing self-assembling systems continues to be extremely challenging. One aspect that remains an open problem is how to design a set of components and their environment, such that the components self-assemble into a desired entity. To embark upon resolving this problem, could one program self-assembling systems?

In the pursuit of answering this question, we present a three-level approach for programming self-assembling systems, which comprises: specifying a set of rules, modelling these rules to determine the outcome of a system in software, and translating to a physical system by mapping the set of rules using physically encoded information [14]. The objective of our approach is to provide a bottom-up design methodology to create components and/or their environment for scalable self-assembling systems. In the case of components, for example, physical information refers not only to geometric, but to other properties such as mass and attraction/repulsion forces. Furthermore, physical information is context sensitive, e.g. components require a corresponding set of physical information of an appropriate environment.

The next section presents background material on physical information encoding in nature and Embodied Computation (EC) [59, 60], which our approach is based upon. This is followed by an in-depth case study of the first mechanical self-assembling system. Next, an implementation of our three-level approach is given. Two physical information schemes are provided to demonstrate how our programming approach can be physically realised. Experiments are presented which encompass a set of macroscale, mechanical, components that were built using rapid prototyping.¹ The chapter concludes by summarising how this work enables self-assembling systems to be programmed via physically encoded information.

2 Background

The origins of self-assembly as a research field can be traced back to Organic Chemistry [70]. Since its initial formal study, the process of self-assembly has been investigated or used in a wide variety of fields and applications. We present an introduction to self-assembly, and focus on the physical information encoding and computing aspects of self-assembly. We also briefly overview applications of self-assembly, and scale considerations. Finally we contrast the previous design approaches to self-assembly to our programming approach by discussing our motivation.

2.1 Introduction to Self-Assembly

Understanding the principles and mechanisms of self-assembly has been described as one of the important aspects to understanding life [34]. In addition to this profound goal, there are general motivating reasons to study self-assembly, including: (1) the recognition that self-assembly will be one of the few practical approaches for building ensembles of nanostructures, (2) the understanding that self-assembly will be common to many dynamic multicomponent systems from smart materials to self-replicating structures, and (3) the foresight that self-assembly (by bridging the study of distinct components and many interacting components) will offer another avenue to investigate the relationship between reductionism to complexity and emergence [70]. There are also specific motivating reasons to study self-assembly, including the computational aspects of self-assembly as EC [59, 60], and the creation of mesoscale (micrometre to millimetre) and macroscale (centimetre and above) self-assembling systems [19, 68, 69].

But what is self-assembly, and what forms does it come in? Natural self-assembly is a process that involves components that can be controlled through their proper design and their environment, and which are adaptable (components can adjust their positions relative to one another) [70]. There are two primary forms of self-assembly, static and dynamic [40, 47, 70]. Static self-assembly occurs when processes lead to structures or patterns in local or global equilibrium and do not dissipate energy (e.g. crystals). In contrast, dynamic self-assembly occurs when processes lead to structures or patterns that can only occur when the system is dissipating energy (e.g. biological systems). Research in static self-assembly is more mature, whereas research in dynamic self-assembly is in its infancy. The relationship between the two (e.g. the formation of a cell) is even less well understood [34]. In this chapter, we focus on static self-assembly.

One of the most successfully studied static self-assembling systems is the creation of artificial snow crystals. In nature, the process of creating a snow crystal is initiated through the use of a seed particle, typically bacteria [22] or a dust particle [41], to which water molecules can attach. The morphology of a snow crystal is dependent on how water molecules selectively attach to the developing structure, based on the hexagonal symmetry of snow crystals. This process has been leveraged to create predictable artificial snow crystals of varying form, under a controlled environment [41]. The self-assembly process is initiated using the tip of an ice needle to act as the seed particle. The ice needle is placed in a chamber, where the supersaturation level of water vapour, temperature, and background gas can be controlled. Understanding the relationship between these three environment variables (information) has led to the creation of predictable artificial snow crystal morphologies.

2.2 Physical Information Encoding and Computation

Crystallography continues to be an active area in science. One of the most prolific insights was that of Erwin Schrödinger and his proposed aperiodic crystal for genetic information encoding, described in his popular science classic What is Life? [56]. Schrödinger’s aperiodic crystal predates [61, 62] the discovery of the aperiodic structure of DNA by James Watson and Francis Crick [67]. Crick acknowledges Schrödinger for providing inspiration to study the structure of DNA [44]. The discovery of the structure of DNA led to the central dogma of molecular biology [23], which describes the transfer of genetic information encoded in DNA through transcription to RNA, and translation to proteins. Proteins, the resulting self-assembling shapes, are the primary building blocks of living organisms.

In addition to understanding how the aperiodic structure of DNA serves as a genetic information medium in biological systems, research is being conducted on manipulating DNA for information encoding and computation. Leonard Adleman first showed that computing using self-assembling molecules, such as DNA, was possible [2]. An algorithm was devised to solve a seven-node directed Hamiltonian path problem [32]. Single strands of DNA were created to encode partial sample solutions to the problem (representing the edges and vertices of the directed graph). These partial sample solutions were then allowed to interact and self-assemble based on Watson–Crick complementarity. The linear double-stranded self-assembled structures representing potential solutions were then filtered using techniques from biochemistry and molecular biology to identify the true self-assembled solution.

With the success of Adleman’s experiment, research has focused on scaling DNA Computing [46] to solve larger problems. This required a shift from the original brute-force approach. Developing new DNA structures and algorithmic techniques has shown tremendous promise in furthering this method of EC. To reach the elusive goals of ME, understanding the central issue between programmability/controllability and self-organisation is required [28]. This is also the central issue for EC [59, 60], where physical computation is dependent on the underlying substrate. Given the parallels between the two, the role of structure and shape in physical information encoding and computation will also play a vital role in ME.

This role is demonstrated in the following example. Wang Tiles [65, 66], created by Hao Wang, are a mathematical construction, where each equal-sized square tile has coloured edges. Wang Tiles can be arranged (translated, but not rotated or reflected) on a rectangular plane only when adjacent tiles have the same colour. Given a set of Wang Tiles, the main question is deciding whether that set (allowing for copies of the tiles in the set) can tile the plane or not. Wang presented an algorithm [65] that could achieve this for any finite set of Wang Tiles. In his proof, Wang assumed that any set that could tile the plane would result in a periodic tiling. However, Robert Berger proved that Wang’s conjecture was false, by creating a set of Wang Tiles that would result only in an aperiodic tiling [10]. This form of aperiodic tiling is similar to a Penrose Tiling [52] and Quasicrystals [57]. Berger’s original set contained 20,426 Wang Tiles. Later, Karel Culik created a set of Wang Tiles of size 13 that would result only in an aperiodic tiling [24] (Fig. 7.1). Any Turing machine [58, 64] can be translated into a set of Wang Tiles, such that this set will only tile the plane if and only if the Turing machine never halts. The halting problem [58, 64] is undecidable just as Wang’s tiling problem is uncomputable. Wang Tiles have been proven to be Turing-universal [58].

Fig. 7.1

Culik’s set of 13 Wang Tiles using 5 colours (left), and a schematic of a DNA Tile (right)

The physical realisation of Wang Tiles was achieved through the creation of DNA Tiles [75] (Fig. 7.1). These tiles use interwoven strands of DNA to create the square body of the tile (double-stranded) with single strands of DNA (representing colours) extending from the north–west–south–east edges of the tiles. This led to the abstract Tile Assembly Model (aTAM [73], an extension of Wang Tiles using DNA Tiles, originally named the Tile Assembly Model, TAM [55]) as a mathematical model of pseudo-crystalline growth. The aTAM has been used to create a physical set of DNA Tiles that are Turing-universal [71]. The aTAM has also been used to study the complexity of constructing structures, such as lines and squares [1, 55, 72]. Complexity is primarily measured in terms of Kolmogorov complexity [40, 47, 55], e.g. the number of unique tiles required to build a structure.

Additionally, the aTAM has been used for analysing algorithmic complexity. It has also led to new algorithmic proposals for using DNA Tiles to perform mathematical operations including binary counters, multiplication, and cyclic convolution product. Several binary counter algorithms have been proposed using DNA Tiles that self-assemble into a 2D structure [9, 30, 33, 40]. There has been progress on constructing a physical example of a binary counter, but with a few counting errors (due to assembly errors) [9]. A theoretical algorithm to perform multiplication also uses a 2D structure [48]. The theoretical algorithm for the cyclic convolution product requires new 3D DNA Tiles allowing for the self-assembly of a 3D structure [48].

2.3 Applications and Scale

Understanding how structures emerge through self-assembly is vital in continuing to develop ME, as experienced in DNA Computing. It is also important in other disciplines, such as Modular Robotics (MR) and Material Science (MS). Techniques have been developed to create component sets that self-assemble into a single desired entity. These techniques all use information from a desired entity’s global morphology to create the set of components. Algorithms evaluating the geometry of a global morphology have been used in MR [35, 39, 45]. Algorithms using the global form to act as a template that dictates the mechanism by which components can reconstitute a 2D image have been used to create DNA Origami [53, 54]. This technique has also been extended to produce 3D structures [27]. However, such techniques will not scale effectively to problems requiring a self-assembly process to create multiple structures, a case likely in ME where a desired entity may require multiple states (structures) to complete.

Additionally, the physical realisation of self-assembling systems need not be at the micro and nano scales. Both mesoscale and macroscale self-assembly have a unique quality in comparison to molecular and nanoscale self-assembly, in that components at these scales offer flexibility in design and access to types of functionality unparallelled in molecular and nanoscale systems [19, 68, 69]. As a corollary, studying self-assembly at the millimetre to centimetre scale provides a “hands-on approach” and a unique opportunity to build knowledge in this nascent research area [47]. However, mesoscale and macroscale self-assembly also have their challenges, including: (1) the fabrication of components, (2) the understanding of what range of structures are possible (including defects), (3) the design of components in terms of size, shape, and complexity, and (4) the design of systems using non-biological parts [69].

2.4 Motivation Behind Our Approach

Our approach is distinguished from the above [35, 39, 45, 53, 54] in two ways: (1) it translates a set of rules to create a physical system, and more importantly, (2) it does not use global information derived from a desired entity. For example, our approach does not dissect a target entity into components and assign their properties based on their final end configuration. Instead of being top-down, our approach uses bottom-up design. This bottom-up aspect is imperative in terms of ME. Typically, physical information encoding and computation are viewed separately. To verify our approach and physically demonstrate its programming capabilities for self-assembly, we use macroscale components with mesoscale features built using rapid prototyping. In the remainder of this chapter, we illustrate how physically encoded information can be used to enable the self-assembly process.

Fig. 7.2

From left to right component c$_{1}$ and c$_{2}$ (in neutral position), and complexes c$_{1}$c$_{2}$ and c$_{2}$c$_{1}$

Fig. 7.3

Example scenario with initial configuration (top) and final configuration (bottom)

3 Case Study: A Self-Reproducing Analogue

Here we use the first mechanical analogue to natural self-assembly, by Lionel S. Penrose and Roger Penrose [51], as a case study. This example is chosen to demonstrate how it is possible to program a self-assembling system via physically encoded information. We first provide an overview of their system. Next, we describe how the information physically encoded in the components and in their environment interacts through a set of rules. This is followed by physical specifications of the Penrose system, which we determine by reverse engineering. Finally, we present test results from our implementation to independently verify this self-reproducing analogue.

3.1 Overview

Self-reproduction was once thought to be an intrinsic property of nature, and one that could not be mimicked in artificial systems. In 1957, L. S. Penrose and R. Penrose were the first to show a mechanical self-reproducing analogue [51]. Their system is akin to molecular amplification in the form of templated self-assembly [70]. They created two component types, labelled here as c$_{1}$ and c$_{2}$. These two components connected in either a c$_{1}$c$_{2}$ or c$_{2}$c$_{1}$ configuration (Fig. 7.2). Multiples of these components were confined to a track in a random ordering. The track was shaken horizontally in 1D, which allowed components to interact with one another and their environment. If only individual c$_{1}$ and c$_{2}$ components were shaken, self-assembly would not occur. However, if a c$_{1}$c$_{2}$ (or a c$_{2}$c$_{1}$) seed complex was placed on the track, only then would neighbouring c$_{1}$ and c$_{2}$ (or c$_{2}$ and c$_{1}$) components self-assemble into c$_{1}$c$_{2}$ (or c$_{2}$c$_{1}$) complexes respectively (Fig. 7.3).

3.2 Information and Rules

Although L. S. Penrose and R. Penrose did not discuss this in particular, they were able to achieve artificial self-reproduction through the morphology of each component type and the design of the environment. As we had originally developed in [14], there are ten information sites physically encoded through hooks, latches, and neutral sites (where no assembly occurs) on the two component types (Fig. 7.4).

Fig. 7.4

Labelled regions of physically encoded information using shapes in c$_{1}$ (left) and c$_{2}$ (right)

Fig. 7.5

c$_{1}$c$_{2}$ assembly (left) using rule (1), and c$_{2}$c$_{1}$ assembly (right) using rule (2)

Fig. 7.6

Rotation rules (3)–(6) promote the creation of new c$_{1}$c$_{2}$ complexes

Fig. 7.7

Rotation rules (7)–(10) promote the creation of new c$_{2}$c$_{1}$ complexes

As an expansion on the rules in this system [14], there are ten component interaction rules present. The information associated with each of these rules is physically encoded by shape. Rules (1) and (2) directly dictate the self-assembly of the two component types, by hooking-and-latching together (Fig. 7.5).

$$\begin{aligned} { \ D}\mathrm{\ fits}{ \ E} \rightarrow \ D + \ E \end{aligned}$$

(7.1)

$$\begin{aligned} { \ C}\mathrm{\ fits}{ \ F} \rightarrow \ C + \ F \end{aligned}$$

(7.2)

There are also two sets of four rotation rules: clockwise (cw) and anti-clockwise (acw). Anti-clockwise rules (3)–(6) apply to the creation of c$_{1}$c$_{2}$ complexes (Fig. 7.6), and clockwise rules (7)–(10) to c$_{2}$c$_{1}$ complexes (Fig. 7.7):

$$\begin{aligned} { \ A}\mathrm{\ rotates_{acw}}{ \ H} \end{aligned}$$

(7.3)

$$\begin{aligned} { \ J}\mathrm{\ rotates_{acw}}{ \ A} \end{aligned}$$

(7.4)

$$\begin{aligned} { \ A}\mathrm{\ rotates_{acw}}{ \ B} \end{aligned}$$

(7.5)

$$\begin{aligned} { \ J}\mathrm{\ rotates_{acw}}{ \ G}\end{aligned}$$

(7.6)

$$\begin{aligned} { \ I}\mathrm{\ rotates_{cw}}{ \ B} \end{aligned}$$

(7.7)

$$\begin{aligned} { \ B}\mathrm{\ rotates_{cw}}{ \ G} \end{aligned}$$

(7.8)

$$\begin{aligned} { \ I}\mathrm{\ rotates_{cw}}{ \ H} \end{aligned}$$

(7.9)

$$\begin{aligned} { \ B}\mathrm{\ rotates_{cw}}{ \ A} \end{aligned}$$

(7.10)

Fig. 7.8

Environment height constraints (represented with lines) prevents components from flipping (left), and provides rotation flexibility to aid in bond creation between components (right)

To facilitate the component interaction rules (assembly and rotation), there are two environment rules in this system. (1) The first environment rule prevents the components from flipping when rotating, so as not to move into a position where self-assembly cannot occur. (2) The second environment rule is the provision of enough rotational flexibility for the components, and aids in bond creation by allowing the components to slide and hook-and-latch onto one another. These two environment rules result from imposing an appropriate environment height (Fig. 7.8).

In addition to the geometry of the environment, the shaking motion of the environment is horizontal. This motion is applied to both individual components (initially placed in their respective neutral position) and seed complexes. These component interaction and environment rules, along with initially placing either a $\text{ c}_{1}\text{ c}_{2}$ or $\text{ c}_{2}\text{ c}_{1}$ seed complex, ensures which information comes in contact and the amplification of $\text{ c}_{1}\text{ c}_{2}$ or $\text{ c}_{2}c\text{ c}_{1}$ complexes through two autocatalysis system rules (11) and (12). These two rules ensure that self-assembly only occurs in the presence of a seed complex (the ; symbol denotes separate entities). When the environment is shaken horizontally, $\text{ c}_{1}\text{ c}_{2}$ or $\text{ c}_{2}\text{ c}_{1}$ complexes act as catalysts as they are not consumed in the creation of creating $\text{ c}_{1}\text{ c}_{2}$ or $\text{ c}_{2}\text{ c}_{1}$ complexes using assembly rules (1) and (2) and rotation rules (3) to (10). Individual $\text{ c}_{1}$ and $\text{ c}_{2}$ components do not act as catalysts in this system, since when the environment is shaken horizontally $\text{ c}_{1}$ and $\text{ c}_{2}$ components cannot rotate, and as a result assembly rules (1) and (2) do not occur.

$$\begin{aligned} \text{ c}_1 \text{ c}_2\ \text{ autocatalysis}\ \text{ c}_1 ; \text{ c}_2 \rightarrow \ \text{ c}_1 \text{ c}_2\ ;\ \text{ c}_1 \text{ c}_2 \end{aligned}$$

(7.11)

$$\begin{aligned} \text{ c}_2 \text{ c}_1\ \text{ autocatalysis}\ \text{ c}_2 ;\text{ c}_1 \rightarrow \ \text{ c}_2 \text{ c}_1\ ;\ \text{ c}_2 \text{ c}_1 \end{aligned}$$

(7.12)

3.3 Specifications

L. S. Penrose built upon this system to develop more sophisticated self-replicating machines in 2D [49, 50]. In 1961, the system described here was independently verified by Moore [43]. However, Moore did not provide an explanation of how this system worked (referring to it as L. S. Penrose’s “basic model”), nor did he provide an explanation or specification on how he built the system:

No picture of Penrose’s basic model is included with this paper, since if the reader attempts the problem of how to design the shapes of the units [c$_{1}$] and [c$_{2}$] so as to have the specified properties, the difficulties he will encounter in his attempt will cause him to more readily appreciate the ingenuity of Penrose’s very simple solution to this problem.

We can attest to the difficulty of building this system, and we certainly do have a greater appreciation for this simple, yet powerful, pioneering self-assembling system. However, in addition to our explanation of how this system works, we provide specifications on how to construct this system (with further information in [12]).

We used the drawings provided in [51] to determine the specification of the c$_{1}$ and c$_{2}$ components. Mathematical specifications for the main surfaces of the two components is provided (Fig. 7.9). Component depth, which was not specified in [51], is primarily dependent on the construction material, and will influence bond strength, as well as the dimensions of the environment.

Fig. 7.9

Cartesian co-ordinates for components c$_{1}$ and c$_{2}$ (construction units in mm)

An environment height of 17 mm was determined, by reverse engineering, to be capable of achieving the two environment rules. The width and depth of the environment were not provided in [51]. The width primarily depends on the number of components, and the shaking strength used. The depth of the environment primarily depends on the depth of the components. A balance must be maintained to allow for the components to be able to slide back and forth, but not to be able to twist and bond incorrectly. Also not discussed in [51], the shape of the ends of the environment will play a role in the self-assembly process. The ends can either break, maintain, or enhance component bonding. Although there may be particular shapes to enhance the self-assembly process, vertical ends are sufficient.

Fig. 7.10

Machined components $\text{ c}_{1}$ (left) and $\text{ c}_{2}$ (right)

The mathematical specifications of the components and the environment were used to create a set of physical specifications, accounting for tolerances. In the original system [51], it was suggested that components could be made from wood or vulcanite. In our implementation, we instead made $\text{ c}_{1}$ and $\text{ c}_{2}$ components from standard brass plate (7/64” depth, approximately 2.78 mm). The components were cut using a 3-axis milling machine (CNC Takumi V6). The vertical edges of the top point of the $\text{ c}_{2}$ component were slightly narrowed, by 2 $\mu$. This provided enough tolerance for the two components to hook-and-latch together, and not disassemble easily. In addition, a slight curvature was put at eight points, related to four information locations on the two components. This curvature also assisted in creating and maintaining bonds between components. Figure 7.10 provides a photograph of the physically implemented c$_{1}$ and c$_{2}$ components. The environment for the components consisted of three main parts: back, middle, and front. These parts were made from clear acrylic sheet (3 mm depth), and cut on a laser cutter (Trotec Speedy 300 Laser Engraver). The three parts were connected to hold the components, using two stainless steel screws and wing nuts.

3.4 Test Results

Four tests were conducted on our implementation. Figure 7.11 provides photographs of the test results. There are three characteristics of the implemented system that should be noted: (1) component-component bond strength, (2) component-environment spatial relationship, and (3) shaking motion of the environment.

Fig. 7.11

Initial (left) and final (right) configurations after running each of the four system tests

As discussed in [31], the strength of the bonds are weak, as they are simply mechanical bonds. It has been our experience that the mass of the components can influence the bond strength. We have constructed earlier prototypes using plastic components and aluminum components of the same specification. We found the brass components (which have a higher density) to be superior. Brass was used instead of increasing the thickness of the components. The weight of the components also helps prevent them from moving vertically in the environment, when irregular shaking is applied. When this occurs, undesirable, spontaneous assembly can occur. We also observed that two assembled components occupy less physical space as two c$_{1}$ and c$_{2}$ components in their neutral positions. The implication here is that as the self-assembly process progresses, more free space is created in the environment. As a corollary, the more free space there is, the more energy is required.

Furthermore, we observed that the environment does not necessarily have to be shaken horizontally in 1D. The environment can also be shaken in an up-and-down motion, e.g. $\pm 45^{\circ }$ from its centre. A more in-depth investigation into the effects of the environment on this system will be conducted in the future.

These successful results show that the original Penrose system truly is a mechanical analogue to self-replication. The rule-based approach and the notion of physically encoded information used to analyse this system are further developed in the next section.

4 Programming Self-Assembling Systems

The goal of the Penrose case study was to create a system that could replicate structures by means of self-assembly. Specifically of concern for proof-of-concept purposes was the replication of two structures, each independently applicable to a particular system, in 1D (in terms of component movement). A set of simple rules, in conjunction with the physical constraints of the system, were able to capture the dynamics of the system, and describe the results from running the system. Similarly, in the pursuit of answering our question of how one could program self-assembling systems, for proof-of-concept purposes, we consider the self-assembly of a variety of structures in 2D (again, in terms of component movement). Just as L. S. Penrose and R. Penrose took a biomimetic approach inspired by nucleic acid complexes in chromosomes, our approach to programming self-assembling systems is a biomimetic one, inspired by the central dogma of molecular biology [23].

Fig. 7.12

Three-level approach showing that translation can be done directly from Level I to Level III

A breakdown of the three-level approach is given next. An extension of the self-assembly rules presented in [14] is described in Sect. 7.4.1.1. A new modelling technique, which is an extension of the aTAM [73] (introduced in Sect. 7.2.2), is presented in Sect. 7.4.1.2. Physically encoded information sets, to which the set of rules are mapped, are presented in Sect. 7.4.1.3.

4.1 Three-Level Approach

The three-level approach provides a high-level description of our method for programming self-assembling systems via physically encoded information. The three phases of our approach include: (1) definition of rule set, (2) virtual execution of rule set, and (3) physical realisation of rule set (Fig. 7.12). The objective of our approach is to provide a bottom-up design methodology to create components and/or their environment for scalable self-assembling systems. This is achieved by being able to directly map a set of self-assembly rules to a physical system.

4.1.1 Level I: Definition of Rule Set

The following example implementation was constructed to demonstrate how this three-level approach can be used. Its purpose is to show how to create a set of physical, 2D components that self-assemble into a single target structure or set of target structures (created in parallel). The self-assembly rules in this example implementation are divided into the following three categories: component rules, environment rules, and system rules. Combined, these three rule types define a system.

Component rules specify primarily shape and information. Components are similar in concept to DNA Tiles [75]. Abstractly, components are all squares of unit size. Each edge of a component serves as an information location, in a four-point arrangement, i.e. north–west–south–east. Information is abstractly represented by a capital letter (A to G). If no information is associated with an information location (a neutral site), the dash symbol ($-$) is used. The spatial relationship of this information defines a component type (Fig. 7.13).

Fig. 7.13

Two component types with their information arrangements (square body tile, with circles indicating information locations)

Environment rules specify environmental conditions, such as the temperature of a system and boundary constraints. The temperature determines the threshold to which the assembly protocol must satisfy in order for assembly bonds to occur. Components are confined due to the environment boundary, but are permitted to translate and rotate in 2D, and interact with one another and their environment. However, components are not permitted to be reflected.

System rules specify the quantity of each component type, component-component information interactions (i.e. assembly interactions), and component-environment information interactions (i.e. transfer of energy and boundary interactions). In this implementation, there are two types of system interaction rules, referred to as fits rules and breaks rules. Abstractly, if two pieces of complementary information (i.e. pieces that “fit” together) come into contact, the fits rule will cause them to assemble. This rule type is commutative, meaning if A fits B, then B fits A. Conversely, if two assembled pieces of information experience a temperature above a certain threshold, then their assembly “breaks” according to the breaks rule.

4.1.2 Level II: Virtual Execution of Rule Set

At Level II, a self-assembly rule set is mapped to an abstract model. This model is used to aid in assessing the outcome of a system. In this example, the goal is to determine if a set of target structures can be created by a system. We present an extension of the aTAM [73], as a simple modelling technique that is better suited to the type of self-assembling systems that interest us as programming examples.

In the aTAM, a tile type is defined by the binding domains (e.g. colours) on the north–west–south–east edges of a tile. A finite set of tile types is specified (where the instance of each tile type is in infinite supply in the model). Tiles can only bind together if the interactions between binding domains are of sufficient strength (provided by a strength function), as determined by the temperature parameter $T$. The sum of the binding strengths of the edges of a tile must meet or exceed $T$. As a result, $T$ dictates co-operative binding.

There are four constraints with the aTAM:

• 1. At least one seed tile must be specified to start the self-assembly process.

• 2. Tiles cannot be rotated or reflected (realised through co-operative binding constraints).

• 3. There cannot be more than one tile type that can be used at a particular assembly location in the growing structure (although the same binding domain is permitted on more than one tile type).

• 4. All tiles are present in the same environment, referred to as a one-pot-mixture.

These four constraints, along with the set of tiles, binding domains, strength function, and temperature parameter $T$ define the aTAM. The seed tile is first selected and placed on the square lattice environment. Tiles are then selected one at a time, and placed on the grid if the binding strength constraints are satisfied. The output is a given shape of fixed size, if the model can uniquely construct it.

There are several extensions to the aTAM [3, 21, 25, 26, 37, 73], offering an alternative programming approach within tile-based systems, due to their additional model features. These extensions and the aTAM can be classified into the following four programming approaches [26]: (1) Tile Hard-coding Programming (THcP), (2) Staged Programming (SP), (3) Tile Concentration Programming (TCP), and (4) Temperature Programming (TP). THcP relies on hard-coded information in the tiles to enable the self-assembly process (the aTAM falls under this category). SP allows for tiles to be added dynamically in sequence, or intermediate structures can be stored separately and added to the main mixture at a later time. These staged additions of individual tiles and/or intermediate structures enable the self-assembly process in SP. In TCP, tile types are specified in terms of concentration values. The probability of tile interactions is used to enable the self-assembly process in TCP. TP uses changes or fluctuations in temperature to enable the self-assembly process. As part of the implementation of our programming approach, we present a new extension of the aTAM, the concurrent Tile Assembly Model (cTAM). The cTAM combines features in the first three programming categories. Our tile-based modelling approach can be broadly considered a combination of the aTAM and Lego World [38].

Lego World was created by Stuart Kauffman to serve as a model for studying complexity and emergence abstractly. The model generates the possible outcomes (structures) from assembling Lego bricks. The bricks (e.g. rectangular blocks of size 1$\times$1, 1$\times$2, 2$\times$3, and 3$\times$4) represent the primitive set. The primitive operations permitted in Lego World include both construction and deconstruction, as adding two primitive parts together or adding a primitive part to a growing assemblage (object/structure), and removing a primitive part from another primitive part or assemblage. The set specifying the quantities of the unassembled primitive bricks in the primitive set is referred to as the founder set. To determine the types of structures that are possible from a founder set in Lego World, one can consider the number of steps required to reach a structure. At each step, a single primitive operation can be performed. For example, Rank 1 includes all the possible structures that can be built from one construction step, and all the possible structures from two construction/deconstruction steps would be part of Rank 2. The number of ranks may continue to infinity, given an infinite founder set. Kauffman refers to the founder set and the transformations on those bricks into assemblages as a technology graph. He notes [38] that a technology graph is similar to a chemical reaction bipartite graph, where the founder set is a set of organic molecules, the resulting molecules are the objects, and the transformations are the reaction hyperedges linking substrates and products among the objects. The graph is bipartite with two types of entities: nodes (representing objects) and hyperedges (representing transformations). In this form, a technology graph can also be considered as an abstract model for self-assembly, and its relationship to chemical reactions as a parallel to the origins of self-assembly and its roots in Organic Chemistry [70].

There are four features to Lego World that we have incorporated into the cTAM:

• 1. There are no seed tiles. The self-assembly process can be initiated between any two compatible tiles.

• 2. Tiles can be rotated, but like the aTAM, cannot be reflected. Tiles cannot be reflected as their movement is bound to a 2D plane.

• 3. There can be more than one tile type that can be used at a particular assembly location in the growing structure.

• 4. As with the aTAM, all tiles are present in the same one-pot-mixture environment.

However, unlike Lego World, the cTAM does not allow for deconstruction processes. Only construction (assembly) operations are possible, to simplify the model for our purposes. Deconstruction operations in association with the temperature parameter $T$ could be applied to the cTAM if applicable. In this example implementation, we set $T=1$. Consequently, a self-assembly bond can occur between any two compatible pieces of information. As a result, there are five implications based on these four features:

• (i) Any two tiles can start the self-assembly process.

• (ii) Tiles can self-assemble into multiple substructures concurrently.

• (iii) There can be multiple types of resulting structures, some of which may only be possible depending on the set of self-assembly steps. This is because multiple tile types can assemble to the same assembly location, if they have compatible information.

• (iv) Since tiles can be rotated in 2D, fewer tiles are needed for symmetric features in a structure. It should be noted that rotation is not permitted in any of the other extensions to the aTAM, and is an important differentiating factor of the cTAM.

• (v) Since tiles can be rotated and self-assembly occurs in parallel, assembly violations must not be permitted in the cTAM.

The initial (founder) set of tiles in the cTAM is a multiset (in type and frequency). In the cTAM (Fig. 7.14), a single assembly operation is applied at a time, initialised by selecting a single tile/substructure with an open assembly location at random. If no other tile or substructure has an open complementary information location, then the location on the first tile/substructure is labelled unmatchable. If there are tiles/substructures with open complementary information locations, all those tiles/substructures are put into an assembly candidate list. Tiles and substructures are selected at random (from the assembly candidate list) until a tile/substructure can be successfully added. If no such tile/substructure can be added, due to an assembly violation (Fig. 7.14), then the location is labelled unmatchable. If a tile/substructre can be added, the open assembly locations on the two tiles/substructures are updated, and labelled match (all applicable assembly locations must match when adding two substructures). The algorithm repeats, and halts when all assembly locations are set to match or unmatchable. When the algorithm concludes, the resulting structures are placed in a single grid environment to determine if any environment boundary violations occur. A post-evaluation is sufficient for this implementation, as we are more concerned with the set of self-assembled structures than environmental constraints.

Fig. 7.14

Example cTAM steps (left) and assembly violations (right), with solid black circles indicating conflicting information interaction

The cTAM serves as a computationally efficient method for evaluating the types of structures that can result in 2D self-assembly, when component rotation and concurrent assembly are required. The Level I self-assembly rules in the three-level approach can be quickly evaluated using the cTAM. How those self-assembly rules can be mapped to a physical system is detailed next.

4.1.3 Level III: Physical Realisation of Rule Set

While in Level I and Level II it is assumed that component and environment information can be perfectly achieved, in Level III this theoretical information must be physically instantiated, often resulting in precise choices of materials, energy, and forms for components and their environment. The physical systems presented here have similar characteristics. The goal of each system is to investigate whether or not a set of mechanical, macroscale components (with concave/convex polygon shapes) can self-assemble into a target structure (of a specific polygon perimeter form, with symmetric/assymetric features). The assembly process is initiated by placing the components on a tray, which is shaken parallel (in 2D) to the surface of the tray. Energy is transferred to the components as vibrational energy, causing components to move around and interact with one another, while magnets are used to enable components to attract and repel one another. Our approach to physically encoding information in terms of a component design space is inspired by chemistry, particularly molecular interactions. The roles of component shape and magnetic interactions are contrasted to demonstrate how to leverage particular aspects of component interactions during self-assembly.

4.1.3.1 Design Space

Over a century ago, Emil Fisher proposed the key-and-lock principle to explain the mechanism of enzyme action [4]. The idea was that an enzyme has a binding site that fits the shape of its substrate. Shape and geometry are central to molecular interactions, within the context of an appropriate environment. Fisher’s principle is still valid today, and the analogy is applicable in explaining molecular recognition.

We extend this principle to a key-lock-neutral concept (“neutral” meaning where no binding is possible) and apply it to self-assembly. This concept is central to the component design space that we use here, which defines the set of physically feasible designs. In our examples, it is a combination of a shape space and an assembly protocol space: the shape space is based on the key-lock-neutral concept to define component shape, the assembly protocol space uses magnetism to define binding. Together, they can be used to enable the self-assembly process.

However, the shape space and the assembly protocol space must be used in such a way to give the component design space two properties: (1) using shapes to create stable joints between complementary components, and (2) creating the ability for components to selectively bind to corresponding components and not to conflicting components. The first property is achieved by using both concave and convex shapes, creating joints which are less likely to disassemble during collisions with other components and the environment. The second property is achieved in this example by placing the magnets in the interior of a non-magnetic material. By not allowing components to join directly together, components have a higher degree of freedom to move around and interact with one another. This is an important aspect to the definition of self-assembly, requiring adaptive component interactions [70].

The following is an example to illustrate the two properties of the component design space (Fig. 7.15). Components were hand-built using foam board to define their shapes. A disc magnet was placed on the top interior component surface. Consequently, an effective magnetic region was created, due to the force of friction between the components and the surface of the tray. As a result, having parts of the component’s shape outside of this region would create neutral sites. Polygon shapes with concave/convex features in relation to this region define the shape space. The three stable patterns of disc magnets were used to define the assembly protocol space.

Fig. 7.15

Effective magnetic radius and three magnetic disc patterns: chain, grid, and triangular

The environment information corresponding to this component design space consisted of a tray that was also made from foam board, with side-walls to confine components, and was shaken by hand randomly in 2D. This shaking motion allowed assembled complementary components to remain assembled. Unintended bonds between conflicting components would be broken when collisions with other components and the tray side-walls occurred. Five physical self-assembling systems were created by building components using this component design space (varying the number and types of components) and their corresponding tray environment (Fig. 7.16). Further details on these systems can be found in [11, 13, 36].

Fig. 7.16

Example systems using the continuous design space (from [13])

The implementation of this component design space was a continuous one. We now demonstrate how this component design space can be transformed into a discrete one. A discrete space is better suited to illustrate how differences in the implementation can be used to direct component interactions. Two implementations of this discrete design space are contrasted, and used with the three-level approach.

4.1.3.2 First Example of a Discrete Physical Information Encoding Scheme

This first discrete component design space (Fig. 7.17) was used in the original implementation of the three-level approach [14]. Similar to the previous example, components and the environment were hand-built from foam board, and the environment was shaken by hand in 2D. In contrast to the previous example, this discrete design space uses a simplified set of shape primitives and more complicated magnetic interactions. A component’s base shape is a square, where a shape primitive is applied to each edge: key (convex), lock (concave), and neutral (linear). Three magnets are associated with each key and lock, but not with neutral sites. Magnets are placed within the sides of the components, and covered with foam, to allow for selective binding. A single magnet is used at each location in the 3-magnetic-bit encoding (magnetic north/south arbitrarily assigned to 0 and 1). By manipulating the designation of 3-magnetic-bit encoding to keys and locks, convex key-to-key errors can be reduced (Table 7.1). However, this is at the expense of not being able to minimise key-to-lock errors. Due to the challenges of building components from foam by hand, the shortcoming of this shape space was that neighbouring lock shapes on the same component were not well defined (Fig. 7.17).

Fig. 7.17

Design space for the first physical information encoding scheme (left), and an example component showing the shortcoming of neighbouring lock shapes (right)

Fig. 7.18

Example systems using the first discrete design space (from [14])

Table 7.1 Key/lock designations to magnetic patterns with abstract label, and interaction rules

The corresponding environment information for this first discrete design space matched the environment for the continuous design space in materials (foam board), shaking motion (by hand in 2D), and resulting component-component/environment interactions (for corresponding and conflicting components). Five physical self-assembling systems were created by building components using this component design space (varying the number and types of components) and their corresponding tray environment (Fig. 7.18). Despite the shortcoming of this shape space, the five systems were able to achieve their target structures.

4.1.3.3 Second Example of a Discrete Physical Information Encoding Scheme

A solution to the shortcomings of the first physical information encoding scheme is achieved by using rapid prototyping to create the components (Fig. 7.19). As with the first discrete shape space, three shape primitives are used in association with a base square shape. Smaller and stronger components can be built, since rapid prototyping is used. As a result, neighbouring lock shapes on the same component are well defined. The main body of a component is made from plastic. Similar to the first discrete assembly protocol space, a 3-magnetic-bit encoding scheme is used. Lock-to-lock interactions never occur and more magnets can be placed within the sides of the components (creating an air gap along an edge for selective binding), because of the greater precision in building components using rapid prototyping. Here, the 3-magnetic-bit encoding uses one magnet in each position associated with a key and two magnets in each position associated with a lock (Table 7.1). This ensures strong binding between keys and locks, and weak binding between keys. Weak binding can then be avoided through an appropriate environment temperature setting. Therefore, key-to-key matching errors can be avoided and key-to-lock matching errors can be reduced through proper designation of the 3-magnetic-bit encoding to keys and locks.

Fig. 7.19

Design space for the second physical information encoding scheme (left), physical specification (in mm, centre), and example physical component (right)

Fig. 7.20

The three types of target structures (from left to right): I-shape (Ex1), L-shape (Ex2), and T-shape (Ex3)

The corresponding environment information for this second discrete design space contrasts with the environment for the first discrete design space in the materials (fabricated from plastic using rapid prototyping) and shaking motion (in a 2D orbital motion, automated using a Maxi Mix II Vortex Mixer). Achieving an appropriate environment temperature, to maintain bonds between complementary components and break bonds between conflicting components, was extremely difficult. As with the two previous physical self-assembling systems examples, the environment temperature corresponds to a mechanical shaking level. This mechanical shaking level is a combination of the speed of the mixer, the total number of components in the system, and the size of the tray environment. Also, the Maxi Mix II Vortex Mixer is not a purely orbital shaker. A spring joint in the mixer adds variability to the shaking motion. This variability is another factor in the mechanical shaking level. However, a setting of 1,050  rpm was found to create the appropriate temperature (abstractly equivalent to 1).

5 Experiments and Results

Following the design space examples, components resulting from the second physical information encoding scheme (in correspondence with their automated environment) are used in three different experiments, denoted by Ex1, Ex2 and Ex3, to show how self-assembling systems can be programmed via physically encoded information. Our hypothesis was that, given the attributes of a target structure, information encoded in the components can be used to enable the components to self-assemble into that target structure. The three-level approach was used to test our hypothesis, abstractly (Level II) and physically (Level III). A different type of target structure was assigned to each experiment: an I-shape, an L-shape, and a T-shape (Fig. 7.20). Enough components were supplied to create up to three instances of a given shape, and five trials were run for each experiment. A trial was evaluated to be successful if all three instances of a shape were created at Level II, and if at least one instance was created at Level III. The experimental procedure and results are described according to the three-level approach: defining a self-assembly rule set (Level I), modelling using the cTAM (Level II), and physically testing systems using the second physical information encoding scheme (Level III).

5.1 Level I: Definition of Rule Set for Experiments

At Level I, self-assembly rules sets (including component definition) are specified for Level II and Level III experiments. The types of target structures shown in Fig. 7.20 were chosen because they offer various degrees of complexity in terms of the number of components required and symmetric/assymetric features in the structure. Consequently, none of the desired entities can be created by pattern formation exclusively, and it is appropriate to determine whether the components have sufficient information to achieve the target structures by self-assembly.

The independent variable in these experiments is the set of components, defined by their type and quantity. The dependent variable is the resulting self-assembled structures. For each experiment, a designed component set is specified along with a randomly generated component set, in order to test the independent variable. For the designed component sets, component types and quantities were specified to create a single target structure. After this initial set was specified, the quantity of each component type was multiplied by three to be able to create the maximum number of copies of target structures for each experiment (conducted at Level II and Level III; see next sections). For the randomly generated component sets, component types were specified by selecting with uniform probability the information (A to G, and $-$) assigned to each information site. Then, the quantity of each component type was also multiplied by three.

Table 7.2 Component type and quantities—represented as ‘(north, west, south, east) $\times$ #’, where the directions refer to component information locations, and the # symbol represents the quantity—for each of the designed and randomly generated component sets, in the three experiments (Ex)

Component rules and quantities are provided in Table 7.2. The environment rule associated with size was set to 10 units, and the temperature was $T=1$. The system rules (component interactions) followed Table 7.1.

5.2 Level II: Virtual Execution of Rule Set for Experiments

For each experiment, the cTAM was used to virtually evaluate the ability of each self-assembly rule set (designed or randomly generated) to create its respective target structure. The Level II experimental set-up and results are described below.

5.2.1 Level II: Experimental Set-Up

Component rules from Table 7.2 and the environment rules were mapped to an abstract representation appropriate for the cTAM. Each component’s shape was a unit square. The size of the environment was represented as a ratio between the boundary of the environment and the size of the base component shape (square with neutral sites at all four information locations). The environment size used in the cTAM was $10 \times 10$ units in these experiments. Additionally, since the cTAM selects components at random from an assembly set to step through the self-assembly process, a different random seed was used to initialise the cTAM for each trial. Five trials were conducted for each of the two self-assembly rule sets associated with each experiment.

5.2.2 Level II: Experimental Results

At Level II, the cTAM was used to evaluate each trial. Each of the designed component sets successfully created three instances of their applicable target structure. These results show that even with no component acting as a seed structure, it is still possible to successfully create target structures when appropriate component information is used. Furthermore, these results also show that it is possible to create multiple copies of the same desired entity, again when appropriate component information is used.

In contrast, none of the randomly generated component sets successfully created at least one instance of a desired entity, in each experiment. The reasons for the unsuccessful results can be explained in two ways. (1) The first reason, which applies to the randomly generated component sets in Ex1 and Ex3, was that no compatible fits rule existed for the information encoded in the components. As a result, no assembly could take place with these components. (2) The second reason, which applies to the randomly generated component set in Ex2, is that multiple fits rules apply to either multiple component types or to multiple information locations within the same component type. For example, there were two information locations labelled D in Component Type 3 (see Table 7.2, Ex2, random set). These two information locations could bind to information locations labelled C in Component Type 1 and Component Type 2. In addition, since multiple Component Type 3’s existed, they could also bind to each other. As a result, the generated structures were not stable, meaning that during different executions of the cTAM, similar structures would not be created.

5.3 Level III: Physical Realisation of Rule Set for Experiments

With the success of each system using a designed component set, a Level III translation was performed for each experiment. A Level III translation was not performed on the systems using a randomly generated component set, since they were not successful. The Level III experimental set-up and results are described below.

5.3.1 Level III: Experimental Set-Up

Component mapping followed Fig. 7.19. Components were fabricated using an Eden 333 Polyjet rapid prototyping machine with Vero Grey resin. Neodymium (NdFeB) disc magnets ($1/16^{\prime \prime } \times 1/32^{\prime \prime }$, diameter $\times$ radius; grade N50) were inserted into the components. Blue/red paint (north/south) was used to mark magnetic patterns. Mapping for the environment size was done in accordance with the base component size, to specify the dimensions of the circular environment tray. The tray was fabricated using a Dimensions Elite rapid prototyping machine with ABS plastic (sparse-fill option was used to create a rough surface texture). The outer radius of the tray was 135 mm and the inner radius 125 mm, while the outer wall height was 9 mm and the inner wall height 6 mm. The tray was mounted to a Maxi Mix II Vortex Mixer (using a tray mounting bracket, also fabricated using the Dimensions printer). A tray lid was cut using a Trotec Speedy 300 Laser Engraver laser cutting machine with a 2 mm clear acrylic sheet. The tray lid was secured to the tray using polycarbonate screws and wing nuts. Further hardware details are provided in [12].

Each physical trial followed seven steps:

• (a) Set the continuous speed control on the Maxi Mix II Vortex Mixer to 1,050  rpm.

• (b) Secure the mixer to a table, using a 3” c-clamp and six hex nuts (to help secure the c-clamp to the back of the mixer).

• (c) Randomly place components on the surface of the tray (trying to ensure that complementary binding sites on the components are not in-line with each other).

• (d) Secure the tray lid.

• (e) Run the mixer for 20 min.

• (f) Turn the mixer off.

• (g) Record the state of the system, observations including: the number of target structures created, the number of matching errors (between conflicting physical information, where no fits rule is applicable), and the number of assembly errors (partial attachment where a fits rule is applicable).

 

5.3.2 Level III: Experimental Results

The results for the five trials in each of the three experiments are summarised in Fig. 7.21. Each trial, except for one, was able to create at least one instance of a desired entity. Figure 7.22 shows the final state for the best trial, for each of the three experiments (Ex1, trial 4; Ex2, trial 5; and Ex3, trial 3). In Ex3, one trial was unsuccessful, as the components self-assembled into two partial structures, which moved into a spatial configuration that would not allow the self-assembly process to continue (Fig. 7.22, bottom right).

Fig. 7.21

Experimental results (numbered by Ex/trial): bar chart showing the number of successful target structures (in black) and matching errors (in grey)

Fig. 7.22

Best experimentsl results (numbered by Ex/trial) and an example error (bottom right), corresponding to Fig. 7.21

No assembly errors were present at the end of each of the five trials in any of the experiments. Only Ex1 had zero matching errors, due to the single physical code pair used. Ex2 had more matching errors present at the end of trials in comparison to Ex3, for two reasons. (1) The two physical code pairs used in Ex2 had the highest matching error possibility. (2) The total number of components used in Ex2 were fewer, hence there were less components moving around to break apart assembly errors. With the exception of one trial in Ex3, at least one desired entity was successfully created in each trial in each experiment. Therefore, all the experiments were a success.

5.4 Discussion

Three experiments were conducted to show how self-assembling systems could be programmed via physically encoded information. At Level II, all three designed rule sets were successful in creating their respective target structures, whereas the randomly generated rule sets were not. At Level III, all the translated designed rule sets were able to create at least one target structure (with the exception of one trial from Ex3). Therefore, these successful experimental results confirm our hypothesis that, given the attributes of a target structure, information encoded in the components can be used to enable the components to self-assemble into that target structure.

These successful results add to those previously achieved using the three-level approach [14]. We have also built upon the work presented in this chapter by using the three-level approach to design 3D self-assembling systems (in terms of component movement), create staged self-assembling systems (where the self-assembly process is divided into time intervals), and evolve self-assembling systems. More specifically, the following findings emerged from this work:

• Although the benefits of 3D DNA systems have been demonstrated theoretically [48], the creation of physical 3D DNA Tiles does not appear to have been achieved to date. We have fabricated 3D components using rapid prototyping that use a higher-dimensional magnetic-bit encoding scheme to create 3D self-assembling systems, which incorporate rotations in component-component interactions [16].

• One of the practical challenges facing the creation of self-assembling systems is being able to exploit a limited set of components and their binding mechanisms. “Staging”, which consists of adding new components into the environment at different time intervals, is one method to address this challenge by encoding the construction of a target structure in the staging algorithm itself, and not exclusively into the design of the components. We showed how the interplay between component physical features over time can be used to further reduce assembly errors and exploit rotational properties to create physical 2D and 3D self-assembled structures [17]. In addition, we have also shown in theory how staging can be used to leverage a limited self-assembly rule set, where previously used component information can be reused at later time intervals to create more complex structures that would not otherwise be possible [12, 18].

• Another practical challenge is that it becomes cumbersome, if not impossible, to define self-assembly rule sets for more sophisticated self-assembling systems. Therefore, we have also created new design techniques that incorporate Evolutionary Computing [42] into our inherently bottom-up three-level approach. We have used Evolutionary Computing to evolve self-assembly rule sets to physically create self-assembling systems in 2D [15] and 3D [16].

As future work, we are investigating expanded rule sets, including construction and deconstruction operations, to create dynamic structures. We are also exploring the influence of changing environmental conditions over time (i.e., staged environment) in conjunction with more cell-like components that can reconfigure themselves based on temporal and positional information to create more sophisticated staged self-assembling systems. Dynamic interactions, changing environmental conditions, and adjustable components together are being used to conduct research into using physically encoded information to design self-assembling machines.

6 Conclusions

How does one program self-assembling systems? In the pursuit of answering this question, we first presented L. S. and R. Penrose’s classic physical self-assembly [51] as a case study. We demonstrated how physically encoded information in the components, in relation to the interaction rules between components and their environment, enables the self-assembly process by amplifying the seed structure. We tested a version of the Penrose system to see if our analysis was consistent with the physical results. The successful outcome confirmed that the Penrose system truly is a mechanical analogue of self-reproduction. As an extension of our methodology in the case study, we presented a three-level approach for programming self-assembling systems. The approach involves specifying a set of self-assembly rules, modelling these rules to determine the outcome of a system in software, and translating to a physical system by mapping the set of rules using physically encoded information. At Level I, we presented a methodology for specifying a self-assembly rule set for 2D systems. At Level II, we presented a new modelling technique, the cTAM, for modelling self-assembling systems in 2D (with component rotations, no use of seed components, and concurrent self-assembly of multiple structures). At Level III, we presented two physical information encoding schemes, which used different physical properties to reduce errors and enable the self-assembly process. In addition to the original five experiments used with the three-level approach, we presented three new experiments. Rapid prototyping was used in these experiments to construct the translated components and their environment. The successful experimental results demonstrate how our three-level approach can be used for programming self-assembling systems via physically encoded information.