Evolutionary robotics

1. Three problems that defeat manual design

The evolutionary robotics lecture opens with three problems. Read them as a single argument: each one is a design task with an enormous search space, non-linear interactions and a costly evaluation.

The summary slide draws the common structure:

• huge — if not uncountable — sets of possible configurations;
• non-linear relations among solution components;
• performance is not a well-defined mathematical function, so there are no heuristics for estimating the impact of a change in a decision variable;
• a solution process should not only explore the search space, but at the same time learn what good partial configurations are, so as to reduce the number of tested configurations.

This is the thread that connects to Chapter 1: the course's two structural answers to "robustness and flexibility are hard to bring together" are swarm robotics (Chapter 9) and automatic design (Chapter 11). Evolutionary robotics is the founding member of the second family — and the bridge between them.

2. Evolutionary computation: the inspiring principle

Evolutionary computation (EC) draws inspiration from biological evolution, based on three observations:

1. Adaptation: organisms are suited to their habitats.
2. Inheritance: offspring resemble their parents.
3. Natural selection: new, adapted types of organisms emerge, and those that fail to change adequately are subject to extinction.

From these, four key concepts: the fittest individuals have a high chance of having a numerous offspring; children are similar but not equal to their parents; the traits characterising the fittest individuals spread across the population generation by generation; selection acts on the individuals as they appear and behave, but it indirectly acts on their heritable traits.

The idea was anticipated by Turing in 1950, in the passage Chapter 2 quoted:

The metaphor is usually written as a table:

Two observations attached to the table: in evolution the environment is changing and individuals interact, while in EC methods we often suppose the environment is constant and the evaluation of the individuals only depends on external functions; and a possible solution is in general encoded in a kind of genetic code — a data structure that can be manipulated by suitable operators.

3. The evolutionary cycle and the simple genetic algorithm

Evolutionary computation encompasses genetic algorithms, genetic programming, evolution strategies, estimation of distribution algorithms, and more — different names for different implementations of the same overall scheme.

The simple genetic algorithm

Developed by John Holland in the early '70s, the simple genetic algorithm (SGA) codes solutions as bit strings. One string is usually divided into m blocks that codify m objects. The string is the genotype; the solution it codifies (integers, reals, a plan, rules...) is the phenotype. Encoding examples from the slides: a block of genes can codify one move (e.g. 1000 → move ahead); a rule like if obstacle in front then stop is codified by a block split in two parts, the first codifying the condition, the second the action.

The high-level algorithm:

Initialize Population
Evaluate Population
while Termination conditions not met do
   while New population not completed do
      Select two parents for mating
      Copy their chromosomes
      Apply crossover to produce two new individuals
      Apply mutation to each new individual
   end while
   Population ← New population
   Evaluate Population
end while

Termination conditions: execution time limit reached; satisfactory solution(s) obtained; stagnation (limit case: the population converged to the same individual).

4. Genetic operators, selection and the survival of the good

Mutation and crossover in the SGA

Mutation: each gene has probability p_M of being flipped. Recombination (crossover): cross-combination of two chromosomes at one (or more) cut points. Alternatives: multi-point crossover, multi-parent crossover, uniform crossover (each parent k is associated a probability g_k used to pick the value of gene i in the child).

Selection

Proportional (roulette-wheel) selection: the probability for an individual to be chosen is proportional to its fitness — usually represented as a roulette wheel whose slices are the fitness shares. Alternatives: selection based on the ranking of individuals (it does not favour the fittest as much as the proportional rule), and tournament selection (iteratively pick two or more individuals and put the best among them in the mating pool; less computation — best choice when evaluation is costly; it also favours exploration).

Generational replacement and elitism

Generational replacement: the new generation replaces entirely the old one. Advantage: very simple, computationally cheap, easier theoretical analysis. Disadvantage: good solutions might not be maintained in the new population. Hence a kind of elitism is always used: for example, the best k individuals from the previous population are kept in the new one (discarding some offspring if the population must keep the same size).

