Leo Cazenille
email: leo.cazenille@lri.fr

Nicolas Bredeche
email: nicolas.bredeche@lri.fr

Heiko Hamann
email: heiko.hamann@uni-graz.at

Jürgen Stradner
email: juergen.stradner@uni-graz.at

Impact of Neuron Models and Network Structure on Evolving Modular Robot Neural Network Controllers

Keywords: I.2.9 [Computing Methodologies]: Artificial Intelligence-Robotics Experimentations, Algorithms, Reliability Evolutionary Robotics, Artificial Neural Networks, Evolutionary Algorithms, Modular Robotics

This paper investigates the properties required to evolve Artificial Neural Networks for distributed control in modular robotics, which typically involves non-linear dynamics and complex interactions in the sensori-motor space. We investigate the relation between macro-scale properties (such as modularity and regularity) and micro-scale properties in Neural Network controllers. We show how neurons capable of multiplicative-like arithmetic operations may increase the performance of controllers in several ways whenever challenging control problems with non-linear dynamics are involved. This paper provides evidence that performance and robustness of evolved controllers can be improved by a combination of carefully chosen micro-and macro-scale neural network properties.

INTRODUCTION

Evolving Artificial Neural Networks (ANN) for robotic control offers many interesting properties: ANN are easy to implement, easy to compute on-board, robust to noise, expressive and evolvable. In the recent years, several methods have been proposed to evolve ANN, through direct or indirect encodings, and with various macro-scale properties (e.g. regularity, modularity and hierarchy), either hand-crafted or obtained through spontaneous evolution (see next section for references).

However, properties at the level of a single neuron have been largely overlooked and most models proposed so far are based on variations of the seminal McCulloch and Pitts summing unit neuron (e.g. weighted sum of inputs, with a sigmoidal activation function). However, this original model is but a very basic interpretation of what can be observed in nature. Evidence from biology shows many cases of nonlinear interactions between sensory inputs, which are addressed by unit (single neuron or population of neurons) performing multiplicative operations [START_REF] Koch | Biophysics of computation: information processing in single neurons[END_REF]. Multiplicative models have been introduced in Machine Learning [START_REF] Rumelhart | A general framework for parallel distributed processing[END_REF][START_REF] Durbin | Product units: A computationally powerful and biologically plausible extension to backpropagation networks[END_REF], and their benefits in term of expressivity have been thouroughly studied [START_REF] Schmitt | On the complexity of computing and learning with multiplicative neural networks[END_REF]. This is particularly relevant with modular robotics where non-linear interactions in the feature space are an important part of the problem of designing distributed controllers. This paper is related to our on-going research on this topic, where control is decentralized among autonomous robotic units assembled together into a larger robot, as illustrated in figure 1. In this setup, each robotic unit communicates with its direct neighbors and cooperation must be achieved so that the whole organism can address a given task [START_REF] Levi | Symbiotic Multi-Robot Organisms[END_REF].

This paper explores the benefits of macro-scale properties on network structure (regularity and modularity) and micro-scale properties at the level of a single neuron (summing vs. multiplicative operations) with respect to an evolutionary robotics problem involving non-linear dynamics and complex interactions between autonomous units. We consider an existing benchmark that is designed to match the properties of distributed control in modular robotics and we investigate the impact of several properties on control performance and robustness to generalization. We show that while modularity and regularity are important features for neural networks controllers, as advocated in other works, properties at the level of the neuron can also lead to an increase in performance, generalization and speed of convergence, under certain conditions.

The paper is organized as follows: the next Section provides some background regarding both micro-scale properties and macro-scale Neural Networks properties. Then Section 3 describes the task and the Neural Networks models under scrutiny. Results and Analysis are presented in Section 4. Then, the last Section concludes and sketches future directions.

BACKGROUND

This section provides background information on microscale (neuron models) and macro-scale properties (network structures).

Neuron Models

In this review, we exclusively consider discrete time neural networks, due to the ease of implementation within onboard micro-controller with limited computational power and memory (e.g. spiking neurons offer original computational properties but also require additional computational resource which can be a problem when low-cost hardware is considered).

In this context, the classic summing unit is the most commonly used neuron model in Artificial Neural Networks. It is expressed as:

ai = f ( N j=1 wji * xj + w0), (1)
where ai is the activation of a given neuron, which results from the application of an activation function f on the weighted sum of signals from incoming neurons xj (with wji ∈ R), plus bias. Depending on the nature of f , this may corresponds to the classic threshold, sigmoidal or Radial Basis Function neuron models.

Most published works in Neuro-Evolution rely on this summing unit model as being the standard for neuron computation. Some few exceptions exists, in particular with respect to periodic functions, such as Karl Sims complex function for locomotion [START_REF] Sims | Evolving virtual creatures[END_REF] or Compositional Pattern Pro-ducing Networks [START_REF] Stanley | Compositional pattern producing networks: A novel abstraction of development[END_REF] (CPPN), which is not restricted to any particular kind of function.

While the original motivation for the summing unit model is based on its relevance to early biological data, as the original McCulloch and Pitts model suggests, other models have been explored, both in Biology and Computer Science. Multiplicative operations have been observed in various animals and experimental evidence has been found both at the level of population of neurons and single neurons [START_REF] Koch | Biophysics of computation: information processing in single neurons[END_REF].

In Computer Science, various multiplicative unit models have been introduced: the Sigma-Pi model [START_REF] Rumelhart | A general framework for parallel distributed processing[END_REF], the Pi-Sigma model and the more general Product-Unit model (PUNN). The PUNN model [START_REF] Durbin | Product units: A computationally powerful and biologically plausible extension to backpropagation networks[END_REF] can be described as follows:

ai = f ( N j=1 x w ji j ) ( 2
)
Notations are similar as before, including wji ∈ R, which is of utmost importance as negative exponents enable division operations. The number of exponents to multiply gives the order of the unit, hence the general term Higher-Order Neural Networks (HONN). Figure 2 shows a classical HONN topology where the hidden layer uses HONN units while the read-outs are summing units. Such models offer an increased computatioanal power as they can address non-linear interactions among sensory inputs. While multiplication and division can be accomplished using summing units, it would require much more neurons and layers just to match what a single multiplicative unit can do, in particular when real numbers and calculus precision are considered [START_REF] Schmitt | On the complexity of computing and learning with multiplicative neural networks[END_REF].

■ ✁✂✄☎ ❖✂✄✁✂✄☎ ▼✂✆✄✝✁✆✝✞✟✄✝✠✡ ☛✝☞☞✡ ✌✡✂✍✎ ☎ Σ Σ Σ Π Π Π Π

Network Structure

Several authors have highlighted the importance of topological structure for neuro-evolution [START_REF] Lipson | Principles of modularity, regularity, and hierarchy for scalable systems[END_REF][START_REF] Hornby | Measuring, enabling and comparing modularity, regularity and hierarchy in evolutionary design[END_REF]. The main desired properties are modularity, regularity and hierarchy. These terms are defined as follow:

• Modularity: clearly identified localization of a specific element, either functional or structural; • Regularity: repetitions of one or several patterns observed in the description; • Hierarchy: recursive composition of a structure and/or function.

These properties have been studied both with respect to their functional relevance and possible spontaneous emer-gence during the evolutionary process. For example, early works with Cellular Encoding implemented regularity through recursive decomposition, and was successfully applied to a six-legged robot locomotion problem [START_REF] Gruau | Modular genetic neural networks for six-legged locomotion[END_REF]. Recent works focused on how such properties emerge during evolution, either with direct encoding [START_REF] Kashtan | Spontaneous evolution of modularity and network motifs[END_REF][START_REF] Bongard | Spontaneous evolution of structural modularity in robot neural network controllers hardware[END_REF] or indirect encoding approaches [START_REF] Verbancsics | Constraining connectivity to encourage modularity in hyperneat[END_REF]. The trade-off between capturing regularity and irregularities with indirect encoding methods has also been studied [START_REF] Clune | On the performance of indirect encoding across the continuum of regularity[END_REF].

Another important property is related to feature space design, that is how sensory inputs are processed within the neural network. On the one hand, independent features with few interactions may be processed through different pathways and recombined in the last step (e.g. weighted aggregation). On the other hand, features may be strongly interacting and higher-level feature construction may be required to capture the information needed for the decision process. In Machine Learning, this is sometimes addressed as feature extraction [START_REF] Guyon | Feature extraction: foundations and applications[END_REF], through feature decomposition (non-correlated features are treated separately) or construction (new features are constructed as combination of previous features). The challenge is to come up with a well-balanced trade-off between expressiveness and complexity (size of the feature space). As with other properties, feature space decomposition may or may not be relevant depending on the problem at hand. In the following, modularity is defined to enforce feature space decomposition (i.e. each module gets only part of the feature space as input).

