Institut des Systèmes Intelligents
et de Robotique

Partenariats

UPMC

CNRS

INSERM

Tremplin CARNOT Interfaces

Labex SMART

Rechercher

 

Architectures and Models for Adaptation and Cognition

 

 

Research axis: Multi-objective evolutionary robotics

Contact

Contents

Introduction

The advent of genetic algorithms in the sixties promised to transfer the richness and efficiency of living organisms to artificial agents, such as robotic systems. This envisioned future inspired a whole field of research, now called Evolutionary Robotics (ER), in which researchers create evolutionary algorithms to design robots, or some part of robots such as their ``artificial brain''. The long-term goal of this field is to obtain an automatic process able to design, and even build, an optimal robot given only the specification of a task; the main underlying hypothesis is that Darwin's theory of evolution is the best source of inspiration, in particular because Nature demonstrated its efficiency; the main hope is to obtain machines that fully and robustly exploit the non-linear dynamics offered by their structure and their environment without having to model them explicitly. Hence evolutionary robotics lies at the interfaces between artificial intelligence, bio-inspired robotics, computer-aided design and stochastic optimization.

After almost twenty years of research, simple crawling robots have been automatically designed then manufactured; neural networks have been evolved to allow wheeled robot to avoid obstacles then autonomously charge their battery; neural networks have also been evolved to drive walking and flying robots, as well as self-organizing swarm of robots.

A brief introduction to evolutionary robotics is available online in:

[2009ACTI1385] - Doncieux, S. and Mouret, J.-B. and Bredeche, N. (2009). Exploring New Horizons in Evolutionary Design of Robots.
IROS Workshop "Exploring New Horizons in Evolutionary Design of Robots" . Pages 5--12. Saint Louis, USA.
[ PDF | BIB ]

ISIR's work in evolutionary robotics is focused on the automatic design of neural networks to control robots. This rises several questions:

  • how to apply a selective pressure that can lead to complex behaviors?
  • how to automatically design neural networks that are similar to natural and human-designed structures: large, complex, modular, hierarchical,...
  • how to mix evolution in simulation with application on real robots?

We apply our techniques to mobile robotic problems, with a special emphasis on flying robots (see UAV@ISIR )

Our experiments rely on the SFERESv2 framework, a free and highly-efficient framework for evolutionary computation. The source code of our experiments is available on the EvoRob_Db web site

Multi-objective selective pressures

 

 Incremental evolution
 Keyword: Incremental evolution, multi-objective evolutionary algorithms, bootstrap

(a) A typical incremental evolution scheme with a fitness change. (b) Multi-objective formulation.

Evolutionary algorithms have been successfully used to create controllers for many animats. However, intuitive fitness functions like the survival time of the animat, often do not lead to interesting results because of the bootstrap problem, arguably one of the main challenges in evolutionary robotics: if all the individuals perform equally poorly, the evolutionary process cannot start. To overcome this problem, many authors defined ordered sub-tasks to bootstrap the process, leading to incremental evolution schemes.

Published methods require a deep knowledge of the underlying structure of the analyzed task, which is often not available to the experimenter. In a 2008 paper (Mouret and Doncieux, 2008), we proposed a new incremental scheme based on multi-objective evolution. This process is able to automatically switch between each sub-task resolution and does not require to order them.

The proposed method has been successfully tested on the evolution of a neuro-controller for a complex-light seeking simulated robot, involving 8 sub-tasks.

 

 

 

Publications

[2008ACTI850] - Mouret, J.B. and Doncieux, S. (2008). Incremental Evolution of Animats' Behaviors as a Multi-objective Optimization.
From Animals to Animats 10 Springer, publisher. Vol 5040 Pages 210--219. LNCS.
[ PDF | BIB ]

 

Behavior-based multi-objectivization
 Keyword: behavioral diversity, novelty search, multi-objectivization, sequential task, bootstrap

Overview of the arena and of the robot for the ball-collecting task.

Encouraging exploration, typically by preserving the diversity within the population, is one of the most common method to improve the behavior of evolutionary algorithms with deceptive fitness functions. Most of the published approaches to stimulate exploration rely on a distance between genotypes or phenotypes; however, such distances are difficult to compute when evolving neural networks due to (1) the algorithmic complexity of graph similarity measures, (2) the competing conventions problem and (3) the complexity of most neural-network encodings.

In several papers (Mouret and Doncieux, 2009b, Doncieux and Mouret 2009, Mouret 2009), we introduced and compared conceptually simple, yet efficient methods to improve exploration and avoid premature convergence when evolving both the topology and the parameters of neural networks. The two proposed methods are built on multiobjective evolutionary algorithms and on a user-defined distance between behaviors. They can be employed with any genotype.

We benchmarked them on the evolution of neural networks to compute a Boolean function with a deceptive fitness, on a maze navigation task, on an incremental task (ordered light switching) and on a ball-collecting task for a mobile robot.

Publications

[2009ACTI951] - Mouret, J.-B. and Doncieux, S. (2009). Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity.
IEEE Congress on Evolutionary Computation, 2009 (CEC 2009).
[ PDF | BIB ]

[2009ACTI968] - Mouret, J.-B. and Doncieux, S. (2009). Using Behavioral Exploration Objectives to Solve Deceptive Problems in Neuro-evolution.
GECCO'09: Proceedings of the 11th annual conference on Genetic and evolutionary computation ACM, publisher. Pages to appear.
[ PDF | BIB ]

