System description

System description

The robots used in this work have a genome based on what has been previously used in RoboGen[1], which is a single-rooted tree graph encoding the layout of the robot body. A few extensions have been made to incorporate the robot brain, a fully connected recurrent neural network, in this genome as well. This chapter outlines the properties of the resulting genome as well as the phenotypical properties the resulting robots possess.

Genome

In RoboGen, each robot consists of a number of body parts taken from a predefined set of parts T . These parts form a tree graph, where each node encodes a body part. This graph serves as a building plan for both a robot’s body and brain in either simulation or real space. The genome employed in this work still consists of a set of nodes R forming a fully connected tree graph. Extending the tree with brain encoding properties has resulted in each node now having the following parameters:

• A body part type τ ∈ T . The part type implies a few other properties of the node, which are detailed in section Phenome along with the actual parts being used.
• A list of values πbody for the numeric parameters specified by the body part type.
• An orientation ω encoding the pose of the body part in space.
• A set of labeled node edges C, describing how this body part is attached to other body parts. Each connection c i ∈ C is a tuple (r,f,t) where r ∈ R defines a child node and f and t are the from and to slots of the connection respectively. Which slots are actually supported by a specific node is one of the implied properties of the part type τ. As the genome is a tree structure, C is not allowed to form any cycles in the node graph.
• Two lists of neuron types and parameters, N output and N hidden. Each is a list of tuples (t, π neuron), where t ∈ Λ is a supported neuron type and π neuron is a list of values for the parameters specified by this neuron type. |N output | is determined by the number of outputs specified by the body part type, |N hidden | can vary.
• A set of paths Q. Each path q i ∈ Q is a tuple (s,w,o 1,t 1,o 2,t 2) with s being an ordered list positive integers (s 0, s 1, ...), |s| ≥ 0 and w a numeric weight. Furthermore, t 1 ∈ {input, output, hidden}, t 2 ∈ {output, hidden} denote the type of a neuron, with o1,o2 being corresponding integer offset values. Every path q ultimately encodes a connection in the neural network of the robot.

Phenome

The genome defined in section Genome forms a blueprint for a robot, which can be turned into an actual robot representation only given the set of part types T . Every part type t ∈ T defines the following properties:

• The physical properties of the part, such as weight and structure.
• A number of attachment slots, describing where this part can be attached to other parts. A single slot is a combination of a point on the part surface, a vector normal to the attachment surface and a vector tangent to this normal vector describing its +zero orientation+.
• A number of inputs (i.e. sensors) i contained within the part. An input is defined as a single numerical value, if a sensor outputs more than one value this results in multiple defined inputs.
• A number of outputs (i.e. actuators) o on the part. Again, if an actuator has multiple control values it defines multiple outputs.
• A number of (bounded) numeric parameters, which could in principle

Body part types

This section details the set T of body part types used in the experiments in this work. In large, these are the same body parts as used by RoboGen at the time of this writing[2], though improvements and changes to this package are continuously made and they may no longer match. The parts are therefore detailed briefly for completeness.

|. Part |. Slots |. Inputs |. Outputs |. Parameters |. Image | | Core Component | 6 | 6 | 0 | 0 | !{width:200px}robogen-core.component.png! | | Fixed Brick | 6 | 0 | 0 | 0 | !{width:200px}robogen-brick.png! | | Parametric Bar Joint | 2 | 0 | 0 | 3 | !{width:200px}robogen-param.bar.joint.png! | | Active Hinge Joint | 2 | 0 | 1 | 0 | !{width:200px}robogen-active.hinge.holder.png! | | Passive Hinge Joint | 2 | 0 | 0 | 0 | !{width:200px}robogen-passive.hinge.holder.png! | | Light Sensor | 2 | 1 | 0 | 0 | !{width:200px}robogen-light.sensor.png! | | Touch Sensor | 2 | 2 | 0 | 0 | !{width:200px}robogen-touch.sensor.png! |

Table 1. Body part type properties as described at the start of the section.

Detailed structure meshes suitable for use with a 3D-printer are available for these body parts, such that these robots could in principle be constructed in real life. Table 1. shows a brief overview of each type’s properties as enumerated at the start of this section, accompanied by a short section dedicated to each part. In addition to the part-specific parameters, each part has three color parameters (red, green and blue) which are used for visualisation purposes.

Core component

This component forms the root of every robot and in real life holds the electronics controlling it. Two sensors are included on the component: an accelerometer and a gyroscope. The x, y, z values for both these sensors result in a total of 6 inputs. The component has four attachment slots: apart from the top and bottom face every side can be attached.

Fixed brick

The fixed brick has the same dimensions as the core component, but does not contain any electronics or sensors. In addition, other components can be attached to all six faces.

Parametric bar joint

The parametric bar joint introduces fixed angles into a robot structure. The part has three parameters:

• H, the length of the joint, between 2 and 10 centimeters
• α, the tilt of the joint, between −90 and 90 degrees
• β, the rotation of the joint, between 0 and 90 degrees

Active hinge joint

A simple hinge joint powered by a servo motor. It has one output value, which is truncated to the interval [0, 1] and corresponds to a target position between −45 and 45 degrees.

Passive hinge joint

Similar to the active hinge joint, but as the name suggests the joint is not powered by a servo but rather moves freely.

Light sensor

A simple light sensor. Defines one input value in the interval [0, 1] depending on the intensity of the light reaching it.

Touch sensor

A two-value binary touch sensor. Each sensor covers half of the total part surface, and outputs a value that is either 0 or 1 depending on whether touch is registered.

Neuron types