5. Why it works: fitness landscapes and model-based search

The intuition: mutation introduces diversity; selection drives the population toward high fitness values; crossover might combine good parts from good solutions.

Beyond the intuition, the slides offer an abstract view of the search process: the GA performs an iterative sampling over the search space, based on a probabilistic model; the parameters of the model are tuned as a function of the population fitness, so as to intensify the sampling around promising regions. This makes the process similar to importance sampling and model-based search (the loop model → sample, with an auxiliary memory for learning).

Solution representation is free: besides the simple binary representation, solutions can be encoded by n-dimensional arrays of floating point numbers, permutations, finite state machines, trees — anything a suitable set of operators can manipulate. This matters enormously for robotics: a probabilistic FSA (Chapter 6), a behaviour tree (Chapter 8), a neural network or a whole morphology are all just genotypes awaiting operators.

6. Genetic programming

Genetic programming (GP) can be seen as a variant of GA in which individuals are programs: it is used to build programs that solve the problem at hand (specialised programs), and it is extended to automatic design in general (controllers, electronic circuits). Fitness is given by evaluating the performance of the program on some defined criterion. In most cases individuals are represented as trees that encode programs:

          +
       /      \
      1        2       IF
                    /      \
                   >       3   4
                  / \
                 T   6

Operators: mutation randomly selects a subtree and substitutes it with a well-formed randomly generated subtree; crossover swaps subtrees between two parents. The five preparatory steps of the basic version: specify (1) the set of terminals, (2) the set of primitive functions, (3) the fitness measure, (4) run parameters, (5) termination criterion and result designation. The fitness measure is the primary mechanism for communicating the high-level statement of the problem's requirements: it specifies what needs to be done.

For robotics the lesson is methodological: the same machinery that synthesises circuits and antennas synthesises controllers, with function sets made of integrators, gains, adders, and so forth. Chapter 11 will use a much more constrained version of this idea: instead of arbitrary programs, a parametric architecture whose free parameters are tuned by search.

7. Evolutionary robotics: definition and workflow

Doncieux, Bredeche, Mouret and Eiben (2015) put it in one sentence: evolutionary robotics applies the selection, variation and heredity principles of natural evolution to the design of robots with embodied intelligence. The pivotal feature: it considers the whole robot at once — sensory apparatus, morphology and control simultaneously — and enables the exploitation of robot features in a holistic manner, rather than designing each part in isolation and putting them together at the end. This contrasts with the reductionist approach of most engineering, which often "fights" the interdependencies to keep the design modular.

The workflow (Doncieux et al., Fig. 1) has an evolutionary component and an evaluation component:

1. The first generation of candidate solutions, represented by their codes — the genotypes — is usually randomly generated.
2. Fitness is evaluated: translate the genotype into a phenotype (a robot part, its controller, or its overall morphology); put the robot in its environment; let it interact for some time and observe the behaviour; compute a fitness value.
3. The fitness is used to select individuals to seed the next generation.
4. The selected parents undergo randomised reproduction through stochastic variation (mutation and crossover).
5. The evaluation–selection–variation cycle is repeated until a stopping criterion is met (typically a given number of evaluations or a predefined quality threshold).

Who benefits

ER is at the crossroads between engineering science and biology (Doncieux et al., Fig. 2): engineers get a method to design simple yet efficient robots, whose integrated view opens new design spaces (morphology as a variable, not something decided a priori); biologists get a synthetic approach to study evolution experimentally — as Maynard Smith put it: "so far, we have been able to study only one evolving system and we cannot wait for interstellar flight to provide us with a second. If we want to discover generalizations about evolving systems, we have to look at artificial ones."

8. What we know: controllers, encodings and selection pressure

Neural networks are the preeminent controller paradigm