[2009ACTI969] - Doncieux, S. and Mouret, J.-B. (2009). Single Step Evolution of Robot Controllers for Sequential Tasks.
GECCO'09: Proceedings of the 11th annual conference on Genetic and evolutionary computation ACM, publisher. Pages to appear. (abstract and poster).
[ PDF | BIB ]

 

Modular and bio-inspired genotypes for neural networks

 

Map-based encoding
 Keyword: neuro-evolution, computational neuroscience

Neuro-evolution and computational neuroscience are two scientific domains that produce surprisingly different artificial neural networks. Inspired by the ``toolbox'' used by neuroscientists to create their models, this work argues two main points:

  • neural maps (spatially-organized identical neurons) should be the building blocks to evolve neural networks able to perform cognitive functions;
  • well-identified modules of the brain for which there exists computational neuroscience models provide well-defined benchmarks for neuro-evolution.

To support these claims, a method to evolve networks of neural maps is introduced then applied to evolve neural networks with a similar functionality to basal ganglia in animals (i.e. action selection).

Results show that:

  • (1) the map-based encoding easily achieves this task while a direct encoding never solves it;
  • (2) this encoding is independent of the size of maps and can therefore be used to evolve large and brain-like neural networks;
  • (3) the failure of direct encoding to solve the task validates the relevance of action selection as a benchmark for neuro-evolution.

This work is part of the EvoNeuro ANR project

Publications

[2010INVN1636] - Pinville, T. and Doncieux, S. (2010). Automatic Synthesis of Working memory neural networks with neuroevolution methods.
Neurocomp 2010. [ PDF | BIB ]

[2010ACTI1526] - Mouret, J.-B. and Doncieux, S. and Girard, B. (2010). Importing the Computational Neuroscience Toolbox into Neuro-Evolution---Application to Basal Ganglia.
GECCO'10: Proceedings of the 12th annual conference on Genetic and evolutionary computation ACM, publisher .
[ PS | PDF | BIB ]

 

 

Exaptation, link between evolutionary pressures and modularity
 Keyword: multi-objective evolutionary algorithms, modularity, bootstrap

Despite their success as optimization methods, evolutionary algorithms face many difficulties to design artifacts with complex structures. According to paleontologists, living organisms evolved by opportunistically co-opting characters adapted to a function to solve new problems, a phenomenon called exaptation. In this work, we draw the hypotheses:

  • exaptation requires the presence of multiple selection pressures,
  • Pareto-based multi-objective evolutionary algorithms (MOEA) can create such pressures
  • the modularity of the genotype is a key to enable exaptation.

To explore these hypotheses, we designed an evolutionary process to find the structure and the parameters of neural networks to compute a Boolean function with a modular structure. We then analyzed the role of each component using a Shapley value analysis.

Our results show that:

  • the proposed method is efficient to evolve neural networks to solve this task;
  • genotypic modules and multiple selections gradients needed to be aligned to converge faster than the control experiments.

This prominent role of multiple selection pressures contradicts the basic assumption that underlies most published modular methods for the evolution of neural networks, in which only the modularity of the genotype is considered.

Publications

[2009ACTI950] - Mouret, J.-B. and Doncieux, S. (2009). Evolving modular neural-networks through exaptation.
IEEE Congress on Evolutionary Computation, 2009 (CEC 2009). (Best student paper award).
[ PDF | BIB ]

 

 

MENNAG: a Modular Encoding for Neural Network based on Attribute Grammars
 Keyword: generative grammars, genetic programming, modularity

Recent work in the evolutionary computation field suggests that the implementation of the principles of modularity (functionallocalization of functions), repetition (multiple use of the same sub-structure) and hierarchy (recursive composition of sub-structures) could improve the evolvability of complex systems. The generation of neural networks through evolutionary algorithms should in particular benefit from an adapted use of these notions. We have consequently developed MENNAG (Modular Encoding for Neural Networks based on Attribute Grammars), a new encoding designed to generate the structure of neural networks and parameters with evolutionary algorithms, while explicitly enabling these three above-mentioned principles. We expressed this encoding in the formalism of attribute grammars in order to facilitate understanding and future modifications.

It has been tested on two preliminary benchmark problems: cart-pole control and robotic arm control, the latter being specifically designed toevaluate the repetition capabilities of an encoding.

We compared MENNAG to a direct encoding, ModNet, NEAT, a multi-layer perceptronwith a fixed structure and to reference controllers. Results show that MENNAG performs better than comparable encodings on both problems,suggesting a promising potential for future applications.

Publications

[2008ACLI931] - Mouret, J.B. and Doncieux, S. (2008). MENNAG: a modular, regular and hierarchical encoding for neural-networks based on attribute grammars.
Evolutionary Intelligence. Vol 1 No 3 Pages 187--207.
[ BIB ] [Springer]

 

 

 

Conferences and workshops
 Keyword: evolutionary robotics, evolutionary intelligence, evolutionary computation

Members of ISIR are among the organizers of:

  • The 11th International Conference on Simulation of Adaptive Behavior (SAB2010); Details.
  • Workshop "Exploring new horizons in Evolutionary Design of Robots (Saint-Louis, Missouri, USA; october 2010); Details and proceeding.

 Aditionaly, the following conferences have dedicated evolutionary robotics tracks:

 

Publications

A post-proceedings of EvoDeRob should be published by Springer at the end of year 2010. The digital papers are accessible on the workshop website .