Saturday, June 22, 2013

85. Evolutionary Robotics

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).