Embedded Solver

A third approach to the NTP problem was to incorporate the network flow into the representation of the structure. Thus structures and solutions evolve together: instead of using a network flow algorithm to find a flow, the flow is uniquely encoded in the genetic code of the structure, and is allowed to evolve along with it.

With a few modifications we extended the genotype to represent not only the position of the bricks, but also a unique flow for each force into a sink. With this, a structure can evolve along with the flows that represent a solution to the NTP problem.

As seen in the previous sections, a set of flows, one for each force, determines the total torque demanded from each joint in the structure (eq. 2.2). With the embedded solver, the evolutionary algorithm searches both the space of structure layouts and the space of flows at the same time. If the torques generated by the distribution of forces specified by the genotype exceed the joints' capacities, the structure is considered invalid.

Our representation for bricks structures (see section 2.3) is a tree graph whose nodes represent bricks. All descendants of a node are bricks which are physically in contact with the parent. In a structure there may be multiple paths from a brick to the ground, but genetically, there is a unique branch from each brick to the root. The root node is always a brick that rests on the ground, so all paths that follow the tree structure terminate on the ground. The following extensions to the genotype allowed us to evolve a structure along with the solution to the NTP problem:

1.

Load flows only from descendant to ancestor

Loads flow only down from descendants to parents. This defines the positive or negative sign of for each joint and force. For the previous algorithms we had an undirected graph. Now the graph is strictly directed: for each brick pair a,b either joint j(a,b) exists or j(b,a), but not both.

2.

Multiple trees rooted at grounds

Instead of only one root, there can be multiple roots now situated at the grounds of the problem. Each load now has at least one possible path to flow to a sink, although it may or may not violate the joint's constraints.

3.

``Adoptive'' parents may also bear weight

When two bricks happen to be physically linked, but neither of them is a descendant of the other, the first one^2.3 will become an ``adoptive'' parent, so the joint created flows from the lower-order brick to the higher-order.

4.

Flow determined by joint size and weight vector.

A weight parameter w_j was added to the representation of the joints. When a joint is created, w_j is initialized to 1, but then it may change by random mutation or by recombination. The flow for each force and joint is determined by the joint size (number of knobs) and the flow weight, as follows:

Let x be a brick in the path of force F. The flow of Finto x must equal its flow out of x, thus

$$F_{x}=\sum _{a}\phi _{F}(a,x)=\sum _{b}\phi _{F}(x,b)$$ (2.4)

The outgoing flow is uniquely determined by F_x and the proportion that goes to each parent b of x (either ``adoptive'' or ``original'').

For each brick b that is a parent of x, let be the size (in knobs) of the joint j(x,b) and w(x,b) the encoded weight of the joint. Let and . For each joint now we define the proportion of total flow that follows each outgoing path as:

$$\lambda (x,b)=\frac{\omega (x,b)w(x,b)}{\Omega W}$$ (2.5)

which defines the behavior of all flows going through x:

$$\phi _{F}(x,b)=F_{x}\lambda (x,b)$$ (2.6)

With this configuration, the flow of a force through brick x is by default proportional to the size of the joint -- stronger joints are asked to support proportionally more weight. But the genotype encodes weights w(x,b) for each joint so the flow of the force can be redistributed.

5.

Additional Mutations

Two mutation operators were added to allow the structures to explore the space of possible flows:

(a)

Jump: A brick and its subtree of descendants is cut off from the original parent and becomes a descendant of one of its ``adoptive'' parents. This does not change the positions of any brick, but the directions of flow may change as bricks which were ancestors become descendants.

(b)

Redistribute Weight: A random joint's weight w_j is multiplied by a random number between zero and one resulting in a change of flow magnitudes.

This genotype extension was used for the tree experiments (section 2.8) and for EvoCAD (section 2.9). It does without any network problem solver and thus is much faster (by ten-fold, approximately) at the cost of failing to approve many valid structures. In all, there was a speed benefit but changes of function were unlikely to happen (see section 2.6.2), meaning that some of the richness of the dynamics between evolving agent and complex environment was lost when we embedded more of the environment inside the agent.