Stephane Doncieux
email: doncieux@isir.upmc.fr

Jean-Baptiste Mouret
email: mouret@isir.upmc.fr

Behavioral Diversity with Multiple Behavioral Distances

Recent results in evolutionary robotics show that explicitly encouraging the behavioral diversity of candidate solutions drastically improves the convergence of many experiments. The performance of this technique depends, however, on the choice of a behavioral similarity measure (BSM). Here we propose that the experimenter does not actually need to choose: provided that several similarity measures are conceivable, using them all could lead to better results than choosing a single one. Values computed by several BSM can be averaged, which is computationally expensive because it requires the computation of all the BSM at each generation, or randomly switched at a user-chosen frequency, which is a cheaper alternative. We compare these two approaches in two experimental setups -a ball collecting task and hexapod locomotion -with five different BSMs. Results show that (1) using several BSM in a single run increases the performance while avoiding the need to choose the most appropriate BSM and (2) switching between BSMs leads to better results than taking the mean behavioral diversity, while requiring less computational power.

I. INTRODUCTION

Evolutionary Robotics (ER) aims at designing robot controllers and, optionally, morphologies to reach a particular behavior whose efficiency is described by a fitness function [START_REF] Floreano | Evolutionary Robotics[END_REF], [START_REF] Doncieux | Evolutionary Robotics: Exploring New Horizons[END_REF]. This function is then optimized thanks to an Evolutionary Algorithm (EA) that explores a search space of parameters, e.g. R n , or structures, e.g. neural networks topologies. Discovering interesting solutions implies to balance exploration -to avoid local optima -and exploitation -to get the nearest optimal solution. Preserving diversity in the population is known to be an efficient way to deal with a natural tendency of EAs to favor exploitation. In classic EA, this diversity preservation in computed in the space of genotypes, phenotypes or fitness values [START_REF] Goldberg | Simple genetic algorithms and the minimal, deceptive problem[END_REF], [START_REF] Mahfoud | Handbook of Evolutionary Computation, chapter Niching Methods[END_REF]. In ER, it has been widely observed that many genotypes and phenotypes lead to similar behaviors, whereas a very small difference in a genotype can substantially modify the behavior of the robot [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. Since ER is ultimately seeking behaviors, the diversity that appears to matter is the diversity in behavior space. In accordance with this intuition, explicitly encouraging diversity in this space revealed to drastically improve convergence of ER experiments in multiple contexts [START_REF] Gomez | Sustaining diversity using behavioral information distance[END_REF], [START_REF] Mouret | Using Behavioral Exploration Objectives to Solve Deceptive Problems in Neuro-evolution[END_REF], [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF].

Behavioral diversity methods foster diversity by rewarding individuals whose behavior is different from the rest of the population. The similarity is computed using behavior Main proposition. Encouraging behavioral diversity drastically improves the convergence of evolutionary robotics experiments [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF], but it requires defining a Behavior Similarity Measure (BSM). Using many BSM avoids the need to choose and leads to similar or better convergence rates. similarity measures (BSM) that can be problem-specific [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF], [START_REF] Lehman | Abandoning objectives: evolution through the search for novelty alone[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF], [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF] or designed to be used on a large class of robotic tasks [START_REF] Doncieux | Behavioral diversity measures for Evolutionary Robotics[END_REF], [START_REF] Trujillo | Speciation in Behavioral Space for Evolutionary Robotics[END_REF], [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF], [START_REF] Gomez | Sustaining diversity using behavioral information distance[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. Empirical comparisons between BSM have been made in several papers [START_REF] Gomez | Sustaining diversity using behavioral information distance[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF], but, although different BSM yielded different results, no measure has proved to be "the one" for every contexts. The present work investigates another approach: if the best BSM is not known, is it possible to efficiently exploit all the different BSM an experimenter can think of without having to choose among them?

Besides removing the need to choose, relying on several BSM instead of one may also increase the impact of behavioral diversity. A BSM is not perfect when it fails to recognize new behaviors that could substantially increase the best fitness on the long term. Using several different BSM may then lead to a better exploration as their criteria for recognizing a behavior as new and different are not the same. More behaviors will then be recognized as new along a run, leading to a better exploration.

How to take into account several BSM? Two different approaches have been compared. In the first approach, the behavioral diversity objective is simply the average value of the behavioral diversities associated to each BSM 1 . In the second approach, one BSM is used at a time. At a given a period, a new BSM is randomly chosen out of the available BSM and used to compute the behavioral diversity. This second approach decreases the computational load as only one BSM is used at a time. The sensitivity of the results to the switching period is studied.

Hence, this article aims to validate the following hypotheses:

1) using several BSM instead of a single one doesn't decrease performance; 2) a unique BSM does not capture and appropriately reward every original behavior; 3) using several BSM gives statistically more chance to original behaviors to be rewarded during an evolutionary run.

Using several BSM may seem at first sight to be a practical limitation of this approach compared to single BSM approaches because it requires more work to prepare an experiment. In practice it reveals to be easy to find different BSM and quite difficult to choose the one to be used. The only way to do it now is to make some preliminary experiments to evaluate the relative efficiency of each candidate BSM. Not having to choose between different alternatives therefore substantially decreases the amount of preparation for an experiment.

Two setups have been considered: a ball collecting task [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF] and an hexapod walking task.

II. RELATED WORK

While most EA have diversity preserving mechanisms based on the genotype or fitness space, the introduction in ER of a behavior space, may be exploited in this context to foster exploration. Three different approaches dedicated to ER can be identified: novelty search [START_REF] Lehman | Abandoning objectives: evolution through the search for novelty alone[END_REF], behavior speciation [START_REF] Trujillo | Speciation in Behavioral Space for Evolutionary Robotics[END_REF] and behavioral diversity [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. Novelty search aims at abandoning any task-related objective to reward behavioral novelty only [START_REF] Lehman | Abandoning objectives: evolution through the search for novelty alone[END_REF]. Behavior speciation subdivides the population in several sub-populations on the basis of individuals behavior, thus replacing a global competition by a local competition between individuals with similar behaviors [START_REF] Trujillo | Speciation in Behavioral Space for Evolutionary Robotics[END_REF]. Lastly, behavioral diversity defines an helper objective that evaluates the difference in terms of behavior of an individual relative to the current population. This objective is then maximized in a multiobjective scheme together with goal related objectives [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. All these methods rely on comparisons of behaviors.

How to compare behaviors? A robot behavior results from its interaction with the environment. Different behavior descriptors can be used:

• robot trajectory [START_REF] Doncieux | Behavioral diversity measures for Evolutionary Robotics[END_REF], [START_REF] Trujillo | Speciation in Behavioral Space for Evolutionary Robotics[END_REF], [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF] • robot perceptions and/or actions [START_REF] Gomez | Sustaining diversity using behavioral information distance[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF] • adhoc measures depending on the problem to solve [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF], [START_REF] Lehman | Abandoning objectives: evolution through the search for novelty alone[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF], [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF].

Once such descriptors are available, and depending on their features, a similarity can be computed with different kinds of distances, like for instance an Euclidean distance [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF], [START_REF] Lehman | Abandoning objectives: evolution through the search for novelty alone[END_REF], a hamming distance [START_REF] Gomez | Sustaining diversity using behavioral information distance[END_REF], [START_REF] Doncieux | Behavioral diversity measures for Evolutionary Robotics[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF] or an edit distance [START_REF] Trujillo | Speciation in Behavioral Space for Evolutionary Robotics[END_REF], [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF].

Few comparisons have been performed on the choice of the descriptor and distance to use [START_REF] Gomez | Sustaining diversity using behavioral information distance[END_REF], [START_REF] Doncieux | Behavioral diversity measures for Evolutionary Robotics[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. They highlighted that this choice has a significant impact on the performance and that performing a hamming distance on a temporal sequence of discretized robot actions -and eventually perceptions -gives an overall good performance even if has failed in several setups [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. Some features of BSM, like, for instance, the adequacy to human classification [START_REF] Doncieux | Behavioral diversity measures for Evolutionary Robotics[END_REF], were also investigated in an attempt to characterize efficient BSM, but such studies did not lead to any clear conclusion yet. Up to now, it is therefore hard to know whether a single BSM will outperform other BSM in any context or if some method can be built to design an efficient, if not optimal, BSM for a particular problem. The rationale of the present work is different: if several BSM are known and no criteria to decide which one is the best, is it possible to use all of them instead of just one?

III. MULTI-DIST BEHAVIORAL DIVERSITY

Following the results of [START_REF] Jong | Reducing bloat and promoting diversity using multi-objective methods[END_REF], [START_REF] Bui | Diversity as a selection pressure in dynamic environments[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF], a multi-objective diversity mechanism has been used. The general framework of this approach is to add a helper objective in addition to the objectives rewarding the performance on the task [START_REF] Knowles | Reducing Local Optima in Single-Objective Problems by Multi-objectivization[END_REF]. The helper objective measures the mean distance of the evaluated solution to the rest of the population on the basis of behavior comparisons [START_REF] Mouret | Using Behavioral Exploration Objectives to Solve Deceptive Problems in Neuro-evolution[END_REF], [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF].

Instead of using a single BSM during the whole run, the proposed methods consists in using several BSM. The first method consists in averaging the behavioral diversities computed with each BSM. The mean behavioral diversity objective is then defined as follows:

BD mean (x) = 1 M M -1 k=0   1 N y∈P d k (x, y) max a,b∈P (d k (a, b))   (1)
where P is the current population and then x, y, a, b individuals in the population. N the size of the population and d k (x, y) a BSM between x and y (k ∈ [0, M -1]), M being the number of available BSM.

The second method consists in changing the BSM used along the generations. For each generation, a single BSM is used, but at a given generation period p g , the BSM is changed and chosen out of a set of M BSM.

BD switch (x) = 1 N y∈P d k (x, y) (2)
where k the index of the BSM to be used at the current generation, k ∈ [0, M -1]. Every p g generation, a new value of k is chosen out of a uniform distribution over [0, M -1]:

k = rand(M ) (3)
A typical experiment consists then in maximizing the following objectives: An alternative to this approach may be to simultaneously use several behavioral diversity objectives, each of them relying a different BSM. Although it may in theory lead to the similar results, the performance in practice of multiobjective EA quickly decreases when the number of objectives grows [START_REF] Teytaud | On the hardness of offline multi-objective optimization[END_REF]. The design of the proposed multi-dist behavioral diversity objectives takes it into account. Furthermore, using several diversity helper objectives would reduce the selection pressure exerted by F (.).

Maximize F (x) BD mean (x) or BD switch (x) (4)
In both experiments, NSGA-II [START_REF] Deb | A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi-Objective Optimization: NSGA-II[END_REF], a state-of-the-art multiobjective evolutionary algorithm, has been used with a population size of 200. When only one objective is optimized, NSGA-II is a classic elitist evolutionary algorithm with a tournamentbased selection. The best-of-run individual is the individual with the best F (.) value 2 . The source code of both experiments is available at http://pages.isir.upmc.fr/evorob db.

IV. BALL COLLECTING TASK

A. Experimental setup

The goal of this task is to collect balls in an arena and put them into a basket (figure 2). The task has been first described in [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF]. The arena contains four balls and a switch button that allows the robot to open the door of a room containing four more balls. The robot has two wheels and twelve sensors: three wall distance sensors, two bumpers, two ball detection sensors, two switch sensors, two basket detection sensors and one "carrying ball" sensor. It has three effectors: left and right motors as well as an "action" effector. A nearby ball is 2 the behavioral diversity is used as an helper objective during an optimization. It can be discarded once the results have been generated.

collected or the switch is activated if the value of the "action" effector value is above 0.5. If it is below 0.5, a carried ball is released. A released ball disappears from the arena. If, at that time, the robot was in front of the basket and touching it, then the ball is considered to be collected.

The fitness function is the number of collected balls divided by the maximum number of balls available. The performance is evaluated in three different contexts (with different starting positions, as shown on figure 2). The maximum number of balls is then 24 and a fitness of 0.5 corresponds to 12 collected balls.

Four different BSM have been considered:

• adhoc [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF]: the behavior of a robot is described by the final position of the balls, i.e. the initial position of balls that have not been moved and the last position of the robot if it was still carrying the ball at the end of the run or else the position of the robot when it has released the ball. The behavior descriptor is the vector of ball positions and the BSM is the Euclidian distance between these vectors;

• hamming [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]: the value of each sensor and effector is discretized and memorized during 4000 time steps. It results in a binary vector of 60000 bits (4000 × (12 sensors + 3 effectors)). The BSM is then the Hamming distance that measures the number of bits that differ between the two vectors;

• trajectory [START_REF] Ollion | Why and How to Measure Exploration in Behavioral Space[END_REF]: the discretized position of the robot is recorded each 50 time-steps. This vector is the behavior descriptor. The BSM is then the edit distance between the two vectors [START_REF] Trujillo | Discovering several robot beaviors through speciation[END_REF];

• entropy: the entropy is computed for each sensor and effector. For binary sensors, i.e. bumpers, balls, basket and switch sensors, the entropy has been computed as follows:

E = - i=0,1 p i ln(p i ) ln (2)
with p i the probability that the corresponding sensor takes the value i during the evaluation. For sensors and effectors with a continuous value, the range of possible values has been divided in ten different subranges and the entropy has been computed as follows:

E = - 10 i=1 p i ln(p i ) ln( 10
)
with p i the probability that the sensor or effector value belongs to the i-th subrange. The behavior descriptor is then the vector of the entropies of each sensors and effectors. The corresponding BSM is an Euclidean distance between those vectors;

The robot is controlled by a neural network with twelve inputs and three outputs. Both structure and parameters of the neural network are evolved with DNN [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. DNN (Dynamic Neural Network) is a simple direct encoding with no crossover. Mutations can add or remove neurons and connections and change connection weights. As in NEAT (NeuroEvolution of Augmenting Topologies) [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF], DNN starts with a perceptron with no hidden layer. DNN parameters used for these experiments are listed in the appendix.

B. Experiments and results

a) Main results: Figure 3 shows the number of collected balls for each of the 30 runs and for the treatments without diversity (no div), with a single BSM (adhoc) and with the proposed multi-dist behavioral diversity objectives that use all of the four BSM previously defined. Both the BD mean and BD switch outperform the runs without diversity and also the runs relying on a single BSM 3 (p-value< 1e -4 in the worst case for BD switch , p-value< 0.022 in the worst case for BD mean ). Furthermore, the runs using BD switch outperform BD mean . This is particularly interesting as computing a behavioral distance is expensive, in particular for certain BSM, like hamming distance, for instance. BD switch is then more interesting than BD mean both in terms of efficiency and required computational power. Further results aim at more deeply exploring the efficiency of each BSM, the influence of p g parameter and the influence of number of available BSM. b) Control: single BSM: Treatments using a single BSM were considered as control experiments. Two other treatments were added: one without diversity (one single objective to optimize: the number of collected balls) and another one with a BSM that returns a random value. Results are plotted on figure 4. Median fitnesses range between 0.125 and 0.375 (medians of the control experiments are 0). The low fitness of the experiments using hamming distance seems contradictory with the results reported in [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. In this paper, the setup was the "simple" collectball, i.e. the collectball without the switch and the other room. As new sensors have been added in the 3 adhoc BSM is one of the most efficient BSM on this task, see figure 4. *** Fig. 5. Influence of the switching period between BSM. Experiments with 4 BSM (adhoc, hamming, trajectory, entropy). Medians of 30 runs after 4000 generations. The medians of the control runs have been reported on the plot to ease comparisons. Only statistical difference between pg = 2000 and the other treatments are shown.

setup used here, the dimensionality of the binary vector used to compute hamming distances has increased. To explain these bad results of hamming BSM, we hypothesize that either the vector size has grown too much or that some features of the added sensor values decrease the efficiency of this measure. These results highlight that, even a BSM that revealed to be efficient on some problems may well not be that efficient on new problems, even if they are very similar. This highlights the difficulty of choosing the right BSM and confirms the potential of an approach that do not need to choose a single BSM. c) Random choice between 4 BSM: influence of the switching period p g : In these experiments, the BD switch objective is used. Every p g generations, one of the four BSM previously introduced is randomly selected (adhoc, hamming, trajectory and entropy) and used for the next p g generations. Treatments with p g ∈ {1, 10, 20, 50, 100} give better results Fig. 6. Experiments with a switch between two BSM: influence of the available BSM. pg = 50. Medians of 30 runs after 4000 generations. The medians of the control runs have been reported on the plot to ease comparisons. Statistical significances have not been reported for clarity reasons.

than any of the single BSM treatments (statistically significant, Mann-Whitney U test, p -value < 0.01) 4 . The median of all sets of experiments except for p g = 1000 and p g = 2000 equal 0.5. The results of treatments with p g ∈ {1, 10, 20, 50, 100} are not statistically different between each other (Mann-Whitney U test, p -value > 0.05) and they are all different from those with p g ∈ {1000, 2000}. Treatments with p g ∈ {20, 50} give statistically different results from the treatment with p g = 500.

As the runs last for 4000 generations, it is not surprising that above a period of 500, the effect of BSM switching starts to decrease as at p g = 500, there are only 8 BSM switches during a run. For p g = 2000, there is only one switch. This treatment gives then, not surprisingly, performances that are close to the control experiments with a single BSM. Figure 5 highlights then that as long as enough switches are done during the run, p g has a weak influence. This parameter is then not critical. d) Random choice between 2 BSM: influence of the set of available BSM: Figure 6 shows the results of treatments with a switch between two different BSM at a period of 50 generations. All treatments are significantly different from treatments with a single BSM, except the hamming-trajectory whose difference is not statistically significant with the adhoc treatment and the hamming-entropy with the adhoc and the trajectory treatments. It means in particular that any pair of BSM gives better results than each of these BSM considered separately. Even with only two BSM then, a significant increase in performance is observed. Although the median is the same for all runs, some results are statistically different. The adhoc-entropy run, for instance, is statistically different from all other treatments (p -value < 0.05), except adhochamming. e) 2 BSM vs 4 BSM: All treatments with 2 BSM and 4 BSM with p g ∈ {1, 10, 20, 50, 100} have the same median at 0.5. The results of treatments with adhoc-hamming and adhoc-entropy are not statistically different from any of the treatments with 4 BSM and p g ∈ {1, 10, 20, 50, 100}. The Fig. 7. Fitness along the 300 first generations for all the 30 runs of the treatments with pg = 50. Vertical dotted lines represent the generations in which a switch occurred. results of adhoc-trajectory are statistically below those of the treatment with 4 BSM and p g = 50 (p -value < 0.02). The results of the trajectory-entropy treatment are statistically below those of the treatments with 4 BSM and p g ∈ {20, 50} (resp. p -value < 0.05 and p -value < 0.006). Finally, the treatments with hamming-trajectory and hamming-entropy are statistically below any of the treatments with 4 BSM and p g ∈ {1, 10, 20, 50, 100} (p -value < 0.031 in the worst case). To sum up this part, the difference between treatments with 2 BSM and treatments with 4 BSM is low, but significant for several treatments and in every case in favor of 4 BSM treatments.

f) Correlation between behavioral diversity switch and fitness increase: Figure 7 shows the fitness of the 30 runs with p g = 50. There is no clear and immediate effect on the fitness of the behavioral diversity switch. This is not surprising as this switch has an impact only on the exploration ability. A better exploration ability do not immediately result in best results as exploration may take time before interesting solutions are discovered.

g) Example of result: Individuals able to collect up to 23 balls out of a maximum of 24 have been generated (figure 8). Surprisingly, some of the most efficient neural networks do not contain any recurrent connection and only one hidden neuron (figure 9). The network topology only needs three structural mutations to be found, but probably requires an accurate tuning that makes it difficult to discover without specific exploration fostering mechanisms.

