Command Sequence GA

The command GA uses a model found by the morphology GA that can self-replicate. It then finds a location where a copy of the model, in some orientation, can be placed in the area reachable by the end effectors. Once this location (goal location) is found, it tries to find a sequence of commands that end with a copy of the model existing in this location.

There are three types of commands: swivel, attach and detach. A swivel command tries to swivel one of the swivel blocks. The attach command creates a new block beside an electromagnetic block and attaches them. The new block can only be created if its initial location is only adjacent to electromagnetic blocks. The detach command causes a block in the copy that is currently attached to an electromagnetic block to detach. To simplify the command sequence, this block can never be reattached to the electromagnetic block.

In the simulation for this GA, a few changes are made to account for the new blocks being added. First, all new blocks that are created to make a copy of the model are treated as normal blocks for simplicity. This can be done since any block can remain passive and act just like a normal block. Second, swivel motions are allowed that create connections between two blocks in the copy. Lastly, electromagnetic blocks are assumed to not make a connection unless the connection already exists in the model, or the connection is created by an attach command.

The GA used to find command sequences for both of the morphologies in Figure 3, used the parameters defined in Table 3.

Table 3: Parameter values for the command sequence GA

Genome Encoding

The command sequences are encoded as an array of floating point numbers from 0.0 to 1.0. Three floats represent each command and any extra floats at the end of the array are ignored. The first float describes the command from the three available (swivel, attach detach). The encoding for the last two floats is described in Table 4.

Table 4: Description of how the 2^nd and 3^rd floats in a block are used to encode command sequences for the command GA

Creating Successive Generations

The next generation is created by first taking the top percentage of the population (defined in Table 3) and copying those genomes directly into the new generation without mutation. Then, the rest of the new generation is filled by children created using the dual point crossover technique described in Genetic Algorithims who then undergo mutation. The parents to be used for each mating are chosen randomly with the probability of choosing a particular model to act as a parent being directly proportional to that model’s fitness.

Mutations

Whenever a child is created in a new generation, it undergoes a maximum of three types of mutation: modification, addition and subtraction. Modification and subtraction are both applied to each element in the array, whereas addition is only applied to the entire array. The probabilities of any of these mutations occurring are described in Table 3. Modification replaces a given element with a new random float. Subtraction removes a given element from the array and fills the empty space by pushing elements from the right. Addition appends a random float to the end of the array.

Fitness Function

The fitness function is based on three goals. The first, and most important is the ability to create a structural copy of the model. Initially, this was measured simply by the amount of the goal location containing blocks for the copy. However, the GA was having problems filling in corners of the goal location. I hypothesized that this was occurring because the corners are harder to fill in once blocks have already been placed. To solve this, the corners were weighted so that each ninety-degree angle made by adjacent locations in the goal location caused the corner to gain an extra 25% value when filled. This caused early solutions where the corners were filled first to be ranked slightly above solutions where other locations were filled first, causing the GA to have less of a chance of backing itself into a corner. This change was successful, causing the GA to consistently find solutions.
The second goal for the GA it is to try to minimize the number of locations where blocks are created. It is more impressive for a machine to be able to self-replicate if it is taking materials from a few locations instead of having the placement of pieces be highly structured.

The last goal, which was added near the end to make the solutions more efficient, is to punish a solution if it creates more blocks for the copy than is strictly necessary. Before this was added, the best solutions still contained many blocks that were created but not used. This has also seemed to reduce the number of pointless moves contained in the command sequence. 

The final fitness function is:

g(cmds) = 0.8p + 0.2(c-s+1)/c -0.03e

p = weighted fraction of the goal location covered
c = number of blocks in the model
s = number of locations where blocks were created
e = number of extra blocks created beyond those needed by the copy