Construction Automation with Bio-Inspired Hierarchical Extremely Modular Systems

Zawidzka, Ela; Zawidzki, Machi

Loading...

Full Article

1.

Introduction

Construction automation deals with applying the principles of industrial automation to the construction sector or in the prefabrication of construction components.

Extremely Modular System (EMS for short) is a relatively new concept introduced a few years ago in [1]. It represents a new approach to the design of engineering structures and architectural objects where the assembly of congruent units allows for the creation of free-form shapes.

The main difference from the traditional modular systems used in engineering and building construction is the emphasis on the minimal diversity of types of modules, ideally—just one. This is why these systems are extremely modular.

These are five basic advantages of EMSs:

1)
Economical – as they are suitable for mass fabrication, thus lowering the cost, so they can be broadly applied;
2)
Functional – as they allow for reconfiguration, expansion, reduction;
3)
Robust – since every module that fails can be easily replaced with an identical but functional one;
4)
Discrete – as they are suitable for intelligent mathematical modeling, and their configurations can be subjected to discrete (multi-objective) optimization using efficient search algorithms;
5)
Uniform – this feature is advantageous for rapid deployment and automated assembly.

Pipe-Z (PZ) is a more fundamental system introduced in [2]. Its purpose was to form spatial mathematical knots by assembly of one type of unit (PZM), as shown in Fig. 1.

The shape of PZ is controlled by the relative twists of congruent modules in a sequence.

Truss-Z (TZ) is a skeletal-frame hybrid construction system introduced in [3] for creating free-form pedestrian ramps and ramp networks connecting any number of terminals in space. TZ is composed of four variations of a single basic module subjected to affine transformations (mirror reflection, rotation, and combination of both). Figure 2 shows an example of TZ.

Although originally Pipe-Z allows for the creation of single-branched structures, by the introduction of an additional “branching buds,” it is also possible to construct multi-branched structures. Such a system is called EMS-2; an example based on PZ with an additional dodecahedron branching bud is shown in Figure 3.1.

2.

The Nomenclature and Encoding

The basic elements for both EMS and qEMS are the units. They are added sequentially along the direction of the construction, as illustrated with PZ in Figure 4.

The core of the EMS concept is the shape of the unit, which allows the creation of various forms depending on its relative rotation. Its angular direction is relative to the directions of the branches, that is stems or twigs. For clarity all the following examples are reduced to 2D. Figure 5 shows examples of unit assembly for EMS and for the projection of SC³ to 2D, called SC².

1)
TZ is a strict EMS. By rotation, the basic unit can be added in two ways, determining the shape of the structure. 1 and 0 turn right and left along the direction of the structure, respectively. 2) SC² : the basic unit of this qEMS can be added in three ways: at the right, front, and left face, as indicated by numbers 1, 2, and 3, respectively.

In genetic algorithms, all candidate solutions have sets of properties encoded in so-called genotypes, usually as binary strings, arrays, trees, lists, or matrices, which can be mutated and/or altered [6].

A phenotype is an actual EMS with its (physical) form and structure encoded in a given genotype. Obviously, there is a bijection (one-to-one correspondence) between the set of genotypes and phenotypes.

Figure 6 illustrates the nature-inspired naming for the components ofan EMS phenotype and parts of the corresponding genotype, which is a simple nested list.

As illustrated in Figure 5, EMS-2 is comprised of two types of elements: the basic unit and bud. The units have two orientations: 0 and 1, and each stem ends with a pentagonal bud. For the consistency of notation, the initial unit is also attached to a “virtual” bud.

As mentioned in the Introduction, plesiohedra [4] are not considered as EMSs. The cube is the only regular solid that is also a plesiohedron [5]. Nevertheless, the multi-branched structures built with space-filling polyhedra can also be encoded in the same way. Figure 7 shows the genotype of the 2D projection (SC²) of the cube-based qEMS structure (SC³) shown in Figure 2.2.

As Figures 3 and 4 indicate, the hierarchical structures of EMS (and quasi-EMS) are defined as follows:

i.
In general, the structure is constructed with branches.
ii.
Branches are: stems and twigs.
iii.
Stems end with buds. Twigs do not have buds
iv.
Buds can have any number of faces (BFs)
v.
A branch can be connected only to a bud.
vi.
A stem has at least one unit. In the case of a one-unit long stem, it becomes a bud.
vii.
Stems must not form closed loops.
viii.
The first stem is connected to a “virtual” bud.
ix.
The first stem is also rooted to the initial terminal. There are no more stems directly attached to a terminal.
x.
A terminal can only be reached by a twig,% exclusive of the first stem and terminal.