The neurons in the hidden and output layers of the neural network that is the robot’s brain have one of three activation functions. The first two, linear and sigmoid, are common neural network activations whose parameter set pineuron consists of a bias and a gain value. The third possible type is an oscillator neuron, whose value depends not on its input values but rather is a sinusoid depending only on the current time. The three parameters for this neuron type are the wave period, phase offset and gain.

Genotype to phenotype conversion

Construction of an actual robot from a genotype starts at the root node, which is always a core component. The robot body is constructed by recursively traversing the tree edges attaching components at the from and to slots of the connection. This process aligns the body parts such that the slot normal vectors point in opposite directions, the slot tangent vectors point in the same direction and the slot surfaces touch at the slot points. The interface of the robot’s neural network results directly from parts’ inputs and outputs, all of which is represented by one respective input or output neuron in the brain. The properties of each node’s output neurons are set to match the values in its N output . For each node, |N hidden | hidden neurons are constructed with corresponding type and parameter values. The fully connected neural network is initialized with zero weights for all connections. For each node r i, the path portion s of Q is traversed following node edges where the from slot f matches the path value si, until no s i are left upon which point node r j is reached. The weight of the network connection between r i(t 1, o 1 ) and r j(t 2, o 2 ) is then set to the weight portion w of Q, where r i(t,o) denotes the oth neuron of type t belonging to node r i. If at any point the path cannot be traversed, either because a node edge at the from slot si is not available or because r i(t 1, o 1) or r j(t 2, o 2 ) does not exist, the path is simply ignored and no weight is set.

|. Parameter |. Description | | |R|max | Maximum number of nodes | | |R|min | Minimum number of nodes | | o max | Maximum number of outputs in a robot | | i max | Maximum number of inputs in a robot | | h max | Maximum number of hidden neurons in a robot | | ν(τ) | Function returning the maximum number of nodes with part type τ | | T root | Set of allowed part types for the tree root node | | T child | Set of allowed part types for the tree child nodes |

Table 2. Genotype restriction parameters.

Restrictions

The genome paired with the available body parts impose a few natural restrictions on a genotype, namely the values for τ and V as well as from and to slot values for the tree edges. Next to these restrictions, a genotype is further constrained by several system parameters, which are listed in Table 2. Paths in Q that do not resolve to any node/neuron combination are allowed, they will simply not lead to any neural connection. Furthermore, the phenotype space is constrained to containing only robots that could realistically be constructed, i.e. robots with intersecting body parts are rejected.

Evolution

Two parent robots can produce offspring through several operations on their genotype trees. This section discusses these operation in the order in which they are applied to create a child robot c from parents a and b.

Crossover

In the first step, a node a c from a is randomly chosen to be the crossover point. A random node b c from b is chosen to replace this node, with the condition that doing so would not violate the restrictions as given in previous section. If no such node is available, evolution fails at this point and no offspring is produced. If such a node is found, c 1 is created by duplicating a and replacing the subtree specified by a c with the subtree b c.

Subtree removal

This step involves picking a random node from c 1 and removing it and its subtree from c 1 to produce c 2. Subtree removal happens with a probability P remove subtree, which is an experimental parameter.

Subtree duplication

In subtree duplication, a random node d from c 2 is chosen to be duplicated, along with a random free slot on one of c 2’s parts, again only provided that duplicating this node would not violate robot restrictions. The subtree specified by d is then duplicated onto the chosen free slot to produce c 3. This operation is performed with parameter probability p duplicate subtree. If no trees could be duplicated without violating restrictions, this step is skipped and c 3 = c 2.

Subtree swap

With probability p swap subtree, a random node s 1 is chosen from c 3. Another random node s 2 is chosen provided it has no ancestral relationship with s 1 (i.e. it is not a parent or child of this node). If no such node is available the step is again skipped, otherwise s 1 and s 2 are swapped in c 3 to produce c 4.

Hidden neuron and neural connection removal

For each node in c 4, its hidden neurons N hidden and paths Q are traversed. For each hidden neuron, a choice is made to either keep or delete the neuron with probability p remove hidden neuron. The same decision is made for paths in Q, which are removed with probability p remove neural connection. The resulting genotype is c 5.

Parameter mutation

Each node in c 5 has the parameter set π body and parameter sets π neuron for each hidden or output neuron. These parameters π are all iterated, and a new parameter π∗ is generated with a random uniform draw from within the valid range of the respective parameter. The parameter is then changed from c 5 to c 6 to have the value (1−ε)π+επ∗, where ε is a property that determines the mutation rate.

Hidden neuron and neural connection addition

To prevent the number of hidden neurons from tending to zero over many generations, hidden neurons are added to c 6 to create c 7. The number of newly created hidden neurons in c 6 is equal to the expected number of removed hidden neurons between c 4 and c 5. This is done to keep the number of neurons the same on average, while not keeping it strictly the same between generations. The type and parameters of newly created hidden neurons in c 7 are randomly generated. A similar process is performed for each neuron’s paths in Q, which are added in an equal number as that is expected to have been removed. It should be noted that these paths are initialized to point to valid neurons, so no broken paths are initially generated. Path weights are randomly drawn.

Part addition

Again in order to keep robot complexity roughly the same, a new part is added with a probability proportional to the number of parts that are expected to have been removed by subtree removal, minus the number of parts expected to have been added by subtree duplication. The new part is randomly generated with both hidden neurons, neural connections and all parameters, and attached to a random free slot on the tree to produce the final robot c. Again, this step is skipped if adding a part would violate restrictions.

fn1. Joshua Auerbach et al. “RoboGen: Robot Generation through Artificial Evolution”. In: Artificial Life 14: Proceedings of the Fourteenth International Conference on the Synthesis and Simulation of Living Systems. EPFL-CONF-200995. The MIT Press. 2014, pp. 136–137.

fn2. http://robogen.org/docs/robot-body-parts/