Evolutionary
robotics is a technique for the automatic creation of autonomous robots (Nolfi and Floreano 2000). It works in
analogy with the Darwinian principle of selective reproduction of the fittest.
I described
genetic algorithms (GAs) in Part 75. Typically, a
population of artificial chromosomes or digital organisms (strings of command)
is created in the computer controlling the robot. Each such chromosome encodes
the control system (or even the morphology) of a robot. The various possible
robots (actual, or just simulations) then interact with the environment, and
their performance is measured against a set of specified criteria (the ‘fitness
functions’). The fittest robots are given a higher chance of being considered
for the creation of next-generation robots (specified by a new set of
chromosomes drawn from the most successful chromosomes of the previous
generation). Processes such as mutations and crossover etc. are also
introduced, by analogy with biological evolution. The whole process of decoding
the instructions on the chromosomes and implementing them is repeated, and the
fitness functions for each member of the new robot population are computed
again. This is repeated for many generations, till a robot configuration having
a pre-determined set of performance parameters is obtained.
The goal here
is to evolve robots with creative problem-solving capabilities. This means that
they must learn from real-life
experiences, so that, as time passes, they get better and better at
problem-solving. The analogy with how a small child learns and improves as it
grows is an apt one. The child comes into the world equipped with certain
sensors and actuators (eyes, ears, hands, etc.), as well as a brain. Through a
continuous process of experimentation (unsupervised learning), as well as
learning from parents and teachers etc. (supervised learning), and also learning
from the hard knocks of life, including rewards for certain kinds of action
(reinforced learning), the child’s brain performs evolutionary computation. This field of research involves a good
deal of simulation and generalization work. Apart from GAs, other techniques of
computational intelligence are also employed.
In
evolutionary robotics, the key question to answer is: Under what conditions is
artificial evolution likely to select individual robots which develop new
competencies for adapting to their artificial environment? Nolfi and Floreano(2000) discuss the answer in terms of three main
issues:
(i) generating
incremental evolution through interspecific and intraspecific competition;
(ii) leaving
the system free to decide how to extract supervision from the environment; and
(iii) bringing
the genotype-to-phenotype mapping into the evolutionary process itself.
Incremental
evolution
In biological
evolution, natural selection is governed by the ability to reproduce. But there
are many examples of improvements (sophisticated competencies) over and above
what is essential for sheer survival and propagation of a species. Emergence of
the ability to fly is an example of this. A more complex example is that of the
emergence of speech and language in humans. Obviously, such competencies, which
bestow a survival and propagation advantage to a species, do arise from time to
time.
As discussed in Part 78 Holland used GAs in his model for
ensuring an element of perpetual novelty in the adapting population. He
also incorporated, among other things, the notion of classifier systems.
Classifier systems were also introduced by Dorigo and Colombetti (1994, 1997), who used the term robot shaping, borrowing it from experimental psychology wherein animals are trained
to elicit pre-specified responses.
A simple approach to evolving a particular ability or competency in a
robot is to attempt selection through a suitable fitness function. This works
well for simple tasks. For a complex task, the requisite fitness function turns
out to be such that all individuals fail the test, and evolution grinds to a
halt. This is referred to as the bootstrap problem (Nolfi and Floreano
2000).
Incremental evolution is a way out of this impasse. Define a new task and
the corresponding fitness function or selection criterion that is only a slight
variation of what the robot is already able to do. And do this repeatedly. The
sophisticated competency can thus be acquired in a large number of incremental
stages (Dorigo and Colombetti 1994, 1997). Such an approach has the potential
drawback that the designer may end up introducing excessive constraints.
A completely self-organized evolution of new competencies, as happens in
biological evolution, has to invoke phenomena like the 'coevolution of species' and the attendant 'arms races' within a species or between species (I shall discuss these in future
posts). Coevolution can lead to progressively more complex behaviour among
competing robots. For example, predator and prey both improve in their struggle
for survival and propagation. In such a scenario, even though the selection
criterion may not change, the task of adaptation becomes progressively more
complex.
Extracting supervision from the environment through lifetime learning
A human
supervisor can help a robot evolve new competencies. But it is more desirable
if the robot can autonomously extract that high-level supervision from the
environment itself. A large amount of information is received by the robot
through its sensors, and it adapts to the environment through the feedback
mechanisms. As the environment changes, new strategies are evolved for dealing
with the change. The evolving robot also gets feedbacks on the consequences of
its motor actions. Thus, the robot can effectively extract supervision from the
environment through a lifetime of adaptation and learning about what actions
produce what consequences.
One makes a
distinction between ontogenetic
adaptation and phylogenetic
adaptation. The former refers to the adaptation resulting from a lifetime
of learning, in which the individual is tested almost continuously for fitness
for a task. The latter involves only one
testing for fitness, namely when it comes to procreating the next generation of
candidate robots. Not much progress has been made yet regarding the
exploitation of phylogenetic adaptation in evolutionary robotics.
Development
and evolution of evolvability
In a GA the
chromosomes code the information which must be decoded for evaluating the
fitness of an individual. Thus there is a mapping of information from the
genotype to the phenotype, and it is the phenotype which is used for evaluating
the fitness. Genotypes of individuals with fitter phenotypes are given a larger
probability for selection for procreating the next generation. The problem is
that a one-to-one genotype-to-phenotype mapping is too simplistic a procedure.
In reality, i.e. in real biological evolution, a phenotype may be influenced by
more than one genes. The way genetic variation maps onto phenotypic variation
in evolutionary biology is a highly nontrivial problem, and is commonly
referred to as the representation
problem. The term evolvability is
used for the ability of random variations to result in improvements sometimes.
As emphasized by Wagner and Altenberg (1996), evolvability
is essential for adaptability. And incorporating evolvability into evolutionary
robotics amounts to tackling the representation problem. Efforts have indeed
been made to incorporate more complex types of mapping than a simple one-to-one
mapping of one gene to one robotic characteristic (Nolfi and Floreano 2000).
No comments:
Post a Comment