Page 145 - Biomimetics : Biologically Inspired Technologies

Bar-Cohen : Biomimetics: Biologically Inspired Technologies DK3163_c004 Final Proof page 131 21.9.2005 9:37am

Evolutionary Robotics and Open-Ended Design Automation 131

maximize a target function. The set of parameters, their meaning, and their ranges are predeter-
mined. Synthesis, on the other hand, is an open-ended process, where we can add more and more
components, possibly each with their own set of parameters. Consider, for example, a case where
we need to design a new electronic circuit that performs some target function. One approach would
be to manually provide a basic layout of resistors, capacitors, and coils, and then try to automat-
ically tweak their values so as to maximize performance. Alternatively, we could start with a bucket
of components, and use an algorithm to automatically compose them into a circuit that performs the
target function. The former would be a case of optimization, and the latter an example of synthesis.
There are numerous examples and many books dedicated to the application of evolutionary
optimization in almost any engineering domain (e.g., Gen and Cheng, 1999; Zalzala and Fleming,
1999; Jamshidi et al., 2002; Karr and Freeman, 1998; Mazumder and Rudnick, 1998), but the use of
evolution for open-ended design remains relatively unexplored, yet has the highest potential impact
in its ability to ‘‘think outside the box.’’

4.1.1 Structure of This Chapter

As we shall see in the next few sections, we can use many of the ideas of biological evolutionary
adaptation to inspire computational synthesis methods. To keep things intuitive, we shall describe
some of these methods in the context of designing electromechanical machines, such as robots, and
in particular legged robots. But these methods can be (and indeed have been) applied to numerous
engineering application areas. This chapter is not intended to be a comprehensive review of
evolutionary robotics or of evolutionary design research. Instead I have chosen a small set of
results that portray an interesting perspective of the field and where it is going. These results are not
necessarily in chronological order — scientific discoveries are not always made in an order most
conducive for learning. Interested readers are encouraged to see the ‘‘further reading’’ section for
more in-depth and broader reviews.

4.2 A SIMPLE MODEL OF EVOLUTIONARY ADAPTATION

There are a variety of computational models of open-ended synthesis loosely inspired by natural
evolutionary adaptation. Perhaps the simplest approach uses a direct representation. We start off
with a large set of initial candidate designs — this is the initial population. These designs may be
random, blank, or may be seeded with some prior knowledge in the form of solutions we think
are good starting points. We then begin evolving this population through repeated selection and
variation. To perform selection, we first measure the performance of each solution in the popula-
tion. The performance, fitness in evolutionary terminology, captures the merit of the design with
respect to some target performance we are seeking as designers. The fitness metric needs to be
solution-neutral, i.e., measure the extent to which the target task has been achieved, regardless
of how it was achieved. We select better solutions ( parents) and use them to create a new
generation of solutions (offspring). The offspring are variations of the parents, created
through variation operators like mutation and recombination. The process is repeated generation
after generation until good solutions are found.
In practice, there are many modifications to the simple process described above. We use
special representations, clever selection methods, sophisticated variation, evaluation methods,
as well as multiple co-evolving populations. Most interestingly, we let the representations
and the evaluation methods evolve too, to allow for a more open-ended search. Mitchell (1996)
provides a review of many of these processes. Let us look at some simple examples applied
to robotics.