V. LOCOMOTION TASK

A. Experimental setup

The control of legged robots combines the challenge raised by the use of many redundant degrees of freedom with the need to tame dynamic behaviors. This difficult problem in robotics has a long history in evolutionary computation because it is often seen as an interesting benchmark to evolve controllers that could be useful in robotics [START_REF] Kodjabachian | Evolution and development of neural networks controlling locomotion, gradient-following, and obstacleavoidance in artificial insects[END_REF], [START_REF] Meyer | Evolutionary approaches to neural control of rolling, walking, swimming and flying animats or robots[END_REF], [START_REF] Clune | The Sensitivity of HyperNEAT to Different Geometric Representations of a Problem[END_REF], [START_REF] Valsalam | Evolving Symmetry for Modular System Design[END_REF], [START_REF] Koos | The Transferability Approach : Crossing the Reality Gap in Evolutionary Robotics[END_REF]. This continuing interest is also rooted in the observation that locomotion is one of the most fundamental ability of animals.

Here we use this task to assess the advantages of using several BSM by testing it in a setup very different from ball collecting.

A hexapod robot is simulated in a dynamic simulator5 (figure 10) and its 18 degrees of freedom must be synchronized to move as fast as possible. The angular position of each degree of freedom i is governed by the periodic function

Fig. 1 .

 1 Fig. 1.Main proposition. Encouraging behavioral diversity drastically improves the convergence of evolutionary robotics experiments[START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF], but it requires defining a Behavior Similarity Measure (BSM). Using many BSM avoids the need to choose and leads to similar or better convergence rates.