METHOD

This section introduces the robotic task and representation formalisms considered to model the control architecture, each with specific micro-and macro-scale properties. Evolutionary setups and parameters are also presented.

The Robotic Task

The Coupled Inverted Pendulums benchmark introduced in [START_REF] Hamann | Coupled inverted pendulums: a benchmark for evolving decentral controllers in modular robotics[END_REF] (and termed "multipole benchmark" in the following) extends the standard inverted pendulum scenario with nonlinear dynamics. The goal of the multipole benchmark is to provide a challenge that is close to what one would expect from modular robotics scenarios, with interactions between autonomous parts and non-linear dynamics.

In this benchmark, pendulums are started in lower positions, hence, the non-linear upswinging phase is included, and the cart track length is restricted. In combination with a limited acceleration of the cart motor the upswinging cannot be managed by just moving back and forth once. In addition sampling rates of all sensors are limited, which is documented by the relation between the pre-defined cycle length τ of the controller and the maximal angular velocity of 0.05π[1/τ ] = 9 • [1/τ ] (pendulum motion of up to 9 • between two calls of the controller). The sensors do not deliver actual angles and positions directly, but instead partition the original values onto several intervals and sensors (a total of 10 sensors). The controllers have two outputs, left actuator A0 and right actuator A1 and the acceleration control of the cart is determined by their difference. Therefore, there is a total of 10 sensory inputs and 2 motor outputs. For each ANN model, there are two additional inputs and outputs to enable communication between controllers of connected, neighboring carts. These communication channels corresponds to additional inputs/outputs in the controller In addition to the original definition of the benchmark, referred to as multipole-velocity from now, we consider an additional setup where the sensors for cart velocities and pendulum angular velocities are removed. This will be referred to as the multipole-no-velocity benchmark and it offers an increased challenge as velocities may be required, and thus reconstructed, to completely address the balancing problem. Due to the removal of velocity sensors, the multipole-no-velocity benchmark provides 6 (+2 for communication) sensory inputs instead of 10 (+2). An important fact is that when coupled carts are considered, it is theoretically possible to obtain memory-based behaviors even if the controllers are not capable of memorization as information can be transmitted back and forth between controllers of the carts.

The coupling of carts by chains is the most important difference to the standard inverted pendulum. Carts can move independently as long as they do not pull a chain or run into each other. Hence, each cart has to avoid other carts and walls (cart track ends) and has to balance its pendulum at the same time. In the following investigations, the cart number is increased without changing the track length so as to model problems of growing difficulty.

The fitness function is basically the percentage of time steps that all pendulums spent in the upper equilibrium position (φ = 0) -the higher the fitness, the better the behavior. Deviations from φ = 0 are linearly scaled, that is, φ = 0.5π, for example, is evaluated as '50% in upper position'. If any constraint is violated (e.g., cart runs into other cart, cart runs into chain, cart runs into wall, pendulum velocity too high, etc.) an evaluation run is aborted and the fitness is reduced proportionally to the elapsed time. An extensive description can be found in [START_REF] Hamann | A hormone-based controller for evaluation-minimal evolution in decentrally controlled systems[END_REF].

The Controllers

Each pole is controlled by an Artificial Neural Networks, which can communicate with its direct neighbors. As with homogeneous distributed control in modular robotics, only one neural algorithm is evolved for control, which is considered as a template and duplicated within each cart. As a consequence, each cart will behave differently depending on its initial position, sensory inputs and past experience.

Controllers have been designed so that it can be possible to evaluate the relevance of specific properties, both at the level of the network structure and neuron model. In particular, we aim to address the following questions: Is there a benefit in modularity in processing specific inputs through well identified group of neurons? Is there a benefit in regularity as evolving few patterns (i.e. groups of neurons with a given structure and weights), duplicated to form a final, larger, network? What is the benefit of using multiplicative neurons compared to summing units? The following models are devised to address these questions: HONN and MLP: Higher-Order Neural Networks (HONN) and Multi-Layered Perceptron (MLP) are similarly defined as Multi-Layered Neural Networks: the input and output layers are fully connected to the hidden layer, and neurons for the output layer use a summing unit model with a sigmoidal activation function. They differ only in that MLP gets only one hidden layer of sigmoidal summing units while the HONN gets one hidden layer of multiplicative units.

C-MLP and C-HONN (i.e. with compartment): The notion of "compartment" (i.e. a structural module) refers to dedicated groups of neurons that are connected to only one input and one output. Figure 4 illustrates the structure of a Compartment Artificial Neural Networks. For C-MLP, a compartment is an MLP with one input, a hidden layer of sigmoid summing units, and one output with linear activation function. A C-HONN is similarly defined, except that there are two hidden layers, the first with multiplicative units, and the second with summing units, and a multiplicative unit as output (sigmoid activation functions are used for all neurons). In both cases, read-out neurons for the whole network are summing units with linear activation function. The number of compartments is fixed a priori, but the connection to one specific input and output is evolved, as well as the weights within each compartment. Weights connecting each compartment to its selected input and selected read-out neurons are also evolved. To some extent, this is an extreme case of feature space decomposition where the whole network may be considered as a mixture of experts, each expert specialized for processing a specific feature.

C-MLP-WP and C-HONN-WP (i.e. with pattern(s)): As previously, the neural network structure is organized into compartments with one input and one output. All compartments, however, may be identically defined as an instance of a reference evolved pattern. A pattern is defined as a compartment template, i.e. a neural network with one input, one output and one (MLP) or two (HONN) hidden layers. The motivation is to explore the impact of regularity in the network. In the extreme case, only one pattern may be evolved, and cloned during the actual construction of the neural network. As previously, weights connecting each compartment to its selected input and output are evolved.

In addition, we considered several well established neuroevolution methods from the literature: Echo State Networks [START_REF] Jaeger | Tutorial on training recurrent neural networks, covering bppt, rtrl, ekf and the echo state network approach[END_REF] (ESN), NEAT [START_REF] Stanley | Evolving neural networks through augmenting topologies[END_REF] and HyperNEAT [START_REF] Stanley | A hypercube-based encoding for evolving large-scale neural networks[END_REF] (used to generate an ANN which is then used for control). It should be noted that the original HyperNeat implementation used for this experiment has been shown to produce sub-optimal solutions whenever regularity is required [START_REF] Clune | On the performance of indirect encoding across the continuum of regularity[END_REF]. Hence, different results may be obtained with further extensions of this algorithm that are able to deal with regularity [START_REF] Verbancsics | Constraining connectivity to encourage modularity in hyperneat[END_REF]. However, we highlight that the goal here is to provide a baseline with well-known algorithms from the literature, so as to advocate for the relevance (or not) of micro-and macro-scale properties in various experimental setups.

We also considered the Artificial Homeostatic Hormone Systems (AHHS), initially used for the multipole-velocity version of the benchmark, and which provides the best solution so far (compared to NEAT) on performance and generalization. To some extent, AHHS also models several properties evoked earlier: feature space is decomposed as each feature is processed separately by specialized "rules" and multiplicative operations can be computed through virtual "hormones", that are used to transmit information in the system. An extensive description can be found in [START_REF] Hamann | A hormone-based controller for evaluation-minimal evolution in decentrally controlled systems[END_REF].

❍ ✁✁ ❍ ✁✁ ❍ ✁✁ ✳✳✳ ■✂✄☎✆✝ ❈✞✟✄✠✡✆✟☛✂✆✝ |☛✠☞ ☎✆✝ ✳✳✳ w i 1 w i 3 w i 2 w r 3 w r 2 w r 1 Π Σ Π

Evolutionary Optimization

All models (except Neat, HyperNEAT and AHHS) are optimized using the state-of-the-art CMA-ES [START_REF] Auger | A restart cma evolution strategy with increasing population size[END_REF] algorithm. The official rtNeat and HyperNEAT-C++ implementations are used for the corresponding models. The original AHHS implementation is used [START_REF] Hamann | Coupled inverted pendulums: a benchmark for evolving decentral controllers in modular robotics[END_REF].

A fixed budget of 20,000 (resp. 50,000) evaluations is set for the multipole-velocity (resp. multipole-no-velocity) benchmarks. 30 independent runs have been performed for each setup (NN model, cart number, with/without velocity information). In the next section, all claims consider statistically significant measure based on Wilcoxon tests (i.e. with p-value < 0.05).