Evolutionary algorithms can be used with almost any controller representation, but the ideal substrate should constrain evolution as little as possible and use raw sensor inputs and low-level actuator commands. Given these requirements, artificial neural networks are currently the preeminent controller paradigm in ER: feed-forward networks can reproduce any function with arbitrary precision; with recurrent connections they can approximate any dynamical system. Evolution can act on synaptic parameters, on the architecture, or on both (neuroevolution). Simple McCulloch-Pitts neurons are common; leaky integrators (continuous-time recurrent neural networks, CTRNNs) take time into account and suit dynamical systems; spiking neurons are not yet common.

Selective pressure is at least as important as the encoding

Many complex encodings were proposed to evolve morphologies and controllers, but they did not enable the unbounded complexity hoped for. Two main reasons: evolution often converges prematurely on a single family of designs; and evolution selects individuals on the short term, whereas increases in complexity are often beneficial only in the medium-to-long term. Mouret and Doncieux (2012) tested the relative importance of selective pressure and encoding, and concluded that modifying the selective pressure to avoid premature convergence matters at least as much as the encoding.

9. Key experiments: from navigation to altruism

Floreano and Keller (2010) review experimental evolution with robots controlled by simple neural networks whose genomes mutate randomly, all with real robots (or partly so). The claim that runs through all of them: a few hundred generations of selection suffice to evolve complex, adaptive behaviours. The methodological criteria of the review are worth stating: neural networks with simple architecture (no synaptic plasticity, no ontogenetic development, no detailed modelling of ion channels); genomes directly mapped into the neural network (no gene-to-gene interaction, no time-dependent dynamics).

Collision-free navigation

A Khepera robot with eight distance sensors (six on one side, two on the other) in a looping maze; the genome is a bit sequence encoding the connection weights between input and output neurons. Three independent populations of 80 individuals. Within less than 100 generations most robots exhibited collision-free navigation. Two findings: the best evolved individuals moved in the direction corresponding to the side with the highest number of sensors (individuals moving the other way collided more and were selected against); and the driving speed settled at about half the maximum speed and did not increase even after 100 more generations — at higher speed the 300-ms sensor refresh rate did not allow the robots to detect walls in time. The evolved behaviour takes into account not only the environment, but also the robot's own morphological and mechanical properties.

Homing

The same robots, a dark room with a small light tower behind a nest (a black patch that recharges the battery), battery discharging linearly over 50 sensory-motor cycles. Fitness proportional to average wheel speed and distance from walls. After 200 generations the best individuals performed wide explorations and returned to the nest only when their batteries had approximately 10% residual energy, staying only long enough to recharge. The timing behaviour was mediated by the evolution of a neuronal representation of the environment combining location and battery level — reminiscent of "place cells" and "head-oriented cells" in the rat hippocampus: artificial organisms may evolve functionally similar internal representations to real organisms.

Predator–prey coevolution

Populations of predator and prey robots (prey twice as fast, predator with vision; fitness inversely proportional to capture time for the predator, proportional to survival time for the prey), tested one-to-one in tournaments against the five best of the other population. Over 100 generations the strategies cycled: uncoordinated turning → fast motion vs visual tracking → predators so efficient they lost wall avoidance → prey waiting and moving backward → prey coasting walls at maximum speed → predators' "spider" strategy → prey rotating in place and facing the predator with the sensor-rich side. None of the strategies were stable over time — a coevolutionary dynamics in which each party exerts selective pressure on the other, as in natural systems.

Cooperation and altruism

In a foraging arena with small tokens (pushable by one robot) and large tokens (requiring at least two), the fitness of groups of 10 robots was measured. With only large tokens, all 20 replicates evolved cooperative pushing. With both tokens: in groups of unrelated robots, individuals specialised in pushing small tokens (the most efficient strategy for individual fitness); in "clonal" groups (identical genomes), individuals pushed the large tokens even though it was costly — altruism evolved. The genetic relatedness of the group changes what selection can produce.