Fig. 2 .

 2 Fig.2. Overview of the arena and of the robot. The goal of the experiment is to place as many balls as possible into the basket. A robot controller is evaluated three times at three different initial positions. To reach the four balls in the left room, the robot has to open the door by first pressing the switch button.

Fig. 3 .

 3 Fig. 3. Number of collected balls for 30 runs after 4000 generations and for the treatments without the diversity objective (no div), with the most performing single BSM diversity objective (adhoc) and with the proposed BDmean and BD switch (pg = 50 generations). The statistical significance is represented with the horizontal lines: '****' means p -value < 10 -4 , '***' means p -value < 10 -3 , '**' p -value < 10 -2 and last '*' p -value < 0.05. No horizontal line between two treatments means no statistical difference in the results. The boxes extend from the lower to upper quartile values of the data, with a line at the median. The whiskers show the range of the data.

Fig. 4 .

 4 Fig. 4. Control experiments using a single BSM during evolution on the ball collecting task. Medians of 30 runs after 4000 generations.

Fig. 9 .

 9 Fig. 9. Neural network generating the behavior shown on figure 8 for the ball collecting task.

Fig. 8 .

 8 Fig. 8. Example of trajectory for an individual collecting 23 balls. Only the trajectory of the first evaluation is shown. Lines with circles show part of the trajectory where the robot carries a ball.

Fig. 10 .

 10 Fig. 10. Overview of the hexapod robot used in these experiments. 15 degrees of freedom must be controlled.

Each behavioral diversity is normalized by its maximum value in the current population.

Treatments with pg ∈ {500, 1000} are also significantly better than single BSM treatments, except for adhoc BSM.

http://www.ode.org

ϑ i (t) [START_REF] Cully | Behavioral Repertoire Learning in Robotics[END_REF]:

F is fixed and it is common to all degrees of freedom; c j and A j are shared by all joints of the same class (there are three classes of joints, each leg being moved by one joint of each class: knee, up-down hip and forward-backward hip); p i is different for each degree of freedom. The total number of parameters for this controller is therefore 3 × 18 + 3 + 3 = 60.

To make the discovery of regular behaviors easy, only 5 values are possible for each parameter. They are uniformly spread over the range of movement of each degree of freedom

The fitness is the distance covered in 25 simulated seconds (time-step is 0.01 seconds). h) Behavior similarity measures and distances: The choice of the best BSM to improve diversity when evolving gait controllers is an open problem. Here we investigate four different BSM:

• Contact. Walking gaits have been historically described by entomologists using parallel diagrams in which each horizontal line corresponds to a leg (e.g. [START_REF] Delcomyn | The Locomotion of the Cockroach Pariplaneta americana[END_REF]). For each time step, a black dash is drawn when the leg is in contact with the ground, otherwise nothing is drawn (see e.g. figure 12). For instance, such diagrams make easy to distinguish a tripod gait from a tetrapod gait. Taking inspiration from this description, the gait of an hexapod robot can be described by a matrix C, in which each row corresponds to a timestep:

Behaviors are compared by computing the number of differences between their matrix C.

• End point. When evolving a biped gait with the novelty search algorithm -which also relies on a BSM -, Lehman and Stanley [START_REF] Lehman | Abandoning objectives: evolution through the search for novelty alone[END_REF] proposed to describe each behavior by the position of the center of mass at the end of the experiment. Behaviors are compared by computing the Euclidean distance between end points. • State. At each time step, the position of each degree of freedom describes the current state of the robot.

The behavior of the robot can therefore be described by the list of angular positions for each time step. Behaviors are then compared by computing the average Euclidean distance between vector states at each time-step.

• Trajectory. The behavior of the robot can also be described by the 3D trajectory of its center of mass. In this case, behaviors are compared by computing the average Euclidean distance between 3D positions at each time step.

We consider the following treatments:

• fitness only (no diversity, control experiment). Diversity is not encouraged at all; the EA is therefore a standard single-objective (rank-based) EA.

• fitness + a single BSM behavioral diversity objective;

• fitness + BD mean ;

• fitness + BD switch (p g = 50 generations).

We launched 60 runs of 2000 generations and we encouraged diversity using the same multi-objective approach as the one used in the previous section. The size of the population was 200. The 60 parameters have been mutated using a shift to the left value or to the right value (only 5 values are possible for each evolved parameter); cross-over was not used. For each time-step, the presence of a black dot denotes that the leg is in contact with the ground. This gait is mostly stable because three legs are always in contact.

B. Results

Figure 11 shows the median distance achieved with each of the treatment. Surprisingly, using a single BSM does not seem to improve performance much and only the "contact" BSM leads to results statistically different from the control experiment (no diversity). At first sight, this result appears to contradict recent results about behavioral diversity [START_REF] Gomez | Sustaining diversity using behavioral information distance[END_REF], [START_REF] Mouret | Using Behavioral Exploration Objectives to Solve Deceptive Problems in Neuro-evolution[END_REF], [START_REF] Mouret | Overcoming the bootstrap problem in evolutionary robotics using behavioral diversity[END_REF], [START_REF] Mouret | Encouraging Behavioral Diversity in Evolutionary Robotics: An Empirical Study[END_REF]. However, the analysis of the controllers obtained with the control runs (no diversity) shows that they actually perform well, hence showing that this walking task is easy enough to not require any diversity preservation mechanism to obtain good controllers (the controller is designed so that many different gaits are possible but many of them are working).

There is nonetheless room for improvement: the "switch" the "mean" variants obtained better results than any of the other approach, with statistically significant p-values (p < 0.025 in the worst case). This result confirms that using several BSMs removes the need to choose between BSMs and improves the performance. Figure 12 describes the best gait obtained with the "switch" variant.

VI. CONCLUSION AND PERSPECTIVE

The obtained results can be summarized as follows:

• using several BSM in a single run increases the performance while releasing the constraint to choose the most appropriate BSM;

• switching between BSM is more efficient than taking the mean behavioral diversity while requiring less computational power;

• the difference is significant with two BSM only, but different BSM pairs may yield different results;

• treatments with four BSM slightly outperform those with two BSM;

• the period of the switch is a non critical parameter, as long as enough switches are performed during a run (more than eight).

The results validate the hypotheses we made, at least on the considered setups: using several BSM during a run actually do not decrease performance. It gives more chance to avoid local optima and converge towards more efficient solutions. It also validates the hypothesis that a single BSM may not reward every potentially interesting original behavior.

The results suggest to use as many BSM as available, at least up to four. Although it may seem to be a limitation of this approach, as more BSM are required, in practice, defining different BSM is not a difficult problem, whereas choosing one out of these is very difficult. Switching between BSM simplifies then the preparation of an experiment, does not significantly increase the computational load and introduces no critical parameter.

The mean BSM approach could easily be extended to novelty search, but the BSM switch approach would need some adaptations in the archive management process as randomly changing the BSM during the run will impact the choice of individuals to include in it.

VII. ACKNOWLEDGMENTS

This work is supported by the ANR CreAdapt project (ANR-12-JS03-0009).


Miguel Alexandre

Campos Oliveira

Stephane Doncieux

Jean-Baptiste Mouret

Cristina Peixoto Santos

Optimization of Humanoid Walking Controller: Crossing the Reality Gap

Humanoid locomotion remains a challenge because of the inherent instability of such robotic platforms. Inspired from observations on animals, Central Pattern Generators have been proposed to support the generation of rhythmic patterns able to make a robot smoothly walk while requiring few computational power. Nevertheless, tuning such controllers is challenging, in particular because small irregularities in the walking pattern easily make the robot fall. Optimization algorithms can be used to tune them in simulation, but the transfer of such solutions to the real robot raises the reality gap problem, as a solution efficient in simulation may well be inefficient in reality. It is proposed here to use the transferability approach to solve this problem. Its principle is to learn a model of the transferability between simulation and reality while doing several evaluations on the real robot. This model is then used to estimate how well a controller will transfer onto the real robot and the optimization process tries to optimize it besides other cost functions related to locomotion and tested in simulation only. The approach has been applied to the DARWIN-OP robot.

I. INTRODUCTION