A large number of preliminary experiments were performed to find operational experimental parameters for each approach. Table 5 summarizes parameters for each approach, as well as comments on robustness of parameters and genome size for each setup (except for Neat and HyperNEAT, which use variable-length genomes). Genome sizes vary to a large extent, depending on the structure of the controllers, but the evaluation budget remains the same to provide fair comparison. Note that the source code for running all the experiments is freely available1 .

RESULTS

Figure 7 show the results from experiments on the multipolevelocity and multipole-no-velocity benchmarks, using a sin- Results on the multipole-velocity benchmark (see Figs. 7(a), 7(c), 7(e)) show that while well-established neuro-evolutionary algorithms (MLP, ESN, Neat, HyperNeat) perform extremely well on the simplest setup (1 cart), performance drops dramaticaly whenever more carts are considered. On the other hand, all other models (except for HONN) remain remarkably stable for any number of carts considered. For the more difficult multipole-velocity with 3 or 5 carts, models with compartments (incl. AHHS) dominate in term of average performance. It is even more true for pattern-enabled models (C-MLP-WP, C-HONN and C-HONN-WP) which provide the best results whenever more than one cart is involved.

Several observations can be drawn from these results: firstly, it appears that modularity (using compartments) and regularity (using duplicated patterns) are key features as difficulty grows. Secondly, multiplicative units (HONN) appears as a counter-productive property if used alone, while they yield to the best scores when combined with modularity (and regularity) on the more complex setups. Also, the good performance of decomposing the feature space, thanks to specialized compartments with one input each, may advocate that the multipole-velocity does not require complex interactions between inputs to be solved.

The fact that modularity and regularity are relevant properties is not a new idea and has been claimed elsewhere on many occasions (cf. section 2.2). However, it is interesting to note that both Neat and HyperNeat are unable to reach the best performance while they could theoretically evolve such properties in the controllers: this issue relates to the trade-off between expressivity and evolvability that have been addressed elsewhere (e.g. see [START_REF] Verbancsics | Constraining connectivity to encourage modularity in hyperneat[END_REF] on enabling HyperNeat to generate regularity and modularity).

Let us now consider the multipole-no-velocity benchmark. Results with one cart are roughly the same as previously except for HONN controllers which go from the worst performing controllers (if velocity information is available) to the top performing controllers, implying that multiplicative units can be exploited in the current setup. Another surprising results is achieved with MLP, which successfully succeeds in balancing the pole. Looking carefully at the evolved strategies, we found that the one-cart multipole-no-velocity can indeed be solved without memory capabilities: using the distance sensors to the wall, a simple MLP is able to learn a perfect trajectory from the cart initial position to the balanced position. While this trick is possible with one cart, the complex dynamics involved when several carts are considered did not permit to find such a solution in further experiments. At this point, an important fact to keep in mind is that a controller from a cart is able to communicate with its neighbors. As a consequence, memorizing information is possible even when the controller is a feed-forward neural network as information can be transmitted back and forth between carts.

Results are quite different when more than one cart is of the pole with respect to the horizon so as to maximize the time spent near the equilibrium position while avoiding the other carts. In the 3-carts multipole-no-velocity, evolved behaviors are similar with some exceptions for some HONN and ESN controllers that achieve equilibrium for one cart, and adopt swinging behaviors for the two other carts. What makes a significant difference between these approaches is to be found in their generalization capabilities. The goal is to evaluate how controllers for each model evolved for the 3-carts version of the multipole-no-velocity perform when tested with 1, 2, 4 or 5 carts. Firstly, in the multipolevelocity benchmark, 3-carts evolved controllers from all approaches yield similar good results with different number of carts, except for MLP, ESN, and Neat which completely fail the generalization test. Secondly, the multipole-no-velocity provides an increased challenge with respect to generalization, as shown in figure 8. The supposedly nearly best results in performance with HONN (and, to some extent, with MLP) are strongly counter-balanced by their very bad results in generalization. Then, only C-MLP and C-HONN controllers (and to less extent C-MLP-WP and C-HONN-WP controllers) produce similar perfomance with 1 or 2 carts while still performing quite well with 4 or 5 carts, at least for some individuals (cf. upper quartiles, maximum values and outliers).

From the results in performance and generalization, it appears that both macro-scale properties and micro-scale properties are relevant to achieve good performance and generalization. In the multipole-velocity benchmark, using modularity (i.e. with compartments) or, even better, modularity combined with regularity (i.e. with patterns) provide the best results, and using multiplicative unit neurons even increases performance as C-HONN and C-HONN-WP both improve over the performance of their MLP equivalents. In the multipole-no-velocity, generalization plays a key role for comparing the different models: this time, modularity alone provides the best controllers on performance and generalization, and using summing units leads to slightly better results than using multiplicative units. However, a closer look at the actual course of the evolutionary process advocates for the benefits of using multiplicative units: figure 9 shows progress throughout the evolutionary process for the various flavors of additive-and multiplicative-based models and establish that C-HONN and C-HONN-WP controllers improves much faster than any other methods on the most complex versions of the multipole-no-velocity benchmark, especially with respect to other models capable of generalization (results are similar for both the 3 and 5 carts configurations). As a matter of fact, C-HONN almost converged in less than 10,000 evaluations (followed by C-HONN-WP), while other methods require more than 40,000 evaluations to reach similar performance.

CONCLUSIONS

This work demonstrates the importance of micro-scale properties in Artificial Neural Networks, in particular with control problems that are characterized by non-linear dynamics and complex interactions between autonomous systems, as it is often the case in modular robotics. The benefits of neuron models that enable multiplicative operations have been demonstrated in combination with other macro-scales properties, in particular when modularity is involved. The take-home message advocates for the use of multiplicative units in neuro-evolutionary algorithms: multiplicative units used in conjunction with modularity, or modularity with regularity, always lead to at least similar or better results when complex dynamics are involved, in much less evaluations.

This work assumed a straight-forward approach to implementing modularity and regularity as explicit features of neural network controllers. This was justified as the goal was to evaluate the positive or negative impacts of such properties. However, and with respect to further use, relaxing this assumption may lead to more adaptive neuro-evolutionary algorithms that can exploit results obtained here. For example, recent works on spontaneous evolution of such network properties [START_REF] Bongard | Spontaneous evolution of structural modularity in robot neural network controllers hardware[END_REF][START_REF] Verbancsics | Constraining connectivity to encourage modularity in hyperneat[END_REF] suggest that the decision to use summing and/or multiplicative units may be evolved as well, to match the requirements of the problem at hand. Hierarchy as a macro-scale property has not been discussed in this paper while it could be combined with the properties evoked earlier. Indeed, preliminary experiments yielded limited results, which are mostly due to the difficulty of defining an explicit encoding allowing for hierarchical organization of compartments. This also advocates for an indirect encoding representation, that is leaving the algorithm to decide on the structure of the controllers, rather than enforcing it. To this end, extensions of this work towards integration of evolving micro-scale properties in Cartesian GP [START_REF] Miller | Cartesian genetic programming[END_REF] and/or HyperNeat-like methods are currently under investigation.

We conclude this paper with a last remark on the multipole benchmarks. The no-velocity version remains very challenging for all approaches as only sub-optimal solutions have been found whenever there is more than one cart. Moreover, it offers an interesting environment with regards to generalization because some methods appear to be much more efficient than others with respect to the transferability of the controllers. Also the memory issue is addressed because operations requiring memorization (such as reconstruction of velocity information) may be achieved through sharing information between several carts.

Figure 1 :

 1 Figure 1: Five modules connected together to form a larger organism in the Symbrion project. Each module embeds its own controller and communicates with its neighbors.

Figure 2 :

 2 Figure 2: Example of Higher-Order Neural Network. The hidden layer embeds product units while the read-out neurons are summing units (possibly with sigmoid activation function).

Figure 3 :

 3 Figure 3: Coupled inverted pendulum benchmark with two carts, pendulums are free to move full 360 • mounted on the carts that move in one dimension (left/right) bounded by walls (track ends) and other carts. Marked angle is pendulum angle φ.

Figure 4 :

 4 Figure 4: Structural description of a C-HONN. A C-MLP is described in a similar fashion by replacing the embedded HONN networks by MLP networks with one hidden layer. Similarly, C-HONN-WP, resp. C-MLP-WP, accept the same description, with embedded HONN, resp. MLP, as copies of a specific reference template (i.e. an evolved pattern).

Figure 5 :Figure 6 :

 56 Figure 5: Parameters for all the models. The third column gives genome size for (a) multipole-velocity with 1 cart; (b) multipole-velocity with > 1 carts; (c) multipole-no-velocity with 1 cart; (d) multipole-no-velocity with > 1 carts

