Danesh Tarapore
email: daneshtarapore@gmail.com

Jean-Baptiste Mouret

Comparing the evolvability of generative encoding schemes

The evolvability of a system is the ability to generate heritable, novel and non-lethal phenotypes, from random genetic mutations. However, most evolutionary computation studies estimate evolvability either as, (i) the proportion of mutations beneficial to an individual's performance, irrespective of the phenotypic diversity of the mutants, or (ii) the range and diverseness of mutated phenotypes, without taking into account the viability of the genetic change. This paper reports a novel approach to measure the evolvability provided by an encoding, by characterizing both the quality of the mutations and the quantity of phenotypic variation. We evolved controllers for hexapod robot locomotion using a parameterized direct encoding, and the generative encoding of artificial neural networks (similar to HyperNEAT) and single-unit pattern generators (SUPGs). Our results reveal that the performance of an encoding is not always a good assessment of evolvability. Although both the generative encodings evaluated had individuals with high performance gaits, there were apparent differences in their measured evolvability. A direct and predictive relationship is indicated between our measure of evolvability, and the number of generations required by amputated individuals to recover an effective gait.

Introduction

The capacity of a population to rapidly adapt to novel environments, called evolvability, is critical in the evolutionary processes of natural organisms and artificial systems [START_REF] Hu | Evolvability and speed of evolutionary algorithms in light of recent developments in biology[END_REF]. In the natural world, the high evolvability of biological systems is hypothesized to be responsible for the rich diversity of the millions of species creatively adapting to diverse niches, all arising from a combination of random mutations and natural selection [START_REF] Pavlicev | Coming to grips with evolvability[END_REF]. Evolvability is also of interest in evolutionary computation (EC), wherein highly evolvable solutions are considered to optimize faster and achieve a greater performance than non-evolvable solutions (e.g., [START_REF] Cheney | Unshackling evolution: evolving soft robots with multiple materials and a powerful generative encoding[END_REF]), and may be capable of of generalizing previously learned information and adapting it to new environments (e.g., [START_REF] Reisinger | Towards an empirical measure of evolvability[END_REF]; [START_REF] Clune | The evolutionary origins of modularity[END_REF]), desirable characteristics from an engineering perspective.

The developmental mechanisms translating genetic change into phenotypic change, that is the genotype-phenotype map, is commonly understood to play a key role in the evolvability of evolutionary systems [START_REF] Kirschner | Evolvability[END_REF][START_REF] Wagner | Perspective: Complex adaptations and the evolution of evolvability[END_REF]. Mappings facilitating evolvability, confer on the individual a robustness to lethal mutations, and exhibit a modular architecture wherein genes preferably only affect traits with the same function [START_REF] Pavlicev | Coming to grips with evolvability[END_REF]. Inspired by the evolvability of biological systems, researchers in EC have abstracted the underlying developmental processes, to formulate generative genotype-phenotype maps for artificial systems (e.g., [START_REF] Stanley | Compositional pattern producing networks: A novel abstraction of development[END_REF]). The resultant generative encodings frequently outperform traditional direct encodings for various application problems such as, designing 3D objects (e.g., [START_REF] Hornby | Measuring, enabling and comparing modularity, regularity and hierarchy in evolutionary design[END_REF]), game playing (e.g., [START_REF] Reisinger | Acquiring evolvability through adaptive representations[END_REF]; [START_REF] Gauci | Autonomous evolution of topographic regularities in artificial neural networks[END_REF]), pattern matching (e.g., [START_REF] Clune | On the performance of indirect encoding across the continuum of regularity[END_REF]), and robot locomotion (e.g., [START_REF] Hornby | Creating high-level components with a generative representation for body-brain evolution[END_REF]; [START_REF] Seys | Genotype reuse more important than genotype size in evolvability of embodied neural networks[END_REF]). Furthermore, the higher evolvability provided by generative encodings is often considered as the reason for the observed differences in performance, consequent to their capability to reuse parts of the genotype to affect different phenotypes, scale well to large phenotypic spaces, and generate modular architectures [START_REF] Stanley | A taxonomy for artificial embryogeny[END_REF].

In the field of EC, there are two main approaches to estimate the evolvability of artificial developmental systems. Most studies estimate evolvability either as, (i) the proportion of genetic mutations that are beneficial to an individual, irrespective of the phenotypic novelty of the resultant offspring (e.g., [START_REF] Hornby | Generative representations for the automated design of modular physical robots[END_REF]; [START_REF] Reisinger | Acquiring evolvability through adaptive representations[END_REF]), or as (ii) the range and diversity of the phenotypic variants resulting from genetic change [START_REF] Lehman | Improving evolvability through novelty search and self-adaptation[END_REF][START_REF] Reisinger | Towards an empirical measure of evolvability[END_REF][START_REF] Lehman | Evolvability is inevitable: Increasing evolvability without the pressure to adapt[END_REF], usually without considering the deleteriousness of the change. Importantly, both these estimates when considered alone do not discount for mutations that, (i) generate very diverse phenotypes but prove lethal to an organism, and (ii) result in minor improvements to a phenotype, but are unable to generate novelty. According to the theory of facilitated variation [START_REF] Gerhart | The theory of facilitated variation[END_REF], the capacity of an individual to evolve is a function of its ability to curtail lethal mutations, and simultaneously to decrease the number of mutations necessary to evolve diverse or novel phenotypes.

In this study we present a novel approach to visualize evolvability provided by direct and generative encodings, featuring both the quality and quantity of phenotypic variation consequent to genetic change, for hexapod robot locomotion. Evolvability is analyzed for a parametrized direct encoding, and the generative encoding of artificial neural networks (similar to HyperNEAT, [START_REF] Stanley | A hypercube-based encoding for evolving large-scale neural networks[END_REF]) and single-unit pattern generators [START_REF] Morse | Single-unit pattern generators for quadruped locomotion[END_REF], in three independent experiments. The significance of our measure of evolvability is analyzed by the ability of the robot to adapt to previously unencountered changes in its morphology.

Measuring evolvability

The evolvability provided by the direct and generative encodings is measured by computing the effect of genetic mutations on, (i) the viability of the mutated individual, and (ii) the diversity of phenotypes generated. The two resultant effects are treated separately instead of being combined into a single quantitative measure of evolvability, to consider the trade-offs between them in their individual influence on evolvability.

Feature 1: Deleteriousness of mutations. The first feature in our measure of evolvability is computed as the proportion decrement in the fitness of a mutated individual.

For an individual i and the mutant i ′ , we have,

f1 = (F ′ i -Fi)/Fi (1)
where F i and F ′ i , are the fitness values before and after the application of a random genetic mutation, respectively.

The feature f 1 reflects the phenotype quality following beneficial (f 1 > 0), neutral (f 1 ≈ 0), and deleterious (f 1 < 0) genetic change.

Feature 2: Diversity of phenotypes. The second feature in our measure of evolvability is quantified as the difference in the phenotype, resulting from genetic mutation. There are many available diversity metrics to measure behavioral differences, ranging from the classical euclidean distance, to correlation coefficients, and various information theoretic measures (reviewed in [START_REF] Mouret | Encouraging behavioral diversity in evolutionary robotics: An empirical study[END_REF]). The mutual information metric, in comparison with other measures such as correlation, provides a more general criterion to investigate statistical dependences between behaviors, and is applicable to numerical and symbolic phenotypic representations.

We compute the phenotype diversity as the normalized mutual information [START_REF] Cover | Elements of information theory[END_REF] between behaviors of an individual, before and after its genome is mutated. Assuming that the behavior of an individual i can be represented as a discrete vector B i (details in [START_REF] Mouret | Encouraging behavioral diversity in evolutionary robotics: An empirical study[END_REF]), for the behaviors B i and B ′ i , of individual i and mutant i ′ , we have:

H(Bi) = - b i ∈B i p(bi) log p(bi) (2a) H(Bi, B ′ i ) = - b i ∈B i b ′ i ∈B ′ i p(bi, b ′ i ) log p(bi, b ′ i ) (2b) f2 = H(Bi) + H(B ′ i ) -H(Bi, B ′ i ) max(H(Bi), H(B ′ i ) (2c)
where H(B i ) is the entropy of the behavior B i comprising the individual states b i with probability p(b i ), H(B i , B ′ i ) is the joint entropy between behaviors B i and B ′ i with joint probability density function p(b i , b ′ i ), and f 2 denotes the normalized mutual information distance between the two behaviors.

The feature f 2 in our measure of evolvability represents the quantity of phenotypic variation following genetic change, and is indicative of the ability of the evolutionary system to produce novel phenotypes.

Hexapod locomotion problem

The evolution of locomotion gaits for multilegged robots is a classical problem in EC, addressed in many prior studies utilizing both direct and generative encodings (e.g., [START_REF] Liu | A hierarchical approach for adaptive humanoid robot control[END_REF]; [START_REF] Clune | On the performance of indirect encoding across the continuum of regularity[END_REF][START_REF] Valsalam | Modular neuroevolution for multilegged locomotion[END_REF]). In the large majority of these studies, the performance of evolved individuals is analyzed solely by the walking speed of the robot and the required number of generations of evolution. The rate of evolution and evolved performance has also been linked to evolvability provided by the encoding scheme, wherein controllers achieving a higher task fitness and requiring fewer generations to evolve are considered more evolvable (e.g., see [START_REF] Hornby | Generative representations for the automated design of modular physical robots[END_REF]; [START_REF] Komosiński | Comparison of different genotype encodings for simulated three-dimensional agents[END_REF]). While these approaches provide interesting insights on the characteristic of the underlying genotype-to-phenotype mapping, they largely ignore its capabilities to generate viable phenotypic variations (diverse gaits in case of legged robots). However, the diversity of evolved walking gaits is important for the legged robot to recover rapidly from faults such as, the loss of one or more limbs, or motor malfunctions [START_REF] Koos | Fast damage recovery in robotics with the T-resilience algorithm[END_REF], and for the robot to adapt to previously unencountered environmental changes. Furthermore, an efficient recovery is particular relevant for hexapedal legged robots, wherein the probability of component failure is high, consequent to the large number of moving parts.

Hexapod platform details: The hexapod robot is simulated on a flat, horizontal surface (Fig. 1a), with the Open Dynamics Engine1 (ODE) physics simulator. The robot has 18 Degrees of Freedom (DOF), 3 for each leg (Fig. 1b), and each DOF is actuated by a single servo. The first servo on each leg (s 1 ) actuates the horizontal orientation of the leg within range [-π/8, π/8] radians. The second (s 2 ) and third (s 3 ) servos control the leg elevation and extension, respectively, each within the range of [-π/4, π/4] radians. Angular positions are sent to the 18 servos once every 15 ms. Furthermore, in order to maintain the last subsegment of each leg vertical (for enhanced stability), the control signal for the third servo (s 3 ) is always in antiphase to that of the second servo (s 2 ). Consequently, the robot is reduced to a 12 DOF system, despite being actuated by 18 motors.

Hexapod gait representation: The phenotypic diversity in our measurement of evolvability corresponds to the intergait diversity in the hexapod robot locomotion problem. For this measurement, a hexapod gait is represented using a gait diagram (Kajita and Espiau, 2008, p. 379), comprising a binary matrix C of leg-surface contacts:

C tl = 1 if leg i makes surface contact at time-step t, 0 otherwise.
where t ∈ {0 . . . T }, the gait is evaluated for T time-steps, and the hexapod legs l ∈ {0 . . . 5}.

The hexapod gait for an individual i is represented by binary vector B i , comprising the contacts in C concatenated in row-major order, B i = [C 00 , C 10 . . . C T 5 ]. The difference between two gaits is measured as the normalized mutual information between the corresponding gait vectors (eq. 2c).

Encoding schemes

The generative encodings for evolving hexapod locomotion controllers are based on compositional pattern producing networks (CPPNs) [START_REF] Stanley | Compositional pattern producing networks: A novel abstraction of development[END_REF]. CPPNs abstract the processes of embryonic development by determining the attributes of phenotypic components as a function of their geometric location in the individual, instead of simulating complex inter-cellular interactions.

The CPPN genome is represented as a directed graph, comprising a set of Sine, Gaussian, Sigmoid, and Linear type of nodes, connected by weighted links. The node type indicates the activation function applied to the sum of its weighted inputs, to compute the node output. Selected activation functions can succinctly encode a wide variety of phenotypic patterns, such as symmetry (e.g., a Gaussian function) and repetition (e.g., a Sine function), that evolution can exploit. Mutations to the CPPN genome can change the connection weights and node type, and add or remove nodes from the graph. Consequently, the topology of the CPPN is unconstrained, and can represent any possible relationship between the input coordinates of the phenotypic component and its output attributes (see details in [START_REF] Stanley | Compositional pattern producing networks: A novel abstraction of development[END_REF]).

In this study, the CPPN genotype is mapped to two very different phenotypes, the conventional Artificial neural networks (ANNs), and the Single-unit pattern generators (SUPGs). The SUPG is a new type of macro-neuron introduced by [START_REF] Morse | Single-unit pattern generators for quadruped locomotion[END_REF] to genetically encode spatiotemporal oscillatory patterns.

ANNs with CPPNs (minimal HyperNEAT):

The first generative encoding scheme evaluated is a simplified version of HyperNEAT indirect encoding2 [START_REF] Stanley | A hypercube-based encoding for evolving large-scale neural networks[END_REF][START_REF] Clune | On the performance of indirect encoding across the continuum of regularity[END_REF][START_REF] Yosinski | Evolving robot gaits in hardware: the hyperneat generative encoding vs. parameter optimization[END_REF]. The CPPNs encode the weights of a fixed topology, single-layer feedforward ANN, featuring 2-D cartesian grids of inputs, hidden and output neurons (Fig. 2). Neurons are placed in a geometric space termed the substrate, so that each neuron in a layer has a distinct (x, y) coordinate. In addition, the placement of the input and output neurons is meant to reflect the hexapod robot morphology. The CPPN is iteratively input the positions of all source (x 1 , y 1 ) and target (x 2 , y 2 ) neurons in proximal layers, along with a constant bias, and it outputs the corresponding weights of the input-hidden and hidden-output neuron connections (see Fig. 2).

The ANN receives as input the previously requested angles (actual angles unknown) for each of the 12 pivot joints of the robot (s 1 and s 2 , for 6 legs). In addition, sine and cosine waves of frequency 1 Hz are also input to the ANN, to facilitate output periodic oscillations. The output from the ANN at each time-step are 12 numbers (one for each of s 1 and s 2 , on each of 6 legs) in interval [-1, 1], that are scaled to the allowable angular range of the corresponding motors, and indicate the next position of each motor.

In preliminary experiments, this encoding evolved ANNs that exhibited high frequency output oscillations (in excess of 20 Hz). In the resultant gaits, the robot could traverse large distances by vibrating its legs rapidly, and in unison. Encoding SUPGs with CPPNs: In the second generative encoding scheme evaluated, the CPPN encodes the attributes of a SUPG. The SUPG is a macro-neuron (Fig. 3) that upon being triggered, produces a single cycle of a CPPN encoded activation pattern. Consequently, the repeated triggering of the SUPG results in temporal oscillations, that can be used to drive the motors of a legged robot [START_REF] Morse | Single-unit pattern generators for quadruped locomotion[END_REF].

In this encoding, the CPPN is input the position (x, y) of the SUPG in the substrate, and the elapsed time (in interval [0, 1]) since the SUPG was last triggered (Fig. 3a). During the period of the SUPG, its internal timer ramps upwards with each simulation time-step, from an initial value of 0 to a maximum value of 1 (Fig. 3b). Therefore, the resultant activation pattern output by the SUPG is a function of both, its position in the substrate, and the time since the last cycle was initiated.

Applying the SUPGs for hexapod locomotion, the substrate comprises 12 SUPGs positioned to reflect the robot morphology (Fig. 3c). The outputs of the SUPGs at each time-step specify the desired angles for the first and second servos (s 1 and s 2 ), on each leg of the robot. The two SUPGs on each leg of the robot are triggered by the corresponding foot touching the ground, resulting in a closed-loop control. Finally, to avoid all the SUPGs being triggered simultaneously, the first trigger to each SUPG is delayed by an offset. In this study, the offset output of the CPPN is determined for the s 1 SUPG on each leg by supplying its coordinates as input, and setting the time input to 0. The same offset value is also applied to the s 2 SUPG on the leg, allowing both the oscillators on each leg to start simultaneously.

Direct encoding: Locomotion controllers evolved with direct encoding are designed to be simple, wherein the actuation along each DOF of the robot is governed by the periodic signal of an uncoupled amplitude controlled phase oscillator. For an oscillator controlling servo s j on leg l of the robot, we have:

αlj = β β 4 (A lj -α lj ) -αlj (3a) γ lj = α lj cos (2π (t + φ lj )) (3b)
where α lj and φ lj denote the amplitude and phase of the oscillator, A lj represents its intrinsic amplitude, and γ lj represents the control signal with frequency of 1 Hz. The uncoupled oscillator amplitude α lj converges to the intrinsic amplitude A lj at rate determined by positive constant β (set to 10 for rapid convergence). The Euler integration method with a step-size of 20 ms is used to solve the differential equation.

Hexapod leg actuation is governed by the differential equation model (eq. 3) instead of a standard periodic function (e.g., [START_REF] Koos | Fast damage recovery in robotics with the T-resilience algorithm[END_REF]), to allow for smooth transitions in amplitude and frequency of the control signal between different gaits and to investigate the effects of coupling between oscillators, in our future work.

There are four evolved parameters (A l1 , φ l1 , A l2 , φ l2 ) on each leg l ∈ {0 . . . 5} of the robot. Consequently, a directly encoded controller for the hexapod robot is fully represented by 24 parameters.

Experiments

We conducted 8000 generations of artificial selection in populations consisting of 100 individuals. Our aim was to evolve controllers for the hexapod robot to walk forward, evaluated for a period of 5 s (334 time-steps). The nondominated sorting genetic algorithm II (NSGA-II) was used to simultaneously optimize the following three objectives:

Maximize      -Fi -|Θi| 1 N j=N j=0 D(Bi, Bj) (4)
where for individual i in the population, F i is the fitness computed as the distance between the final position of and a goal located 25 m directly in front of the robot's initial position, Θ i denotes the angle of the robot's trajectory with respect to the normal forward walking direction, D(B i , B j ) is the hamming distance between the binary gait vectors of individual i and j, and N is the size of the population.

In eq. 4, the first and second objectives reward individuals to walk forward large distances towards a goal, unattainable by the robot within the experiment evaluation time. The third objective is introduced to facilitate the exploration of diverse solutions and avoid premature convergence [START_REF] Mouret | Encouraging behavioral diversity in evolutionary robotics: An empirical study[END_REF].

Artificial selection was conducted in 20 independent replicates, for each of the three encodings. Performance and evolvability analysis are reported for the best individual of each replicate, selected to have the highest fitness in the population, and with an angle of trajectory in the range of ±1 • (simulation source code can be downloaded from http://pages.isir.upmc.fr/evorob_db.)

Individual performance

In all the encodings, the performance of the best individuals rapidly increased with a quasi-stable equilibrium being reached with less than 5000 generations of selection (Fig. 4a). Additionally, the directly encoded individuals converged more rapidly as compared to those encoded with ANN and SUPG schemes (Fig. 6a). After 8000 generations, the performance of the Direct, ANN and SUPG encodings, was 1.94 ± 0.18, 2.93 ± 1.60 and 2.78 ± 1.43 meters, respectively (Median±IQR, see Fig. 4b). Amongst the three encoding schemes, the directly encoded individuals received the lowest performance (Mann-Whitney test, d.f. = 2, p < 0.001), while no significant difference in performance was detected between the two generative encoding schemes. Importantly, the frequency of the directly encoded oscillations governing leg actuation was prefixed at 1 Hz (eq. 3b). By contrast, the individuals evolved with generative encodings were capable of expressing higher frequency oscillations (2.56 ± 1.25 Hz for ANN, and 3.81 ± 0.73 Hz for SUPG), and the frequency of the gait may itself be under selection. Consequently, an assessment of the three encodings solely on the basis of the performance is biased, and other measures are needed to compare encodings.

Evolvability analysis

The evolvability provided by the encoding schemes is analyzed by mutating the best individual of each replicate at generation 8000, and reporting the following: (i) The proportion decrease in performance consequent to the mutation (eq. 1); and (ii) The gait diversity, computed as the mutual information between gait vectors of the original and mutated individual (eq. 2c). The individual is mutated 1000 times, in separate, independent instances. Finally, a kernel density estimation [START_REF] Scott | Multivariate density estimation: theory, practice, and visualization[END_REF], is used to visualize the resultant landscape of 20000 data points (1000 mutations × 20 replicates), pooled together from all replicates. 3Across the three encoding schemes, the SUPG approach revealed the highest evolvability, with the capability to explore very different but viable gaits (see Fig. 5). In evolvability analysis with Direct encoding, a conservative exploration of the phenotype, limited to solutions close to the unmutated individuals was found (0.33 and 10.5%, median gait diversity, and drop in performance, respectively). By contrast, the generative encodings were aggressive in the exploration of the phenotypic landscape, with the gait diversity of mutated individuals at 0.95 for ANN, and 0.99 for the SUPG encodings. However, differences existed in the severity of negative effects of mutations amongst the two encoding schemes. The ANN encoded individuals were sensitive to the effects of deleterious and lethal mutations4 , resulting in a 78.9% drop in performance. In comparison, individuals evolved with the SUPG encoding were much more resilient to the negative effects of mutations, with a smaller decrement of 43.1% in performance following mutation.

Adaptation to faults

The significance of our measure of evolvability of the Direct, ANN and SUPG encodings was investigated by analyzing the adaptation of the evolved robot's gait, following the removal of one of its legs. We expect that for the encodings registering a higher measure of evolvability, the corresponding evolved individuals would require fewer generations to recoverer an effective walking gait.

In these experiments, the new populations comprised 100 mutated individuals of the best individual of each replicate at generation 8000. We conducted a further 10000 gener-ations of artificial selection on the populations of amputee hexapods (leg 1 removed). The number of generations required to regain an effective gait and the proportion of the original performance recovered, was analyzed. In the 10000 generations of selection, all the three encodings were capable of recovering the majority of their original performance (see Fig. 6a). After 10000 generations post leg removal, the recovered proportion of performance of the Direct, ANN and SUPG encodings, was 0.88 ± 0.04, 0.92 ± 0.38, and 1.02 ± 0.14, respectively (Median±IQR, see Fig. 6b). Furthermore, amongst the three encoding schemes, the SUPG encoded individuals recovered the most of their original performance (Mann-Whitney test, d.f. = 2, p < 0.001), while no significant difference in recovered performance was detected between the Direct and ANN schemes.

In order to analyze the recovery rate of amputee hexapods, in Fig. 7 we have plotted the performance lost immediately after leg removal in each of 20 replicates (horizontal axis) and the number of generations required to recover 90% of the original performance in each replicate (vertical axis). The directly encoded individuals could make a 90% recovery in only 6 of 20 replicates, and suffered a median drop in performance of 60.9% immediately following leg removal. By contrast, the ANN and SUPG generative encoding schemes were better able to recover the loss in performance following amputation. In experiments with ANN encoding, 12 of 20 replicates recovered 90% of their original performance in 4392 generations (median for all replicates), despite a drastic initial loss in performance of 93.9%. The SUPG encoded amputee hexapods exhibited the fastest recovery, with 18 of 20 replicates being able to make the mark in 559 generations (median for all replicates), after incurring a smaller initial drop in performance of 67.3% consequent to leg removal.

Discussion

We investigated the evolvability provided by generatively encoded ANNs [START_REF] Clune | On the performance of indirect encoding across the continuum of regularity[END_REF][START_REF] Yosinski | Evolving robot gaits in hardware: the hyperneat generative encoding vs. parameter optimization[END_REF] and SUPGs [START_REF] Morse | Single-unit pattern generators for quadruped locomotion[END_REF], and a direct encoding, quantifying both, (i) the robustness to deleterious mutations, and (ii) the variations in the phenotypes after genetic change, for the hexapod locomotion problem. The significance of our measure of evolvability was evaluated by the individual adaptation response to morphological changes, not previously encountered by the hexapod.

Our results revealed a direct relationship between the estimated evolvability, and the capability of an individual to adapt to severe changes in its morphology, simulated by the amputation of one of its legs. Amongst the three encodings evaluated, SUPGs exhibited the highest evolvability, and were best able to recovery following leg removal. In all but two replicates, the individuals were capable of recovering 90% of their original performance, and did so almost an order of magnitude faster than the other encodings, perhaps consequent to the closed-loop control ingrained in the SUPG encoding scheme. Such a mechanism would attempt to reform deleteriously mutated gaits, and consequently buffer the individual from the negative effects of such mutations. However, the effects of such a self-correction mechanism on evolvability needs further investigation.

The generatively encoded ANN and SUPG individuals achieved high performance gaits, when evolved for the symmetric hexapod robot. However, the performance recovery following leg removal was appreciably different between the two encoding schemes. The longer recovery of ANN individuals may be consequent to the resultant unsymmetrical and irregular hexapod morphology, a region of the problem geometry space wherein ANN generative encodings have been shown to perform poorly [START_REF] Clune | On the performance of indirect encoding across the continuum of regularity[END_REF]. Consequently, the damage recovery of ANN-encoded individuals would improve in situations wherein changes to the hexapod morphology preserve its symmetry (such as the removal of two middle legs). The outcome of such a scenario needs to be explored further.

For our measure of evolvability, we mutated the individuals with a predetermined mutation rate, tuned to allow a speedy convergence of the evolved solutions. This is a critical consideration, as variations to the mutation rate can affect the viability and gait diversity of generated mutants. Preliminary results suggest that with an increase in mutation rate, the peak of the distribution of mutants shifts towards more diverse gaits. However, the overall shape of the distribution, highlighting desirable regions of the evolvability landscape, remains the same for all three encodings. A rigorous analysis on the effect of variations in mutation rate and size (e.g, small mutations to many genes, or large mutations to a few genes) on the evolvability landscape, is part of our future work.

In this study, we present a novel approach to visualize the evolvability of a genotype-phenotype map, to analyze simultaneously the quality of genetic mutations, and the quantity of phenotypic variation generated. Our measure of evolvability may allow the selection of an encoding capable of producing adaptable individuals, when a inter-encoding performance comparison is no longer sufficient. In our model, the phenotypic variation was associated with the mutual information between hexapod gaits, but the diversity may be similarly computed for bipedal and quadrupedal robots, and for other qualities, such as the final position of a robot in a maze navigation task [START_REF] Lehman | Improving evolvability through novelty search and self-adaptation[END_REF][START_REF] Mouret | Encouraging behavioral diversity in evolutionary robotics: An empirical study[END_REF]. In this way, we hope our work may serve as a stepping stone for further research on evolvability, applied to a wide range of problems in the field of evolutionary computation.

Supplemental data: Movies of hexapod walking behavior are online at http://goo.gl/4HC5MY.

  Figure 1: (a) Snapshot of an 18-DOF simulated hexapod robot walking on a horizontal surface, with contacts simulated. (b) Kinematic scheme of the robot, with cylinders representing actuated pivot joints. The three servos on each leg, s 1 , s 2 and s 3 , are labeled in increasing order of distance to robot torso.

Figure 2 :

 2 Figure2: Encoding ANNs with CPPNs (inspired by[START_REF] Clune | On the performance of indirect encoding across the continuum of regularity[END_REF];[START_REF] Yosinski | Evolving robot gaits in hardware: the hyperneat generative encoding vs. parameter optimization[END_REF]). Inter-neuron connection weights are encoded as function of the position source and target neurons of each neural connection. The CPPN outputs the weights of input-hidden and hidden-output neuron connections, for each source (x 1 , y 1 ) and target neuron (x 2 , y 2 ) in proximal layers. The ANN is input the requested angles of the previous time-step for the first two servos (s 1 and s 2 ) on each leg, and a sine and cosine wave. The output neurons specify the new joint angles for the current time-step.

Figure 3 :

 3 Figure 3: Encoding SUPGs with CPPNs (inspired by Morse et al. (2013)). (a) The SUPG output is a function of its coordinates (x, y) in the substrate, and the elapsed time since last trigger (output of Timer). The time of first trigger is determined by an offset. (b) Once triggered, the SUPG timer ramps upward linearly from 0 to 1 and stays there, until it is re-triggered. (c) Positions of the 12 SUPGs in the substrate, outputting the desired angles for the first two servos (s 1 and s 2 ), on each leg of the hexapod.

Figure 4 :

 4 Figure 4: Performance in forward displacement for the Direct, ANN, and SUPG encodings: (a) Median performance for the 8000 generations of evolution; and (b) Performance of encodings at generation 8000.

Figure 5 :

 5 Figure 5: Gait diversity and the proportion decrease in performance, consequent to each of 20000 independent mutations, for the Direct (left), ANN (middle), and SUPG (right) encoding schemes, pooled from all 20 replicates.

Figure 6 :

 6 Figure 6: Recovered performance in forward displacement with the removal of leg 1 (legs numbered in Fig. 1a), for the Direct, ANN, and SUPG encodings: (a) Median proportion of performance before (left), and after (right) leg removal; and (b) Proportion of performance recovered 10000 generations after leg removal.

Figure 7 :

 7 Figure7: Proportion of performance lost immediately after leg removal and the number of generations (of 10000) required for recovery, in each of the 20 replicates (small markers), and the corresponding medians (large markers), for the Direct, ANN, and SUPG encoding schemes. The bounding boxes extend from first to third quartile.

http://www.ode.org

The CPPN is evolved with a simple multi-objective evolutionary algorithm, instead of the NEAT method (details in[START_REF] Tonelli | On the relationships between generative encodings, regularity, and learning abilities when evolving plastic artificial neural networks[END_REF]).

Bivariate density estimation, with Gaussian type kernels over a grid of 100 × 100 equidistant points.

Lethal mutations result in performance drops in excess of 100%, corresponding to the failure of any forward movement by the robot.

Acknowledgment: This study was supported by the ANR Creadapt project (ANR-12-JS03-0009).


J.-M Jehanno

A Cully

C Grand

J.-B Mouret

Design of a Wheel-Legged Hexapod Robot for Creative Adaptation

Keywords: wheel-legged robot, mechatronic design, hexapod, adaptation

Thanks to recent advances in adaptation algorithms, it is now possible to give robots the ability to discover by trial-and-error the best way to behave in unexpected situations, instead of relying on contingency plans. In this paper, we describe the kinematic and mechatronic design of the Creadapt robot, a new mobile robot designed to take full advantage of these recent adaptation algorithms. This robot is a versatile wheel-legged hexapod designed for both legged and wheeled locomotion. It is reversible to be able to continue its mission if it flips over and it uses 6 legs to be able to move efficiently if one or several legs break. This robot also embeds two RGB-D cameras to estimate its velocity onboard, thanks to a RGB-D visual odometry algorithm. Overall, the Creadapt robot is one of the first mobile robot designed with adaptation algorithms in mind.

Introduction

Autonomous robots are inherently complex machines that have to cope with dynamic and often adverse conditions, may they be on a remote planet, in a city, or even in a house. As a consequence, they have to be capable of recovering from unexpected damages and deal with unforeseen situations. 1 Robustness and fault tolerance are classic research topics in robotics and engineering. The classic approaches rely on a combination of contingency plans, redundancy of components, and diagnostic of the faulty subsystems. [START_REF] Koren | Fault-tolerant systems[END_REF] However, they require extensive self-monitoring abilities and are costly to operate because of the redundancy.

In the Creadapt project a , we investigate an alternative approach: instead of trying to anticipate faults, we endow our robots with learning abilities that allow them to discover by trial-and-error the best way to behave in the current situation. Following this line of thought, we recently introduced the T-Resilience algorithm, which allowed a hexapod robot to learn to walk again in less than 20 minutes after the loss of a leg removal, a broken leg or a motor failure. Nevertheless, the learning algorithm is only half of the story because, however good the algorithm, such a robot needs to possess the physical capabilities to achieve its mission in alternative ways. For instance, if a car breaks its engine, no learning algorithm will make it discover a new way to move.

In the present paper, we describe our attempt at designing a mobile robot that can move in many different ways so that the T-Resilience algorithm can be used at its full potential (Fig. 1). We designed our robot with legs because it is a versatile locomotion mode, especially in rough terrains. We used six legs, so that if one or several legs break, the robot can still find efficient gaits. On simple terrains, wheeled locomotion is often more efficient than walking. We therefore extended each leg by a powered, steerable wheel, so that the robot can rely on classic wheeled locomotion when possible. This architecture also enables hybrid locomotion modes, depending on how the wheels and the legs are coordinated. In addition, one of the classic issue with legged robots is their tendency to flip over and not being able to recover. We cannot pre-program a recovery procedure because we do not know whether the robot is broken, how it could be broken, or the features of the terrain. We therefore equipped our robot with special legs that allows it to walk on its back. Last, we gave the robot two embedded RGB-D sensors and a visual odometry algorithm 3 so that it can estimate its velocity on-board.

Background and Context

A hybrid locomotion system is defined as a mechanical system that combines various types of propulsion devices such as wheels, legs, or tracks, and that can handle specific locomotion modes like the roller-walking [START_REF] Hirose | Study on roller-walk (basic characteristics and its control)[END_REF] or the crawling modes. [START_REF] Besseron | Locomotion modes of an hybrid wheel-legged robot[END_REF] There are numerous ways to combine the propulsion devices, considering parallels 6 or serials 7 arrangements, or by using mechanical reconfiguration of a subsystem, like a wheel that transforms to a foot. [START_REF] Hirose | Study on roller-walk (basic characteristics and its control)[END_REF] Some systems are based on multiple propulsion devices, like the Azimut robot, which uses wheels, legs and tracks. [START_REF] Michaud | [END_REF] In this project, our developments are focused on the wheel-legged hybrid architecture that use wheels mounted at the end of actuated legs. Many robots have already been developed based on this mechanical architecture. Most of them are based on a 4 wheel-legs arrangement such as the Hylos robot, [START_REF] Grand | Stability control of a wheel-legged mini-rover[END_REF] the Workpartner, 10 the RIMRES-Sherpa 11 or the PAW robot. [START_REF] Smith | Paw: a hybrid wheeled-leg robot[END_REF] A minimalist version, the family of robots Tri-Star, uses only three wheels and is dedicated to planetary exploration. [START_REF] Aoki | [END_REF] An interesting variant is implemented in Chimp, from CMU b , which uses tracked locomotion devices at the end of its four limbs. This robot was recently demonstrated during the DARPA Robotics Challenge.

Wheel-legged robots with three or four limbs are interesting structures because they can adapt their posture to the terrain and optimize some performance criteria like their tip-over stability. However, they easily become sub-efficient if they are damaged, for example when a motor fails or when a mechanical part breaks. The use of more than four legs offers more versatility and extends the behavioral diversity, allowing the system to learn new locomotion modes when needed. To our knowledge, Athlete, developed by NASS/JPL, 14 and Asterisk-H, from the Arai Laboratory, 15 are the only wheel-legged robots with more than four legs.

In the following section, we describe the path that we followed to develop our 6-wheel-legged robot.

Kinematics

A1 A2 A3 A4 A5 A1 A2 A3 A4 & P3 A5 P3 P2 P1 P2 P1 Figure 2
. Kinematic design of the legs. A1, A2, A3, and A5 are actuated. The wheel is also actuated. A system of pulleys (P1, P2, and P3) drives the degree of freedom A4, so that the wheel is always perpendicular to the body. The foot is not mounted on this prototype.

The Creadapt robot has a semi-hexagonal body shape with six identical legs (Fig. 1). Each leg has in total 6 degrees of freedom (DOF): 4 actuated DOFs, 1 underactuated DOF, and 1 actuated wheel.

The kinematics of each leg (Fig. 2) is divided into two parts: (1) a classic 3-DOFs leg kinematics, with a first vertical joint (Fig. 2: A1), which controls the orientation of the leg, and two horizontal joints (Fig. 2: A2 and A3), which control its elevation and extension; and (2) a steerable, actuated wheel (Fig. 2: A5 and the wheel). All these degrees of freedom and the wheel are actuated.

The normal direction of the contact surface between the wheel and the ground directly impacts the friction and thus the thrust produced by the wheel. For this reason, the two kinematics parts are coupled with an underactuacted joint (Fig. 2: A4) that keeps the wheel perpendicular to the robot's body. The alignment is obtained thanks to a cables and pulleys system that copies the orientation of the body. This system includes a combination of three serial pulleys. The first pulley (Fig. 2: P1) is fixed to the first segment (between A1 and A2) which has the same angular orientation than the body. The second pulley (Fig. 2: P2) is free. The third one is fixed to the pivot joint axis (Fig. 2: A4). Two cables transmit the movement from the first pulley to the second, and from the second to the last one. As a consequence, the first and the final pulley always have the same angular position, whatever the position of intermediate segments.

If the robot flips over, this system will prevent the robot to flip the wheel segment. To cope with this issue, we append a foot to the top of each leg so that the robot can continue its mission by walking on its back. Thanks to the cable system, the the feet will still be perpendicular to the body. The position of the tip of the foot (the contact point) is symmetrical to the wheel. To explore the design trade-offs, we designed a preliminary design algorithm that searches for the best servo-motors and battery combinations for all the actuated joints. The algorithm takes as input a set of parameters that constrain the design: body shape (semi-hexogonal, width equals to length of A2 to A3), minimum and maximum limbs length, autonomy (here fixed to 30 minutes), maximum slope angle for wheeled locomotion (10 degrees), and maximum weight (9kg). To increase the range of possible torques, we included the possibility to connect the servo-motors to the axis via a pulley/toothed belt system, whose reduction ratio has to be determined by the algorithm. We here call geometry ratio the length of the segment A2-A3 divided by 122mm (that is, the length of two MX-64 actuators). The width of the body is the same as A2-A3, and the length A3-A4 is equal to 0.8 times the length of A2-A3, as suggested by Kanner and Dollar. 16 The algorithm enumerates all the possible combinations of battery/actuators of each DOF/reduction ratio/geometry ratio by picking servomotors in the Dynamixel servo-motor catalog and batteries in the Protronics LiPo battery catalog. After the enumeration, it selects the candidates that can roll, walk, lift their own legs, get up with only two legs, and whose battery can supply the nominal and peak current required by the motors. These criteria are evaluated with a static computational model. Among valid candidates (if any), we pick the lightest one.

This preliminary design algorithm outputs a 2-dimensional design space (Fig. 3), where solutions are plotted according to their geometry ratio, which characterizes the size of the robot (including the size of the legs), with regard to the toothed belt reduction ratio for the DOFs A2 and A3, and the total weight.

The resulting combinations range from light and weak to heavy and powerful solutions (Fig. 3). Higher toothed belt ratio allow the robot to use weaker and thus lighter servomotors (i.e. AX-12); higher geometry ratio implies to deal with higher torques and thus require stronger but heavier servo-motors (i.e. MX-106).

We selected the final combination (Fig. 3) by searching for the lightest and the largest robot while taking into account three points: (1) many reduction ratios cannot be produced with standard gears and standard toothed belt; (2) a high reduction ratio implies a reduction of the range of movement (servomotors typically have a range of 300 degrees, which is divided by the toothed belt reduction ratio); (3) the feasibility of geometry ratios lower than 1 depends on the combination of actuators.

Table 1 lists the final characteristics and design choices.

Mechatronics

All the actuated degrees of freedom are powered by position driven servomotors from the Dynamixel product range c . These servos offer integrated PID position control and use a communication bus (3-wires RS-485) to communicate with each of the 30 motors. The first leg segment incorporates two servomotors that actuate axes A2 and A3 (Fig. 2). The final design of the toothed belt reduction is made by inverting the position of the 2 servomotors of the second segment (the servomotor nearest to A2 actuate A1, and reciprocally). The belts (in red on Fig. 2, right) actuates an axis that is coaxial to the output of the opposite servomotor. This solution embeds the two servomotors and the reduction system in a single and compact leg segment, and thus reduces the inertia of the terminal segment. The wheel hub embeds a Dynamixel AX12-W servomotor that actuates the wheel (see Fig. 5). We rewrote the firmware of the AX12-W to implement a PID speed control, instead of the original position control. This solution takes advantage of the servomotor compactness to undertake a compact and inertia-centered wheel design. The output of the servomotor is reduced by gears to increase its torque and the final ring gear is fixed to the wheel's rim that makes the wheel rolling. Wires to power and control the motor go through the axis of the wheel. Tires come from radio-controlled cars.

During the learning experiments, the Creadapt robot has to optimize its velocity, which has to be evaluated onboard. For this purpose, our hexapod embeds two RGB-D cameras (Asus Xtion) to estimate the traveled distance with a recent, fast 3D visual odometry algorithm. [START_REF] Dryanovski | Fast visual odometry and mapping from rgb-d data[END_REF] In our preliminary tests, we obtained an accuracy of 5-10% when the robot is walking indoor. The two cameras are located in the front and the back of the robot to maximize their field of view and to ensure that one camera is always pointing forward. Having two cameras also allows the robot to cope with a broken camera.

The robot includes an inertial measurement unit (IMU Xsens MTI-30) to assess the orientation of its body, so that the robot can search for a control policy that minimize the oscillations. In addition, this information helps distinguishing whether the robot is on its wheels (normal operation) or on its feet (if the robot flipped over).

The sensors are connected to an embedded computer (pico-ITX format, Intel Atom Z530 processor -a hyper-threaded mono-core at 1.6 GHz with an x86 architecture), with 2 Gb of RAM. An LCD display and an inputouput board with several switches and LEDS are on a side of the robot (Phidget USB LCD), to show the robot status and to select the operation modes. All these devices are connected to the computer through an USB hub. An ethernet-wifi bridge is used to connect the robot to a wifi network, so that we can remotely operate the robot and send some computations to an external computer, if needed.

The computer runs Ubuntu and the ROS meta-operating system. 17 A single, custom node takes care of the interactions with the servo-motors; a node is connected to each RGB-D sensor, which is itself connected to the visual odometry algorithm; 3 a node interfaces the IMU; a last node interfaces the USB display.

All the devices of the robot are powered by a lithium-polymer battery (4S, 14.8V / 8000 mAh) that provides an autonomy of about 30 minutes, which is enough to evaluate the adaptation algorithm used in this project. 1 The servomotors are directly connected to the battery, but the electronics devices are powered by an custom-made 5V DC-DC converter board. For longer experiments, the robot can be powered with an external power supply. In such configurations, an ethernet cable is directly connected to the robot to avoid WIFI reception issues and improve the bandwidth.

Conclusion

The Creadapt robot blends off-the-shelf components, like Dynamixel actuators, with specific systems, like the cable systems that passively keeps the wheel vertical, or the powered wheel with an integrated actuators and a custom firmware. The preliminary design algorithm allowed us to exploit a computational model to rigorously select the best combination of components. Metal and plastic 3D-printing proved to be invaluable to use off-the-shelf components in original ways. The mechatronics design takes advantage the ROS meta-operating system to easily make a modern, modular software platform. Overall, the design of the Creadapt robot illustrates how machine learning algorithms can influence mechatronics choices; it thus questions the classic design process in which mechanical design precludes control and adaptation algorithms.

All the CAD files and the developed software will be freely available on the website of the project (http://www.creadapt.net).

Figure 1 .

 1 Figure 1. Overview of the Creadapt robot (3D rendering).

4 .Figure 3 .

 43 Figure3. Results of the preliminary design algorithm. Valid servomotors combinations are sorted according to the their toothed belt reduction ratio, geometric ratio, and their weight. White area indicates that no valid candidates are available. The green point is the selected combination (reduction of 2.5 and a geometry ratio of 1). Each colored zone corresponds to a particular combination of servo-motor for the A2 and A3 DOF; servo-motors for A1 and A5 are not displayed on this figure but their are present in the output of the algorithm. For instance, AX-12/MX-28 means that this zone corresponds to an AX-12 servo-motor for A2 and a MX-28 for A3. The Dynamixel AX/MX range contains the following servo-motors, from the lightest (smallest torque) to the heaviest (largest torque): AX-12, MX-28, MX-64, MX-106.

FrontFigure 4 .

 4 Figure 4. Main components of the body: sensors, battery, computer.

cFigure 5 .

 5 Figure 5. (A)Cross section of the wheel. (B) The wheel mounted on the leg.

Table 1 .

 1 Main characteristics of the Creadapt robot.

b http://www.rec.ri.cmu.edu/projects/tartanrescue/

Acknowledgments

This work has been funded by the "Agence Nationale de la Recherche" (Creadapt project, ANR-12-JS03-0009) and a DGA/UPMC scholarship for A.C.


Jean-Baptiste Mouret

Paul Tonelli

Artificial Evolution of Plastic Neural Networks: a few Key Concepts

published or not. The documents may come

L'archive ouverte

Introduction

The abilities of animals to adapt to new environments is one of the most fascinating aspects of Nature and it may be what most clearly separates animals from current machines. Natural adaptive processes are classically divided into three main categories, each of them having been a continuous source of inspiration in artificial intelligence and robotics [START_REF] Floreano | Bio-inspired artificial intelligence: theories, methods, and technologies[END_REF]: evolution, development and learning. While studying each of these processes independently have been widely successful, there is a growing interest in understanding how they benefit from each other.

In particular, a large amount of work has been devoted to understand both the biology of learning (e.g. [START_REF] Schultz | A Neural Substrate of Prediction and Reward[END_REF][START_REF] Trappenberg | Fundamentals of Computational Neuroscience[END_REF]) and the design of learning algorithms for artificial neural networks (e.g. [START_REF] Haykin | Neural networks: a comprehensive foundation[END_REF]); concurrently, evolution-inspired algorithms have been successfully employed to automatically design small "nervous systems" for robots [START_REF] Floreano | Neuroevolution: from architectures to learning[END_REF][START_REF] Kodjabachian | Evolution and development of neural controllers for locomotion, gradient-following, and obstacle-avoidance in artificial insects[END_REF][START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: an Empirical Study[END_REF][START_REF] Mouret | Importing the computational neuroscience toolbox into neuro-evolution-application to basal ganglia[END_REF][START_REF] Stanley | A Hypercube-Based Indirect Encoding for Evolving Large-Scale Neural Networks[END_REF][START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF], sometimes by taking inspiration from development processes [START_REF] Kodjabachian | Evolution and development of neural controllers for locomotion, gradient-following, and obstacle-avoidance in artificial insects[END_REF][START_REF] Mouret | Importing the computational neuroscience toolbox into neuro-evolution-application to basal ganglia[END_REF][START_REF] Nolfi | Phenotypic plasticity in evolving neural networks[END_REF][START_REF] Stanley | A Hypercube-Based Indirect Encoding for Evolving Large-Scale Neural Networks[END_REF]. A comparatively few papers proposed to combine the artificial evolution of neural networks with synaptic plasticity to evolve Jean-Baptiste Mouret and Paul Tonelli ISIR, Université Pierre et Marie Curie-Paris 6, CNRS UMR 7222, Paris, France e-mail: {mouret,tonelli}@isir.upmc.fr

Adaptation Selection Variation

Plastic neural network

Dynamic environment

Population of neural networks

Simulation of behavior

Fig. 1 The artificial evolution of plastic neural networks relies on the classic evolutionary loop used in neuro-evolution. The algorithm starts with a population of genotypes that are thereafter developed into plastic neural networks. The topology of the neural network is sometimes evolved [START_REF] Risi | Indirectly Encoding Neural Plasticity as a Pattern of Local Rules[END_REF][START_REF] Risi | How novelty search escapes the deceptive trap of learning to learn[END_REF][START_REF] Soltoggio | Evolutionary advantages of neuromodulated plasticity in dynamic, reward-based scenarios[END_REF][START_REF] Soltoggio | Evolving neuromodulatory topologies for reinforcement learning-like problems[END_REF][START_REF] Soltoggio | Novelty of behaviour as a basis for the neuro-evolution of operant reward learning[END_REF][START_REF] Stanley | Evolving adaptive neural networks with and without adaptive synapses[END_REF][START_REF] Tonelli | On the Relationships between Synaptic Plasticity and Generative Systems[END_REF]. Typical plastic neural networks use a variant of the Hebb's rule to adapt the weight during the "lifetime" of the agent. The fitness of the agent is most of the time evaluated in a dynamic environment that requires the agent to adapt its behavior. The agent is therefore usually directly selected for its adaptive abilities. artificial agents that can adapt their "artificial nervous system" during their "lifetime" [7, 15-18, 21-23, 28, 30] (Fig. 1). However, the analysis of these works shows that they often address different challenges in very different situations, while using the same terminology (e.g. "learning", "robustness" or "generalization").

The goal of the present chapter is to provide a set of definitions to make as clear as possible current and future works that involve the evolution of such plastic artificial neural networks (ANNs) to control agents (simulated or real robots). While some definitions and some distinctions are novel, the main contribution of the present paper is to isolate each concept and to present them in a coherent framework. For each definition, we will provide examples of typical setups and current results. Figure 2 displays the hierarchy of the concepts that will be introduced; it can serve as a guide to the paper.

Synaptic Plasticity

In neuroscience, plasticity (or neuroplasticity) is the ability of the brain and nervous systems to change structurally and functionally as a result of their interaction with the environment. Plasticity is typically observed during phases of development and learning. Trappenberg [START_REF] Trappenberg | Fundamentals of Computational Neuroscience[END_REF] defines two kinds of plasticity: structural plasticity and synaptic (or functional) plasticity. Definition 1 (Structural plasticity). Structural plasticity is the mechanism describing generation of new connections and thereby redefining the topology of the network.

Evolved neural networks

Acquisition of new behaviors

Skinner box Bumblebee

Behavioral switch

Definition 2 (Synaptic plasticity). Synaptic plasticity is the mechanism of changing strength values of existing connections. It is sometimes termed "functionnal plasticity" [START_REF] Trappenberg | Fundamentals of Computational Neuroscience[END_REF].

Nolfi et al. [START_REF] Nolfi | Phenotypic plasticity in evolving neural networks[END_REF] investigated structural plasticity in a system in which the genotype contained developmental instructions for the construction of a neural network. Genes specified (1) the position of each neuron and (2) instructions that described how axons and branching segments grew. These instructions were executed when a neuron was sufficiently stimulated by its surrounding neurons and by the agent's environment. The authors observed different phenotypes when the same genotype was used in two different environments and concluded that their approach increased the adaptive capabilities of their organisms. Several other authors evolved neural networks while letting them grow axons depending on their location (e.g. [START_REF] Kodjabachian | Evolution and development of neural controllers for locomotion, gradient-following, and obstacle-avoidance in artificial insects[END_REF][START_REF] Stanley | A Hypercube-Based Indirect Encoding for Evolving Large-Scale Neural Networks[END_REF]) but the enviroment was not taken into account.

Most studies on the evolution of plastic neural networks instead focused on synaptic plasticity [START_REF] Blynel | Levels of dynamics and adaptive behavior in evolutionary neural controllers[END_REF][START_REF] Floreano | Evolution of plastic neurocontrollers for situated agents[END_REF][START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments: A Simple Explanation for Complex Foraging Behaviors[END_REF][START_REF] Urzelai | Evolution of adaptive synapses: Robots with fast adaptive behavior in new environments[END_REF], maybe because of the prominence of learning algorithms that only adapt weights in the Machine Learning literature. Most of the works that do not rely on machine learning algorithms (e.g. the backpropagation algorithm) [START_REF] Chalmers | The evolution of learning: An experiment in genetic connectionism[END_REF][START_REF] Nolfi | How Learning and Evolution Interact: The Case of a Learning Task which Differs from the Evolutionary Task[END_REF] use variants of the "Hebb's rule" [START_REF] Blynel | Levels of dynamics and adaptive behavior in evolutionary neural controllers[END_REF][START_REF] Floreano | Evolution of plastic neurocontrollers for situated agents[END_REF][START_REF] Risi | Indirectly Encoding Neural Plasticity as a Pattern of Local Rules[END_REF][START_REF] Tonelli | On the Relationships between Synaptic Plasticity and Generative Systems[END_REF][START_REF] Urzelai | Evolution of adaptive synapses: Robots with fast adaptive behavior in new environments[END_REF], which posits that the simultaneous activation of two neurons strengthens the synapse that link them. Definition 3 (Hebb's rule). Let us denote by i and j two neurons1 , a i and a j their respective activation level, w i j the synaptic weight of the connection from i to j and η a learning rate that describes how fast the change occurs. According to Hebb's rule, w i j should be modified as follows:

w i j (t + 1) = w i j (t) + ∆ w i j (1)
∆ w i j = η • a i • a j (2)
Hebb's rule is often extended to include more complex combinations of pre-and post-synaptic activities [START_REF] Blynel | Levels of dynamics and adaptive behavior in evolutionary neural controllers[END_REF][START_REF] Floreano | Evolution of plastic neurocontrollers for situated agents[END_REF][START_REF] Risi | Indirectly Encoding Neural Plasticity as a Pattern of Local Rules[END_REF][START_REF] Trappenberg | Fundamentals of Computational Neuroscience[END_REF][START_REF] Urzelai | Evolution of adaptive synapses: Robots with fast adaptive behavior in new environments[END_REF].

Definition 4 (Extended Hebbian rule).

∆ w i j = f (a i , a j , w i j ) (3)
Many different f () have been investigated; one of the simplest extended Hebbian rule consists in linearly combining pre-and post-synaptic activities [START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments: A Simple Explanation for Complex Foraging Behaviors[END_REF][START_REF] Risi | Indirectly Encoding Neural Plasticity as a Pattern of Local Rules[END_REF][START_REF] Soltoggio | Evolutionary advantages of neuromodulated plasticity in dynamic, reward-based scenarios[END_REF][START_REF] Urzelai | Evolution of adaptive synapses: Robots with fast adaptive behavior in new environments[END_REF]:

∆ w i j = A • a i • a j + B • a i +C • a j + D (4)
where A,B, C and D are four real numbers. Most authors select a set of values for A, B,C and D, but several different combinations can also be used in the same neural network. For instance, Urzelai and Floreano proposed to evolve the plasticity rules that govern each synapse of fully connnected neural networks [START_REF] Urzelai | Evolution of adaptive synapses: Robots with fast adaptive behavior in new environments[END_REF].

A synapse can also be strengthened or weakened as a result of the firing of a third, modulatory inter-neuron (e.g. dopaminergic neurons) [START_REF] Bailey | Is heterosynaptic modulation essential for stabilizing Hebbian plasticity and memory? Nature reviews[END_REF][START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments: A Simple Explanation for Complex Foraging Behaviors[END_REF][START_REF] Soltoggio | Evolving neuromodulatory topologies for reinforcement learning-like problems[END_REF]. To reflect this phenomenon, two kinds of neurons can be distinguished: modulatory neurons and modulated neurons. Inputs of each neuron are divided into modulatory inputs and signal inputs; the sum of the modulatory inputs of j governs the modulation of the all non-modulatory connections to j: Definition 5 (Modulated Hebbian rule). Let us denote by I (m) j the set of modulatory inputs of neuron j and by I ( j) s the set of non-modulatory inputs. Each incoming connection of neuron j is modified as follows:

m j = tanh    ∑ k∈I (m) j w k j a k    (5) ∀i ∈ I ( j) s , ∆ w i j = m j • f (a i , a j , w i j ) (6)
In addition to its biological realism, this weight adaptation rule makes easier to use rewards signals (for instance, plasticity could be enabled only when a reward signal is on). It also leads to networks in which only a part of the synapses are changed during the day-to-day life of the agent. These two features make such networks match more closely some of the current actor-critic models of reinforcement learning used in computational neuroscience [START_REF] Schultz | A Neural Substrate of Prediction and Reward[END_REF]. Modulated Hebbian plasticity has been used several times when evolving plastic neural networks [START_REF] Kondo | Evolutionary design and behavior analysis of neuromodulatory neural networks for mobile robots control[END_REF][START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments: A Simple Explanation for Complex Foraging Behaviors[END_REF][START_REF] Risi | How novelty search escapes the deceptive trap of learning to learn[END_REF][START_REF] Soltoggio | Evolutionary advantages of neuromodulated plasticity in dynamic, reward-based scenarios[END_REF][START_REF] Soltoggio | Evolving neuromodulatory topologies for reinforcement learning-like problems[END_REF]. In these simulations, experiments in rewardbased scenarios where modulatory neurons were enabled achieved better learning in comparison to those where modulatory neurons were disabled [START_REF] Soltoggio | Evolutionary advantages of neuromodulated plasticity in dynamic, reward-based scenarios[END_REF].

Robustness and Reward-based Scenarios

A major goal when evolving neuro-controllers is to evolve neural networks that keep performing the same optimal (or pseudo-optimal) behavior when their morphology or their environment change. For instance, a robot can be damaged, gears can wear out over time or the light conditions can change: in all these situations, it is desirable for an evolved controller to compensate these changes by adapting itself; we will call this ability behavioral robustness.

Definition 6 (Behavioral robustness). An agent displays behavioral robustness when it keeps the same qualitative behavior, notwithstanding environmental and morphological changes. Behavioral robustness does not usually involve a reward/ punishment system.

In a typical work that combines synaptic plasticity, evolution and behavioral robustness, Urzelai and Floreano [START_REF] Urzelai | Evolution of adaptive synapses: Robots with fast adaptive behavior in new environments[END_REF] evolved neuro-controllers with plastic synapses to solve a light-switching task in which there was no reward; they then investigated whether these controllers were able to cope with four types of environmental changes: new sensory appearances, transfer from simulations to physical robots, transfer across different robotic platforms and re-arrangement of environmental layout. The plastic ANNs were able to overcome these four kinds of change, contrary to a classic ANN with fixed weights.

However, as highlighted by Urzelai and Floreano, "these behaviors were not learned in the classic meaning of the term because they were not necessarily retained forever". Actually, synaptic weights were continuously changing such that the robot performed several sub-behaviors in sequence; the evolutionary algorithm therefore opportunistically used plasticity to enhance the dynamic power of the ANN. These high-frequency changes of synaptic weights appear different from what we observe in natural system (in particular in the basal ganglia), in which synaptic weights tend to hold the same value for a long period, once stabilized [START_REF] Daw | Uncertainty-based competition between prefrontal and dorsolateral striatal systems for behavioral control[END_REF][START_REF] Sutton | Reinforcement learning: An introduction[END_REF].

Besides robustness, an even more desirable property for an evolved agent is the ability to change its behavior according to external stimuli and, in particular, according to rewards and punishments. For instance, one can imagine a robot in a T-maze that must go to the end of the maze where a reward has been put [START_REF] Risi | Indirectly Encoding Neural Plasticity as a Pattern of Local Rules[END_REF][START_REF] Risi | How novelty search escapes the deceptive trap of learning to learn[END_REF][START_REF] Soltoggio | Evolutionary advantages of neuromodulated plasticity in dynamic, reward-based scenarios[END_REF]. The robot should first randomly try different trajectory. Then, once the reward would have been found a few times, the robot should go directly to the reward. Nonetheless, if the reward is moved somewhere else, the robot should change its behavior to match the new position of the reward. Once the robot will have found the optimal behavior (the behavior that maximizes the reward), the synaptic weights of its controller should not change anymore. This ability to adapt in a reward-based scenario can be more formally defined as follows:

Definition 7 (Behavioral change). A plastic agent is capable of behavioral changes in a reward-based scenario if and only if:

• a change of reward makes it adopt a qualitatively new behavior;

• the synaptic weights do not significantly change once an optimal behavior has been reached.

Notable setups in which authors evolved plastic neuro-controllers for behavioral changes are the T-maze [START_REF] Risi | Indirectly Encoding Neural Plasticity as a Pattern of Local Rules[END_REF][START_REF] Risi | How novelty search escapes the deceptive trap of learning to learn[END_REF][START_REF] Soltoggio | Evolutionary advantages of neuromodulated plasticity in dynamic, reward-based scenarios[END_REF], the bumblebee foraging task [START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments: A Simple Explanation for Complex Foraging Behaviors[END_REF], the "dangerous foraging task" [START_REF] Stanley | Evolving adaptive neural networks with and without adaptive synapses[END_REF] and the Skinner box [START_REF] Tonelli | On the Relationships between Synaptic Plasticity and Generative Systems[END_REF].

Learning Abilities in Discrete Environment

The main challenge when evolving plastic agents for behavioral change is to make them able to learn new behaviors in unknown situations and, in particular, in situations that have never been encountered during the evolutionary process. Put differently, selecting agents for their abilitities to switch between alternatives is not sufficient; the evolved agent must also be placed in completely new situations to assess its ability to find an optimal behavior in a situation for which it has never been selected. We previously introduced a theoretical framework to characterize and analyze the learning abilities of evolved plastic neural networks [START_REF] Tonelli | On the Relationships between Synaptic Plasticity and Generative Systems[END_REF]; we will rely on this framework in the remainder of this paper. For the sake of simplicity, we focus on a discrete world, with discrete stimuli and discrete actions. The canonical setup, inspired by experiments in operant conditioning, is the Skinner Box [START_REF] Skinner | Operant behavior[END_REF]: an agent is placed in a cage with n stimuli (lights), m actions (levers), positive rewards (food) and punishments (electric shocks). The goal of the agent is to learn the right associations between each stimulus and each action. This task encompasses most discrete reward-based scenarios (Fig. 3). For instance, the discrete T-maze experiment [START_REF] Risi | Indirectly Encoding Neural Plasticity as a Pattern of Local Rules[END_REF][START_REF] Risi | How novelty search escapes the deceptive trap of learning to learn[END_REF][START_REF] Soltoggio | Evolutionary advantages of neuromodulated plasticity in dynamic, reward-based scenarios[END_REF][START_REF] Soltoggio | Evolving neuromodulatory topologies for reinforcement learning-like problems[END_REF][START_REF] Soltoggio | Novelty of behaviour as a basis for the neuro-evolution of operant reward learning[END_REF] can be described as a special case of a Skinner box.

Discrete T-maze

More formally, an evolved neural network N(I, λ ) must adapt several synaptic weights λ ∈ R z such that each input pattern I ∈ [0, 1] n is associated to the best rewarded output vector K ∈ [0, 1] m . The adaptation is performed by a learning function such that λ = g(λ r , I, R I,K ), where λ r is a random vector in R z and R I,K the reward function. These notations lead to the following definitions: Definition 8 (Association set). An association set A = (I 1 , K 1 ), • • • , (I n , K n ) is a list of associations that covers all the possible input patterns. The set of all association sets is denoted A.

Definition 9 (Fitness associations set). The fitness associations set

F A = {A 1 • • • A k }
is the set of the association sets that are used during the fitness evaluation.

For a given topology, some association sets may not be learnable by only changing synaptic weights. This case occurs in particular when the topology of neural networks are evolved: if there is no selective pressure to maintain a connection, it can easily disappear; but this connection may be required to learn a similar but different association set. Some association sets may also be not learnable because they require specific topologies. For instance, the XOR function requires a hidden layer of neurons to be computed. Definition 10 (Learnable set). Given a suitable reward function R I,K , an association set A ∈ A is said to be learnable by the neural network N, if and only if ∀λ r ∈ R z and ∀(I, K) ∈ A, ∃λ = g(λ r , I, R I,K ) such that N(I, λ ) = K. The set of all learnable sets for N is denoted L N .

Definition 11 (sGLA). A plastic ANN is said to possess synaptic General Learning Abilities (sGLA) if and only if

∀A ∈ A, A ∈ L N .
Although it does not use Hebbian learning, the multi-layer perceptron with the backpropagation algorithm is an example of a neural network with synaptic General Learning Abilities. At the opposite, a neural network in which each input is connected to only one output can learn only one association set.

To evolve a plastic ANN with sGLA, the simplest method is to check the learnability of each association set during the fitness evaluation, that is the fitness associations set is equal to the set of all the association sets; this approach has often been followed by the authors who evolved agents to solve the T-maze task [START_REF] Risi | Indirectly Encoding Neural Plasticity as a Pattern of Local Rules[END_REF][START_REF] Risi | How novelty search escapes the deceptive trap of learning to learn[END_REF][START_REF] Soltoggio | Evolutionary advantages of neuromodulated plasticity in dynamic, reward-based scenarios[END_REF][START_REF] Soltoggio | Evolving neuromodulatory topologies for reinforcement learning-like problems[END_REF][START_REF] Soltoggio | Novelty of behaviour as a basis for the neuro-evolution of operant reward learning[END_REF].

We propose to call such approaches the evolution of behavioral switches to distinguish it from the evolution of more general learning abilities.

Definition 12 (Evolution of behavioral switches).

A study deals with the evolution of behavioral switches when the fitness associations set F A is equals to the set of all association sets that are possible for the studied task (called A): F A = A However, a plastic ANN that can cope with unknown situations must have sGLA while only a subset of the possible association sets (i.e. a subset of problems from the same problem class) has been used during the evolutionary process.

Definition 13 (Evolution of sGLA for unknown situations). A study deals with the evolution of synaptic General Learning Abilities for unknown situations when the goal of the authors is (1) to use a fitness associations set that is smaller than the set of all association sets (card(F A ) < card(A)) and ( 2) to show that all associations sets are learnable with evolved solutions (∀A ∈ A, A ∈ L N ): card(F A ) < card(A) and ∀A ∈ A, A ∈ L N .

At first sight, Nature relies on the long lifetime of animals (compared to the "lifetime" of artificial agents) and on the large size of the populations to obtain a stochastic evaluation of virtually every possible scenarios. This probably explains why most authors tried to obtain agents with sGLA by using a large, often randomized subset of the association sets in the fitness association set. In supervised learning, Chalmers [START_REF] Chalmers | The evolution of learning: An experiment in genetic connectionism[END_REF] assessed how well an evolved plastic ANN can cope with situations never encountered during the evolution. In his experiments, he evolved the learning rule for a small single-layer ANN (5 inputs, 1 output) and his analysis showed that at least 10 sets of input/output patterns (among 30 possible sets) were required to evolve an algorithm that correctly learns on 10 unknown sets. In reinforcement learning, Niv et al. [START_REF] Niv | Evolution of Reinforcement Learning in Uncertain Environments: A Simple Explanation for Complex Foraging Behaviors[END_REF] evolved plastic ANNs to solve a bumblebeeinspired foraging task in which simulated bees must select flowers by recognizing their color. To promote general learning abilities, they randomly assigned rewards to colors at each generation and they showed that the resulting ANNs successfully learned unknown color/reward associations. In the "dangerous foraging task", Stanley et al. [START_REF] Stanley | Evolving adaptive neural networks with and without adaptive synapses[END_REF] similarly randomized the parameters of the fitness function to avoid overspecialized behaviors.

However, the encoding and the development process may also play a key role in allowing the adaptation to situations which have never been encountered before [START_REF] Tonelli | On the Relationships between Synaptic Plasticity and Generative Systems[END_REF]. Intuitively, a very regular network may repeat the same adaptation structure many times whereas it was only required once by the fitness; it could therefore "propagate" the adaptation structure. Since most developmental encoding are designed to generate very regular structures [START_REF] Clune | On the Performance of Indirect Encoding Across the Continuum of Regularity[END_REF][START_REF] Mouret | Importing the computational neuroscience toolbox into neuro-evolution-application to basal ganglia[END_REF][START_REF] Tonelli | On the Relationships between Synaptic Plasticity and Generative Systems[END_REF], using such encodings could substantially reduce the number of evaluations required to obtain general learning abilities. In the ideal case, we should be able to show that the developmental process implies that if a few association sets have been successfully learned, then all the other sets have a high probability of being learnable. Such networks will be said to possess "synaptic Transitive Learning Abilities". Definition 14 (sTLA). Let us denote by T N a subset of the learnable association set A. A plastic ANN is said to possess synaptic Transitive Learning Abilities (sTLA) if and only if ∃ T N ⊂ A such that the following implication is true:

T N ⊂ L N ⇒ L N = A p = card(T N ) will be called the "sTLA-level".
Definition 15 (Optimal-sTLA). A plastic ANN is said to possess Optimal synaptic Transitive Learning Abilities (optimal-sTLA) if and only if it possesses sTLA and card(T N ) = 1.

The sTLA-level of certain families of topologies (i.e. topologies generated by a specific genetic encoding) can possibly be computed theoretically. It can also be easily evaluated by a succession of evolutionary experiments: (1) select p association sets; (2) evolve ANNs that successfully learns the p association sets; (3) check the sGLA of optimal ANNs; (4) if optimal ANNs do not possess sGLA, then increase p and start again.

Using this method, Tonelli and Mouret [START_REF] Tonelli | On the Relationships between Synaptic Plasticity and Generative Systems[END_REF] showed that a very regular mapbased encoding proposed in [START_REF] Mouret | Importing the computational neuroscience toolbox into neuro-evolution-application to basal ganglia[END_REF] have a TLA-level or 1 or 2. Preliminary experiments suggest that other generative encodings such as HyperNEAT [START_REF] Clune | On the Performance of Indirect Encoding Across the Continuum of Regularity[END_REF][START_REF] Stanley | A Hypercube-Based Indirect Encoding for Evolving Large-Scale Neural Networks[END_REF] could also possess a low TLA-level. Overall, the concept of sTLA highlights how evolution, learning and development are interwoven.

All these definitions are well suited for discrete worlds and discrete behaviors. Future work should try propose equivalent definitions for continuous worlds.

Concluding Remarks

With the rise of computing power, it is now easy to simulate artificial agents for enough time for them to learn and to evolve; this allows the study of well-defined scientific questions with modern experimental and statistical techniques. Nevertheless, future work in this direction will have to precisely define what they work on: do they aim at behavioral robustness or at behavioral change? how do they evaluate the general learning abilities of the evolved agents? do the evolved neural network manage to learn in unknown situations? what is the role of the encoding in the final result? The definitions proposed in the present paper will hopefully help to design a methodology to answer such questions.

The present work also highlights open questions and avenues for future researches:

• Should future work focus more on structural plasticity? This approach to plasticity may be more complex but it may also allow agents to learn new skills without forgetting the old ones (because the previous structure is not deleted). • How to evaluate learning abilities in continuous world and with continuous behaviors?

• What are the links between encodings, plasticity and learnability? [START_REF] Tonelli | On the Relationships between Synaptic Plasticity and Generative Systems[END_REF] provides first answers but only for simple and discrete scenarios.

Acknowledgement

This work was funded by the EvoNeuro ANR-09-EMER-005-01 project.

Fig. 2

 2 Fig. 2 Hierarchy of concepts described the present paper. See text for a definition of each gray box.

We focus our discussion on classic neurons (as used in classic machine learning) and populationbased models of neurons (e.g. leaky integrators) because they are the neuron models that are used by most of the community. Spiking neuron models can make use of other plasticity mechanisms (e.g. STDP) that will not be described here.