Humanoid robots are highly unstable robotics platforms. Making a humanoid robot move around in a robust fashion still remains a challenge. Approaches like ZMP (Zero Moment Point) [START_REF] Vukobratović | Zero-moment point-thirty five years of its life[END_REF], [START_REF] Nishiwaki | Simultaneous planning of com and zmp based on the preview control method for online walking control[END_REF] have proved their efficiency in a well controlled environment. Such approaches require a high computational load as they require complex geometrical computations to be performed at each time step. Likewise, they require to know beforehand where the feet should be placed. Although it may be appropriate in some situations, it would be interesting to design controllers that require less computational power and that are also more robust. Drawing inspiration from how animals do indeed walk, approaches based on Central Pattern Generators adopt a completely different point of view [START_REF] Ijspeert | special issue: Central pattern generators for locomotion control in animals and robots: A review[END_REF]. Instead of computing exactly the position of each part of the robot, they consist in synchronized dynamical systems linked to leg motors and that make them move in a rhythmic fashion. Using CPG *This work is funded by FEDER Funding supported by the Operational Program Competitive Factors -COMPETE and National Funding supported by the FCT -Portuguese Science Foundation through project PTDC/ EEACRO/100655/2008. Miguel Oliveira is supported by grant CRO-BI-2012 1,4 Miguel Oliveira and Cristina P. Santos are with Industrial Electronics Department, School of Engineering, University of Minho, 4800-058 Guimaraes, Portugal mcampos@dei.uminho.pt, cristina@dei.uminho.pt 2,3 Stephane Doncieux and Jean-Baptiste Mouret are with ISIR, Université Pierre et Marie Curie-Paris 6, CNRS UMR 7222 4 place Jussieu, F-75252, Paris Cedex 05, France doncieux@isir.upmc.fr, mouret@isir.upmc.fr for walking results then in a smoother walking pattern and also requires much less computational power as all is needed is to update the dynamics of the CPG, what is by far less demanding than other geometrical based approaches.

CPG based controllers have been used in different kind of legged robots, even quadruped [START_REF] Righetti | Pattern generators with sensory feedback for the control of quadruped locomotion[END_REF], [START_REF] Maufroy | Integration of posture and rhythmic motion controls in quadrupedal dynamic walking using phase modulations based on leg loading/unloading[END_REF] and biped robots. Most typical approaches when implementing CPGs for bipedal walking use phase oscillators that are fed into pattern generation layers [START_REF] Morimoto | Modulation of simple sinusoidal patterns by a coupled oscillator model for biped walking[END_REF], [START_REF] Aoi | Evaluating functional roles of phase resetting in generation of adaptive human bipedal walking with a physiologically based model of the spinal pattern generator[END_REF], [START_REF] Aoi | Generation of bipedal walking through interactions among the robot dynamics, the oscillator dynamics, and the environment: Stability characteristics of a five-link planar biped robot[END_REF], [START_REF] Oliveira | Multi-objective parameter cpg optimization for gait generation of a biped robot[END_REF] or using neural oscillators [START_REF] Miyakoshi | Three dimensional bipedal stepping motion using neural oscillators-towards humanoid motion in the real world[END_REF].

One of the main difficulties while using CPGs, consists in finding out how to tune them to exhibit a particular motion pattern. This is particularly critical when designing walking controllers for humanoid controllers as they can easily fall. Optimization tools are particularly interesting in this context to automatically find the most appropriate set of parameters and thus avoid a tedious manual tuning. Anyway, they raise a difficult problem: as the system to optimize is highly nonlinear, appropriate methods mostly rely on metaheuristics, e.g. evolutionary algorithms, and thus require a large amount of tests. Such an approach is difficult to apply directly to the real robot, because it would require a huge amount of time and the robot could be damaged during the process, may it be because of the large number of tests or because some of them may put a great strain on the mechanics.

In this work, it is proposed to rely on a simulation to avoid such problems. In this case, there is a risk of over-fitting to features that are specific to the simulation, thus leading to a reality gap, i.e. to a situation in which a controller works well in simulation, while being completely inefficient on the real robot. To avoid this problem, the transferability approach has been used [START_REF] Mouret | Crossing the reality gap: a short introduction to the transferability approach[END_REF], [START_REF] Koos | The transferability approach: Crossing the reality gap in evolutionary robotics[END_REF]. This approach consists in performing some experiments on the real robot in order to learn a model of the transferability of controllers between simulation and reality. This model is then used in the optimization process in order to favor controllers that do transfer well. The approach is tested on a DARWIN-OP robot.

II. RELATED WORK

A. Humanoid walking with a CPG Typical solutions to the problem of biped locomotion make extensive use of the knowledge of the robot and of its environment. Most of them are model-based solutions and employ inverse kinematics and kinetics in order to generate feet placement sequences, according to determined constraints established through some stability criterion, as the popular Zero-Moment Point (ZMP) [START_REF] Vukobratović | Zero-moment point-thirty five years of its life[END_REF], [START_REF] Nishiwaki | Simultaneous planning of com and zmp based on the preview control method for online walking control[END_REF].

Bio-inspired approaches appear as possible alternatives to humanoid locomotion generation with quite successful results and less requirements. One such approach is based on the concept of Central Pattern Generators (CPGs), and exploits the characteristics of intraspinal neural networks in vertebrates [START_REF] Ijspeert | special issue: Central pattern generators for locomotion control in animals and robots: A review[END_REF]. These generate rhythmic activations for walking motor patterns.

There are several key points which make CPGs good candidates for legged robot control and can potentially generalize their ability in dynamic environments. These include (see [START_REF] Ijspeert | special issue: Central pattern generators for locomotion control in animals and robots: A review[END_REF] for a review): 1) CPGs produce stable rhythmic patterns with respect to their limit cycle behavior, returning to the normal stable state after transient perturbations. 2) They typically have a small number of control parameters, reducing the dimensionality of the control problem on higher level control. 3) Small changes in control parameters, even if abrupt, result in smooth modulations for the produced trajectories. 4) CPGs are well suited to integration of sensory feedback pathways [START_REF] Kim | Robust control of cpgbased 3d neuromusculoskeletal walking model[END_REF], [START_REF] Aoi | Evaluating functional roles of phase resetting in generation of adaptive human bipedal walking with a physiologically based model of the spinal pattern generator[END_REF]. This provides the ability for the robots to tackle unexpected disturbances and thus make them able to work in dynamic and not completely known environments.

In [START_REF] Ha | Gait pattern generation and stabilization for humanoid robot based on coupled oscillators[END_REF], the authors proposed a CPG-based locomotion controller for Darwin-OP robot capable of achieving a velocity of ≈ 10cm/s in simulation. In [START_REF] Oliveira | Multi-objective parameter cpg optimization for gait generation of a biped robot[END_REF], it is also proposed a locomotion controller based in CPGs. They achieved a 8cm/s velocity from a hand tuned CPG parameterization in simulation, and were able to optimize the robot velocity to 10(cm/s) using the multi objective NSGA-II algorithm.

However, the lack of a defined framework promoted the development of several CPG approaches [START_REF] Aoi | Adaptive behavior in turning of an oscillatordriven biped robot[END_REF], [START_REF] Righetti | Programmable central pattern generators: an application to biped locomotion control[END_REF], [START_REF] Morimoto | A biologically inspired biped locomotion strategy for humanoid robots: Modulation of sinusoidal patterns by a coupled oscillator model[END_REF], [START_REF] Nakanishi | Learning from demonstration and adaptation of biped locomotion[END_REF], [START_REF] Chung | Neurobiologically Inspired Control of Engineered Flapping Flight[END_REF], [START_REF] Seo | Cpg-based control of a turtlelike underwater vehicle[END_REF], [START_REF] Matos | Omnidirectional locomotion in a quadruped robot: A cpg-based approach[END_REF]. Furthermore, many of these approaches rely on hand tuned ad-hoc solutions. Typically, the large number of parameters needed for robot locomotion and the lack of knowledge about the dynamical behavior between the robot and environment makes hand-tuning a difficult task for locomotion beyond simple flat terrain walking and navigation [START_REF] Lee | Multi-objective walking trajectories generation for a biped robot[END_REF].

B. Crossing the reality gap

Many authors note that solutions optimized in simulation often do not work well once tested on the real robot [START_REF] Jakobi | Evolutionary robotics and the radical envelope-of-noise hypothesis[END_REF], [START_REF] Zagal | Combining simulation and reality in evolutionary robotics[END_REF], [START_REF] Mouret | Crossing the reality gap: a short introduction to the transferability approach[END_REF], [START_REF] Koos | Fast damage recovery in robotics with the t-resilience algorithm[END_REF]. This issue, termed the "the reality gap" [START_REF] Jakobi | Evolutionary robotics and the radical envelope-of-noise hypothesis[END_REF], is critical to enable the adoption of optimization algorithms in engineering: optimizing directly on the real device is too slow to be practical, but optimizing in simulation has a high probability of leading to useless solutions.

The most intuitive idea to cross this gap is to put the blame on simulators and to improve their accuracy. Several authors proposed to automatically optimize it, for instance by learning a surrogate model of the objective function [START_REF] Jin | A comprehensive survey of fitness approximation in evolutionary computation[END_REF], or to automatically improve an existing simulator [START_REF] Bongard | Resilient Machines Through Continuous Self-Modeling[END_REF], [START_REF] Zagal | Combining simulation and reality in evolutionary robotics[END_REF] with tests in reality. Nevertheless, automatically optimizing a simulator that is general enough to be used to optimize solutions is at least as challenging as creating good optimization algorithms for robotics. Moreover, more accurate simulators often means slower running times, which may cancel out the benefits of simulation.

In a radical proposition, Jakobi proposed to make simulator less accurate by hiding badly modeled phenomena in in an "envelope of noise". Despite some success with the evolution of a controller for an hexapod robot [START_REF] Jakobi | Evolutionary robotics and the radical envelope-of-noise hypothesis[END_REF], Jakobi did not precisely describe how to choose what has to be noised and how this noise should be applied. For instance, it is hard to know how to add noise when optimizing locomotion controllers for humanoid robots.