Genotype of an i^th Extremely Modular System G_i is encoded as a sequence of branches. The sequence of branches included two sub-sequence of stems and twigs: $\begin{matrix} G_{i} : (S_{i}, T_{i}) \\ S_{i} : (s_{1}, s_{2}, \dots, s_{n}) \\ T_{i} : (t_{1}, t_{2}, \dots, t_{m}) \end{matrix}$ where S_i and T_i are the sequences of n stems and m twigs, respectively.

Moreover, s_j is a j^th stem from the sequence of stems S_i encoded in the following way: $s_{j} : (j, p_{j}, f_{j}, u_{j})$ where: j is the index of the j^th stem, p_j is its j^th parent, the index of that is the stem to which the j^th.

f_j is the index of the face of the parent’s bud (to which the jth stem is connected), and u is the sequence of units that constitute the j^th stem

Units u depend on the type of EMS. E.g., for the systems shown in Figures 3.1 and 3.2: u ∈ (0, 1) and u ∈ (1, 2, 3), respectively. Buds also depend on the type of EMS. E.g., Truss-Z and SC³ do not have additional units for buds.

In Truss-Z, buds are constructed by reflecting the last unit in the stem sequence across the longer base of the trapezoidal unit.

In SC³, the last unit in a stem serves as a branching bud. On the other hand, the buds for EMS-2 systems can have any shape. In the examples shown in Figures: 3.1, 6 and 8 & 9 they are: dodecahedron, pentagon and heptagon, respectively.

Since the first stem does not have a parent, p₁, and f₁ are dummies (blank).

The k^th twig from the sequence T_i is defined in the following way: $t_{k} : (p_{k}, f_{k}, u_{k})$ where p_k is the parenting stem to which this twig is connected,

f_k, is the index of the face of the parent’s bud (to which the k^th twig is connected), u_k is the sequence of units that constitute the k^th twig.

There is a full analogy between the list of twigs and stems.

3.

Operators on the EMS Genotype

There are seven operators collected in Table 1 that allow the construction of any EMS or the transformation of any EMS_A to any other EMS_B.

Table 1.

Steps for creating an Extremely Modular System or its transformation

Start	Transformation	Operator
General structure↓	↴Add a stem	aS [G_i, (i_i, BF_i, u_i)]
	Add twigs	aT[G_i, ((p₁, BF₁, u₁),(p₂, BF₂, u₂),…,(p_k, BF_k, U_k))]
	Remove branches	rB [G_i, ((p₁, BF₁), (p₂, BF₂), …,(p_i, BF_k))]
