Towards an Evolutionary Design of Modular Robots for Industry - Foundations on Natural and Artificial Computation - page 54

As the search space determined by the possible morphological configurations
and control systems is huge, not necessarily continuous and usually very badly
configured, we have opted for using evolution in order to obtain the robot con-
figuration and control. However, most traditional evolutionary algorithms are
not very well suited to this type of search spaces due to their intrinsic decep-
tiveness. This is, for instance, when trying to produce a robot that moves in
a given direction, partial solutions that only lack a single module or solutions
with perfect morphology but some problem in the control may not move at all
or move in the opposite direction. Additionally, the evolutionary temporal scales
of the morphology and the control system must be quite different even though
they must be cooperatively coevolved. Finally, it is a problem where the pheno-
type and, consequently, the genotype is of variable size and there are all kinds
of dependences between phenotypic components.
As a first approach to address these problems, we propose a constructive
evolutionary algorithm. In fact, we have developed a constructive evolutionary
strategy, the operation of which can be summarized into the following steps:

1. Creation of a random population of size N modular robots encoding each
modular system as a tree. Each module is represented as a node with con-
nections to child nodes. Connections contain the information about the side
of the parent where the child is connected and the orientation of the child.
The root node is a rectangular module that acts as a structural base with
12 connection points.
2. Mutation: we have developed a set of mutation operators that can be applied
to each individual:

- Add Node : this operator generates n variations of the current morphology
by adding a new random module in a random position and orientation
to the robot. This phase evaluates the fitness of the n variations and
selects the best one replacing the parent morphology even if it is worse.
This decision was taken because adding a node can cause a fitness fall
in a given generation but act as a root for a higher growth in the next.
- Shake Modules : this operator generates n variations of the current robot
by changing the connections between modules. The change affects the
side of the parent module to which the child module is attached and the
orientation of the child. The fitness is calculated and the best variation
is selected.
- Shake Control : this operator generates n variations of the current robot
by changing, with probability p , all the control parameters of the mod-
ules. The fitness is calculated for each case and the best one is selected.
- Delete Nodes : this operator produces all the possible pruning variations
of a robot by deleting all the modules that are downstream from a given
connection. All the connections are pruned once and it is not allowed to
prune two connections at the same time. So, if a robot has m modules,
this operator will produce m

1 robots. The fitness is calculated for each
case and the best one is selected.

−