The transferability approach is a recent alternative to cross the reality gap. It led to promising results when optimizing controllers for a wheeled robot [START_REF] Koos | The transferability approach: Crossing the reality gap in evolutionary robotics[END_REF], a quadruped [START_REF] Koos | The transferability approach: Crossing the reality gap in evolutionary robotics[END_REF], [START_REF] Mouret | Crossing the reality gap: a short introduction to the transferability approach[END_REF] and a hexapod [START_REF] Koos | Fast damage recovery in robotics with the t-resilience algorithm[END_REF]. This approach relies on the observation that simulators make mistakes but they are also often right. For instance, the rigid body simulator ODE have a very simple model of viscous joint damping, but systems with low viscous damping coefficients are accurately simulated [START_REF] Drumwright | Extending open dynamics engine for robotics simulation[END_REF]. The goal of the transferability approach is to make the optimization algorithm aware of such limits of the simulation thanks to an automated process. To this end, a few controllers are transferred during the optimization and a regression algorithm (e.g. a SVM or a neural network) is used to approximate the function that maps behaviors in simulation to the difference of performance between simulation and reality. To use this approximated transferability function, the single-objective optimization problem is transformed into a multi-objective optimization in which both performance in simulation and transferability are maximized.

III. METHOD

A. Fitness Specification

Based on the literature [START_REF] Lee | Multi-objective walking trajectories generation for a biped robot[END_REF] and on our expertise in dynamical systems, the following objectives are used to evaluate the walking gait performance:

• COP edge distance, f COP : the average distance of the COP to the edge of the foot support polygon, D COP , when the foot is in stance phase is to be maximized. • Force, f F : a good gait should keep the feet parallel to the floor; have a minimum impact force between the feet and the floor when the stance starts, and have the measured force of the four built-in force sensors in each foot, uniformly distributed. • Displacement, f D : a gait is considered better if it achieves higher frontal displacements. • Ground Clearance, f GC : the robot should raise its feet while walking. In order to calculate the highest distance from the ground of a swing foot, we take the maximum distance to the ground of the lowest sensor of a swing foot. • Transferability, f T : as defined in section III-B. Limb trajectories are shaped by varying the CPG parameters. In order to achieve biped locomotion for a biped robot that is stopped and has to start walking, we have considered a 3 staged evolution. Each stage is performed during a certain amount of time and different motions are sequentially

B. Transferability for a humanoid robot

Each candidate solution i is described by a vector of 5 values S i = {f Dsi , f Fsi , x si , y si , φ si }, where f Dsi corresponds to the displacement, f Fsi to the force sensor value, x si to the forward displacement, y si to the lateral displacement and φ si to robot's pitch, φ s . If a candidate solution is tested on the real robot, the same values can be computed on the real robot, leading to an evaluation of the transferability (the "size" of the reality gap):

g i = |S i -R i |
, where R i corresponds to S i but measured on the real robot.

The set of couples (S j , g j ), where j is a transferred controller, make a database that is used to train a Support Vector Machine (SVM). Once trained, this predictor can predict g i for each value of S j . 1) Initialization a) The initial population, of size n p , is generated out of a hand tuned solution which is known to be able to walk on the real robot [START_REF] Oliveira | Multi-objective parameter cpg optimization for gait generation of a biped robot[END_REF]. b) All individuals p i ∈ P, i = {1, . . . , n p } are executed in simulation, yielding S i . c) n s individuals are chosen from population P .

C. Optimization Loop

First we choose the best individual (with higher fitness functions), then, we incrementally select the most different w.r.t. those already chosen. By choosing the most different, we are increasing the diversity of the elements stored in the Database and then used to train the transferability function.

The difference is computed according to:

d i = ns j=1 |S i -S j |, that
, is, we incrementally select the individuals with higher d i . Where i indicates those from the population, i ∈ {1, . . . , n p }, that are being compared with j already chosen, j ∈ {1, . . . , n s }. d) Each of these selected individuals, p i ∈ P, i = {1, . . . , n s }, is executed in reality, yielding R i = {f Dri , f Fri , x ri , y ri , φ ri }. e) Compute the reality gap g i for each individual p i , between the performance in simulation and in reality:

g i = |S i -R i |. f) For each individual p i , a Database entry, D i = {p i , S i , R i , g i }, is
g i = |S i -R i |.
6) Update Database a) Create a new entry D i for each of the new k executed individuals: , where i = {1, . . . , n e } Best simulation solutions are often not transferable to reality because they typically exploit every details of the simulation, whereas differences between simulation and reality lies in these details. To be able to deal with possible conflicting solutions and search for relevant trade-off solutions, we apply a multi-objective approach,that considers several task-dependent objectives and a transferability objective.

D i = {p i , S i , R i , g i }. b) m ← m + k. c) If

D. CPG based control architecture

The locomotion controller used in this work relies on a Central Pattern Generator (CPG) capable of generating bipedal locomotor behaviors, such as walking forward/backwards and turning, as described in [START_REF] Matos | Central pattern generators with phase regulation for the control of humanoid locomotion[END_REF]. The system could easily integrate local sensory feedback. The proposed CPG controls a single leg, divided in rhythmic and unit motion pattern generators.

The use of a phase oscillator as a rhythmic generator allowed for a simple contralateral coupling between the left and right CPGs, maintaining the correct coordination between the generated locomotor trajectories in both legs by producing each a driving rhythmic signal φ i in strict alternation (i for left/right leg). Motion pattern generators receive this rhythmic input and produce the corresponding joint trajectory, z, in a synergistic approach of modular motion primitives encoded as a set of non-linear dynamical equations with well defined attractor dynamics, similarly to other works [START_REF] Nakanishi | Learning from demonstration and adaptation of biped locomotion[END_REF]. Basic parameterized motion primitives, e.g. sine and bell-shaped motions (implemented as Gaussians), were considered.

The joint angle value z i,j , for leg i and joint j, is:

żi,j = -α (zi,j -Oi,j) + f m j zi,j, φi, φi . (1)
The final motor program in a single joint results from the sum of rhythmic motion primitives f m j around a center point O i,j . α is a relaxation parameter for the offset. j specifies the joint: hip roll (hRoll), hip yaw (hYaw), hip pitch (hPitch), knee (kPitch), ankle roll (aRoll) and ankle pitch (aPitch); and i specifies the left or right leg.

The balancing motion is controlled as follows:

f balancing hRoll = -A balancing ω sin (φi) (2)
f balancing aRoll = -f balancing hRoll (3)
i specifies the left or right leg, φ i is the phase of left or right CPG, and parameter A balancing specifies the amplitude of the lateral displacement motion. Leg flexion motion is performed by the unloaded leg.This is shown in eq. ( 4) for hip, eq. ( 5) for knee, and eq. ( 6) for ankle.

f flex hPitch = A hip ωφi σ 2 exp - φ 2 i 2σ 2 (4)
f flex kPitch = - A knee ωφi σ 2 exp - φ 2 i 2σ 2
(5)

f flex aPitch = -f flex hPitch + f flex kPitch (6)
The amplitude of the bell trajectory is specified by parameter A hip for the hip and A knee for the knee. The pelvic rotation is performed at the hip yaw joints, described by :

f rotation hYaw = -Arotationω sin φi + π 2 (7)
The propulsion of the body during locomotion stems from leg motions in the sagittal plane, alternately moving the contralateral legs forward and backward, like a compass:

f compass hPitch = -Acompassω sin φi + π 2 (8)
f compass aPitch = -f compass hPitch (9)
The overall result of all the motions is straight bipedal walking. Here we summarize all the motions assigned to each joint:

żhRoll = -α(z hRoll -O hRoll ) + f balancing hRoll , ( 10
) żaRoll = -α(z aRoll -O aRoll ) + f balancing aRoll , ( 11
) żhYaw = -α(z hYaw -O hYaw ) + f rotation hYaw (12) żhPitch = -α(z hPitch -O hPitch ) + f flex hPitch + f compass hPitch (13) żkPitch = -α(z kPitch -O kPitch ) + f flex kPitch + f yield kPitch (14) żaPitch = -α(z aPitch -O aPitch ) + f flex aPitch + f compass aPitch (15)
Further details about this approach can be found in [START_REF] Matos | Central pattern generators with phase regulation for the control of humanoid locomotion[END_REF].

A correct tuning of parameters, p, is necessary for achieving bipedal walking in the robot. The upper an lower bounds of each parameter are shown in Table I.

IV. EXPERIMENTAL SETUP A. Implementation on the Darwin-OP

The Darwin-OP is a lightweight humanoid robot with 20 Degrees of Freedom (DOFs) equipped with eight Forcesensing Resistors on the soles of the feet. In this work trajectories were generated for 6 DOFs per leg.

Experiments were carried out on the Darwin-OP robot and on the Webots physics simulator. The robot is expected to move in flat floor straightforward during 20 s. At each sensorial cycle (16 ms), sensory information is acquired. The system is integrated considering the Euler method with 1 ms fixed integration step. At the end of each solution evaluation, the robot is set to its initial position and rotation, so that the initial conditions are equal for the evaluation of all solutions of all populations in real or simulated environment.

To assure that at least one solution has a good performance in the real robot, we introduce a hand-tuned solution in the n s solutions which we a priori know that is able to walk both in simulation and in the real robot. This hand tuned solution was determined after some time in order to produce a solution able to achieve the best displacement both in simulation and in the real robot, while still producing good results from a functional perspective. That is, a locomotion that visually looked stable and smooth without producing large oscillations in pitch or in roll. This hand-tuning required the know-how of someone used to deal both with CPGs biped locomotion.