10. Evolving bodies: morphology, development and the GOLEM project

The evolution of robot bodies and brains differs markedly from all other approaches to robotics in that it does not presuppose the existence of a physical robot: the user provides a metric for robot performance and a simulation of the task environment, and the algorithm produces the body plan and control policy. Such an algorithm could, in principle, continually receive new desired behaviours and continuously generate novel robots — the "robot-generating algorithm" that Bongard identifies as the field's long-term goal.

• Karl Sims (1994) coevolved brains and body morphologies of simulated robots in a competitive scenario — a pioneering study for both morphology and behaviour.
• Evo-devo-robo: biological systems change over multiple time scales (development within a lifetime, evolution across generations — the "evolution of development"). In early evo-devo experiments, robots changed from a crawling worm into a legged walking machine over their lifetime, with the infant form gradually lost as evolution proceeds; this evolved walking machines faster than approaches without the crawling stage.
• L-systems (Lindenmayer systems) encode genetic instructions as formal grammars originally devised to model plant growth. Hornby demonstrated that robots evolved with such grammars produce repeated (self-similar) forms, and that this repetition makes it easier for evolution to improve them. Encoding assembly instructions rather than blueprints means more complex machines can be evolved with little or no increase in the information content of the genome.
• The GOLEM project (Lipson & Pollack, 2000): evolved body plans and control policies for robots composed of linked linear actuators, then printed the 3D architectures in plastic; motors, circuitry and batteries were added by hand. Many of these automatically designed and manufactured robots reproduced the locomotion patterns evolved in simulation — the first demonstration of an integrated evolution–manufacture pipeline.

11. Open challenges: reality gap, evaluation cost, evolvability

The reality gap

Both biological and artificial evolution are notorious for exploiting the relationship between the agent and its environment. If the simulator has no noise, a control policy may evolve to rely on a very narrow range of sensor values that the physical robot never sees; the failure of evolved solutions to "cross the gap" from simulation to reality is the reality gap problem (Jakobi 1995; Koos et al. 2013). Proposed remedies:

• sample the physical sensors and use the samples in simulation; add noise to sensors, motors and position so evolution cannot exploit artefacts of the simulation (each noise source forces more evaluations);
• bidirectional approaches that alternate between simulation and reality: Bongard, Zykov and Lipson (2006) ran three evolutionary algorithms — one optimising a population of physical simulators to predict the real robot, one optimising exploratory behaviours that extract the most new information, and one evolving control policies on the improved simulator. An added advantage: the robot could recover from physical damage (e.g. loss of a leg) automatically, because the updated simulator incorporated the change;
• Koos et al. evolved controllers maximising behaviour in simulation while minimising a predicted disparity between simulated and real behaviour (transferability), tackling the trade-off between behavioural efficiency and transferability — running fast is efficient but fragile, walking is transferable.

Combinatorics of evaluation

The time required to evaluate a single robot may grow exponentially with the number of parameters describing its task environment: a robot that must grasp m objects under n lighting conditions needs mn evaluations; with p parameters each taking s settings, s^p evaluations per robot. One possible solution: co-evolution — a population of robots and a population of task environments competing against one another.

Evolvability and fitness design

A species with high evolvability adapts more rapidly to changes in its environment. One goal of the field is to create increasingly evolvable algorithms — algorithms that discover useful aggregate patterns in candidate solutions and elaborate them, rather than independently optimising individual parameters. And designing a fitness function that rapidly discovers desirable solutions without biasing toward particular ones is notoriously difficult; novelty search (section 8) is one attempt to eliminate the fitness function altogether.

ER is a small but productive niche field: it has yet to evolve a robot superior to one produced by mainstream methods such as reinforcement learning (a challenge taken up in Chapter 12), but it has produced a wider variety of robots automatically — including swarm behaviours (the bridge to Chapter 9), modular self-reconfiguration, tensegrity and soft robots.

Check your understanding