Substructure @ buds	↲
Substructure @ buds	↴
↓	Displace branches	dB[G_i, (((p_i, BF_i),(p_j, BF_j)),…)]
Units @ branches	↲
Units @ branches	↴
↓	Add units @ branches	aU[G_i,((p₁,BF₁,(v₁¹,l₁¹),…,(v_k¹,l_k¹)),…,(p_j,BF_j,(v₁^j,l₁^j),…,(v_k^j,l_k^j)))]
	Remove units @ branches	rU[G_i,((p₁,BF₁,(l₁¹,…,l_k¹),…,(p_J,BF_J,(l₁^j,…,l_k^J)))]
	Invert units @ branches	iU[G_i ((p₁,BF₁,(l₁¹,…,l_k¹),…,(p_j,BF_j,(l₁^j,…,l_k^j)))]
End	↲

In addition, four operators for the population-based algorithm are defined and listed below.

Random genotype generator $r G [(s_{\min}, s_{\min}), (t_{\min}, t_{\max}), (u_{\min}, u_{\max})]$ where G_k, is the number of stems, t is the number of twigs, and u is the number of units to be generated in all branches.

Fix genotype $F [G_{k}, s, t, l]$ where G, is the given k^th genotype,

s is the desired number of stems,

t is the desired number of twigs,

l is the number of units generated randomly in additional branches, if applicable.

Tabulate genotype

This function transcribes genotype G_i into matrix T[G_i] with respect to the buds. See Figure 8 for an illustrative example.

Compare (tabulated) genotypes $C [G_{j}, G_{k}] = Δ (T * [G_{j}], T * [G_{k}])$ where T* [G_j] is the normalized and tabulated genotype G_j and T* [G_k] is the normalized and tabulated genotype G_k.

Normalization here means that T[G_j] and T [G_k] have the same general structure. For example, if the dimensions of these genotypes differ, dummy elements are added. Moreover, C[G_j, G_k] ≥ 0.

Δ sums up the differences between the bit-strings of respective branches of the compared genotypes. Figure 9 illustrates the way how Δ is calculated.

Finally, four types of mutation and their combination have been defined as follows:

Displace-branch-mutation

M d B [g_{k}, m_{i}]

where is the g_k is the k^th genotype, m_i is the normalized intensity of mutation, so that for 0 there is no displacement and for 1 all branches are displaced.

Add-unit-mutation

M a U [g_{k}, m_{i}]

in this case, m_i is normalized so that for 0, no units are added, and for 1, the number of units is doubled. Loci for the added units are distributed randomly among the branches. The values of the added units are random integers: 0 or 1.

Remove-unit-mutation

M r U [g_{k}, m_{i}]

Unlike stems, twigs can have zero length. Here, m_i is normalized so that for 0, no unit is removed, and for 1, all units but one randomly selected unit per stem are removed. The loci for units to be removed are distributed randomly among the branches.

Invert-unit-mutation

M i U [g_{k}, m_{i}]

where m_i is normalized, so that for 0 there is no change to any unit, and for 1 the values of all units are inverted. The loci for units to be inverted are distributed randomly among the branches.

Multi-mutation (combines all types of mutations defined previously)

M [g_{k}, m_{i}, (w_{d b}, w_{a U}, w_{r U}, w_{i U})]

where m_i is the normalized intensity of mutation,

M randomly selects the mutation type according to parameters w_db, w_aU, w_rU, and w_iU, which are the normalized weights (from 0 to 1) for corresponding mutations: MdB, MaU, MrU, and MiU.

4.

Minimization by Evolution Strategy

Evolution Strategy is a classic nature-inspired heuristic method introduced in [7].

Unlike other evolutionary algorithms, it does not employ recombination but only intensive mutation. For a review of the literature on this method, see [8].

This experiment is a two-objective minimization defined as follows:

1)
Create a layout of a multi-branch Truss-Z (MTZ).
2)
There are six terminals at given locations: the initial terminal (T_s), and five aligned terminals T₁…T₅, as shown in Figure 15.
3)
The (initial) direction of the first unit is given at T_s.
4)
The number of units is to be minimal.
5)
The reaching error (rE) is to be minimal (explained below).

Reaching error (rE) is the sum of distances between each terminal and respective twig tips, as illustrated in Figure 10.

The cost function CF for a given i^th multi-branch Truss-Z (MTZ_i) with m number of destination terminals is calculated as follows: $C F (M T Z_{i}) = n + w_{p} \times r E = \int_{i = 1}^{m} ε_{i}$ where n is the total number of units in MTZ, ε_i is the distance between the i^th terminal and corresponding twig tip, w_p is the penalizing weight adjusted by trial-and-error; for small values of w_p algorithm gets stuck in local minima and as a result, solutions do not improve.

The initial population is generated randomly using rG operator described above. However, it is rational to start from the most reasonable initial population by using certain observations. E.g., the number of twigs must be exactly 5. This is because only twigs can reach the terminals, and there are five of them. However, with the number of stems it is not so obvious. Figure 11 shows four different allowable MTZ configurations connecting five terminals with the initial terminal T_S.

Therefore, the number of stems in every candidate solution must be within the range [2,5]. The initial population of 200 MTZs has been generated with the following parameters: $r G [(s_{\min}, s_{\max}), (t_{\min}, t_{\max}), (u_{\min}, u_{\max})]$ the number of stems: s_min = 2, s_max = 5;

the number of twigs: t_min = t_max = 5;

the number of units in each branch: u_min = 5, u_max = 15.

Several trials at various combinations of parameters have been performed. Each experiment has been terminated after 100 iterations. Figure 12 shows the best phenotypes in the final trial.

As Figure 12 indicates, in the beginning, several individuals were infeasible due to self-intersection. Nevertheless, relatively soon, this problem disappeared, as gradually the feasible offspring were produced by infeasible parents. Figure 13 shows the final solution and its three-dimensional interpretation.

5.

Conclusion

The concept of hierarchical structures has been outlined in the context of Extremely Modular Systems. The biology-inspired nomenclature, genetic encoding, and operations for this class of structures have been explained and illustrated.

Although the evolution strategy-based algorithm presented here has not been optimized for efficiency, it shows relatively good convergence. For more information on this approach, see [9].

Loading...

Construction Automation with Bio-Inspired Hierarchical Extremely Modular Systems

Full Article

Paradigm

My account