For the reality gap process we consider, n p = 100, n e = 30, k = 5, n g = 12. The SVM uses the polynomial kernel with a parameter degree of 2. To train the SVM with the first data, we test n s = 20 solutions in the real robot. All of them are chosen from the initial population of the NSGA-II, in such way that the most different are selected.

The ARToolkit [START_REF] Kato | Marker tracking and hmd calibration for a video-based augmented reality conferencing system[END_REF] is used to calculate the displacement of the Darwin robot. A camera is mounted on the ceiling faced downwards. We rely on 1 marker in top of the robot head. We are only interested in frontal and lateral robot displacement. In case the marker position is not acquired or the returned confidence factor is small, the system assumes it did not change.

B. Treatments

The following treatments were considered in the simulator and in the real robot, by considering the following objectives:

• Exp1 -max(f D ), min(f F ) and min(f T ) • Exp2 -max(f D ), min(f F ), max(f GC ) and min(f T ). • Exp3 -max(f D ), max(f GC )
and min(f T ). The Force was set as a constraint. Five experiments have been run for each treatment. Furthermore, each solution has been tested 5 times both in simulation and in the real robot.

A control treatment, SimOnly, was considered in which no experiment was done on the real robot. It was inspired from [START_REF] Oliveira | Multi-objective parameter cpg optimization for gait generation of a biped robot[END_REF] and considered the following objectives: max(f D ), min(f F ) and max(f GC ). 10 experiments were performed and afterwards the transferability (f T ) for the 10 non-dominated sets of solutions were calculated. Among these, the 10 solutions with best transferability were selected and run on the real robot.

V. RESULTS

A. Walking performance achieved

Figure V-A depicts the results of the simulated displacement for the last non-dominated population of each experiment(f Ds ) (blue circles) and the real displacement (f Dr ) of all solutions that were able to walk (red crosses), for each of the treatments. Considering the walking behavior in simulation, the SimOnly and the Exp 3 were able to obtain the solutions with best displacement. However, note that SimOnly was not able to generate a single solution that walks on the real robot. The Exp 1 and Exp 2 treatments obtain almost similar values of displacement in the real robot. It is important to emphasize that 1) controllers able to make the robot move were generated by the proposed approach and 2) without any manual tuning between simulation and reality.

Figure V-A(b) shows the percentage of solutions that were able to make the real robot walk without falling. The Sim Only experiment was unable to find solutions that walk in the real robot. Exp 1 and Exp 2 treatments obtain the highest number of solutions that walk. This number is lower for Exp 3 experiment, though this was able to find solutions with better displacement (see Figure V-A(a)).

Figure 3 depicts, for the real robot tests, the values of CoM lateral and frontal displacement of the hand tuned H solution (red dashed line) and the S i solutions.S i are solutions that achieved the maximum displacements for Expi in simulation while being able to make the real robot walk. These solutions are considered as risky solutions, as the displacement was considered in priority on other functions rewarding the stability. H (red dashed line) has a better frontal displacement than S 1 and S 2 solutions but similar to the S 3 solution. However, the hand tuned solution has a much higher lateral displacement compared to any of these solutions. For instance, the S 3 solution has a very low lateral displacement and a very high frontal one. These values are displayed on Table II. This shows up the obtained improvement in the performance criteria. In the following, the impact of the evolutionary approach on the roll, pitch and force measures made on the real robot is studied. These are assessed through the built-in gyroscope and accelerometer sensors of the robots. In the top panel of figure 4, the mean roll of the solutions is similar (H : -0.009, S 1 : -0.0034, S 2 : 0.0016, S 3 : 0.005) but the roll of the hand tuned solution presents a higher oscillation (H : 0.25, S 1 : 0.22, S 2 : 0.24, S 3 : 0.21). The third panel depicts the values of the 4 left foot sensors of both solutions during the locomotion. In order to simplify the visualization we sum the value of the 4 left foot sensors. We can see that the S 2 solution has a tendency to have force during longer periods of time in the robot left foot, and stance periods increase. This means that the robot rises less times its foot (similar behavior for right foot), but rather drags them. On the other hand, solution S 1 and S 3 are solutions with well identified stance and swing phases.

B. Functional Gait Analysis

In the second panel of Figure 4, the hand tuned solution shows a lower mean pitch (H : -0.068, S 1 : -0.03, S 2 : -0.03, S 3 : -0.039), meaning that the robot slightly tilted forward comparatively to the S solutions, which are more vertical. Furthermore, the pitch oscillation of the S solutions is lower than the one of the hand-tuned solution (H : 0.316, S 1 : 0.22, S 2 : 0.21, S 3 : 0.26). Regarding the pitch, one can see that the S solutions were able to perform a smoother locomotion in despite these are risky solutions which aim was to improve the displacement.

C. Sensitivity Analysis

In this section we are interested in verifying if there is any relationship between the CPG parameters and the obtained reality gap. In order to verify which CPG parameters most influence the gap, we verify the correlation between the gap (g) and the parameters of the solutions that were tested in the real robot and so belong to the database.

The correlation between the parameters and reality gap (g) is assessed by computing the Pearson correlation coefficient (R) as a summary statistic. Table III presents the R coefficients between the parameters and the g, as well as the corresponding p-values (p) for the statistical significance of the association. The statistical significant associations (p < 0.05) and the strongest correlations (R > 0.5) are highlighted. The highest correlation is obtained for O kPitch (R = -0.52). This means that by increasing the O kPitch value (flexing the knee joint) we decrease the value of the g, therefore reducing the reality GAP. Thus, this reality GAP problem seems to be correlated to the posture.

VI. DISCUSSION AND CONCLUSION

The transferability approach allowed a multi-objective optimization algorithm to optimize CPG parameters in simulation while ensuring that a least some of the evolved solutions do indeed work on the real robot.

Despite the use of the transferability objective, significant differences can still be observed between the behavior in simulation and on the real robot. This suggests that the webots simulator used in these experiments could probably be improved to generate a behavior that is closer to that of the real robot. The transferability model, by highlighting what behaviors do transfer and what behaviors don't, could actually be used by the simulation designers to find out which are the less precisely modeled parts of the simulation and then update them. Another perspective of this work would be to better exploit the non dominated set of solutions generated at the end of an experiment in order to choose, depending on the context, the fastest controller, the more stable one or a trade-off between the two. Generating all these solutions in a single optimization run is actually another advantage of multiobjective evolutionary algorithms over a careful hand tuning resulting in a single solution.

Fig. 1 .

 1 Fig. 1. Proposed Reality GAP Algorithm.

Figure 1

 1 Figure 1 presents the algorithm's fluxogram, each step being defined as follows:

  created. This Database is used to maintain a record of all the individuals already executed in reality (and necessarily in simulation). g) Update the Database size, m, to the current number of elements: m ← m + n s .2) Update Transferability functionThe SVM is trained with all the m individuals in the Database and yields an updated transferability Function f T (p). 3) Optimization The NSGA-II loop is executed for n e generations: a) NSGA-II Optimization loop for p i ∈ P, i = {1, . . . , n p }: i) Evaluate individual p i in simulation. ii) Acquire S i . iii) Compute the objective functions. iv) Generate the new population based on NSGA-II algorithm. 4) Selection a) For each individual p i ∈ {1, . . . , n e × n p }, calculate d i = m j=1 |S i -S j |, where j iterates the elements in the Database. b) Select the k individuals with higher d i , so as to maximize the diversity. 5) Execution in Reality a) Execute individuals p i , i ∈ {1, . . . , k} in reality. b) Observe R i . c) Compute the reality gap, g i , for each individual:

Fig. 3 .

 3 Fig. 3. Frontal and Lateral CoM displacements values of the H hand tuned solution (red dashed line), and the best S 1 solution (solid blue line), S 2 solution (dashed green line) and S 3 solution (dotted black line).

Fig. 4 .

 4 Fig. 4. Roll, Pitch and Force values of the H hand tuned solution (red dashed line), and the best S 1 solution (solid blue line), S 2 solution (dashed green line) and S 3 solution (dotted black line).

  the stop criteria is not met -the number of gap iterations, n g , is not reached -return to point 2. 7) Selection of the Initial Population if the number of gap iterations, n g , is not reached, it is necessary to calculate the new population n p for the Simulation NSGA-II loop. The selection of the individuals for the new population respect the following criterions: a) The individuals that were able to perform the walking stage in the real robot are selected. b) The individuals from all n p populations of all n e generations of one n g gap iteration, with the best f t are selected. To guarantee that only individuals with good f t are chosen, we pick the individuals with f t >

	ne
		xi
	i=1 ne , and chose those with the best np
	f t and xi =	f T j np j=1

TABLE I PARAMETER

 I BOUNDS Parameter A balancing A hip A knee σ Arotation A yield Acompass ωsw(rad/s) O hRoll O hPitch O kPitch O aRoll O aPitch

	Lower bound (l)	0.01	0.01 0.01 π/4	0.01	0.01	0.01	1.57	-50	-19	0	-50	-19
	Upper bound (u)	40	80	110 π/4	100	8	80	6.28	40	19	100	40	19

TABLE II H

 II AND S i SOLUTIONS WITH THE BEST DISPLACEMENT FOR EACH EXPERIMENT i.

	Experiment	Pitch mean ± std amplitude mean ± std amplitude Frontal Lateral fD fGC fF fT Roll COM Objective functions
	S1(run3)	-0.03±0.07	0.22	0.003±0.06	0.22	0.29 0.07 0.33 0.006 0.55 0.82
	S2(run2)	-0.03±0.06	0.21	-0.002±0.05	0.24	0.32 0.049 0.23 0.006 0.56 0.85
	S3(run3) -0.039±0.07	0.26	-0.005±0.05	0.21	0.71 0.048 0.6 0.006 0.6 0.97
	H	-0.068 ± 0.08 0.316 -0.009 ± 0.069 0.25	0.65 0.29 0.16 0.006 0.74 0.8005

