Evolutionary Robotics and Open-Ended Design Automation - Biomimetics: Biologically Inspired Technologies - page 140

component. The T operator replaces a given link with two links that pass through a newly created
node. The new node is also connected to some other existing node. In both operators, the position of
the new nodes is specified in coordinates local to link being modified.
The T operator specifies the external connecting node by providing coordinates relative to link
being modified; the closest available node from the parent structure is used. This form of specifi-
cation helps assure the operators remain as context and order independent as possible. Figure 4.5c
shows how a certain sequence of operators will transform a dyad into a triad. Figure 4.5c also shows
how application of a tree of operators to the embryonic mechanism will transform it into an
arbitrary compound mechanism with exactly one DoF. Terminals of the tree are the actual links
of the mechanism.
Alternatively, bottom-up construction of a one-DoF mechanism begins at the leaves of the tree
with atomic building blocks and hierarchically assembles them into components. The atomic
building block is a dyad as shown in Figure 4.4a, and has exactly one DoF when grounded. The
composition operator ensures that the total number of DoF is not changed when two subcomponents
are combined, and thus the total product of the tree will also be a mechanism with exactly one DoF.
When combining two components, each of one DoF, the resulting assembly will have five DoF (one
DoF from each, plus three DoF released by ungrounding one of the components). The total DoF is
restored to one by eliminating four DoF through the merging of two point pairs. An example of this
process is shown in Figure 4.5d. Note that points must be merged in a way that avoids overlapping
constraints, such as causing two links to merge. The components may need to be scaled and oriented
for the merger to work. The ground link of the entire structure is specified at the root of the tree.
Figure 4.5b shows an application of this representation to the design of a single DoF mechanism
that when actuated traces a nearly exact straight line, without reference to an existing straight line.
This problem may seem somewhat arbitrary, but it was of major practical importance in the 19th
century and many notable inventors, including James Watt, spent a considerable amount of time
developing mechanisms to meet this requirement as the bootstrap of precision manufacturing. It
therefore serves as a nice benchmark for the ''inventiveness'' of the algorithm. Using evolutionary
computation based on tree representations, we were able to evolve machines, from scratch, that
infringe and outperform previous established designs (Lipson, 2006).

4.4.2 Developmental Representations

Other types of representations allow the robot's morphology to develop from a basic ''seed'' and a
set of context-free development rules. Consider, for example, the two rules ''A ! B'' and ''B ! AB.''
If we start with the seed ''A,'' and apply these two rules wherever they are applicable, the seed will
develop as follows: A ! B ! AB ! BAB ! ABBAB ! BABABBAB . . . , and so forth. A seed and
two simple rules can thus create very complex and elaborate structures. This type of representation,
similar to an L-system or cellular automaton, can be applied to evolving morphologies and
controllers of robots.
We start with a constructor that can build a machine from a sequence of build commands. The
language of build commands is based on instructions to a LOGO-style turtle, which direct it to
move forward, backward or rotate about a coordinate axis. Robots are constructed from rods and
joints that are placed along the turtle's path (Figure 4.6a). Actuated joints are created by commands
that direct the turtle to move forward and place an actuated joint at its new location with oscillatory
motion and a given offset. The operators ''[''and '']'' push and pop the current state — consisting of
the current rod, current orientation, and current joint oscillation offset — to and from a stack.
Forward moves the turtle forward in the current direction, creating a rod if none exists or traversing
to the end of the existing rod. Backward goes back up the parent of the current rod. The rotation
commands turn the turtle about the Z -axis in steps of 60 8 , for 2D robots, and about the X , Y or
Z -axes, in steps of 90 8 , for 3D robots. Joint commands move the turtle forward, creating a rod, and
end with an actuated joint. The parameter to these commands specifies the speed at which the joint