Figure 7 :

 7 Figure 7: Performance of all controllers. For a given model and configuration, each boxplot aggregates the best individuals from 30 independant runs (i.e. 30 values).

Figure 8 :

 8 Figure 8: Generalization capability of the best controllers evolved for three carts, in the multipole-no-velocity benchmark. Each controller is re-evaluated with 1, 2, 4, and 5 carts to assert its transferability in a different setup. Neat and HyperNeat are omitted due to poor performance (similar to MLP and ESN).

  (a) multipole-velocity, 3 carts (b) multipole-no-velocity, 3 carts

Figure 9 :

 9 Figure 9: Evolutionary runs: tracking improvements throughout evaluations using medians of the best-ever individuals from each runs. (a) multipole-velocity, 3 carts ; (b) multipole-no-velocity, 3 carts. Note that results with 5 carts are similar (not shown due to page limit restriction).

http://pages.isir.upmc.fr/evorob db/

Acknowledgments

This work was made possible by the European Union FET Proactive Initiative: Pervasive Adaptation funding the Symbrion project under grant agreement 216342. Experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER and several Universities as well as other funding bodies (see https://www.grid5000.fr). We also would like to thank Jean-Marc Montanier and Taras Kowaliw for many helpful scientific and technical discussions.


Nicolas Bredeche

Jean-Marc Montanier

Environment-driven Open-ended Evolution with a Population of Autonomous Robots

This paper summarizes work done since 2009 on running swarm of autonomous robots with Environment-driven Distributed Evolutionary Adaptation algorithms (EDEA). The motivation behind this work is to design algorithms that can cope with unknown environmental pressure, that is to learn (through evolution) efficient survival strategies in order to address a priori unknown constraints existing in the environment. We are concerned with a fixed-size population of autonomous robotic agents facing unknown, possibly changing, environments, which may require the robots to evolve particular behaviors such as cooperative behaviors, specialized behaviors, etc. We describe a particular flavor of EDEA, termed minimal EDEA (mEDEA), and summarize results obtained so far, both with real robots and in simulation. This algorithm is shown to be both efficient in unknown environment and robust with respect to abrupt, unpredicted, and possibly lethal changes in the environment. Moreover, the ability of mEDEA to evolve various types of behavior, including cooperative and specialized behaviors, is summarized.

Introduction

Achieving Self-sustainable Autonomous Robotics is one challenging task that is yet to be fully addressed. Designing such systems is motivated by applications where humans are no longer able to craft the system to the environment, either due to environmental complexity or lack of prior knowledge. Examples of applications can be found whenever unpredictable situations arise during the actual use of a robotic systems: deployment of mobile sensor network devices with limited communication abilities [START_REF] Hauert | Evolved swarming without positioning information: an application in aerial communication relay[END_REF], self-reconfigurable robots for highly constrained environments [START_REF] Yim | Modular self-reconfigurable robot systems: challenges and opportunities for the future[END_REF][START_REF] Shen | Multimode locomotion via superbot reconfigurable robots[END_REF], radiation shielding and site clearing [START_REF] Engwirda | Sustainable polymorphic colonial robotics and large scale off-world construction[END_REF] or even space exploration, as illustrated by NASA's interest in selfsustainable robotic systems [START_REF] Colombano | Self-sustaining robotic systems[END_REF].

In a different area, Open-ended Evolution has drawn quite a lot of attention in the field of Artificial Life, with Tierra [START_REF] Ray | An approach to the synthesis of life[END_REF] and its followers. While the scientific objectives are related to the simulation of open-ended evolutionary processes, these approaches may also be studied from the perspective of algorithmic design towards a prac-tical problem: how to achieve open-ended evolution in the real world using artificial systems such as robots.

In this paper, we consider a population of autonomous robots (i.e. fixed population size) with limited local communication capability that should be able to learn how to achieve self-sustainability (i.e. survive) in an unknown, possibly dynamic, environment. The work described hereafter is concerned with the design of distributed algorithms to endow a swarm of autonomous robots with the capability to change its behaviour on-the-fly depending on the environmental conditions at hand. We refer to this particular class of algorithms as Environment-driven Distributed Evolutionary Adaptation, or EDEA for short.

In EDEA, evolution occurs among a population of (evolving) behavioural strategies (encoded within genomes), considering the population of robots as the actual resource to share (cf. section 2 for details) -as with Dawkins selfish gene metaphor, a survival strategy that succeeds in generating many offsprings (i.e. spreading in the population) is considered a fitted strategy. As the population is limited in size, strategies compete with one another to share such resource. In previous works, we addressed open-ended evolution in a population of robotic agents under various environmental pressures, such as changing environments [START_REF] Bredeche | Environment-driven Embodied Evolution in a Population of Autonomous Agents[END_REF], environments requiring the emergence of altruistic behaviors [START_REF] Montanier | Surviving the tragedy of commons: Emergence of altruism in a population of evolving autonomous agents[END_REF], with both simulated and real robots [START_REF] Bredeche | Environment-driven Distributed Evolutionary Adaptation in a Population of Autonomous Robotic Agents[END_REF]

(cf. figure 1 for an illustration).
This paper is organized as follows: the mEDEA algorithm is described and discussed in Section 2. In section 3, results from experiments using 20 e-puck robots are summarized, including some considerations on the robustness of the algorithm in the real world. Then, Section 4 gives a summary of results and lessons learned so far. Section 5 presents a discussion on this class of algorithms, and highlight similarities and differences with closely related fields, with a particular emphasis on Embodied Evolutionary Robotics. Finally, the last Section sketches a tentative roadmap for future investigations and general considerations. The mEDEA algorithm, as in minimal EDEA, was initially introduced in [START_REF] Bredeche | Environment-driven Embodied Evolution in a Population of Autonomous Agents[END_REF]. It performs as an evolutionary adaptation algorithm that can be distributed over a population of robotic agents (i.e. each agent in the population runs the same algorithm, but carries different genomes). mEDEA has been designed from the start with on-board robotic implementation as a primary motivation, and has been tested in various setups and environments so far.

Figure 2 provides an illustrative example of how mEDEA works (see Annex for a description of the algorithm). Each agent/robot contains an active genome, which (indirectly) controls the agent's behaviour, and a reservoir of stored genomes, which is empty at first. At each time step, each agent broadcasts in a limited range a slightly mutated copy of its active genome (gaussian mutation) and stores genomes received from neighbours, if close enough (and if not already stored). At the end of a generation (i.e. a pre-defined number of time steps), each agent "forgets" its active genome and randomly picks one genome from its reservoir of stored genomes (if not empty). Then the reservoir is emptied, and a new generation starts. This algorithm is duplicated within each agent in the population, even though agents' behaviours differ depending on each agent's current active genome.

As in other algorithm for open-ended evolution, selection pressure occurs at the population level (the more a genome spreads itself, the higher the probability it will generate offsprings) rather than at the individual level (random sampling). Then, genomes survive only through spreading (as an active genome is automatically deleted locally at the end of a generation) and individual may get better over time as conservative variations generate new candidates that explore (1): generation starts, genome lists are empty; (2) and (3): robots move around (each robot is controlled by its own active genome) and exchange genomes when close enough ; (4): generation ends -the red genome spread more and thus have higher probability of being selected (in this case, probability is indeed p = 1 in two robots while the two other genomes only get p = 0.5 in one single robot. Note that the next generation will contain slightly mutated copies of the original genomes alternative (but closely related) behavioural strategies. As with mEDEA, the most important characteristics for algorithms that belong to the EDEA class is that no fitness function is ever formulated, making it possible to address truly open-ended environments.

In addition to this description, several additional mechanisms are implemented that deal with specific issues:

• While only a mutation operator is used in mEDEA, other variation operators may be used as well. As with other Evolutionary Algorithm, conservative variations (i.e. generating offsprings in the vicinity of their parents, in term of fitness landscape) are preferable. For example, we have also experimented with various cross-over operators, including horizontal gene transfer operators.

• A minimum of 3 agents is required in order to ensure that selection pressure is possible (but not guaranteed). Indeed, two agents would only exchange genomes, implying deterministic rather than random selection. In practical, larger populations are preferred (cf. next sections).

• There is no guarantee whatsoever that a given robotic agent will be able to meet with at least one single other agent during its lifetime. This would result in the "death" of this robot, as no new genome is available to be picked. Several workarounds may be applied, however it is mandatory to avoid introducing a pressure towards unwanted selection pressure (e.g. reusing the previous genome should be avoided as it would result in providing a selective advantage towards "getting lost" behaviours).

Of course, global extinction is always possible, and depends on various parameters, including the interaction between the environment and the population (cf. next sections for practical solutions).

The mEDEA algorithm provides an evolutionary adaptation mechanism in open-ended environment, but does not provide a control function. The actual control of the agent behavior shall be performed by a dedicated controller whose parameters are determined from the genome. In other words, the mEDEA algorithm provides evolutionary adaptation by tuning the control architecture, which can be (and is, in some of our experiments) a Multilayer Perceptron that maps the sensory inputs to motor outputs (e.g. 8 infrared sensors and left/right motors of a robot resembling the e-puck mobile robot) and whose weights are encoded within the genome.

A population of e-pucks running mEDEA

This section summarizes several experiments using several e-puck robots that have already been described in [START_REF] Bredeche | Environment-driven Distributed Evolutionary Adaptation in a Population of Autonomous Robotic Agents[END_REF], and provides new details regarding behavioural strategies as well as considerations with respect to real world implementation.

We implemented the mEDEA algorithm within a population of e-puck robots, provided by the Bristol Robotics Lab. Each e-puck is equipped with 8 Infra-Red (IR) proximity sensors, 3 microphones, 1 loudspeaker, 1 IR remote control receiver, a ring of 9 red LEDs + 2 green body LEDs, 1 3D accelerometer and 1 CMOS camera. Moreover, each e-puck is extended with a linux board [START_REF] Liu | Open-hardware e-puck linux extension board for experimental swarm robotics research[END_REF], which makes it possible to implement the algorithm in C/C + +.

A population of up to 20 e-pucks robots is placed in a 280 cm * 230 cm empty arena. Limited-range communication (approx. 20cm) is emulated by using a WiFi network combined with a Vicon TM tracking system1 . All experiments described in this section lasted from 30 min to 45 min, and at least 25 generations (each generation lasts approx. 1 min and 10 sec, corresponding to 400 controller update stepsthis time is sufficient for a controller to cross the whole area, and therefore meet most of the robots). The refresh rate for a robot controller is limited to 5 updates per second due to various technical limitations of the setup. Robots are not globally synchronized, implying the generation number may vary from one robot to another (asynchroneous evolution).

An additional object is introduced into the arena and is referred to as the sun: each robot knows the sun's relative orientation and distance thanks to the Vicon TM system -being close to, or away from the sun provides a priori no selective advantage. The experimenter may arbitrarily change the sun's location from time to time during the course of the experiment, switching the sun location from one end of the arena to the other. The goal in this experimental setup is to study how a population of robots may evolve towards a behavioural strategy for survival within an environment with one particular, a priori useless, singularity.

Figure 3 illustrates one typical run (out of 8 independent runs with 20 robots). Figure 4 details this run and shows the corresponding trajectories. Each image represents a 4 minutes time span (approx. 3 generations), during which each robot location is recorded every 1 sec (the sun location is illustrated as a yellow circle). The experiments is started with a sun located in the south-east quadrant of the environment. While robots are initially displaying various simple behaviours (turning around, heading forward, standing still, etc.), one strategy quickly evolves as a large part of the population drive to and remain at the singularity point (i.e. the sun). Though this strategy is not the only one to be observed, it is displayed by more than half the population. After some time (approx. 25 min), the sun is moved to some other location by the experimenter (i.e. the two-legged primate in figure 3, image no.3). This makes it possible to witness a sun-following behavior that was evolved earlier. Note that as a large part of the population travel towards the new sun location, these robots may also encounter other robots -possibly wiping out less represented alternative strategies, and ending with even more robots displaying the same behaviour (cf. full details can be found in [START_REF] Bredeche | Environment-driven Distributed Evolutionary Adaptation in a Population of Autonomous Robotic Agents[END_REF]).

These experiments revealed a number of technical issues unfamiliar to experiments in simulation, as can be expected when trying to cross the so-called reality gap [START_REF] Jakobi | Noise and the reality gap: The use of simulation in evolutionary robotics[END_REF]. In the present setup, the following issues where experienced:

• Proximity sensors are unreliable: the low quality of the infra-red sensors makes it very difficult to detect obstacles and/or other robots (with a binary positive response only for distances under 1cm). Also the e-puck body is more or less transparent, making it almost invisible in some cases.

Adding a coloured plastic skirt to the robots only partly solves the problem as the proximity sensors are occasionally blinded by the skirt. As a consequence, proximity sensor values must often be disregarded because of their unreliability.

• Colliding robots are regularly unable to send/receive genomes to their neighbours. This is due to our particular setup where local communication is emulated using the Vicon TM system for computing the local communication network based on distance between robots (the Vicon TM fails to identify colliding robots). While this approach was originally motivated by the absence of local robot-robot communication (and lack of time2 to develop IR-based communication libraries), it ended up as quite a problem as robots could not participate in the evolutionary adaptation process during collisions. In practice robots were occasionally lost from the emulated communication network but always recovered when moving away from one another.

• On-board processing is slow: the combination of onboard computation with limited hardware and the particular setup for emulating local communication has a negative impact on speed of execution. In fact 5 updates/sec was observed, with often asynchronous updates of sun distance and orientation from the tracking system (i.e. out-of-date information, or missing opportunities).

While simulation and real world experiments do differ as expected, the MEDEA algorithm proved to be remarkably robust to the reality gap, as it manages to deal with all of the issues outlined above and still demonstrates interesting behaviours that manage to survive in the environment. As a matter of fact, the most critical issue (in simulation and in the real world) is the size of population: larger populations display more stable behaviours, while very small population (e.g. < 20 robots in this context) are prone to extinction. This was confirmed by results from some previous experiments using less than 10 robots: results were difficult to analyze (few runs converged towards behavioural consensus, and some did not even converge at all (i.e. extinctions))this was also experimentally confirmed using extensive simulation (cf. [START_REF] Bredeche | Environment-driven Distributed Evolutionary Adaptation in a Population of Autonomous Robotic Agents[END_REF]).

Lessons learned so far

The mEDEA algorithm has been studied in various contexts so far: given an a priori unknown environment with specific properties, the goal is (a) to study the evolutionary dynamics of mEDEA (or variations) to achieve survivability, (b) to identify the particular strategies that have been evolved, (c) optionally, to modify the algorithm so as to increase the ability for the whole population to survive in this particular setup. In the following, questions addressed so far, as well as lessons learned, are briefly summarized:

• Evolving homogeneous behavior [START_REF] Bredeche | Environment-driven Distributed Evolutionary Adaptation in a Population of Autonomous Robotic Agents[END_REF]:

extending what was presented in the previous section, we studied how consensus towards a specific behaviour could be evolved and spread over the population. In these experiments, the importance of population size and mating opportunities (which depends on population size, radius of communication and environment size) was highlighted.

It was also shown that as both population size and mating opportunities increase, a single behavioural strategy would dominate within the entire population.

• Robustness to environmental changes [START_REF] Bredeche | Environment-driven Embodied Evolution in a Population of Autonomous Agents[END_REF] : In this work, the ability of mEDEA was experimentally tested with respect to changing environmental conditions. It was shown that a population of (virtual) robots running mEDEA was able to recover from a sudden change in the environment towards much more challenging conditions. While survival rate was largely affected by such a change, mEDEA quickly recovered by evolving behaviours fitted to the new environment at hand, without having to be modified or notified by the user.

• Learning altruistic behaviour [START_REF] Montanier | Surviving the tragedy of commons: Emergence of altruism in a population of evolving autonomous agents[END_REF]: mEDEA was tested within a particular environment inspired from the Tragedy of the Commons [START_REF] Hardin | Extensions of the tragedy of the commons[END_REF]. In such environments, altruistic behaviours (i.e. choosing to share part of what one could keep for itself) is required in order for the whole population to survive.

In this setup, it was shown that mEDEA naturally evolves altruistic behaviours over the population if environmental conditions become too challenging. Also, it was shown that the algorithm globally converges towards a trade-off between altruism and selfishness to ensure survival of the majority of the population (i.e. sharing as much as possible as long as it does not impact one's own survival chances).

• Specialization through speciation (on-going work): mEDEA is currently studied with respect to its ability to converge towards specialized sub-populations whenever it is required (e.g. foraging two energy resources, each available in limited quantity and each requiring specific skills). In this scope, we consider behaviour specialization through speciation (i.e. generalists cannot be evolved). Results show that while protecting species can

(a) (b) (c) (d) (e) (f) (g) (h)
Figure 4: E-pucks' trajectories: each image records the locations of all e-pucks during 4 minutes, using a one location per e-puck per second resolution be achieved with dedicated selection and/or variation operators such speciation is very (but not completely) unlikely to appear spontaneously. As with previous studies about the evolution of a homogeneous behaviour, the number of mating opportunities is a critical parameter as few opportunities are mandatory for the evolution of speciation.

Most experiments have been performed using the Roborobo simulator3 , originally developed by Nicolas Bredeche, which is a simulator for large population of robotic agents. It is programmed in C++ using the SDL graphics library. It features basic robotic-inspired agent dynamics with friction-based collision, and provide very fast simulation (> 1000 position update per second with 100 virtual robots resembling e-pucks). While most extensive tests are performed in simulation (due to time constraint limitation), the model scrutiny is also considered valid with respect to real world implementation thanks to occasional real world validation, such as described in the previous section.

Note that all source code and parameters for all experiments published so far are available on-line in the Evolutionary Robotics Database4 .

Discussion and Related Works

A related research area is Embodied Evolution [START_REF] Watson | Embodied evolution: Distributing an evolutionary algorithm in a population of robots[END_REF] (EE), a sub-field of Evolutionary Robotics that deals with the on-line, possibly distributed, evolutionary acquisition of behaviours. In most cases, EE considers a population of robots that interact with one another depending on spatial relations -and bares some similarities with Island Models in Evolutionary Computation (EC). As with other EC algorithms, EE is objective-driven, that is the user defines a particular objective function to optimize. In most works so far, these objective functions are used to optimize individual skills, with some very few exceptions targeting coordinated behaviours [START_REF] Prieto | Open-ended evolution as a means to self-organize heterogeneous multi-robot systems in real time[END_REF].

Objective functions may be characterized in various ways, depending on the detail of description (explicit vs. implicit), type of description (behavioural vs. functional) or origin of information used to compute the fitness (internal vs. external) [START_REF] Nolfi | Evolutionary Robotics: The Biology, Intelligence, and Technology of Self-Organizing Machines[END_REF], p.67). At this point, it should be noted that the terminology is sometimes prone to confusion regarding the term implicit fitness. Indeed, there is a strong difference between objective-driven evolution and environment-driven evolution, which is what is considered throughout this paper.

On the one hand, objective-driven evolution requires the human user to write down a function used to evaluate the performance (or utility) of a particular behaviour. In this scope, an "implicit fitness" designates the fact that the user Figure 5: Classification of Embodied Evolution (EE), Open-ended Evolution in Artificial Life (ALife) and Environment-driven Distributed Evolutionary Adaptation (EDEA): a perspective from the nature of the selection pressure. Note that (1) this table is limited to contributions that deals with on-line evolution (ie. Evolutionary Robotics is omitted, but otherwise would match EE classification); (2) this table ignores other important axis that could be used to discriminate among these research fields, in particular wrt. the motivation (modeling the real world vs. engineering).

explictly designed a fitness function which description gives few indications on how to achieve an "efficient" behaviour. As an example, an implicit fitness function may be used to assign higher fitness values to a particular individual that maximizes its own energy level, while this could ultimately depend on displaying a particular skill such as the ability to aggregate with other robots (see [START_REF] Weel | The emergence of multi-cellular robot organisms through on-line on-board evolution[END_REF] for an example). In other words: while an implicit fitness function gives loose indications on the behaviour to learn, it enables to compare candidate behaviours, therefore making it possible to perform non-uniform selection (as usual with evolutionary optimization).

On the other hand, environment-driven evolution implies that evolution is performed without any fitness function description -i.e. in its seminal form, that means than selection pressure occurs at the level of the population, but cannot be modelled at the level of the individual due to the inability to evaluate individual performance. In other words, random selection at the level of the individual is performed, but selection pressure will act at the level of the population, as with mEDEA, but also with various artificial life systems dealing with open-ended evolution, such as Tierra (where selection pressure results from memory limitation).

Figure 5 suggests a classificiation of the different fields discussed in this Section, from the perspective of the nature of the selection pressure considered. Of course, the limit is often unclear. Many open-ended evolution models that can be found both in Artificial Life (e.g. contributions using Genetic Algorithm to model the selection/replacement process) or Evolutionary Biology [START_REF] Gavrilets | Fitness Landscapes and the Origin of Species[END_REF] rely on the more explicit formulation of an implicit fitness, as it makes experimental studies more controllable and easier to interpret. Avida's metabolic function can also be seen as an indirect way to favor objective-driven selection (though it does not automaticaly imply reproduction). The limit is not clear either when it comes to biased vs. non-biased environmentdriven selection. As an example, assortative mating stands as a mechanism that bias natural selection due to a particular mating strategy.

An additional concern would then be to evaluate if the definition of a fitness function results either from a predefined implementation choice from the user (user-defined objective-driven function) or from the evolution of phenotypic traits that can be used by individuals in order to select particular candidates for mating (evolved objective-driven function or mating strategy). As an example, a population of robots could learn an efficient cooperative behaviours to survive in a given environment, then learn to display their altruistic nature through the occurrence of a phenotypic trait such as growing a green beard (for example). Such a phenotypic trait could then be used as a basis to evolve a nonuniform selection mechanisms for mating and reproduction.

Open Problems with EDEA

The scientific question behind this work is to produce algorithms to learn efficient behaviours w.r.t. survivability in the context of open-ended environments, where selection pressure is solely driven by the environment. As such, the roadmap should follow an engineering viewpoint, listing and successfully addressing a list of challenges that may occur in the real world. In addition to those already described in the previous Section, it is possible to identify several issues that remain to be addressed. While the list to follow is far from exhaustive, we can already sketch three (complementary) research directions:

• Environment-driven Evolution: extending existing works (see previous Section), several issues may be addressed from the evolution of communication, of cooperation (division of labor), of developmental, epigenetic and learning mechanisms, to the evolution of phenotypic traits and mating/reproductive strategies, to name a few. For some of these issues, several other domains (such as Evolutionary Biology, Evolutionary Robotics, Swarm Robotics or Machine Learning) share similar concerns and can provide many insights and information w.r.t. our own objectives.

• Defining an optimal performance zone: a human en-gineer may possibly define a priori a set of restrictions over possible actions to be taken, both at the individual or group levels. For example, one may implement restrictions with respect to what can be considered as dangerous actions (e.g. falling into a hole, breaking contact with other robots, ...). This can be achieved by particular choices of implementation, such as using a subsomption architecture, with an EDEA running as a meta-behaviour with low priority, and dedicated behaviours for critical situations. As an example, one may want to enforce particular communication graph topological properties, such that a robot cannot get lost voluntarily. The main issue is then to address the trade-off between restricting the so called performance zone, where any authorized actions can be performed, and relaxing such constraints so as not to limit behaviours that can be evolved.

• Controlling the swarm: in this work, an underlying hypothesis is that self-sustainability must be achieved before addressing user-controllable robot swarm. This usually implies the ability to recharge one's battery from time to time, but may also require more complex organization at the level of the population depending on the environment at hand (see above). Indeed, one important objective is to mix both environment-driven and user-defined objectivedriven evolution so that a swarm could achieve one particular tasks without the user having to deal with robot's self-sustainability issues. Then, controllability can be interpreted in many ways, from endowing all robots with a global utility function (which may be reformulated within each robot) to on-the-fly control through interaction between the user and one (or several) robot(s), as well as specific robot recruitment strategies.

Beyond swarm robotics, EDEA may also be of interest whenever distributed processing among a large set of autonomous components is involved. Indeed this kind of situation is ubiquitous in todays environment : the Internet, Cloud Computing, e-mobility, etc. In this scope, Autonomic Computing [START_REF] Murch | Autonomic Computing[END_REF] considers one particular major challenge: how to endow distributed systems where multiple units interact on a local basis with a self-managing capability (i.e. self-configuration, self-healing, self-optimization, selfprotection) as the user (or system administrator) may not be able to manage such complex systems by him/herself.

Concluding remarks

This paper provided a short introduction to on-going research done in algorithm design for Environment-driven Distributed Evolutionary Adaptation (EDEA). A rather simple algorithm was described that can be used to generate complex evolutionary dynamics within a swarm of real robots. A description of open issues and a discussion of related works was provided, in order to clarify the particular class of problems addressed.

The underlying motivations behind EDEA are both fundamental, i.e. understanding which mechanisms are required to address particular environmental conditions, and applied, as the ultimate goal is to design algorithms that can actually be deployed and used in the real world.

Figure 1 :

 1 Figure 1: Environment-driven self-adaptive swarm of robots -experiment with 20 e-puck mobile robots (details in (Bredeche et al., 2012))

Figure 2 :

 2 Figure 2: The mEDEA algorithm: a simplified illustration.(1): generation starts, genome lists are empty; (2) and (3): robots move around (each robot is controlled by its own active genome) and exchange genomes when close enough ; (4): generation ends -the red genome spread more and thus have higher probability of being selected (in this case, probability is indeed p = 1 in two robots while the two other genomes only get p = 0.5 in one single robot. Note that the next generation will contain slightly mutated copies of the original genomes

Figure 3 :

 3 Figure 3: A typical experiment with 20 e-pucks running mEDEA. These four images are extracted from a sequence available at this address: http://www.youtube.com/watch?v= ilRGcJN2nA

http://www.vicon.com

Implementing and running the experiments was completely done during a one-month stay at BRL.

http://code.google.com/p/roborobo

http://www.isir.fr/evorob db/

Acknowledgments

This work was made possible by the European Union FET Proactive Initiative: Pervasive Adaptation funding the Symbrion project under grant agreement 216342. The authors also wish to thank several people with whom, at some point, we collaborated: Wenguo Liu, Alan Winfield, Simon Carrignon, Antoine Sylvain, Leo Cazenille.

Annex: the mEDEA algorithm

The following description is copied and adapted from (Bredeche and [START_REF] Bredeche | Environment-driven Embodied Evolution in a Population of Autonomous Agents[END_REF]. The mEDEA algorithm ("minimal EDEA") is described in table 1. This algorithm is implemented in each robot and describes how evolution is handled localy. This algorithm works along with a communication routine (not shown here), which purpose is to receive incoming genomes and store these in the list of imported genomes for later use (genomeList).

At a given moment, an agent is driven by a control architecture (e.g. an artificial neural network) which parameters are extracted from an "active" genome, which remains unchanged for a generation. This genome is continuously broadcasted to all agents within (a limited) communication range. This algorithm actually implements several simple, but crucial, features, that can be interpreted from the viewpoint of a traditional evolutionary algorithm structure:

Selection operator: the selection operator is limited to simple random sampling among the list of imported genomes, ie. no selection pressure on a local individual basis. However, cumulated local random selection ultimately favor the most widespread genomes on a global population basis as such genomes have greater probability to be randomly picked on average. In fact, the larger the population and mating opportunities, the more accurate the selection pressure at the level of the population.

Variation operator: the variation operator is assumed to be rather conservative to ensure a continuity during the course of evolution. Generating altered copies of a genome only make sense if there is some continuity in the genome lineage: if no variation is performed, the algorithm shall simply converge on average towards the best existing genome initially in the population. In the following, we assume a gaussian random mutation operator, inspired from Evolution Strategies [START_REF] Beyer | Evolution strategies -A comprehensive introduction[END_REF], which conservative behavior can be easily tuned through a σ parameter.

Replacement operator: lastly, replacement of the current active genome to control a given agent is performed by (1) local deletion of the active genome at the end of one generation and (2) randomly selecting a new active genome among the imported genome list (cf. selection operator). On a population level, this implies that surviving genomes are likely to be correlated with efficient mating strategies as a given genome may only survive through (altered) copies of itself in the long run.

The positive or negative impact of environmental variability on genome performance is smoothed by the very definition of the variation operator as newly created genomes are always more or less closely related to their parent. As a consequence, each genome results from a large number of parallel evaluations, both on the spatial scale as closely related copies sharing the same ancester may evaluated in a population, and on the temporal scale, as one genome is also strongly related to its ancestors. Hence, a single genome may get lucky once in a while, but it's highly unlikely that a "family" of closely related genomes manage to survive in the population if there are more efficient competitors.


Anthony Mouraud

Quentin Barthélemy

Aurélien Mayoue

Anthony Larue

Cedric Gouy-Pailler

Hélène Paugam-Moisy

Cédric Gouy-Pailler

From Neuronal cost-based metrics towards sparse coded signals classification

Introduction

Sparse coding has been intensively studied in relation with signal decomposition and dictionary learning, making an extensive use of sparsity constraints through the ℓ 0 -or ℓ 1 -norm to decompose and recover signals from a small number of coefficients. Whereas classic decompositions on bases of exponentials (Fourier), wavelets or curvelets may be badly adapted to the signal at hand, dictionary learning algorithms extract patterns characteristic of a given database [START_REF] Aharon | K-SVD : An algorithm for designing overcomplete dictionaries for sparse representation[END_REF][START_REF] Lewicki | Coding time-varying signals using sparse, shiftinvariant representations[END_REF]. The paper focuses on sparse coding methods that learn to convert a raw signal into a multisource spikegram, a sparse and temporal coding [START_REF] Barthélemy | Multivariate Dictionary Learning and Shift & 2D Rotation Invariant Sparse Coding[END_REF]. While robustness and compression arguments are usually employed to justify sparse coding, sparse representations lack for appropriate tools for classification purpose.

In the meantime, recent techniques in neuroscience give access to large multineuronal spike train recordings. Thereby, several spike train analysis methods have been proposed by computational neuroscientists in the last few years [START_REF] Paiva | A comparison of binless spike train measures[END_REF]. Among the approaches aiming at quantifiying the degree of similarity between pairs of spike trains, the paper focuses on the spike train metrics that quantify the cost of a transformation from one spike train into another by means of elementary steps [START_REF] Victor | Metric-space analysis of spike trains: theory, algorithms and application[END_REF]. Other metrics have been proposed, as reviewed in [START_REF] Victor | Analysis of Parallel Spike Trains[END_REF].

The present work proposes an original approach to multivariate signals classification through the coupling of sparse coding processes and spike train analysis methods. First, a sparse coding step consists in building a set of spikegrams from a database of signals (Section 2). Second, a cost-based metric-space analysis (described in Section 3) is applied to clustering spike trains that can be derived from spikegrams (Section 4). Experiments on character trajectories and comparative results are presented in Section 5.

The method for sparse coding multivariate signals defined by Barthélemy et al. is summarized in this section (see [START_REF] Barthélemy | Multivariate Dictionary Learning and Shift & 2D Rotation Invariant Sparse Coding[END_REF] for details) and the visualization of resulting sparse codes is illustrated. A signal sampled in N temporal bins can be represented by a vector s ∈ R N and a multivariate signal with V components is a matrix y ∈ R N ×V . For multivariate signals, a normed dictionary

Φ ∈ R N ×V ×M is composed of M elementary patterns {φ m } M m=1 ∈ R N ×V usually called atoms.
The decomposition of a signal y on a dictionary Φ is defined by:

y = Φx + ǫ = M m=1 x m φ m + ǫ (1)
with x ∈ R M the vector of coding coefficients and ǫ ∈ R N ×V the residual error.

Due to the temporal nature of a signal1 , two atoms of the dictionary may correspond to a same short signal, starting at different times t 1 and t 2 in {1..N }. Thereby a compact dictionary Ψ can be defined as a set of Λ shiftable kernels {ψ λ } Λ λ=1 , each translatable at any temporal position τ . As a result, each atom of the dictionary Φ can be rewritten φ m (t) = ψ λ (t -τ ) since it is characterized by a kernel of index λ and its temporal starting position τ .

The sparse decomposition methodology is two-fold. On the one hand, the adapted dictionary is learned from a sample of signals, by alternating between two steps [START_REF] Barthélemy | Multivariate Dictionary Learning and Shift & 2D Rotation Invariant Sparse Coding[END_REF]: i) sparse approximating the coding coefficients x, with a fixed dictionary Φ (multivariate orthogonal matching pursuit), ii) updating the kernels of the compact dictionary Ψ, with fixed x (a gradient descent method). Sparse approximating a signal corresponds to reducing its decomposition on the dictionary Φ to a small number of non-zero coefficients associated to strong energy patterns only. Dictionary learning corresponds to updating the kernels of the compact dictionary Ψ (and thus updating Φ) by maximum likelihood optimization w.r.t. the reconstruction accuracy. On the other hand, each database signal is projected onto the overcomplete basis of the learned dictionary. At the end of the process, each signal y is sparsely coded on Γ atoms2 (with Γ ≪ M ):

(∀t ∈ {1..N }) y(t) = Γ γ=1 x γ φ γ (t) + ǫ(t) = Λ λ=1 τ ∈σ λ x λ,τ ψ λ (t -τ ) + ǫ(t) (2)
where σ λ is the set of all starting times of a kernel ψ λ when detected in the signal y. Note that σ λ is an empty set or reduced to a single element for most values of λ, and most coefficients x λ,τ are set to zero (if τ / ∈ σ λ ). The sparse vector x λ,τ is usually displayed as a time-kernel representation called spikegram (Figure 1 Multineuronal cost-based metric: The present work focuses on cost-based metrics as defined in [START_REF] Victor | Metric-space analysis of spike trains: theory, algorithms and application[END_REF], especially D spike . First defined for monosource spike trains comparison and further extended to multineuronal spike trains by Aronov [START_REF] Aronov | Fast algorithm for the metric-space analysis of simultaneous responses of multiple single neurons[END_REF], the metric relies on the alignment of two multineuronal spike trains. The aim is to compute the cost of aligning the spikes of a train S a onto the spikes of a train S b by means of spike deletion/insertion (cost 1), or spike label-change (cost k), or/and spike temporal shift (cost q factor of temporal shift ∆t):

D spike q,k (S a , S b ) = min r,s M (S a ) + M (S b ) -2r -2s + ks + q × r+s ℓ=0 ∆t ℓ (3)
where M(S) is the number of spikes in trains (S a or S b ), with r shifts between same label spikes and s shifts between different label spikes. An efficient algorithm has been proposed in [START_REF] Aronov | Fast algorithm for the metric-space analysis of simultaneous responses of multiple single neurons[END_REF], based on dynamic programming, to achieve the minimum cost computation. The family of D spike q,k metrics, for q 0 and 0 k 2 (otherwise deletion or insertion is cheaper) is rich. For a given dataset, the cost parameters (q, k) can be adapted to the spike train features.

Clustering and confusion matrix:

Let us consider a dataset of spike trains {S p } 1 p P and their target class3 t p among C classes. The dataset can be clustered in the cost-based metric space: For any given spike train S p , the z-order average distance of S p to any class c is computed according to Eq. 4 and the observed class c p is the nearest class in that sense: c p = argmin c∈{1..C} D(S p , c).

(∀p ∈ {1..P }) (∀c ∈ {1..C}) D(S p , c) = 1 |S c | S∈Sc D spike q,k (S p , S) z 1/z (4)
where S c is the set of all trains of target class c (except S p , when c = t p ) and |S c | its cardinality. The resulting clustering depends on the metric D spike q,k . Its quality can be evaluated by a normalized confusion matrix M (Figure 2) and measured by a classification rate, the trace of the confusion matrix. Each m ij ∈ M can be interpreted as the probability for a spike train S p to have an observed class c p = j when its target class is t p = i. However, the main point is to discover the best metric, i.e. to find the (q, k) couple of cost parameters that maximizes the classification rate.

Experimental settings

From spikegram to spike train: Spikegrams are similar to spike raster plots, with an extra information of amplitude x λ,τ represented by the color of each spike (Figure 1). In order to extend the cost-based metric analysis to signal classification, the matter is to translate the spikegram of a signal y into a representative spike train S. We propose different variants for processing the kernel amplitude information:

Normal: AN forgets the amplitude information. For each spike, only the source and timing are taken into account and Aronov's cost optimization is applied.

Threshold: AT is a pruning variant. The only spikes with an amplitude |x λ,τ | higher than a given threshold are considered (and processed as in AN).

Inter Spike Interval: AI duplicates every spikes. Each spike is duplicated, the spikecopy occurring later on, with an inter spike interval τ ′ -τ proportional to |x λ,τ |.

Sign: AS duplicates every sources4 . The "negative" spikes (x λ,τ < 0) are carried by one source-copy and the "positive" spikes (x λ,τ > 0) by the other.

Experimental protocol: Each signal of a database is first decomposed in a spikegram, by the sparse coding method presented in Section 2. Second, the spikegram is converted into a spike train, by either AN or AT or AI or AS (all four variants are tested). Third, the cost parameters (q, k) are optimized: Since the spike trains are sparse and the performance most likely varies smoothly as a function of (q, k), a hierarchical grid-search is tractable for solving the optimization problem on a sample of data. Finally, the clustering in the D spike q,k metric space is evaluated as explained in Section 3: The classification rate measures the ability of the metric for clustering the signals in a way that is relevant w.r.t. their classes.

Experiments and results

A Python GUI and a C++ library have been developed, starting from the "Spike Train Analysis Toolkit" proposed in Matlab c by Goldberg et al. [START_REF] Goldberg | Spike train analysis toolkit: Enabling wider application of information-theoretic techniques to neurophysiology[END_REF]. The method has been tested on the Character Trajectories dataset available from the UCI Machine Learning repository (and on confidential databases -data not shown). The benchmark dataset [START_REF] Williams | Extracting motion primitives from natural handwriting data[END_REF] contains P = 2858 character trajectories associated to C = 20 different classes of monostroke letters. Each character trajectory is a multivariate signal composed of horizontal and vertical pen tip velocities and the pen tip force, captured along time (sampled at 200Hz).

In first experiments, optimization of (q, k) is performed by cross-validation on one half dataset (z-order = -2) and classification rate computed on the other half (z-order = -10). The threshold of the AT variant is 5 and the proportional factor of the AI variant is 1/2. Classification rates are displayed in Table 1. The AT variant yields the worst performance since around 2/3 of spikes have been thresholded in each spike train, leading to excessive sparsity. The best performance is for the AS variant that reaches 97% correct classification in average, with stable values of the optimal parameters (q, k) around (0.08, 1.8).

A second set of experiments has been performed on the AS variant, reducing to 1/4 of the database the sample for optimizing (q, k) and evaluating the clustering on the 3/4 remaining (z-order = -10). The cross-validation average classification rate is 94.8%. On the other hand, the classification rate, on the whole dataset, for mean values of optimal (q, k) = (0.082, 1.628) is 95.5%. These results confirm both the stability of the performance and the ability for the cost-based metrics to capture the signal features from their sparse codes.

Note that, although the method processes parsimonious representations of the signals, the results are similar or even better than performance of the most recent methods summarized in the right-hand part of table 1. : Fisher kernels [START_REF] Van Der Maaten | Learning discriminative Fisher kernels[END_REF], classification trees [START_REF] Douzal-Chouakria | Classification trees for time series[END_REF] or hidden Markov models postprocessed by support vector machines (HMM+SVM) [START_REF] Perina | A new generative feature set based on entropy distance for discriminative classification[END_REF].

The paper has proposed tools inspired from computational neuroscience for clustering sparse coded multivariate signals. The idea is to associate the compressing power of sparse signal representation as spikegrams with the richness and adaptability of similarity measures of spike trains. The classification rates measuring the clustering quality are similar to the state-of-the-art performance, which proves the efficiency of the method. The strength of the method is twofold: taking into account the temporal features of the signals and achieving efficient clustering from sparse codes without need for signal reconstruction.

The next step is to define an on-line classifier able to predict the class of a new signal from its D spike q,k -distance to previously learned signal prototypes (on-going work).

  , bottom), a sparse and temporal representation of signals by a raster of kernel occurences through time. A spikegram condensates three pieces of information: the kernel temporal position τ (abscissa), the kernel index λ (ordinate), the amplitude x λ,τ (spike gray level). Comparison of the original (top) and reconstructed (middle) signals shows the low residual error. The spikegram (bottom) illustrates the high reproducibility of the decompositions across the five occurrences of a bivariate signal.

Figure 1 :

 1 Figure 1: Sparse decomposition of five occurrences of a bivariate signal.

Figure 2 :

 2 Figure 2: Confusion matrix: Observed (ordinate) vs target (abscissa) class.

3

  Cost-based metrics for spike train analysisMultisource spikegram representations present many analogies with multineuronal spike train raster plots displayed from recorded neuron activities: Neurons correspond to kernels of the dictionary and the timing of spikes correspond to the starting position of atom occurrences. Timing of both neuronal and kernel spikes are decisive for signal discrimination. This section explains how cost-based metrics lead to an accurate spike train clustering.

Table 1 :

 1 Clustering qualities obtained on the UCI Character Trajectories dataset (left) vs state-of-the-art classification performances (right).

	Variant Success rate (%) AN 91.0 (±1.9) AT 88.1 (±0.9) AI 94.9 (± ) AS 97.0 (±0.2)	Other methods Fisher kernels Classification trees HMM+SVM	Success rate (%) 96.7 93.5 92.6

Notation: with t the time variable, in discrete time : y = y(t) t∈{1..N } with (∀t) y(t) ∈ R V .

The number Γ of atoms in the final code can be fixed as a hyperparameter of the method.

The target class can be the stimulus that generated the spike train.

Note that the AS variant can be combined with the others (AT or AI).