TABLE III PEARSON

 III CORRELATION COEFFICIENTS (R) AND THE CORRESPONDING P-VALUES (p) FOR THE STATISTICAL SIGNIFICANCE OF THE ASSOCIATION BETWEEN THE PARAMETERS AND THE GAP A balancing A flexhPitch A flexkPitch σ Arotation A yield Acompass ωsw(rad/s) O hRoll O hPitch O kPitch O aRoll O aPitch

	R	0.057	-0.41	-0.24	-0.029	0.027	0.33	-0.05	-0.19	0.069	0.23	-0.52	0.42	-0.41
	P	0.74	0.011	0.15	0.866	0.873	0.048	0.750	0.257	0.687	0.167	0.001	0.01	0.012

Mean value ( blue circle) and max and min (errorbar) of a) the displacement for the S values for the simulation. Mean value (red x) and max and min (errorbar) of the displacement values for S the real robot. b) k solutions percentage that were able to walk.


Jean-Baptiste Mouret
email: mouret@isir.upmc.fr

Sylvain Koos

Stéphane Doncieux

Crossing the Reality Gap: a Short Introduction to the Transferability Approach

In robotics, gradient-free optimization algorithms (e.g. evolutionary algorithms) are often used only in simulation because they require the evaluation of many candidate solutions. Nevertheless, solutions obtained in simulation often do not work well on the real device. The transferability approach aims at crossing this gap between simulation and reality by making the optimization algorithm aware of the limits of the simulation.

In the present paper, we first describe the transferability function, that maps solution descriptors to a score representing how well a simulator matches the reality. We then show that this function can be learned using a regression algorithm and a few experiments with the real devices. Our results are supported by an extensive study of the reality gap for a simple quadruped robot whose control parameters are optimized. In particular, we mapped the whole search space in reality and in simulation to understand the differences between the fitness landscapes.

Introduction

Gradient-free optimization algorithms underlie many machine learning methods, from policy search techniques [START_REF] Whiteson | Evolutionary function approximation for reinforcement learning[END_REF][START_REF] Heidrich-Meisner | Evolution strategies for direct policy search[END_REF] to automatic design approaches [START_REF] Lohn | Evolvable hardware: using evolutionary computation to design and optimize hardware systems[END_REF][START_REF] Lipson | Automatic design and manufacture of robotic lifeforms[END_REF]. They are also one of the tool of choice for researches in embodied intelligence because they make possible to obtain artifacts (e.g. neural networks to control a robot) without having to describe their inner workings [START_REF] Pfeifer | How the Body Shapes the Way we Think[END_REF].

In many of their applications, these algorithms spend most of their running time in evaluating the quality of thousands of potential solutions. This observation encourages many researchers to work with simulations instead of real devices, because simulations are usually cheaper and faster than real experiments. For instance, most published work in evolutionary robotics (ER) -in which researchers typically aim at finding original controllers for robots -is carried with simulated robots [START_REF] Doncieux | Evolutionary Robotics: Exploring New Horizons[END_REF][START_REF] Nelson | Fitness functions in evolutionary robotics: A survey and analysis[END_REF]. At first sight, robots are articulated rigid bodies for which many simulations tools exist; it is therefore tempting to suppose that an efficient result obtained by optimizing in simu-lation will work similarly on the real robot. Unfortunately, no simulator is perfect and optimization algorithms have no reason to avoid exploiting every badly modeled phenomena that increase performance. It is thus often observed that solutions optimized in simulation are inefficient on the real robot. On the contrary, most engineers intuitively know the limit of their simulation tools and avoid relying on what is incorrectly modeled. This difference in performance with a simulation and with the real device has been termed the reality gap. It is of course not restricted to ER since the same issues are encountered with all the other optimization algorithms and with many other experimental setups. However, we will restrict our current discussion to ER because the reality gap is central in this community. The reality gap is indeed arguably one of the main issue that prevent a widespread use of evolutionary algorithms to optimize parameters of robot controllers: evaluating every potential solutions in reality is very costly because it requires complex experimental setups and a lot of time; evaluating potential solutions in simulation is cheaper and faster but it often leads to solutions that cannot be used on the real device. How could we proceed? If we do not reject the use of simulators, the first idea to reduce this gap is to design better simulators. Such an approach can work up to a certain extent but complex simulators are slow (e.g. simulating fluids can be slower than reality) and even the best simulators cannot be infinitely exact. An attractive idea is to automatically design a simulator, for instance by learning a surrogate model of the fitness function [START_REF] Jin | A comprehensive survey of fitness approximation in evolutionary computation[END_REF], or, following a related idea, to automatically improve an existing simulator [START_REF] Bongard | Resilient Machines Through Continuous Self-Modeling[END_REF][START_REF] Zagal | Combining simulation and reality in evolutionary robotics[END_REF]. Nevertheless, creating an algorithm that automatically designs the perfect simulator appears at least as difficult as designing evolutionary algorithms to learn the optimal behaviors of a robot. Moreover, these methods will never accurately model every possible force that can act on a device. For instance, it is hard to expect that an algorithm will automatically discover a good model of fluid dynamics in a classic rigid-body simulator, whatever the improvements of the simulator are. Figure 1: (a) The quadruped robot is based on a Bioloid robotic kit (Robotis). It has 8 degrees of freedom (wheels are not used in this experiment). We track its movement using a 3D motion capture system. (b) The simulation is based on the Bullet dynamic simulator [START_REF] Boeing | Evaluation of real-time physics simulation systems[END_REF].

As an alternative approach, [START_REF] Jakobi | Evolutionary robotics and the radical envelopeof-noise hypothesis[END_REF] proposed to prevent the optimization algorithm to exploit badly modeled phenomena by hiding them in an "envelope of noise". Despite some success with the evolution of a controller for an hexapod robot, Jakobi did not describe any generic method to choose what has to be noised and how this noise should be applied. Applying the "envelope of noise" technique therefore often requires a lot of experiments and fine-tuning of the simulator, which is exactly what researchers try to avoid when designing optimization algorithms. For instance, it is hard to know how to add noise when evolving locomotion controllers for legged robots.

In the present paper, we describe a recently introduced approach to cross the reality gap: the transferability approach [START_REF] Koos | The Transferability Approach: Crossing the Reality Gap in Evolutionary Robotics[END_REF]. Our aim is to give a didactic presentation of the intuitions that guide this method as well as the main results obtained so far. The interested reader can refer to [START_REF] Koos | The Transferability Approach: Crossing the Reality Gap in Evolutionary Robotics[END_REF] for detailed results and discussions.

Experimental Apparatus

Robot and controller We studied the reality gap with an 8-DOFs quadruped robot made from a Bioloid Kit (Fig. 1). Another experiment inspired by Jakobi's T-maze is reported in [START_REF] Koos | The Transferability Approach: Crossing the Reality Gap in Evolutionary Robotics[END_REF].

The angular position of each motor follows a sinusoid. All these sinusoidal controllers depend on the same two real parameters (p 1 , p 2 ) ∈ [0, 1] 2 as follows:

α(i, t) = 5π 12 • dir(i) • p 1 - 5π 12 • p 2 • sin(2πt -φ(i))
where α denotes the desired angular position of the motor i at time-step t. dir(i) is equals to 1 for both motors of the front-right leg and for both motors of the rear-left leg; dir(i) = -1 otherwise (see Fig. 1 for orientation). The phase angle φ(i) is 0 for the upper leg motors of each leg and π/2 for the lower leg motors of each leg. Both motors of one leg consequently have the same control signal with different phases. Angular positions of the actuators are constrained in [-5π 12 , 5π 12 ]. The fitness is the distance covered by the robot in 10 seconds.

Reality gap

We first followed a typical ER approach: we evolved controllers in simulation and then transferred the best solution on the robot. On average (10 runs), the best solution in simulation covered 1294 mm (sd = 55mm) whereas the same controller leads to only 411 mm in reality (sd = 425mm); thus we observe a clear reality gap in this task.

This reality gap mostly stems from classic issues with dynamic simulations of legged robots. In particular, contact models are not accurate enough to finely simulate slippage, therefore any behavior that relies on non-trivial contacts will be different in reality and in simulation. Dynamical gaits (i.e. behaviors for which the robot is often in unstable states) are also harder to accurately simulate than more static gaits because the more unstable a system is, the more sensitive it is to small inaccuracies.

The small number of parameters of this controller allows the mapping of the whole search space. We realized 5500 experiments on the real robot and interpolated the rest of the search space (Fig. 2(a)). We also mapped the fitness landscape in simulation (5500 experiments, Fig. 2(b)). To our knowledge, this is the first time that we are able to visualize a fitness landscape for a real robot and its simulation.

The differences between the two landscapes correspond to the reality gap. The landscape in simulation contains four main fitness peaks and one global optimum. The landscape obtained in reality is noisier but simpler and it seems to contain only one important fitness peak. In both landscapes, we observe a large low-fitness zone but the main high-fitness zones match only a small zone and for only one fitness peak. A typical example of reality gap will occur if the optimization in simulation leads to solutions in the top left corner of the fitness landscape, for which solutions have a high fitness in simulation but a very bad one in reality.

While the fitness landscapes in simulation and in reality are very different, there exist a lot of controllers with a good fitness (greater than 900 mm; these controllers achieve gaits comparable to those obtained with hand-tuned controllers) in both simulation and reality (Fig. 3). If we visually compare gaits that correspond to this zone in simulation and in reality, we observe a good match.

Our interpretation is that the simulation is accurate in at least this sub-part of the search space

The Transferability Function

This interpretation leads to the fundamental hypothesis of the transferability approach: for many physical systems, it is possible to design simulators that work accurately for a subset of the possible solutions. In the case of dynamic simulators, physicists work on the dynamic of rigid body since the XVII-th century and the accumulated knowledge allows engineers to make good predictions for many physical systems.

Since simulations will never be perfect, our approach is to make the system aware of its own limits and hence allows it to avoid solutions that it cannot correctly simulate. These limits can be captured by a transferability function:

Definition 1 (Transferability function) A transferability function is a function that maps, for the whole search space, descriptors of solutions (e.g. genotypes, phenotypes or behavior descriptors) to a transferability score that represents how well the simulation matches the reality.

There are many ways to define a similarity, therefore there are many possible transferability functions. Describing the similarity of behaviors in robotics has recently been investigated in the context of diversity preservation [START_REF] Mouret | Encouraging behavioral diversity in evolutionary robotics: An empirical study[END_REF] and novelty search [START_REF] Lehman | Abandoning Objectives: Evolution through the Search for Novelty Alone[END_REF]. Many measures have been proposed. For a legged robot, one can compare covered distance (i.e. compare the fitness values), trajectory of the center of mass at each timestep, angular positions of each joint for each time-step, contact of the legs with the ground, ... At any rates, the best similarity measure highly depends on the task and on the simulator. The most intuitive input space for the transferability function is the genotype space. However, the maps from genotype to transferability may be very non-linear because the relationship between genotypes and behaviors is often complex in evolutionary robotics. Many genotypes (e.g. neural networks or development programs) are also hard to put as the input of functions. An alternative is to use the behavior in simulation, which is easy to obtain. The transferability function then answers the question: "given this behavior in simulation, should we expect a similar behavior in reality?". For instance, in many dynamic simulations we observe robots that unrealistically jump above the ground when they hit it. If the 3D-trajectory of the center of mass is used as an input space, then the transferability function will easily detect that if the z-coordinate is above a threshold, then the corresponding behavior is not transferable at all.

For the considered quadruped robot, we computed two transferability functions:

• input space: genotype; similarity measure:difference in covered distance (fitness) (Fig. 4(a));

• input space: genotype; similarity measure: sum of the squared Euclidean distance between each point of the 3D trajectories of the geometrical center of the robot (Fig. 4(b)).

In both cases we observe that the high-fitness zone of the simulation in the top left corner is not transferable but a large part of the solutions from the other high fitness zone appears transferable.

Learning the Transferability Function

For evolutionary robotics, it is obviously unfeasible to compute the transferability score for each solution of the search space -as we did it in these simple experiments -because this would require to test every point of the search space on the real robot. To avoid this issue, the main proposition of the transferability approach is to automatically learn the transferability function using supervised learning techniques. Using a few tests on the real system and a few evaluations in simulation, we propose to use a regression technique (e.g. a neural network or a support vector machine) to predict how well simulation and reality will match for any solution of the search space. This predictor will thus estimate the transferability of each potential solution. Put differently, the transferability approach proposes to learn the limits of the simulation. It may seem counter-intuitive and inefficient to approximate the transferability instead of the fitness (i.e. using a surrogate model of the fitness), but working with the transferability function is promising for at least two reasons. First, approximating the fitness function for a dynamic system (e.g. a robot) means using a few tests on the real robot to build the whole fitness landscape. In the same way as simulators will never be perfect, this approximation will not be perfect, therefore we will likely face reality gap issues. Second, learning the fitness function is likely to be harder than learning the transferability function. Indeed, using a machine learning technique to learn the fitness function of a robot is equivalent to automatically design a simulator for a complex robot: the function has to predict a description of the behavior (the fitness) from a description of the solution (the genotype). Such a simulator would therefore need to include the laws of articulated rigid body dynamics, but these laws are unlikely to be correctly discovered using a few trajectories of a robot. On the contrary, predicting that a solution will not be transferable can often be done using a few Figure 5: Principle of the multi-objective optimization of both the fitness and the transferability. Individuals from the population are periodically transfered on the robot to improve the approximation of the transferability function.

simple criteria that a machine learning algorithm can find. For instance, a classification algorithm could easily predict that high-frequency gaits are not transferable by applying a threshold on a frequency parameter (the ease of prediction depends on the input space of the predictor). In summary, learning the transferability complements a state-of-the art simulator instead of reinventing or improving it.

Finding Efficient and Transferable Solutions

Using a simulator to find solutions that perform well in reality can be restated as a two-objective optimization problem, where the objectives are (1) the performance in simulation and (2) the accuracy of the simulation for the tested solution. Optimal solutions for this problem will be perfectly simulated and perfectly efficient in simulation. However, there is no reason to believe that the best solutions in simulation will correspond to the best solutions in reality. On the contrary, the best solutions in simulation are often highly dynamic behaviors that strongly rely on unrealistic effects; the best solutions in reality will also be probably highly tuned behaviors instead of simpler, more robust behaviors.

We therefore expect to see a trade-off between transferability and fitness in simulation. Multi-objective evolutionary algorithms (MOEA, see [START_REF] Deb | Multi-objectives optimization using evolutionnary algorithms[END_REF]) are well suited methods for this two-objective optimization: maximize fitness(x) approximated transferability(x)

Nonetheless, we are essentially optimizing the fitness under the constraint of the transferability. While MOEAs are recognized tools to apply soft constraints [START_REF] Fonseca | Multiobjective optimization and multiple constraint handling with evolutionary algorithms. i. a unified formulation. Systems, Man and Cybernetics, Part A: Systems and Humans[END_REF], other constrained optimization algorithms could also be employed.

We chose to use the Inverse Distance Weighting (IDW) method to approximate the transferability function because it's simple and efficient enough. This method can be substituted with any other regression/interpolation method.

An interesting question is when to improve the approximation, that is when to transfer an individual to evaluate it in reality. A first option is to transfer solutions before launching the optimization, build the approximation and do not modify it during the optimization. Another option is to transfer a few individuals before the first generation, in order to initiate the process, and then periodically update the approximation by transferring one of the candidate solution of the population. The second option has the advantage of focusing the approximation on useful candidate solutions because the population will move towards peaks of high fitness. While the first option is simpler, we chose the second one in our current implementation: every 20 generations, the individual from the population that is the most different from the others is tested on the real robot. At the end of the optimization, we select the solution with the best fitness and above a user-defined value for the transferability.

Figure 5 summarizes this process. Our source code is available on EvoRob db (http://www.isir.fr/ evorob_db).

Experimental Results

The two objectives are optimized with the NSGA-II algorithm because it's a classic and versatile MOEA. The size of the population is 40 and the algorithm is stopped after 200 generations. The transferability function takes as input three behavior descriptors, computed using the dynamic simulator: (1) the distance covered during the experiment, (2) the average height of the center of the robot and (3) the heading of the robot at the end of the experiment. The similarity measure is the difference between the trajectories in reality and in simulation (Fig. 4(b)).

We chose a budget of about 10 evaluations on the real robot (depending on the treatment). While this number may appear very small, it is realistic if real experiments are not automated. Additionally, the problem is simple: only two parameters have to be optimized and many high-fitness solutions exist.

We compared the transferability approach to four different treatments, described belows.

Direct optimization on the robot. We used a population of 4 individuals and 5 generations. This leads to 20 tests on the real robot.

Optimization in simulation then transfer to the robot. We expect to observe a reality gap.

Optimization in simulation, transfer to the robot and local search. Parameters of the solutions are modified using 10 steps of a stochastic gradient descent, on the real robot. Surrogate model of the fitness function. We tested IDW [START_REF] Shepard | A two-dimensional interpolation function for irregularly-spaced data[END_REF]) and the Kriging method [START_REF] Jin | A comprehensive survey of fitness approximation in evolutionary computation[END_REF]. Results (Fig. 6) show that solutions found with the transferability approach have a very similar fitness value in reality and in simulation, whereas we observe a large reality gap when the optimization occurs only in simulation. These solutions are also the ones that work the best on the real robot. It must be emphasized that the transferability approach did not find the optimal behavior in simulation (about 1500) nor in reality (about 1500 too). The algorithm instead found good solutions that work similarly well in simulation and in reality.

The surrogate models worked better than the optimization in simulation but it did not significantly improve the result of the direct optimization on the robot. The addition of a local search stage after the transfer from simulation to reality significantly improved the result but final solutions are much worse than those found with the transferability approach.

We obtained similar results with a second experiment, inspired by Jakobi's T-maze [START_REF] Koos | The Transferability Approach: Crossing the Reality Gap in Evolutionary Robotics[END_REF].

Conclusion

The experimental results validate the relevance of automatically learning the limits of the simulation to cross the reality gap. The current implementation relies on several arbitrary choices and many variants can be designed. More specifi-cally, the choice of the approximation model and the update strategy need more investigations.

The transferability approach essentially connects a "slow but accurate" evaluation process (the reality) and a second evaluation process that is "fast but partially accurate" (the simulation). The exact same idea can be used to improve the generalization and the robustness of optimized controllers in robotics: the reality corresponds to the evaluation of the controller in many contexts, whereas the simulation corresponds to its evaluation in a few contexts. We recently obtained promising results based on this idea [START_REF] Pinville | How to Promote Generalisation in Evolutionary Robotics: the Pro-GAb Approach[END_REF].

Last, we also found that learning the transferability function allows the design of a fast on-line adaptation algorithm that deports most of the optimization in a simulation of a self-model [START_REF] Koos | Online Discovery of Locomotion Modes for Wheel-Legged Hybrid Robots: a Transferability-based Approach[END_REF].

Figure 2 :Figure 3 :

 23 Figure 2: (left) Fitness landscape in the dynamic simulator (5500 experiments). (right) Fitness landscape with the real robot (5500 experiments). In both maps, p 1 and p 2 are the evolved parameters of the controller.

Figure 4 :

 4 Figure 4: (left) Transferability function based on the difference of fitness values. (right) Transferability function based on the difference of trajectories. In both maps, the contour line denotes the zones for which the simulation leads to high fitness values (greater than 900mm).

Figure 6 :

 6 Figure6: Average distance covered with each of the tested treatment (at least 10 runs for each treatment). The transferability approach obtains the best fitness in reality (Welsh's t-test, p ≤ 6 • 10 -3 ). Error bars indicate one unit of standard deviation.