Certaines personnes décident de rédiger une section remerciements minimalle et formelle. Cependant, je pense qu'une simple liste ne rendrait pas honneur aux personnes que je souhaite remercier. Par conséquent, le lecteur intéressé devra lire plusieurs paragraphes avant de trouver celui qui le concerne. De plus, l'anglais ou le français sont utilisés en fonction des personnes remerciées.

Some people decide to write minimal and formal acknowledgements. However I feel that a simple list would not do justice to the people i want to thank. Consequently, the interested reader will have to go through multiple paragraphs to nd the one that concerns him. Moreover, these acknowledgements are written in dierent languages depending of the people thanked.

First of all, I'm grateful to the members of the jury who took some of their precious time for my thesis. I add here a particular acknowledgement to the reviewers for having read the thesis from beginning to end and provide meaningful feedbacks. It was also a great pleasure to have such relevant scientic questions asked during my defense (even if sometimes tough).

Merci à Nicolas Bredèche pour avoir encadré cette thèse. Entre mon arrivée pour un stage d'ingénieur, et ma sortie avec un diplôme de docteur, la route a été longue. Il me reste encore beaucoup de chemin à parcourir, c'est une bonne nouvelle.

Je voudrais aussi remercier les équipes de recherches m'ayant accueilli durant mon doctorat : TAO à l'université Paris-Sud et AMAC à Jussieu. Appartenir à ces équipes m'a beaucoup appris sur le plan scientique. J'ai aussi eu la chance d'y rencontrer des stagiaires, doctorants, et post-docs aux qualités humaines uniques, notamment dans les bureaux FZ (on emportera tous un morceau de Pelé dans notre coeur) et J01 (quand je reviens j'achète une nouvelle cible).

Je tiens à remercier ma famille pour m'avoir soutenu (poussé et tiré aussi) pendant toutes ces années. Les débuts n'ont pas été évidents, mais vous voyez, j'ai ni par étudier. Merci à vous pour m'en avoir donné les moyens et parfois la motivation.

Je voudrais aussi remercier mes amis rencontrés au l des années. Pendant ma thèse, ces moments où je pouvais penser à autre chose, ou bien recevoir un point de vue extérieur sur la situation ont été très importants. La liste des noms et des souvenirs est malheureusement trop longue pour être écrite ici. Néanmoins, croyez-bien que ces souvenirs existent dans ma mémoire. Among them I would like to add a special word to Sandra Heinzelmann for having been there and hold it through really hard times. Sorry, mein deutsch ist so schlecht wie immer.

Last but certainly not least, thank you Sandra Astete: the right balance between working hard and not getting insane was hard to nd, but with you on my side it looked a lot easier. Unfortunately, I have keep

Introduction

This thesis describes some of the work done in the context of the Symbrion project 1 . This project targets the realization of complex tasks which require the cooperation of multiple robots within robotic swarms (at least 100 robots operating together). Among issues studied by the project are the selfassembly of robots to form complex structures and the self-organization of large number of robots toward the realization of a common task. Subjects of interests are thus modular self-adaptive robots with both strong coordination properties, and swarm-level cooperation.

The challenge faced by this project is that robots are used in open environments which remain unknown until their deployment. Since operational conditions can't be predicted beforehand, on-line learning algorithms must be used to design behaviors. In the use of large groups of robots, multiple considerations have to be taken into account: reduced communication abilities, small memory storage, small computational power. Therefore on-line learning algorithms have to be distributed among robots.

Multiple approaches have already been proposed to deal with on-line decentralized learning of robotic behaviors, such as probabilistic robotics, reinforcement learning or evolutionary robotics (all of which will be later described). However, the problem addressed here is even more complex as groups of robots are considered, rather than of a single robot. Moreover, due to the open-endedness and unpredictability of the environment, we can safely assume that the human engineer may lack the background knowledge necessary to sketch directions such that learning is possible.

As a matter of fact, ensuring the integrity of the swarm (e.g. simply surviving through energy recharge) is not only mandatory prior to address any further user dened task, but also an already very challenging problem. Hence, the problem of ensuring integrity should be placed as the rst element of the following roadmap, which we assume as a set of necessary steps toward achieving tasks with a group of robots in open environments.

Step 1: Ensuring the integrity of robots.

Step 2: Maintaining robots available as a service to the user.

Step 3: Achieve a user-dened task (optimized or not).

1 IP, FP7, 2008-2013 2

Contents

In this thesis we address the step 1 of this roadmap, and states the following: Statement: Collective robotics in open environment requires to perform self-adaptation prior to address user-specied task.

The subject of interest of this thesis, is to design a decentralized algorithmic solution that can be used to guaranty swarm integrity in open environment, using collective robot system with local communication. This is a dicult problem which hasn't been addressed as such in the literature, even if trails exist (see Chapter 3). The main diculty in the resolution of this problem is the need to take into account the environment. Indeed, robots may have to display a large variety of behaviors at the global scale such as cooperation, specialization, altruism, and division of labor, depending on the environment at hand.

Solving such an environment driven adaptation task can be seen as requiring to satisfy two possibly antagonist motivations. The rst motivation is to guaranty the integrity of a maximum of robots within the group in the environment at hand (extrinsic motivation). The second motivation is to allow the necessary interactions between robots and environment to ensure the well functioning of the algorithm (intrinsic motivation). There is therefore a trade-o between conservative approaches (remain stationary, and thus satisfy the intrinsic motivation, event at the risk of preventing the realization of the task), and exploratory approaches (test every possible interactions, and thus satisfy the extrinsic motivation, even at the risk of breaking a robot or getting lost).

In this thesis we introduce and dene the problem of Environment-driven Distributed Evolutionary Adaptation. We propose an algorithm to solve this problem, which has been validated both in simulation and on real robots. This algorithm has been used to study self-adaptation problems in specic environments:

Environments where behavioral consensus is required (see Chapter 4) Environments where robustness in front of environmental changes is required (see Chapter 5) Environments where altruistic behaviors is required (see Chapter 6)

Organization

The rst chapter of this thesis presents a partial review of the robotic eld. This review briey presents the dierent aspects of the robotic eld. A particular focus is given to the design of controllers for robots deployed in challenging environments.

The second chapter aims at presenting the Evolutionary Robotics eld. The focus is given to algorithms used in robots during their deployment. We also present a contribution made to this eld as an illustrative example.

Contents 3

The third chapter presents the issues faced by the decentralized autonomous optimization of behaviors for robots deployed in unknown environments. Dierent methods known to partially address these are reviewed. After highlighting the strength and weakness of each method, the EDEA domain is introduced.

In the fourth chapter the minimal EDEA algorithm, termed mEDEA is presented. The ability of mEDEA to reach consensus is presented in simulation and real world experiments.

The fth chapter is focused on the capacity of mEDEA to address changing environments. Notably, the main evolutionary dynamics of the algorithm are shown.

The sixth chapter shows the evolution of altruistic behaviors by the mEDEA algorithm in front of challenging environments. Moreover, the mechanism at play during the evolution of altruistic behaviors are analyzed.

The seventh chapter conclude this Ph.D. thesis. A discussion on the work done is presented, and perspectives for future works are highlighted.

i.e. they modify their own environment. Finally, both systems can be controlled: either directly in the case of demining robots, or by modifying the source code of the program in the case of the web crawler.

Finally the link between robots and humans is a key elements to dene them. Robots are often seen has a help to humans by performing the tasks humans don't want to do or can't do. However, the range of tasks a robot should do is always under ethical questions. The sight of robots carrying on always more complex tasks raises also questions on the existence of a boundary between humans and robots that shouldn't be crossed. These aspects will be presented with more details in Section 1.1.3.

History

The history of robots can be divided in two parts, before and after the rise of electronics in the 20 th century. The rst part is the area of automata which started in the 8 th or 7 th century B.C. and has reached its apogee in the 19 th century. At the beginning, automata were mystical ideas, e.g. the God

Hephaestus was reported to have created mechanical servants out of gold. In a matter of centuries, these ideas went to reality in Europe and Asia. Archytas of Tarentum is credited with the creation of a mechanical Pigeon in 400 BC. There are also accounts of ying automata in the Han Fei Zi and other texts, which attributes to Mozi (5th century BC Mohist philosopher) and his contemporary Lu Ban, the invention of articial wooden birds (ma yuan) that could successfully y [Needham, 1956].

These automata escalated in complexity from the 10 th century with the creation of clocks (at rst powered by water and later by mechanical springs) equipped with gures performing complex actions.

These works were later reproduced by Leonardo Da Vinci, and Jacques De Vaucanson (creation of a duck eating and digesting food). The apogee of this area was reached with the development of programmable automata, which were used in Japanese's theaters [START_REF] Ichbiah | [END_REF].

The development of electronic devices and later of computers constitutes a major milestone in the history of robots. From this area of the end of the 19 th century and beginning of the 20 th century two major realizations are remembered: the radio-controlled boat of Nicolas Tesla [START_REF] Tesla | [END_REF], and the Electronic Dog of Benjamin Miessner [Miessner, 1919;Hammond, 1921]. These where the rst autonomous (or at least semi-autonomous) electronic systems, partly controllable by a human. At the same time, the robots appeared in the general culture with the coining of the term Robota (translated to robot in English) in the theater piece R.U.R (Rossum's Universal Robots) written by the Czesh author Karel Capek in 1921. Robota is originally a Czesh and Slovak word carrying the idea of hard work, and slavery. We can therefore see that the idea of performing chores for humans is found in the roots of the word robot. Isaac Asimov made the rst use of the word robotic in the liar! novel in 1941. The list of First of continue on with the creation of the rst electronic autonomous robot (later named Turtoise) by William Grey Walter in Bristol, England, in 1948[Walter, 1950]. While many other robots and scientists should be mentioned, an extensive review of all the robots ever created will be far too long [START_REF] Ichbiah | [END_REF]. The recent achievements in robotics are presented in Section 1.2

1.1. Robots (organized by application eld ).

Society's Perception

The advent of robots in modern occidental societies raises multiple questions and concerns. Among them is the fear of the evil-robot. This image has been associated to robots from the rst apparition of the word in the theater piece R.U.R., and is more generally linked to the Frankenstein syndrome (fear of new technologies getting out of control) [Kaplan, 2004]. This image of robots getting out of control of their human master has also been portrayed in multiple movies: from the rst apparition of a robot in a movie (Metropolis, 1927), to more recent movies (The Terminator, 1984 ;Matrix, 1999 ;I, robot, 2004). This is a common view of robotics in western countries despite authors such as Asimov presenting robots as loyal companions (Robbie, 1940 ;A.I. Articial Intelligence, 2001). Noticeable exceptions are Japan and South-Corea, where robots aren't perceived as such a threat to the humankind. The impact of history, and culture's core foundations on the taming of new technologies in the Japanese culture has been highlighted as an explanation to this dierence [Kaplan, 2004].

Moreover, ethical questions are raised on the ever reducing boundary between humans and robots.

On one hand, this phenomenon can be observed by observing robots looking more and more like humans [Ishiguro, 2008]. On the other hands, humans are getting equipped with articial equipments to overcome biological deciencies (pacemakers, bionic hands 1 ). The term singularity has been coined by Vernor Vinge to mark the moment when humans will be able to create machines smarter than themselves. Proponents of the singularity are found in the scientic community. For example Ray Kurzweil argue about its benets for human-kind [Kurzweil, 2005]. On the other side, Joseph

Weizenbaum (creator of ELIZA [Weizenbaum, 1966]) has always been critical of the use of computer programs on problem not understood by humans [Weizenbaum, 1976]. The two sides of this debate in the scientic community are shown in the movie Plug and Pray [Schanze, 2010], targeted at a general audience.

Finally, the notion of uncanny of valley is used to describe the unease provoked by robots imitating humans closely but not perfectly [Mori, 1970]. The rst reason used to explain this feeling is linked to the human awareness of its eventual death. The presence of a robot looking like a human, but not subject to death might trigger in the human subjects the terror managements process normally used when reminded of an eventual death [MacDorman, 2005]. A second reason advocated is the dierence between the expected behavior of the robot (due its resemblance with a human), and the behavior produced [Saygin et al., 2011]. Logically, in order to avoid the uncanny valley it is advised to match the aspect of a robot and its behavior [Goetz et al., 2003].

1 https://www.youtube.com/watch?v=y0_a_sbEglw -Retrieved 17 December 2012

Chapter 1. Autonomous Robotics

Applications

Nowadays, robots are used in a wide range of applications from hobbyist robotic kits to military robots. We will here review these domains while focusing on the challenges specic to each of them. The presentation will gradually goes from robots away from human life, to robots in daily physical contacts with humans. The last section will be specially dedicated to the areas currently explored as research subjects.

Space Robots

The robots sent in space are of primary use to explore this environment where the human presence is rare and dicult. They are used both to reach physically remote places (e.g. the boundary of the interstellar space for Voyager 1), and to perform measures on even further spatial systems (e.g. observation of galaxies thanks to the hubble telescope). These robots are divided in dierent categories: space probes, landers, exploratory robots and nally satellites. Space probes are spacecrafts leaving Earth in order to explore space in order to bring more information on the composition of planets and space. The rst and most famous of its kind, Voyager 1, has been launched the 5th of September 1977. It is also the farthest human made object from earth, and is in pass of leaving our solar system to reach the interstellar space. The space probes are mostly autonomous, and regularly send back to earth informations obtained through their sensors. They can also be found orbiting around planets other than earth, such as Mariner 9, arrived on Mars the 13th of November 1977.

Space probes sometimes carry landers in charge of performing analysis on the celestial object's surface. The rst robot of this type, Lunokhold 1, landed on the Moon in 1970 and traveled over 10 kilometers in 11 months teleoperated from the Baikonur Cosmodrome. During this time, 25 soil analyses were performed out and 20000 photographs were beamed back to earth. Other famous examples are the Viking 1 and 2 which were the rst man-made object on the soil of Mars. These landers were carrying experiments designed to look for the presence of life on Mars. Landers can carry exploratory robots, which perform similar experiments but are also able to move on the planet and therefore perform experiments in more diverse conditions. The latest of this kind is the robot Curiosity, landed on Mars on the 6 th of August 2012.

Finally it can be argued that the satellites orbiting Earth are also a special kind of robots, as they are performing a specic task specied by man made instructions. Some are used much like space probes in order to analyze the composition of our planet. Others are used to transmit communication signal (tv, internet, phone), or localizing objects (GPS, Gallileo).

Robots out of Earth are facing highly specic constraints due to their distance from any human being. The farthest away from earth the robot is, the more autonomy is required. Moreover, since humans can't repair these robots if a failure occurs, every possible problems have to be taken into account during the design phase.

Robots in Hazardous Environments

Back on earth, some environments are too dangerous for humans (e.g. deep water, nuclear power plant). In order to conduct human activity in such environments, specically designed robots are used. Such robots are often teleoperated by humans from a safer remote place. For example, iRobot sent four robots to the Fukushima nuclear power plant after the accident of the 11th March 2011.

Robots have also been used after the Deepwater Horizon oil spill in the 20th of April 2010, as humans can't survive at such depth (∼ 1500m).

Recently, investigations have been carried to use robots in rescue missions, for example in building's rumbles after an earthquake, or during a re [Kamegawa et al., 2004;[START_REF] Baltes | [END_REF].

These robots have to reach autonomously remote places, and be able to help and cooperate with humans [Murphy, 2004].

Industrial Robots

Industrial robots are often kept far away from any human because of their dangerousness. The car industry is known to be the rst user of industrial robots, as the rst industrial robot has been used in the assembly lines of General Motors [Nof, 1999]. These robots are typically moving heavy objects with great precision and are therefore equipped with powerful motors. Moreover, as they are performing always the same task (moving the same kind of object along a xed path), they are usually equipped with few to no sensors. Since the combination of these two characteristics (i.e. powerfulness and lack of sensory information) make them a potential threat to any human, such robots are usually conned in areas where no human is allowed. The Baxter robot developed by Rethink Robotic, and presented in 2012 challenges this problem with an industrial robot able to operate safely close to humans.

The diculties faced during the conception of this type of robots are mostly due to the need of precision, strength, and robustness in a single device.

Security Robots

Robots are used daily for security and military purposes. Military robots are partly used without weapons for demining missions or recognition missions thanks to Unmanned Aerial Vehicle (UAV).

UAVs have also been equipped with weapons and used for oensive missions (e.g. the MQ-1 predator 2 ).

Ground robots used by the army have also been equipped with weapons (e.g. Gladiator TUGV

3 ). For the moment, the decision to re a weapon is always attributed to a human operator.

2 http://www.af.mil/information/factsheets/factsheet.asp?id=122 -Retrieved 12 December 2012 3 http://www.globalsecurity.org/military/systems/ground/gladiator.htm -Retrived 12 December 2012

The use of these robots in the civilian area has recently started with the development of unarmed UAVs at the American-Mexican border from the 1st of September 20104 . Even closer to the everyday life, surveillance robots such as Rovio5 designed by the WowWee company are available to the general public [Sanchez and Alonso, 2012].

These robots are raising ethical questions due to the dangerous combination of autonomy and possibility to kill humans [Lin et al., 1998]. Moreover, the large range of conditions faced by these robots make them dicult to design. Since most of them are at some point teleoperated, the ergonomic of the interface used by the human operator is also of primary importance.

Medical Robots

Medical robots are used as closely as possible to humans but are always under the control of specialists. They are mainly used in two cases: surgical operations, and rehabilitation. During surgical operations, robots are used to enhance the possibilities of minimaly invasive surgery techniques and the capacity of surgeons. They do so by smoothing the hand movements of surgeons and therefore improving their precision [START_REF] Guthart | [END_REF][START_REF][END_REF]. In this context a robot is teleoperated. In some cases the surgeon doesn't need to be in the same room as the robot, and can therefore operate from anywhere in the world [Taylor et al., 2008]. However, these procedures require a special training from the surgeon (which increase the length of operation) [START_REF][END_REF], and leads to higher price of operations [START_REF] Shukla | [END_REF]. Robots are also used to perform routine tasks alongside the surgeon. A key challenge to the design of these systems is to relieve the surgeon, while still remaining under his control [START_REF] Mettler | [END_REF].

Robotic devices are also used for rehabilitation purposes, targeting two aims : the development of therapies solely based on robotics and the use of robots as therapy aids [START_REF] Der Loos | [END_REF]. This eld has already developed into subelds focused on assistive devices, special needs education, mobility, prosthetics and orthotics, and robot mediated therapy. The newest developments are targeting the creation of exoskeletons to increase strength of movements, quality of movements or to aid the realization of movements [Hillman, 2003].

Domestic Robots

Robots are making their apparition in the domestic area by doing some of the chores of humans.

Additionally to the surveillance robots given in example above, robots are now available to clean the oors. The rst of this type was Roomba from the iRobot company (2002) 6 . This robot is now available in multiple series, and other companies are producing the same type of robot.

Robots are also used for the entertainment of kids and adults. This trend started with the apparition of the Aibo7 robot of Sony in 1999 (last year of production 2006). Aibo has been one of the rst robot used widely in the domestic area and has lead to the creation of multiple hobbyist communities. It has also been used as a research platform, in particular for the Robocup autonomous soccer competition 8 . Nowadays, the Parrot ying robot9 , focuses on a lower price and increased interactions between humans thanks to the use of Augmented Reality games. While being mostly used at the moment for research purpose, the ultimate target of the Nao10 robot developed by Aldebaran, is the general public, though it is not clear what it will be used for. Domestic robots have to meet multiple contradictory constraints: low prices, high security, high exibility. These constraints are imposed on the one hand by the variety of usage conditions (especially for entertainment robots), and on the other hand by their close interactions with a non-roboticist population (which won't take the time to tweak their robot every week).

Finally, the last decade has seen the rise of hobbyist robotic construction kits, such as the Bioloid kit from Robotis11 . These kits are currently targeted for a technical savvy young adult population looking for aordable parts. For younger populations, adapted products are available, such as the Lego Mindstorm12 (1998). Lego kits are simpler to use but oer less exibility on the sensors available and the programming methods one can use.

1.2.7

Research Directions

The use of robots in a large number of environments raise multiple scientic questions. We will here present how these questions are addressed by robotic researchers.

Recongurable robots. Dierent tasks might be better solved by robots of dierent shapes.

Recongurable robotics explore the possibility to have robots changing their shapes with regards to the task they must solve and the environment they are facing. The works done in this eld are based on the use of robotic units able to assemble and disassemble in larger structures.

The demonstration of self-recongurable robots have been achieved in simulations [Spröwitz, 2010;[START_REF] Sproewitz | [END_REF][START_REF] Zykov | [END_REF]Stoy et al., 2010b], and in reality [START_REF] Tolley | [END_REF][START_REF] Yim | [END_REF]]. In the later case, the demonstrations are done with a smaller number of units and are facing a long time of reconguration.

12 Chapter 1. Autonomous Robotics Soft robots. Roboticist aim at designing robots able to face a large number of environmental conditions. To this end, a sound choice in the design of a robot's body can reduce greatly the computational eort needed to control it [START_REF] Pfeifer | [END_REF]. For example, the use of a spring in the leg of a robot remove the need to compute a part of the leg's trajectory. This idea of saving computation time, by using the right structure to represent a problem is also found in the creation of control structures. Thus, by creating articial models of the oscillatory structures found in biological brains, Isjpeert is able to create a virtual salamander behaving like its biological counterpart realistically on land and in water [START_REF] Ijspeert | [END_REF].

Micro/Nano robots.

In order to modify autonomously systems of small size (under 1 micro-meter) a new type of smaller robots has to be developed. Robots of the micro-scale are already in use in the industry, biology and surgery [START_REF][END_REF]. Robots at the scale of a nanometer are however harder to design. They are expected to help in medicine by being able to directly interact with viruses, bacteria and blood cells [Kroeker, 2009]. Their capacity to interact with mater at the molecular scale, will be useful in many more applications from the utility fog to new materials and objects [Crandall, 1996]. Despite the growth of the eld, many challenges remains to be solved before attaining such goals [START_REF][END_REF].

Swarm robots.

Complex problems can be solved by coordinating the work of a high number of simple robots (typically more than 100). The incentive behind this approach is two folds [Sahin, 2005;[START_REF] Sahin | [END_REF]:

Robotic swarms are suited for tasks where a presence is simultaneously required in multiple places (e.g. surveillance).

A swarm can continue its task if a robot fails, whereas the failure of a single robot will ruin the mission.

To achieve this goal, swarm robotics take inspiration from behaviors observed in swarm of insects such as ants and bees. Successful realizations have been shown in multiple scenarios detailed in Section 3.3.1. Moreover, robotic swarms are used as a modelization tool for the study of biological questions such as the emergence of altruism [Waibel et al., 2009].

Challenges

Before analyzing, in the next section, how a robot may address objectives, we will clarify what problems a robot may have to address. The design of one robot doesn't necessarily implies to solve all these problems, and the list might not be exhaustive. As the examples given in the previous section have shown, the task of navigation is one of the most essential. Even the robots operating in a virtual world (web crawlers), are in some sense moving in their own environment. For most of the missions attributed to robots this aspect is necessary. The noticeable exceptions to this rule are industrial robots, far too heavy to be moved conveniently.

Manipulation.

Often, robots are manipulating the environment, at least by pushing objects. In many cases the sole purpose of a robot is to move objects from one place to another, such as the factory robots of the Kiva company in charge moving good from storage to conditioning (this company has been recently bought Amazon) 13 . These manipulations are dicult for robots because they take place in a world designed for humans. Therefore, a robot has to be as precise and dexterous as a human will be. The most recent achievement in this domain have been done by Asimo who is now able to serve food and drinks14 .

Human robot interaction.

Interactions between robots and humans are a key to their future developments as domestic partners (Sections 1.1.3 and 1.2.6). To this end, multiple developments are made on the interpretation of speech and human gestures by robots. A strong emphasis is given to the creation of robots whose behaviors can be understood by humans. This has lead to recent researches on the reproduction of facial expressions [Mayer et al., 2010], and the simulation of personalities [START_REF] Gerlinghaus | [END_REF].

The aforementioned problems can be analyzed and solved independently from each other. However, we have identied another set of problems lying at their intersections.

Perception of the environment.

In order to be able to act on their environment, robots should be endowed with perception abilities. These abilities range from the perception of the inner state of robot, to the perception of the world. On the one side, to measure the inner state of a robot, various sensors have been developed: battery state, torque applied by motors. On the other side, in order to perceive the world, vision sensors are usually completed with depth perception devices (telemetric laser, 3d camera), and microphones. In some cases, the perception of the environment or the current status of the robot is performed thanks to sensors situated outside of the robot, such as camera or localization systems.

Autonomy.

Some tasks require the presence of mobile robots for long periods of time (e.g. see Sections 1.2.1, 1.2.4, and 1.2.6). For these situations, the robots should be able to harvest energy from the environment (solar panel,robots that eat [Wilkinson, 2000], or power plug).

Robot Control

In order to see robots performing the tasks identied above in a wide variety of areas, dedicated bodies and software (to control these bodies) are designed. The software component is called a controller.

From its control perspective, robots can be divided in four categories, depending on their level of autonomy. Teleoperated robots follow orders given by a human operator in a continuous stream. The exact speed of each motor of the robot is assigned by the operator. The controller of the robot activate the motors to match the value given by the operator. Depending on the energy available in the robot and the response time of the motors, this task can be challenging. This approach is used when the robot is in close range of the human, and has few degrees of freedom (e.g. demining robots, robots operating in nuclear power plants). However, teleoperated robotics isn't suitable when the delay needed to transmit an order is too important (e.g. robots in space). Moreover, the manipulation of complex robots can't be achieved by this kind of approach, as the control of a large number of motors will be too dicult.

In the domain of supervised robotics [Kan, 1990], a greater level of autonomy is achieved by increasing the mapping's complexity between orders and motors' activation. The operator doesn't assign the value of each motor speed at each step individually, but gives an order of higher level which will be mapped to motors' speed by the controller itself. This approach is used notably to control multiple UAVs by a single user [Ru et al., 2004;[START_REF][END_REF].

The degree of synchronization needed for teleoperated and supervised robots can't be achieved when a robot is in space. Moreover, a teleoperated robot require the constant care of a human operator. For repetitive, tedious tasks, another degree of autonomy is given to robots by mapping a task order to a sequence of actions (task-level autonomy [Giralt et al., 1992]). Thus, an operator orders to a robot to perform a task (e.g. move to a point, retrieve a box, move an object, drill a hole) and save his attention to choose wisely the next task to be performed by the robot.

Finally, full autonomy is considered for robots out of reach of humans over an extended period of time, or performing a set of task requiring no supervision from humans. This is the case of robot developed to watch over and clean houses while the landlords are absent. As the eld of autonomous computing is developing, new areas can be considered, such as the autonomous vehicles driving safely in towns (Darpa Urban challenge [START_REF] Buehler | [END_REF]). Moreover, full autonomy is a required property for multiple-robots systems, because they are raising coordination issues too complex to be solved by a single human operator.

Issues

Robustness to failures

As an autonomous robot can operate in its environment for an extended period of time, changes in its environment and non-critical failures (due either to the normal wear and tear, or to exceptional conditions) are likely to occur at running time. To address these modications, a robot should be endowed with robustness capacities, that is to say with the possibility to autonomously modify its behavior (i.e. modications of the controller).

Multiple approaches have been proposed to realize robust controllers through resilience property. Among them, [Bongard et al., 2006] propose an algorithm where a robotic controller constructs an internal model of its body shape in order to plan the next movement to perform. Later on, when a part of the robot is broken, the controller accurately adapts the model and its behavior. Another way to robustness through resilience is to rely on the redundancy of multiple parts (swarm robotics). With multiple disposable robots, the system performs its task, even when several robots are out-of-order. However, in this case, the sub-tasks have to be re-scheduled among the robots still active [Parker, 2000].

Another way to reach the robustness goal is to add a plasticity property in the controllers designed. Multiple tracks can be followed to obtain this property. A large number of behaviors can be provided at the creation of the controller [Mataric, 1997]. However, this approach is limited by the number of situations conceivable by the designer of the controller. Dierent learning approaches have been proposed to design controllers with plasticity and able to generalize their behavior in front of multiple environments (see Section 1.4.4).

Performance

Measuring robot's performances on a specic task is a key element to assess the quality of a design method. A low performance means that the task would have been better carried by a human, while a high performance leads to benets for humans at least in terms of time.

The no free lunch theorem state that no method can achieve optimality property on every class of problem [START_REF] Wolpert | [END_REF]. To a certain degree if the optimality is ensured for a specic class of problem, the design method might lead to sub-optimal solutions in dierent class of problems. Therefore, design methods have to solve a trade-o between resilience and plasticity properties on one side, and optimality property on the other side.

Optimal and Hybrid Architectures

A rst approach to the design of robotic controller is to optimize trajectories between two known points. This approach is especially useful to the command of robotic arms performing precise time constraints movements [Zefran, 1994]. In this context, the goal is both physical (reaching the right point), and temporal (reaching nishing the movement on time). This approach has been later extended to the optimization of mobile robots' motions [Laumond, 1998].

The rst architecture proposed to design controllers (termed deliberative approaches) where based on the optimal control paradigm. Their origins can be traced back to the work of Nilsson Nils, where the controller is divided in three components: a sensing subsystem, a planning subsystem, and an execution subsystem [Nilsson, 1980]. In this approach, the sensing subsystem is in charge of mapping the sensory information into a representation of the world, from which further computations are done. The planning subsystem is in charge of computing a plan based on, the task to solve, and the representation of the world. Finally the execution layer executes the plan given by the planning layer. These principles have been used for example on the robot Shakey [START_REF] Nilsson | [END_REF].

While being ecient to bring the robot to one precise position, and carry out long term goals, these methods were criticized as being dicult to apply to real world problems [Firby, 1987;[START_REF] Agre | [END_REF]. Moreover the computation of plans can be computer intensive even for trivial movements, which results in a low response time.

On the one hand, the deliberative approaches provide an ecient way to carry out actions toward the realization of a long term goal. On the other hand, reactive approaches are able to react rapidly to informations from the environment. The hybrid paradigm aim at combining the best of these two approaches [Gat, 1998;Firby, 1989].

These architectures are composed of three layers running in parallel, termed: controller, sequencer, and deliberator. The controller is composed of multiple programs similar to the behaviors of the subsomption architectures (i.e. reactive loop coupling sensors and actuators). An external signal to the controller determines which behavior will be activated at any moment. The deliberator runs the, high level, time consuming, planning algorithms, and interacts with the sequencer. The sequencer choose which behavior to activate based on the up-to-date information from sensors, and the potentially deprecated but highly informative results from the deliberator. A review of the successful implementations of this paradigm, as long as a comparison with the deliberative and reactive paradigms are

given in [Nakhaeinia et al., 2011].

Probabilistic robotic approaches are focused on the realization of robots able to deal with the uncertainty of their environment. For this, they rely on the two following statistical tools: bayes rule and bayes lters [Thrun et al., 2005a]. The main idea is to represent the world as probability distributions, and act on it based on this probabilistic information. The perception and motion models (used for all task of the probabilistic robotics) are built thanks to implementations of bayes lters [START_REF] Sahin | [END_REF]Thrun et al., 2005c]. Probabilistic robotic methods are used to address three typical tasks: Robot localization within a map of the environnement [Ortin et al., 2004;[START_REF] Cox | Modeling a dynamic environment using a bayesian multiple hypothesis approach[END_REF], construction of a map of the environment [Thrun, 2002;Tomatis and Nourbakhsh, 2002], and planning and control of the robot actions [START_REF] Kaelbling | [END_REF]Thrun et al., 2005b]. These methods are relying on computational intensive algorithms, which results either in the integration of powerful computing unit in the robot, or necessary approximations in the computation of statistics.

In known environments or when highly reliable sensors are used, other methods presented above might 1.4. Robot Control 17 be preferred.

Reactive Robots

The reactive paradigm is one of the approach proposed to address these issues. Under this paradigm, the robots' actions are computed solely based on the information available through sensors. Therefore these approaches are focused on the design of robust controllers. The term situated is also used to name these approaches, placing an emphasis on the grounding of the controller in the robot and therefore in the world. We will see how the performance issues have been addressed by successive

contributions. We will also analyze the inherent issues linked to the use of this approach.

The braitenberg vehicles are the rst to illustrate this approach even if only by experiment of though [Braitenberg, 1986]. In this work, robots (presented under the term vehicles) are reacting to the presence of light solely based on direct links between sensors and motors.

Subsomption. Subsomption architectures are based on the wiring of simple behaviors together in order to produce higher level behaviors [Brooks, 1986;Brooks, 1990]. Within this paradigm illustrated in gure 1.1 a behavior can either be inhibited (by other behaviors' suppression output), or restarted. Within this paradigm, the human engineer can design more complex behaviors. However the design of controllers able to follow long term plans remains a goal out of reach.

Biologically-inspired approaches The biologically-inspired approaches pioneered in 1991 by Wilson [Wilson, 1990] focus on the reproduction of animal behaviors in order to produce an Articial Intelligence (the articial animals produced are called animats). The incentive to do so is to use the reproduction of animal intelligence as a proxy to human intelligence. It can be opposed to every other approaches as being a bottom-up approach where previous paradigm reviewed where top-down.

Chapter 1. Autonomous Robotics This approach has lead to the reproduction of insects' behavior [Meyer, 1995], automatic evolution of behaviors [Gruau, 1994], and also to produce original behaviors for ying robots [START_REF] Doncieux | [END_REF]. 1.4.4 Learning and Optimization

The works reviewed previously rely on a knowledgeable human engineer able to foresee much of the situations the robot will face during its operating time. Moreover, it is implicitly supposed that the designer is able to cope with the complexity of both the environment and the robot. While these assumptions may sometimes be fullled, they are invalid for complex situations (e.g. robot performing a large range of manipulations). A way to solve this issue is to conceive algorithms able to design automatically robot controllers.

Reinforcement Learning problems.

Reinforcement Learning (RL) is a eld of Machine Learning (ML) concerned with the optimization of an agent's sequential actions, in interaction with a specied environment, in order to maximize a possibly delayed reward [START_REF] Sutton | [END_REF]]. Adding learning abilities to a robot's controller is a specic case of RL where: the agent is the robot's controller, the environment is the world as perceived by a robot through its sensors, actions are the movements a robot can do thanks to its motors, and rewards are the quality evaluations given by a human designer (directly or through the design of a reward function). Due to the consideration of a robotic setup, specic issues have to be addressed since, the states, actions, and reward spaces are continuous and noisy.

One way to solve RL problems is to use the TD methods which aim at learning an optimal policy based on Bellman equations [START_REF] Sutton | [END_REF]]. These equations are based on the computation of a cumulative reward associated to each state, from which the optimal controller is deduced.

Q-learning algorithms use this method to learn a Q-function, which characterizes the predicted reward of performing a certain action in a certain state. By following the maximal reward path in each state, and updating the Q-value after each action, the controller of a robot will learn to behave optimally.

Evolutionary robotics.

Evolutionary Algorithms (EA) are population based stochastic optmization algorithms. Within these methods, a population of solutions to a problem is iteratively evaluated, and re-generate from its best members. These methods are based on the evaluation of a controller candidate, and therefore don't rely on the computation of a model of the environment. They can be viewed as biologically inspired policy search methods [Moriarty et al., 1999;[START_REF] Heidrich-Meisner | Evolution strategies for direct policy search[END_REF], which are suited to solve Reinforcement Learning problems. Moreover, with these methods dierent controller's representation can be explored [Back et al., 1997].

The proposition to use these methods in robotic scenarios has led to the creation of the Evolutionary Robotic (ER) domain [START_REF] Cli | [END_REF], which has since demonstrated numerous applications and opened the way to other domains [Walker et al., 2003;Gross et al., 2006b]. The dierent representations, evaluations, and replacement procedures, used in robotics scenarios are detailed in Chapter 2.

Developmental robotic.

While being also biologically inspired, the developmental robotic eld (also called epigenetic robotics) focuses on the development of the mind by going through Autonomous Mental Development (AMD). The goal of developmental robotic methods is to achieve behavioral capacities similar to the human ones by imitating the incremental cognitive development observed in animals [Weng et al., 2001]. The methodological dierence with ER lies in the considered time length of learning: a lifetime for developmental robotic, multiple generations for ER methods.

Since the rst system of this type (Cresceptron [START_REF] Weng | [END_REF]), the eld has grown in importance and has achieved major results, such as learning vision guided movements [START_REF] Olsson | [END_REF], and learning how to navigate in an environment [Provost et al., 2006]. A recent review of these achievements can be found in [Asada et al., 2009]. Naturally, this eld grows in close interaction with the ER eld and combined approaches have already been proposed [START_REF] Doncieux | [END_REF].

Summary and Conclusions

In this chapter we gave a brief overview of the robotic eld, which is focused on the design of robots for a large number of applications. Each application eld leads to dierent challenges and require robots tailored to its need.

We have highlighted multiple issues in the design of robotic controllers, namely :

Robustness to failures: Due to the normal wear-and-tear, or exceptional conditions, a robot might be partially broken. Moreover it might be deployed in highly dierent environments. Controllers should be robust to all these unpredictable events.

Performance: In order to be useful to the end user, a controller should display an optimal behavior for certain class of problems. However this property comes as a trade-o to the property mentioned above.

We have reviewed the strengths and weaknesses of dierent approaches to the design of robotic controllers. Among the design methods reviewed, learning methods stand as good candidates to address the trade-o between resilience, adaptability and optimality properties.

In the remaining of this thesis, the adaptation of robots to unknown environment will be addressed. As such, learning algorithms stand as good candidates toward ensuring the integrity of a group of robots in this context. In the next chapter the eld of Evolutionary Computation will be reviewed, as it as already shown its ability to stand as an ecient learning method for robotic behaviors in unknown environments, including in an on-line setup.

Chapter 2

Evolutionary Robotics

In this thesis the problem of the integrity of a group of robots in unstructured environments is addressed. This is a challenging problem as it is poorly dened, and its resolution can't rely solely on the expertise of the human designer. The most promising method to solve this type of problem is to use Evolutionary Algorithms tailored for robotic scenarios. Indeed this approach has already proven to provide valuable results in context where the objective function is ill or poorly dened, and where few background knowledge is available. In Sections 2.1 and 2.1.1 we will introduces the Evolutionary Computation main principles, how it can be used for the design of autonomous robots, and the issues faced by this approach in relation to our scenario. Questions raised by the design of tness functions along with solutions proposed in the literature will be presented in Sections 2.2 and 2.3. One of our contribution to this eld is presented in Section 2.4.3, as an illustration of some of the challenges faced when addressing on-line adaptation.

Principles of Evolutionary Computation

Evolutionary Computation (EC) is a research area of Computer Science concerned with the design of biologically inspired optimization methods called Evolutionary Algorithms (EA). These algorithms are based on a population of individual going through a stochastic optimization process [START_REF] Baeck | [END_REF]. Within the scheme presented in gure 2.1 the population goes through recursive phases of selection and mutation. These two mechanisms (inspired from the two main principles drawn by Charles Darwin in his book Species Origins) can be dened as follows:

Variation: Variation's operators are used to bring novel solutions in the population. In this phase stochastic variation operators are applied to a restricted set of individuals in order to produce new original individuals.

Selection: The aim of the selection process is to increase the quality of the individuals present in the population. During the selection process each individual is given a tness value characterizing its performance on the problem to solve. The best individuals (i.e. those with the highest tness values), are likely to be selected to produce the population at the next generation. Selection operators.

Multiple selection scheme exist, and are used dierently depending on the problems at hand (details in [Eiben and Smith, 2008a]). We highlight here the most studied mechanisms:

Fitness proportional selection: Within this selection scheme, a roulette wheel mechanism is implemented such that the individuals with the highest tness are the most likely to be selected.

This mechanism has been well studied, and numerous problems exist: premature convergence, lack of selection pressure, and dependence to transposition of the tness function.

Ranking selection: This variation of the tness proportional selection uses a roulette wheel mechanism based on the ranking of the solutions. This mechanism avoids the main drawbacks from the tness proportional selection.

Tournament selection: When the population is very large, or distributed among multiple systems, computing the distribution of individuals performance on the entire population can be hard or even impossible. The tournament scheme has been designed to deal with this issue by relying on small subsets of the population. Within this scheme, k individuals are chosen randomly in the population to be evaluated. The individual with the highest tness is selected.

With this scheme the selection pressure is easily controlled by varying the tournament size k.

Variation Operators. Two dierent types of variation operator are mainly used in Evolutionary Algorithms:

Mutations: These operators are used on a single individual, from which they produce a (slightly) modied version. Variations are used to bring new original solutions in the population.

The implementation of these operators can vary depending on the properties of the genotypic space (continuous or discrete). Independently of the search space, genes under mutation are selected randomly with a probability named mutation rate. Depending on the individuals' representation in the genotypic space, dierent variation, and selection operators are preferred.

Encoding Schemes

Through the history of Evolutionary Computation dierent representation scheme of the individuals have been studied, each suited to dierent type of problems [Eiben and Smith, 2008b].

Genetic Algorithm (GA). Researches in this sub-eld aim at solving combinatorial optimization problems. Solutions are represented as strings over a nite alphabet [Holland, 1975]. String of bits are the archetypal example, but other base system can be considered. The commercial software Evolver1 is based on this approach. Rule based controllers are one example of controllers that can be optimized thanks to Evolutionary Algorithms. Successful applications of this approach are shown in single [Grefenstette et al., 1990;Schultz and Grefenstette, 1992] and multi-robot problems [Grefenstette, 1992;[START_REF] Schultz | [END_REF].

Evolutionary Strategy (ES). ES algorithms are concerned with the optimization of solutions to continuous problems. Individuals are encoded as strings of real values [Schwefel, 1995]. In this context the main variation operator considered is the mutation. This approach can be used over a large number of optimization problems [START_REF] Herdy | [END_REF]. Articial Neural Networks are one example of robotic controllers optimized thanks to ES algorithms. Since the rst works on wall avoidance and photo-taxis [START_REF] Cli | [END_REF][START_REF] Nol | [END_REF][START_REF] Nol | [END_REF], this representation has been used for example on multi-robot problems (see Section 3.3.2), and vision based task [START_REF] Harvey | Seeing the light: articial evolution, real vision[END_REF].

Genetic Programming (GP). This methodology uses Evolutionary Algorithms principles to modeling problems, that is to say to optimize models which produce a maximal feet between pairs of input and output. This sub-eld is based on individuals represented as tree structures [Koza, 1992]. GP has been applied to the design of robotics controller in multiple contributions, for example: the design of an electronic circuit [START_REF] Koza | [END_REF], the design of a program controlling a robot [Nordin and Banzhaf, 1997;Lee et al., 1997], and the design of controllers used in multi-robot scenarios [Kala, 2012]. Within this approach the solutions evolved tend to grow in size regardless of the performance. This problem is known as the code bloat [Amil et al., 2009]. Multiple solutions are proposed to face it in [Smith, 2000]. Moreover GP relies often on a LISP interpretor to read the encoded solution, which might be too computationally expensive for a robot computation capacities.

Other encoding schemes have been proposed in the literature such as Evolutionary Programming which is originally based on the optimization of Finite State Machines [Fogel, 1962], or developmental systems which are focused on links between biological development, and evolution [Oyama et al., 2001].

2.1.2

EC and Robotics [START_REF] Doncieux | Exploring New Horizons in Evolutionary Design of Robots[END_REF] have distinguished three use cases for the application of Evolutionary Computation methods to the eld of robotics:

Parameter tuning: In this context, robotic systems have been modelized beforehand, and the control parameters of the system have been identied. However the optimal value of these parameters isn't known and can't be found neither by an analytical method (i.e. method not known) nor by an exhaustive search (i.e. too many parameters). Evolutionary Algorithms are then used to explore the space of parameters in search of a solution. A survey of such approaches used for the control of electronic systems in general is found in [START_REF] Fleming | [END_REF].

Another survey of these approaches applied to the optimization of bio-inspired Articial Intelligence systems is found in [Floreano and Mattiussi, 2008].

Evolutionary aided design: Evolutionary Algorithms are also used to characterize the behavior of a system. In this context Evolutionary Computation methods are used to explore the design space and propose a variety of solutions to the human engineer, who can then analyze the results in order to gain a deeper understanding of the system. This has been used for example in the design of UAV's controllers [Hauert et al., 2009], the control of apping wings [Doncieux, 2009] and lately to the friction stir welding problem [START_REF] Bandaru | [END_REF]. Multi-objective Evolutionary Algorithms are a special kind of Evolutionary Algorithm designed to nd the best trade-os between multiple objectives [Deb, 2001]. This type of algorithm has been used to nd relations between design parameters in a process called innovization [Deb and Srinivasan, 2008a;Deb and Srinivasan, 2008b].

Evolutionary synthesis: The use of Evolutionary Algorithms isn't restricted to the optimization of robot's controllers but are also used to optimize their overall design (structure and controller). These approaches take into account the embodied theories by considering the controller of a robot, its morphology, and its interaction with the environment all at once in the 2.2. Fitness Functions 25 design process. This approach is used for example in the Golem project where robot structures and control architectures are optimized at the same time to be latter produced by 3D printer and deployed in the real world [Lipson, 2007]. This eld of ER is still recent and work is ongoing to address scalability and robustness issues [START_REF] Hornby | [END_REF][START_REF] Gauci | [END_REF]Mouret and Doncieux, 2009a].

Fitness Functions

The formulation of the tness function is an important step in the design of an evolutionary robotic experiment. We present here the main types of tness functions seen in the literature, and take inspiration from [START_REF] Khatib | [END_REF] to build this classication.

Behavioral tness function. This class of tness function, is suited if the human engineer can provide a large amount of knowledge on the problem to solve. Within these methods, the behavior of a robot is closely monitored in order to assess its performance. This type of tness function was used in the rst works of the ER eld [START_REF] Floreano | [END_REF]. It proved its relevance in dierent locomotion tasks such as object avoidance, object following, wall following, and light avoidance [START_REF] Banzhaf | [END_REF]. Another example is found in the locomotion of an octopod robots [Gomi and Ide, 1998]. This approach leaves few degrees of freedom to the evolutionary process and implies that the human engineer has a precise idea of how to perform the task.

Tailored tness function. This approach is based on the measure of task completeness, combined with one or multiple behavioral measure terms detailed in the previous paragraph. For example, in a photo-taxis task, a tailored tness function could be composed of two main components. The rst one rewarding a robot that arrives at the light source, the second one maximized when the robot face the sun. This type of tness function is task-specic but tailored by the human engineer to accommodate the given problem. It is one of the most used class of tness function in the ER eld. Among the achievements made, one can count ball collection [START_REF] Homann | [END_REF], coordinated movements [Quinn et al., 2002], sequential tasks [START_REF] Doncieux | [END_REF], and gait learning for a quadruped robot [START_REF] Hornby | [END_REF]. Within these approaches, the human engineer should know the elements necessary to the success of the task.

Aggregate tness function. Aggregate tness functions reward the accomplishment of a given task or sub-task but uses no information from the human engineer on how to do the task. This type of function aggregates all aspects of a robot's behavior in a single term. For example, if the task is to come closer to an object, the tness function will be the nal distance between the robot and the object. Aggregate tness functions have been applied successfully in multiple cases such as gait learning [Earon et al., 2000;[START_REF] Augustsson | [END_REF][START_REF] Zykov | [END_REF]Chernova and Veloso, 2004] and goal soccer tasks [START_REF] Hornby | [END_REF]].

On the one hand, if the human engineer doesn't have any knowledge about the system optimized this method can be used to produce original solutions. On the other hand, at the beginning of an experiment every strategies are performing equally bad. It is then dicult to determine which solutions should be selected to the next generation(bootstrap problem) [START_REF] Kawai | [END_REF].

Another class of tness function targeting the same class of problems are the multi-objective tness functions. This approach propose to divide a tness function in multiple simple objectives and then explore the Pareto front of these objectives [Deb, 2001]. This approach can be used to solve the bootstrap problem by adding a novelty objective (which favor original solutions regardless of their performance [START_REF] Lehman | [END_REF]) to the main objective [Mouret and Doncieux, 2009b].

Implicit tness function. Implicit tness functions are used when the task to perform isn't known beforehand by the human engineer, and might change with time. In this context the optimization process is based on the pressure to survive. That is to say, a survival indicator (often energy) is used as the tness function of the Evolutionary Algorithm. The optimization of the behavior for a given task is then the implicit result of the maximization of the tness function.

The maximization of the tness function will lead to the evolution of dierent strategies, depending on the environment at hand (possibly composed of other robots). Consequently, this type of tness function can be used in numerous scenarios without any modications.

This approach is still in its infancy, and is mainly used in Embodied ER (see Section 3.3.2). We have also found one application investigating the notion of creativity, where [Bird et al., 2008] use this approach to study the traces of robots as drawings resulting from the pressure to harvest energy in order to survive.

2.3

Transfer to Real Robots While in simulation the world is perfect (no noise), modiable at will, and the evaluations reliable, the real world introduces noise in sensors and actuators. As a consequence solutions optimized in simulation might not answer to a real problem but only to a problem occurring in simulation [Brooks, 1992]. This results in the observation of signicantly dierent behaviors when control architectures are transfered from simulation to reality (reality gap [Jakobi et al., 1995]). Moreover, robots have multiple limitations which make them ill-adapted to run Evolutionary Algorithms on-board [START_REF] Matari¢ | [END_REF][START_REF] Nol | [END_REF]:

Cost: Robots remain expensive devices. Unfortunately , the evaluation of poor controllers likely to damage one robot is common at the beginning of an evolutionary run.

Speed: Evolutionary Algorithms need a high number of iterations in order to evaluation one solution. The main incentive is to actually assess the quality of a solution in a signicant part of the conditions encountered.

Reliability: Despite the latest improvements, robots remain subject to failure, which results in multiple repairs slowing down Evolutionary Algorithms.

In order to solve these issues two main solutions have been proposed:

Modify the simulation environment so that the solution optimized have a similar behavior in simulations and in the real world (see Section 2.3.1).

Produce new Evolutionary Algorithms to carry on evaluations on real robots (see Section 2.3.2) [START_REF] Pollack | [END_REF].

Simulations

Design of simulation environment. [Miglino et al., 1994] advocates that keeping simulation simple and adding an optimal level of noise is a solution to the reality gap problem. For example, [START_REF] Jakobi | [END_REF] propose a framework to design minimal yet ecient simulations, and [START_REF] Nol | [END_REF]Miglino et al., 1995] propose to model the behavior of real sensors in the presence of the object composing the environment. In the later method the behavior of the actuators are modeled from measures made in real conditions. This approach is highly ecient (no decrease of tness observed), but can be used only in a restricted set of conditions (i.e. when the task is known beforehand and the environment measurable through the sensors used on the real robots).

Learning real world dynamics.

In order to avoid the beforehand task of building a simulation, methods have been proposed to learn it based on the measures of the robot itself. This way, an always up-to-date model is built by taking into account the actual shape and behavior of the robot. This approach can be realized by combining an Evolutionary Algorithm with a TD algorithm [START_REF] Kamio | [END_REF](the TD algorithm is used to ll the reality gap). However, it has been later criticized for its need of numerous real-world data [Bongard and Lipson, 2005], and new approaches have been proposed based on the co-evolution of environment model and robotic controllers [Bongard and Lipson, 2005;Bongard et al., 2006;Koos et al., 2009].

2.3.2

Embodied Trials.

In order to address the reality gap problem, the evaluation procedures can be carried on the robots directly. On the one hand, the evaluation times are longer and the work of the human engineer is often increased by the use of real robots. On the other hand, solutions optimized are t to real world problems, and the human engineer doesn't have to design an adapted simulation environment. This approach has been used in numerous cases where it is dicult to build an accurate simulation, such as gait evolution for legged robots [Gomi and Ide, 1998;Earon et al., 2000;[START_REF] Andersson | [END_REF][START_REF] Wol | [END_REF]Okura et al., 2003;Gu et al., 2003;Chernova and Veloso, 2004], legged robots playing football [START_REF] Hornby | [END_REF], snake-like robots made of shape-memory alloy [START_REF] Mahdavi | [END_REF], and ying robots [START_REF] Zuerey | [END_REF].

Within the embodied trials methodology, the human engineer has still a role to play by re-setting the initial conditions of each evaluation, running the Evolutionary Algorithm in a computer, preventing any damage done to the robot, or repairing it in the worst case. Moreover, this approach makes the assumption that the operational conditions will remain constant and conform to the conditions used during the learning phase.

2.4

Beyond Classic ER 2.4.1 Morphological and Controller Co-evolution.

Recent works have investigated the possibility to benet from morphological changes in order to acquire robust behaviors in front of unstructured environments. This approach has been rst envisioned in [Sims, 1994]. [Bongard, 2011] has shown that the co-evolution of body and mind leads to faster optimization and more robust solution. This approach has been rst used by [START_REF] Lipson | [END_REF]Lipson et al., 2006], where bodies and controllers are simulated in the same time and then brought to the real world thanks to a 3D printer. It has also been demonstrated by using aordable modules in [START_REF] Macinnes | Crawling out of the simulation: Evolving real robot morphologies using cheap reusable modules[END_REF]. However these works are relying on the simulation of behaviors before there transfer to real robots, and are therefore facing the reality gap problem. One solution to address this problem is to design robots able to modify autonomously their morphologies at running time, that is to say self-recongurable robots [Stoy et al., 2010a]. These robots can be used in combination with Evolutionary Algorithms in order to co-evolve the morphologies and controllers of robots [Yim et al., 2007;Eiben et al., 2010b].

2.4.2

On-line On-board Evolution.

In classical use of evolution for the design of robot controllers, the human engineer is deeply involved in the management of evolutionary runs. Moreover, once the a solution has been evolved, the evolutionary process is never used again [Eiben et al., 2010b]. We are presenting here an approach to go beyond these two features, that is to say to evolve robotic controllers without human intervention, and continuously adapting during the operation time. These approaches are called on-line approaches as opposed to o-line approaches used in a typical design then use fashion.

Beyond Classic ER 29

Another consideration is given as to where evolutionary operators are used, i.e. in a computer (oboard) or in the robot themselves (on-board). In order to free the human engineer from continuous management, the Evolutionary Algorithms are run in the robot.

Specic issues have to be considered for the design of on-line on-board Evolutionary Algorithms:

Noisy tness evaluation: First, the on-line, on-board evaluation of robot controllers leads inevitably to noisy tness functions. This is principally due to the variability of the initial conditions used to evaluate the genome. The evaluation of a controller starts with the robot as it was left by the previous controller. Therefore an evaluation can start in a dicult part of the environment or with a partially broken robot.

Robotic constraints: The use of real robots implies a limited computational power. This constraint implies the design of lightweight Evolutionary Algorithms, with small population sizes, which reduce the exploratory capacity of the algorithm, and therefore increase the risk of premature convergence.

The on-line on-board approach has been demonstrated in obstacle avoidance and object attraction [START_REF] Nordin | [END_REF] , obstacle avoidance based on vision [Floreano et al., 2002;Marocco and Floreano, 2002], and gait learning in a quadruped robot [START_REF] Hornby | [END_REF]. However, these contributions have dealt with the issues raised above by tailoring Evolutionary Algorithms to a specic task. Because of the lack of general mechanism to deal with the issues of on-line on-board algorithms, it is dicult to use these contributions on any task.

This approach has been considered for problems involving multiple robots [Watson, 1999]. In this context, the Evolutionary Algorithms can benet from the possibility to evaluate solution in parallel.

However, multiple challenges relative to the decentralization of the algorithm, and the interactions between robots have to be addressed. This approach is reviewed in Section 3.3.2.

An Illustration of Challenges in On-line On-board Evolution: the 1+1restart-online Algorithm

In this section, one of our contribution to on-line on-board evolutionary robotics is summarized [START_REF] Montanier | [END_REF]. The (1+1)-online adaptation algorithm from [Bredeche et al., 2009] is presented along with a limitation regarding its ability to perform global search in the space of possible solutions. A new algorithm is described, which addresses the trade-o between local and global search by relying on a restart procedure whenever the algorithm is stuck in a local optima.

In the (1+1)-online algorithm, three mechanisms for the (1+1)-ES algorithm have been designed

to deal with issues of on-line on-board evolutionary robotics (presented in the previous section):

Local and global search: The mutation operator is the gaussian distribution N (0, σ). A low value of σ (resp. high) will result in a local (resp. global) search by minor (resp. major)

Chapter 2. Evolutionary Robotics modications of the original genome. In the (1+1)-online algorithm the σ parameter is initially set to a low value and increased as long as the champion isn't replaced (gradual shift toward a global search). Each time a challenger replace the champion, σ is reset to its initial low value.

Thanks to this mechanism, the search will be broaden to new regions of the search space if a local optima is found.

Re-evaluation: Individuals may get lucky or unlucky during evaluation depending on the environment at hand. This is a typical problem related to tness noise. An ecient solution is to re-evaluate individuals, as proposed by Beyer [Beyer, 1998].The re-evaluated tness overwrite the tness of the champion. This is done to promote individuals with a low variance in their performances. One of the drawback of the overwriting method is that good individuals could be replaced by inferior but lucky individuals. If an individual is lucky during its rst evaluation but has a low mean tness, it will not survive the next re-evaluations. As a consequence, the Evolutionary Algorithm won't be stuck with bad individuals.

Recovery: Since the Evolutionary Algorithm runs without human intervention, the robot isn't repositioned after each evaluation of one individual. For example, a genome may be evaluated starting from completely dierent initial conditions, such as in front of a wall or in a tight corner.

To avoid penalization of good genomes, a recovery period is introduced: during this time, the robot behavior is not considered for evaluation (ie. free of charge), which favors genomes that display good performance independently from the starting position.

In the (1+1)-online algorithm an issue has been identied regarding the abilities of the algorithm to perform global search. More precisely, if a really good champion is found, other challengers aren't considered for a long period (until the champion get unlucky in one of its re-evaluation). This hinder the ability of the algorithm to nd a large number of solutions to a given problem.

In order to address this issue a restart mechanism [Auger and Hansen, 2005] is proposed based on the number of re-evaluation. The indicator chosen to trigger the restart mechanism is the number of re-evaluation. The incentive to do so is that a champion has to be highly capable and robust in order to obtain good results at each re-evaluation. If the champion fails one of its re-evaluation it will be replaced by the next lucky challenger. Therefore, the number of re-evaluations is a measure of the champion's quality in comparison to the surrounding challengers. A high number of re-evaluations (threshold to be determined experimentally) indicate that the current champion is a local optimum from which the algorithm can't escape. Therefore, once a specied threshold of re-evaluation is reached, the algorithm is restarted. The resulting algorithm is named (1+1)-restart-online and described in Algorithm 1.

The objective function used in experiments to test the (1+1)-restart-online algorithm aim at optimizing a controller for exploration and is close to the one described in [START_REF] Nol | [END_REF]:

f itness(x) = n t=0 V t * (1 -V r ) * (1 -D M )
where V t is the speed factor, V r is the rotation factor, and D M the value of the less active sensor, all values are normalized between 0 and 1. Distance sensors returns higher value when they are close to a wall. Therefore, individuals achieve high tness value while moving fast and forward and avoiding walls.

Algorithm 1 The (1+1)-restart-online Evolutionary Algorithm.

for evaluation = 0 to N do if random() < P re-evaluate then if re -evaluation -count < M ax -re -evaluation then Recover(Champion) F itness Champion = RunAndEvaluate(Champion) re -evaluation -count + + else σ = σmin Champion = RandomGenome() F itness Champion = 0 Challenger = RandomGenome() F itness Challenger = 0 end if else Challenger = Champion + N (0, σ) {Gaussian mutation} Recover(Challenger) F itness Challenger = RunAndEvaluate(Challenger) if F itness Challenger > F itness Champion then Champion = Challenger F itness Champion = F itness Challenger σ = σmin else σ = σ • 2 end if end if end for
The (1+1)-restart-online has been tested in simulation with a micro-controller featuring real hardware of the Symbrion project, and in real world with the popular robotic kit Bioloid2 . The Figure 2.2 shows the real wold experimental setup, and Figure 2.3 shows the simulation experimental setup.

Results of experiments have shown that the 1+1 restart-online algorithm is actually able to optimize wall avoidance behavior. Moreover, we have demonstrated that the 1+1 restart-online Chapter 2. Evolutionary Robotics algorithm address the identied design ow of the 1+1-online algorithm, which leads to wider exploration of the search space, potentially making it possible to visit more local optima than the previous implementation, and possibly increasing the probability to end up in a global optima. It should also be noted that results from simulations actually show that divers behaviors can be obtained (see [START_REF] Montanier | [END_REF] for full details). It is important to remind the reader that this section presents only a summary of a contribution in order to highlight important issues in Embodied ER such as noisy evaluations and lack of help from the human engineer. The bottom line is that whenever on-line ER is considered, specic algorithms must be deployed.

This algorithm has later been extended toward a (µ + 1) strategy [START_REF] Haasdijk | [END_REF]. The (µ + 1)online algorithm has then been exented to multi-robot problems in [Eiben et al., 2010a;[START_REF] Haasdijk | [END_REF][START_REF] Weel | [END_REF].

Summary and Conclusions

In this chapter the application of Evolutionary Algorithms to the robotic eld has been presented. After a general presentation of ER and its main applications, a focus has been done on two issues faced by this eld: the design of a tness function, and the transfer of solutions to real robots. Finally recent approaches beyond classic ER have been presented. Within one of these elds (on-line on-board ER), one of our contribution has been presented as one example to illustrate issues faced and possible solutions.

Notably, in every cases reviewed, the tness function is designed by the human engineer. Even implicit tness functions (which are used to address ill dened problems ) are designed by the human engineer. This aspect raises issues in front of complex environments. In these contexts the task to perform can become more complex due to environmental constraints. In worst cases the tness function might not be able to formalize every aspects of the environment and task at hand. One example of such complex situation is the conservation of robots integrity in front of unknown environments. In the next chapter, we investigate how to address such complex situation without relying on possibly misleading background knowledge from the designer, that is, without tness function.

Chapter 3

Environment-driven Distributed Evolutionary Adaptation

In this chapter we present the challenges faced in the autonomous adaptation of groups of robots for ill dened tasks and unknown environments (see Sections 3.1, and 3.2). A solution to this class of problem is a rst step toward the maintenance of a robotic service necessary to the optimization of behaviors. A clear denition of this problem and the challenges faced in its resolution is necessary to the creation of an algorithmic response.

In Section 3.3, we will present the elds related to this problem, and some of the solutions proposed to solve the challenges highlighted. In Section 3.4 we show why these solutions proposed can only address part of the challenges. Finally, this new class of problem is formalized in Section 3.5.

Scenario

As stated in the introduction, we are interested in large groups of robots deployed in environments unknown a priori to the human engineer [START_REF] Baele | [END_REF]. This situation happens for example if groups of robots are sold for household usage, as every houses are potentially dierent. In this context robots will have to solve a task which might be dened in a later phase (e.g. once the nal consumer uses the group of robots). The maintenance of robots integrity is a service necessary to the optimization of behaviors toward the realization of a specic task in an unknown environment. We assume that this service has to be provided independently of the task considered (e.g. building monitoring in the search of intruders, or explore building rumbles), and the robot at hand (e.g. wheeled robots, or legged robots). Moreover this has to be done through unpredicted environmental changes (e.g. the group of robots is sold from one consumer to another). Due to unknown variables (i.e. task to solve and environment at hand), good solutions to maintain integrity can't be pre-programmed by the human engineer beforehand. An auto-adaptive algorithm is a solution to ensure the integrity of robots independently of the environment, the type of robots, or the task. The auto-adaptation process will be solely driven by the environment and its impact on robots integrity.

We are addressing this challenging question in the context of populations of autonomous robots, able to perform local communications, immersed in an unknown, and possibly changing, environment, Chapter 3. Environment-driven Distributed Evolutionary Adaptation which implies :

No external intervention: Human engineers cannot act on the robots once they are deployed. Therefore, if a robot ends up in a dicult situation or even breaks down (partly or completely) two scenarios can be envisaged. On the one hand, part of the remaining robots can repair the damaged robot or bring it back to a place where it can be repaired (e.g. a factor or the human engineer). On the other hand, if a repair isn't possible (e.g. broken robots on mars), other robots can continue to perform the task with the remaining members of the group only.

No external communication: The deployment of a large number of robots implies the use of low cost robots. As a consequence, the communication abilities of such robots are limited, which implies that robots can only communicate with each other (external informations aren't available to the group of robots).

Challenges

Since the human engineer doesn't know beforehand what the environment will be, behaviors ensuring the integrity of the group of robots can't be predicted. Therefore, ecient strategis (from an integrity point of view) have to be found autonomously. We consider here a scenario where the human engineer isn't present to repair damaged robots, which means that the number of robots can't increase with time but might decrease due to hardware failure. Therefore, the algorithm developed has to solve autonomously the following challenges.

Autonomous exploration: Due to slow environmental changes, evolution of interactions between robots, variation in the number of available robots, dierent ways to perform the task in the environment can arise gradually. In order to take advantage of such changes, robots must search autonomously for new behaviors. Moreover, the search mechanism should capitalize on successes and failures of previous behaviors.

Restart of the search procedure: The environment might also change abruptly, thus modifying dramatically the most adapted survival strategy. To face such situations the search mechanism must be able to restart without the intervention of the human engineer. Consequently, the search mechanism has to be embedded in each robot and operate continuously and autonomously.

Exploration/Exploitation trade-o: On the one hand, the continuous search of new solutions impacts negatively the integrity of the swarm, as the evaluation of poor solutions can damage robots.On the other hand, the continuous use of the best known behavior will results in the impossibility to adapt after an environmental change. Consequently a mechanism is needed to solve the trade-o between using the best known way to survive (exploitation of the solutions found) and exploring new solutions.

Distributed cooperation:

We have to consider the lack of a central entity synchronizing the experiences of all robots currently deployed in the environment. This directly results in the distribution of the learning process in the population of robots. Each robot must base its learning only on information transmitted locally by other robots and its own experience of the environment. In the remaining of this chapter, we will see that multiple issues arise from this challenge (combined with the previously mentioned challenges), such as the emergence of consensus toward strategies promoting survival at the population's scale and not only at the robot's scale.

Real robots' constraints:

Due to real world robotics constraints (low computation power, and few sensory informations available), each evaluation of a robot behavior will be noisy. Moreover, since the starting conditions from each evaluation aren't normalized by a human operator, each evaluation is potentially erroneous.

Related Work

In this section, three approaches are reviewed that could stand as possible candidate to address the challenges at hand. The rst one is called Reinforcement learning applied to multi-agent systems and is presented in Section 3.3.1. The goal of the learning algorithms studied in this domain is to optimize agents' behavior on problems found in decentralized systems. We will then present in Section 3.3.2 the Embodied Evolutionary Robotics (EE) methods. These methods are part of the ER eld and aims at addressing the issues relative to the use of real robots. Finally, in Section 3.3.3, we present the Articial Life domain. This domain corresponds to the study of the living systems' properties by relying on their reproduction on articial substrate, and a special emphasis will be put on open-ended evolution.

Reinforcement Learning for Multi-Agent Systems

There are mainly two ways to deal with learning issues in decentralized systems. The rst one, called distributed problem solving, use a central instance organizing the work of slave nodes. The second one named Multi-Agent Systems (MAS) is based on the interactions between multiple autonomous agents. The use of Temporal Dierence methods (also called RL methods, and presented in Section 1.4.4) in MAS denes the domain called Multi-Agent Reinforcement Learning (MARL). MARL methods consider agents learning autonomously behaviors in order to solve a common task. Based on the reviews of [Busoniu et al., 2008;[START_REF] Panait | [END_REF][START_REF] Stone | [END_REF], we present the coordination problems investigated, and one of the main issue arising from the use of MARL methods.

Two classes of problems studied in MARL and Game Theory are of special interest to our scenario:

The coordination problems focus on the search of nash-equilibrium among multiple strategies [START_REF][END_REF]Lauer and Riedmiller, 2000].

This eld is also interested in the study of social dilemmas such as the Iterated Prisoners' game or the Tragedy of the Unmanaged Commons [START_REF] Glance | [END_REF]Lichbach, 1996].

The coordination of multiple robots have been investigated through the following problems:

Cooperative Multi-robot Observation of Multiple Moving Targets (CMOMMT):

This problem is precisely dened in [Parker, 1997]. The aim is to optimize distributed control strategies for multiple autonomous robots collaborating in order to follow multiple moving targets.

Area coverage: Dierent formulations of the same idea are proposed in the literature [START_REF] Ahmadi | [END_REF]Morales, 2003]. The goal is to reduce as much as possible the time between two successive observations of any part of the environment by a team of robots. Certain avors of the problem introduce dierent degrees of priority between dierent parts of the environment.

Robocup Keep-away: The Keep-away task of the Robocup is dened in [START_REF] Stone | [END_REF].

A team of 3 robots currently in possession of a ball have to conserve it while 2 robots of an adversarial team try to intercept it. Various formulations of the same task have been proposed, varying notably in the number of robots involved in each team.

Object pushing: Within this problem lies two specics sub-problems. The rst one is concerned with the shifting of one object too big to be moved by a single robot. The second one focus on the aggregation of multiple small objects by a team of robots [START_REF] Asada | [END_REF].

For MARL methods, the robotics domain constitute a special case where the world is continuous and the observations are partial and noisy. [Brooks and Mataric, 1993] have identied four main types of learning in robotic systems:

Learning numerical functions for calibration or parameter adjustment: In this setup, the problem is to tune parameters in order to compensate the unknown sensor drift, environment changes, and the unmodeled properties of the mechanical system. These parameters are learned autonomously by the controller. Since the eect of each parameter isn't known beforehand, the learning is based solely on the performance of the controllers.

Learning about the world: In this setup the goal is to organize informations from the world in which the agent is placed. This knowledge is then used to learn autonomously how to act in the world. Most of the contributions to the learning eld in AI ts in this category.

Learning to coordinate behaviors: In this setup the selection of behaviors is optimized with regards to the current environmental state. As a matter of fact, Reinforcement learning methods are successfully used to learn the mapping from sensory state (environmental conditions) to action state (behavior).

Learning new behaviors: In this setup primitive actions are combined toward the achievement of a specic goal. The goal is to reduce the involvement of human engineers implied by the previous learning methods.

The main diculty in applying Reinforcement Learning methods in robotic is to be found in the second type of learning (learning about the world). This is because all the Temporal Dierence methods (TD methods, presented in Section 1.4.4) are designed to face a discrete world composed of a nite number of states, actions and rewards. As a consequence, a continuous world becomes too large to be tractable by such methods.

Moreover, this problem, already present when a single agent is under study, is getting worse when multiple agents try to synchronize in order to perform the optimal action. For example, in o-line resolution of problems under a nite time horizon, decentralized partially observable Markov decision process are NEXP-complete [Bernstein et al., 2000], and heterogeneous agents' action selection problem is NP-complete [Parker, 2000]. Two approaches have been proposed to solve this type of problems. [Hansen et al., 2004] construct incrementally polices by eliminating iteratively dominated strategies. [Szer et al., 2005] rely on the evaluation of complete sets of strategies (one per agent). The latest methods can exploit additional informations such as the distribution of start state distribution, or the presence of common reward functions.

The problems considered in this thesis are to be solved on-line without a nite time horizon, and are therefore more complex. In order to reduce the complexity of the learning process multiple approaches have been proposed to either structure the problem or introduce heuristics. In the following we present the main approaches developed so far:

Policy search One way to deal with the great number of states and actions is to work directly in the policy space. In this case a policy is created from a set of parameters, its value is computed after a complete trial. The best policy is obtained by following the gradient of the policies' value in the parameters space [Rueckstiess et al., 2010;[START_REF] Sehnke | [END_REF].

One important contribution has been done in [Mataric, 1997;Mataric, 2001;[START_REF] Ahmadi | [END_REF], where policy search algorithms are used to optimize the parameters of hand-coded behaviors. This eectively reduce the search space from large continuous spaces to a space composed of few parameters, and is applied to numerous problems (see Table 3.1). However, this approach is restricted to the space of basic behaviors a priori hand-coded by the human engineer. Consequently, new solutions to unforeseen problems can't be learned with this method.

Relational representation: In the work presented in [Morales, 2003], a new space of relational representation (both in the search space and the action space) is dened. Relational representations are encoding the transition between two states or two actions. Within this approach, reinforcement learning algorithms are used to optimize the mapping from relational state to relational action. While this solution eectively reduces the search space, states and actions have still to be dened by the human engineer.

Predictive model: A predictive model is an estimator of a robot's current state which is based on historical sequences of inputs and outputs. In [START_REF] Asada | [END_REF] a predictive model is continuously updated thanks to the information given by multiple robots. The state vector produce is a discrete variable (build from observations of the continuous world) that can be used in reinforcement learning algorithms. This model has been tested in a scenario including two robots, which are learning sequentially. However this approach relies on either a central controller, or global communication, which is dicult to obtain with a high number of robots (typically a hundred in our scenarios).

Clusters: Neighbor states in a continuous space can be considered as a unique state in a discrete space. Multiple methods have been used to create discrete states from regions of the continuous space. [Fernandez and Parker, 2001], uses a method called Vector quantization which requires a stopping criterion to avoid the raise of many small meaningless clusters. The design of this criterion requires a priori knowledge on the space to cluster.

Another method, termed tile coding [Sutton, 1996], is successfully demonstrated in [START_REF] Kostiadis | [END_REF]Stone et al., 2001]. This method relies on layered grids, each encoding a binary feature of the environment. Therefore, it doesn't need a stopping criterion, but the human engineer knowledge of the problem are used to generate meaningful binary features.

Sampling: A sampling mechanism will reduce the search space by performing the learning only on a restricted set of all the available states and actions initially present in the continuous space. This idea has been explored in the Pessimistic algorithm proposed in [Touzet, 2004]. This algorithm extends the idea of lazy sampling of the state and action spaces (originally proposed in [START_REF] Sheppard | [END_REF]), to a team of multiple robots. While this algorithm doesn't rely on knowledges from a human engineer to build its nite action and state space, it does so during an initial sampling phase. Consequently, this algorithm isn't able to deal with modication of the environments without a complete reboot of the whole robotics team. Each work listed above use its own specic version of Q-learning. In most cases, the modications come from necessary reformulation due to the use of specic state and action spaces. These algorithms ares listed in Table 3.1.

Article

Space reduction method Learning method Experimental problem [Mataric, 1996;Mataric, 1997] Hand-coded behavior Reinforcement Learning

Object pushing [START_REF] Ahmadi | [END_REF] Hand-coded behavior Reinforcement Learning

Area coverage [Urieli et al., 2011] Hand-coded behavior CMA-ES Robocup [Morales, 2003] Hand-coded behavior rQ-learning Area coverage [Asada et al., 1999] Predictive model Modular reinforcement learning

Object pushing [Fernandez and Parker, 2001] Clustering Vector Quantization Q-learning CMOMMT [START_REF] Kostiadis | [END_REF] Clustering Residual Q-learning [START_REF] Baird | [END_REF] Robocup Keep-away [Touzet, 2004] Sampling Lazy q-learning CMOMMT Table 3.1: Methods to reduce the search space in MARL

We consider the use of hand-coded behaviors as one of the most promising method to address the challenges of our scenario. This consideration is based at rst on the autonomous adaptation capacities demonstrated, which takes into account the absence of central coordinator and the use of local communication. Secondly, the presented algorithms are able to handle changing environments, as shown in [Mataric, 1997] where the behavior learned by agents depends on a cyclic schedule (oscillating between night time and day time). Finally, this approach has been demonstrated numerous time on real robots [Mataric, 1997;Mataric, 1996;[START_REF] Ahmadi | [END_REF]Urieli et al., 2011], and has been used in up to 8 robots in simulation [START_REF] Ahmadi | [END_REF], which is the highest number of robots considered in the approaches reviewed.

These approaches are based on the assumption that the environmental conditions are well known to the human engineer. Based on this assumptions, the use of behaviors designed beforehand by a human engineer is a sound choice. However, we aim to address unknown environmental conditions. As a consequence, a new mechanism to produce autonomously original behaviors has to be used. On-line decentralized Evolutionary Algorithms are considered to address these challenges, as they will benet from the parallel use of multiple robots, and avoid the reality-gap problem (presented in Section 2.3).

[ Watson, 1999] proposed the Embodied Evolution (EE) approach where the Evolutionary Algorithm is run by multiple-robots (on-board). This goes beyond On-line On-board evolution by relying on multiple evaluations of controllers (performed in parallel on multiple robots) in order to get rid of the evaluation noise and therefore free the human engineer from any manipulations.

Moreover, the use of multiple robots let the possibility to break a portion of them during the evolutionary process. This approach is useful in scenarios where the task domain can't be simulated, a centralized global coordinator can't be implemented, the robots must learn in the eld, the task is interactive, and the reproductive behavior itself is under adaptation [START_REF] Ficici | [END_REF]Watson et al., 2002]. These ideas are also found in a more restricted framework presented in [Simoes and Dimond, 1999], centered around two phases in the life of robots (working and mating), and relying on a global communication network. We will review the contributions to this eld depending on how the evolutionary operators are used, that is to say in a distributed or encapsulated fashion [Eiben et al., 2010b].

Encapsulated. Algorithms performing in an encapsulated manner make use of evolutionary operators in the robot themselves. In practice, this result in the constitution of genome's pool, evaluated one after another thanks to a time-sharing system, and ranked accordingly to their performances. Based on this ranking evolutionary operators are applied on the best genomes to produce the new genomes to evaluate at the next generation. This approach doesn't benet from the parallel evaluations of one genome in multiple robots (and therefore multiple environmental conditions). The other robots are then mere moving obstacles increasing the complexity of the environment.

In the work presented in [König et al., 2008] the focus is placed on the possibility to create a controller based on developmental methods. Therefore, the evolutionary mechanisms used aren't design specically for the problems faced by Evolutionary Algorithms in multiple robots.

The second implementation known is focusing on the creation of evolutionary mechanisms to face EE challenges [START_REF] Haasdijk | [END_REF]. In this contribution a (µ + 1) algorithm is encapsulated in one robot, and a reevaluation mechanism is added to face the inherent tness evaluation noise. The use of this algorithm in multiple robot scenarios has been shown in [START_REF] Haasdijk | [END_REF]. [Huijsman et al., 2011;García-Sánchez et al., 2012] have shown the limits of such algorithm due to the absence of communications between robots. This limitation prevent the evolution of more ecient behaviors since controllers aren't evaluated in parallel on multiple environmental conditions. Moreover, each evolutionary process (one per robot) doesn't benet from results obtained by other robots (potentially better). Finally, within this approach the evolution of coordination between robots is also hindered by the lack of communications between robots.

Distributed.

In distributed EE approaches evolutionary operators rely on the interactions between robots. This approach has been initially envisioned in the original presentation of the EE domain, and the seminal works under the PGTA algorithm [START_REF] Ficici | [END_REF]Watson et al., 2002]. This algorithm relies on an implicit tness function (based on energy) to modulate the rate of transmission (proportional to the level of energy) and reception (inversely proportional to the level of energy). The selection mechanism result from the interaction between the robots, which depends on their relative tnesses. A modied version integrating the use of a learning algorithm within PGTA has been proposed in [Wischmann et al., 2007]. This approach has been also used to study the emergence of self-assembly and self-reproduction by relying on implicit tness (based on speed) in [Bianco and Nol, 2004].

Within the distributed EE eld, [Schut et al., 2009b;Schut et al., 2009a] proposed the Situated Evolution approach, which relies on Embryo Based Reproduction mechanism (EBR). EBR is characterized by the use of an embryo always improved by cross-over with encountered genomes. When a robot with a better genome is met, the embryo is replaced by this genome. A well studied example of Situated Evolution algorithm is the ASICO algorithm which make use of EBR and is similar to the contributions of Schut [Prieto et al., 2009;[START_REF] Prieto | [END_REF]Trueba et al., 2011;[START_REF] Trueba | [END_REF].

Finally, [Karafotias et al., 2011] propose to use the distributed evolutionary principles while still relying on more than one genome by accessing a P2P network of communication. This approach has been successfully compared to the encapsulated version of (µ + 1) on phototaxis, fast forward and patrolling tasks. On the one hand, these approaches use the same three mechanisms as the encapsulated approaches: the constitution of a genome's pool, the ranking of genomes thanks to a time-sharing evaluation system, and the constitution of new genomes based on the best genomes of the genome's pool. On the other hand, encapsulated and distributed approaches rely partly on communication facilities of robots. Within these approaches genomes of the genome's pool are ranked with relation to tness value, and a portion of each robot's genome's pool is broadcasted to other robots.

Within this approach [Nehmzow, 2002] proposed an algorithm based on the encapsulation of a (1+1)ES algorithm [Schwefel, 1981] in each robot. [START_REF] Usui | [END_REF]] proposed a more complex scheme, where two lists of genomes are saved: one containing the genomes to evaluate, the other containing a list of the best genomes to be send to other robots (the ttest a genome, the highest chance to be send to other robots). From the list of best genomes and the received genomes, evolutionary operators create new genomes which will be later evaluated. [Huijsman et al., 2011] proposed an algorithm based on the distributed Evolutionary Algorithm

The optimization in a continuous domain is done thanks to evolutionary operators applied to robotic controllers.

The Evolutionary Algorithms are running on the robots in order to avoid the reality gap problem.

The controllers' parameters can be exchanged between robots in order to evaluate controllers in parallel on multiple environmental conditions.

EE methods are objective driven evolutionary algorithms. This objective is formalized by the human engineer as a tness function. As presented in Section 2.2, a large variety of tness function can be used to describe with various level of precisions the goal targeted. As such, implicit tness functions are designed by the human engineer but gives few information about the best behavior. However, we are interested here in problems where the goal thought can't be dened at the individual scale by the human engineer. More specically the maximization of the integrity depends highly of the environment at hand, and the interaction between robots. Therefore, the selection pressure has to be dened at the population scale, and driven by environmental constraints.

Open-ended Evolution in Articial Life

Articial Life (ALife) is a eld of study which examine systems related to life, its processes, and its evolution. The questions targeted by the ALife community are numerous and can be summarized in three main categories [START_REF] Bedau | [END_REF]Bedau, 2003]: How does life arise from the nonliving? What are the potentials and limits of living systems? How is life related to mind, machines, and culture? From a theoretical ground multiple contributions have been made to highlight the minimal properties needed to classify a system (biological or articial) as alive. The Autopoietic systems [START_REF] Varela | [END_REF]McMullin, 2004], Chemical Automaton systems [Gánti, 1975;[START_REF] Ganti | [END_REF][START_REF] Munteanu | [END_REF]] (Chemoton) are two such formalizations initially published practically simultaneously in the 70's. Some reviews analyze the two theories in a common framework [Bersini, 2010;Bich, 2010].

Apart from the main theories on the origin of life and its denition, experimentations have been done to answer questions on the behavior of living systems, and the conditions necessary to obtain these behaviors in articial substrate. These experimentations are classied in three elds : the wet, the soft and the hard [Bedau, 2003]. The wet ALife is mainly concerned with the study of the structures, functions and interactions of molecular components at the heart of life [Couzin, 2002;[START_REF] Blight | [END_REF]. The hard eld aims at the reproduction of selected key-properties of living system in hardware systems such as robots. This eld is discussed at length in this manuscript (an overview can be found in Chapters 1, and 2). The soft community aims at studying the key properties of life by re-creating it in digital simulations. The silico substrate of computers is chosen for its easy manipulation, ease of experimentation and low risk. Multiple behaviors are target for reproduction in articial substrat, such as: self-organization and self-replication phenomenons, evolution of complexity (with the practical case of the origin of multi-cellularity), and the evolution of complex behaviors such as language or cooperation.

More precisely the soft ALife aims at studying the key elements for the evolution of these specic phenomenons observed in the biological realm. To study such issues, we can highlight two methods. Firstly, analytical systems are based on the modelization of a population as a set of equation. The resolution of these equations allow the prediction of outcomes (such as the presence of dierent strategies) with relation to experimental settings. They have been used for example to study the eciency of dierent strategies [START_REF] Axelrod | [END_REF] the impact of noise level on these strategies [Nowak and Sigmund, 1993;McNamara et al., 2004]. However these methods aren't well suited to study the impact of the spatial environmental conditions such as terrain topography, and the locality of food resources.

Secondly, agent-based systems are based on a population of heterogeneous agents simulated step by step and interacting with each other. These methods are designed to study the emergence of high level phenomenon resulting from these interactions in dierent environments [START_REF] Macal | Tutorial on agent-based modeling and simulation[END_REF].

These systems can be combined with Evolutionary Algorithms, i.e. the strategies used are modied by random mutations, and a selection mechanism favor the most successful strategies. These systems are used to study the key mechanisms and conditions necessary for the evolution of complex high-level behaviors (such as cooperation and communication). Notably, one goal targeted by these systems is

the realization of open-ended evolutionary dynamics [Maley, 1999;[START_REF] Bedau | [END_REF]]. Among the contributions to this eld, we present two main approaches:

Modelization of biological dynamics: Contributions to this approach focus on the study of evolutionary dynamics through dierent simplication's level of biological systems. The most known simulator addressing open-ended issues is Tierra [Ray, 1992], which has shown the evolution of parasites, hyper-parasites, and sociality. Other works not focusing on open-ended issues have addressed for example the evolution of shapes [Yaeger, 1994], ecological systems [START_REF] Gras | [END_REF][START_REF] Golestani | [END_REF], and the interplay between three adaptation mechanisms (evolutionary, individual, and social) [START_REF] Gilbert | [END_REF][START_REF] Eiben | [END_REF].

Modelization of biological systems: This approach is focused on the modelization of real biological systems, and notably the comparison between data measured in the real world and obtained by simulation. Within this approach the open-ended evolution properties have been studied based for example on historical data [Epstein et al., 1996]. Other works are used to study the properties of bacteria and viruses. [Adami et al., 1994;Knibbe et al., 2007;Misevic et al., 2012].

Studies in ALife have shown mechanisms to reach open-ended evolution properties. Part of these contributions are focused on the interplay between survival of agents and population dynamics. These systems are therefore a source of inspiration to address problems relative to the integrity of a group of robots, though they have not been designed, and used, for this particular purpose.

Issues

In Section 3.3.1 we have seen that MARL methods are able to learn near optimal solution, while solving the trade-o between exploration and exploitation. However we have also highlighted that MARL methods are ill-adapted to face the on-line search of large continuous search spaces used in robotics. Within this eld, all the methods known to reduce the search space to tractable size relies on a human engineer with a priori knowledges of the problem at hand. Therefore, the resolution of the robotic constraints challenge reduces the ability to solve the autonomous exploration challenge.

3.5. Proposal: Environment-driven Distributed Evolutionary Adaptation 47

The Evolutionary Robotics methods (Chapter 2) propose to optimize the parameters of dierent type of controllers which can express a large number of behaviors (dierent type of controllers are reviewed in Section 2.1.1). While this allow the exploration of new solution unforeseen by a human engineer, in most cases this exploration isn't autonomous. Indeed Evolutionary Robotics methods are typically used in a design, then use fashion which rely on a centralized process.

The approaches reviewed under on-line on-board evolution and EE brings us close to a solution to the scenario presented in Section 3.1. They are all concerned with embodied evaluations which makes sure that the solutions found correspond to real world problems as perceived by the robot. On-line on-board approaches propose methods to overcome the problems of noisy tness evaluation function and restricted capacities of real robots when only one robot is used. While addressing similar problems in multi-robots setup, Embodied trials methods are also challenging self-organization issues. However, these methods are still relying on the knowledge of a human engineer to measure the survival skills of a controller, that is: to dene a tness function.

The soft ALife domain, by studying the way life appears and is sustained, is looking for reliable mechanisms to ensure the survival of a system (biological or articial). The methods of the ALife domain propose to use evolutionary operators relying on the reproductive and survival capacity of the agents. If an agent is able to survive longer and transmit more often its genome, the next generation of agents will most likely inherit from it. By this mechanism the population is always ensuring its integrity by selecting the most adapted agents. The adaptation method is independent from any a priori knowledge of the human engineer, and can therefore face the autonomous exploration challenge. It is important to note here that these methods address primarily modelization problems and not design problems. These methods have been used in virtual environments where the addition ex-nihilo of new agents, or the deletion of ill-adapted agents, is common place. The production of new robots require a great amount of human and can't be done autonomously by other robots. Likewise, the destruction of a robot is an irreversible action and will be avoided as much as possible. As a consequence, we need a way to abstract the addition and removal of agents when considering a robotic substrat. In practice, this will result in the emulation of selection and mutation mechanisms in real robots while maintaining the number of functioning robots as high as possible. and Environment-driven Distributed Evolutionary Adaptation (EDEA): a perspective from the nature of the selection pressure to ensure the survival of one robot, and transmit itself to other robots, the more it should be used by other robots. By this mean variations of strategies eciently maintaining integrity are used and improved at all time. This approach is directly inspired from the mechanism of natural selection as modeled in ALife systems.

As in the EE method, robots aren't added and removed, but controllers' parameters are exchanged between robots. The main dierent with EE algorithms, is that the success of a genome isn't computed thanks to a function relying on the agent's activity (e.g. sensor values, and actuator values). In EDEA methods (alike some ALife systems), the success of a genome is measured only based on its capacity to survive and spread in the current environment.

It follows that the key to EDEA is the environment-driven nature of the adaptation process. This may be seen as the result of two possibly conicting motivations: Extrinsic motivation: An agent must cope with environmental constraints in order to maximize survival, which results solely from the interaction between the agent and its environment (possibly including other agents).

Intrinsic motivation: A set of parameters (i.e. genomes) must spread across the population to survive, in accordance with the algorithmic nature of the evolutionary process. Therefore, genomes are naturally biased toward producing ecient mating behaviors as the larger the number of agents met, the greater the opportunity to survive. By this mean the whole evolutionary process is continuously driven by the environment toward ecient and sustainable strategies.

The level of correlation between these two motivations impacts problem complexity to a signicant degree: a high correlation implies that the two motivations may be treated as one while a low correlation implies conicting objectives. An ecient EDEA algorithm must address this trade-o between extrinsic and intrinsic motivations as the optimal genome should reach the point of equilibrium where genome spread is maximum (e.g. looking for mating opportunities) with regards to survival eciency (e.g. ensuring energetic autonomy).

Figure 3.1 proposes a simplied illustration of these principles by a ctive simulation of one generation. The rst image shows the beginning of a simulation: each robot and start with an empty genome list. The second and third images show the robots moving in their environment (each robot's behavior is controlled by its own active genome), and exchanging genomes when they are close enough. The forth image shows the situation at the end of the generation: the red genome has spread more and thus has a higher probability of begin selected. In this case the red genome has a probability p = 1 to be selected by two robots, and the two other genomes only get p = 0.5 in one robot. The next generation will contain slightly mutated copies of the original genomes. This example highlights the environment-driven nature of the evolutionary process. Indeed, the selection probability of each genomes depends only on the behavior resulting from its expression. The behavior produced depends of the environment in which the genome is found. This point of view is highly dierent from works in objective-driven ER, where the selection probability depends of the evaluation of the behavior by a tness function.

The overall motivation behind the work presented in the remaining of this thesis is the study of general evolutionary adaptation algorithms that can be implemented on real robotic hardware. The next chapter present a novel distributed evolutionary adaptation algorithm for use in a population of autonomous agents. The remaining chapters are dedicated to the study of the evolutionary dynamics of this algorithm in dierent environments (real or simulated).

Summary and Conclusions

In this chapter we detailed the challenges raised by a scenario where a group of autonomous robots have to maintain their integrity in an unknown and possibly changing environment. After having reviewed relevant work in related domains we have further dened the issues faced in this scenario. Three important issues have been identied: a) The lack of information on how to survive in an environment, b) The lack of measure for the survival skills of a controller, c) A population composed of a limited number of robots (upper bound). To solve these issues we have shown the importance of relying on the environmental pressure to drive the learning process. Such environmental pressure is the sole information available to assess the quality of one genome with regards to integrity issues. These aspects have been formalized in a new class of problem, the Environment-driven Distributed Evolutionary Adaptation (EDEA). Finally, we have highlighted in an illustrative example the mechanisms needed to the realization of EDEA algorithms. The thinking behind the mEDEA algorithm is to consider strategies as atomic elements and the population of agents as a distributed substrate on which strategies compete with one another. This approach is better illustrated using the Selsh Gene metaphor [Dawkins, 1976]: one specic strategy (or set of parameters, or genome) is successful if it manages to spread across the population, which implicitly requires to both minimize the risk for its vehicle (i.e. extrinsic motivation) and to maximize the number of mating opportunities (i.e. intrinsic motivation), although the two may be contradictory.

The mEDEA algorithm is original since it is the rst algorithm (to the best of our knowledge) to address the trade-o between extrinsic and intrinsic motivations in collective robotic systems within open environments.

The detailed description of the mEDEA algorithm is given in Section 4.1. The evolutionary dynamics of this algorithm are studied, with a particular emphasis on the evolution of behavioral consensus in Section 4.2. Lastly, the algorithm is implemented and tested with real robots, thus illustrating the transferability to real world problems (Section 4.3). The work presented in this section is based on our publication [START_REF] Bredeche | [END_REF].

Algorithm

The mEDEA algorithm (minimal EDEA), described in Algorithm 2, is distributed among all agents. A given agent is driven by a controller, whose behavior depends of a set of parameter (e.g.

Articial Neural Network). A set of controller's parameters is called a genome. At any moment, the parameters of an agent's controller are extracted from a specic genome, termed active genome.

Each agent is endowed with a communication device which is solely used to broadcast information within a predened communication radius. In this work the communication abilities of each agent is used to broadcast its active genome. Finally each agent has a memory unit, which is used to store the genomes received thanks to the communication device. This is very similar to the illustration shown in the previous chapter (see Section 3.5). This algorithm 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 a random sampling selection among the list of imported genomes. It is important to note that no tness value can even be computed, which makes random selection the only option here. Consequently, there is no selection pressure on a local agent basis. In fact, the selection pressure is active at the global level (population) rather than at the local level (agent): the most widespread genomes on a global population basis are more likely to be randomly sampled on average.

Variation operator: The variation operator is chosen to be rather conservative to ensure continuity during evolution. Generating altered copies of a genome only makes sense if there is some continuity in the genome lineage: with no variation the algorithm will simply converge on average toward the best genome initially existing in the population. In the following, we assume a Gaussian random mutation operator, inspired by Evolutionary Strategies [Beyer and Schwefel, 2002], with which the locality of mutation can be easily tuned through a σ parameter.

Replacement operator: Lastly, the replacement of the current active genome to control a given agent is achieved by (1) local deletion of the active genome at the end of one generation (i.e. a limited pre-dened amount of time) and (2) the random selection of 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 ecient mating strategies, as a given genome will only survive in the long run through more or less slightly dierent copies of itself.

Impacts of environmental uctuations on genomes' performances is smoothed by the denition of the variation operator, as newly created genomes are always more or less closely related to their parent. As a consequence, genotypic traits result from a large number of parallel evaluations, on two scales:

The spatial scale: Closely related copies sharing the same ancestor may be evaluated in dierent agents of the swarm. It is very unlikely that two agents will experience the same evaluation conditions. Therefore copies of the same genome will be evaluated under multiple environmental conditions.

The temporal scale: Each genomes is strongly related to its ancestors. Therefore, the same lineage of genome, carrying the same main behavioral traits, will be evaluated in multiple conditions through time.

A single poorly ecient genome may be picked by chance as the active genome of an agent once in a while. Therefore the following question arise: does a family of closely related genomes manage to survive in the population, despite the presence of more ecient competitors ? We hypothesize that larger swarm will result in lower sampling bias. In other words, better than average genomes will get a better chance of surviving if the population is large. This hypothesis is investigated in the experiments presented in this chapter.

A fundamental requirement for ensuring selection pressure is that there is a strict constraint on the maximum number of genomes N g to choose from during selection with regards to the population size N p . N g < N p -1 must hold for at least one agent (i.e. the received genome list should contain strictly less than all genomes from the population minus the local genome). Otherwise, no selection pressure will apply as genome survival probabilities would be uniform over the swarm. Then again, this worstcase scenario does not necessarily imply failure of the algorithm: the lack of selection pressure may imply a random walk in the genotypic space thanks to the variation operator (i.e. random genetic drift [Futuyma, 2009]), possibly leading to a new possibly more interesting region of the genotypic space, despite a temporary loss of selection pressure.

Preliminary Experiments: Evolution of Behavioral Consensus

In this section we study how the agents behave as a population, that is to say, we study the populationwide dynamics resulting from agents local interactions. While the local interactions between the agents are well known, the resulting global dynamics might be dicult to predict. This diculty arises from the fact that new strategies appear continuously (represented by genomes) during a simulation, and that their survival in the population depends of other strategies present at that moment. Moreover, the survival of a genome is achieved by a trade-o between intrinsic and extrinsic motivations. Thus, the global outcome of all the local interactions can be unpredictable and dynamic. In this section, we are interested in the following questions: does the whole population converge to one specic canonical behavior ? If not, how dierent are the behaviors ? Are there transient behaviors ? Is it possible for two sub-populations with dierent behaviors to co-exist (i.e. multiple stable attractors) ?

Given a swarm of agents, each running mEDEA, how are ecient behaviors acquired and how are they distributed across the population. In practice, we study the emergence of consensus, where a population of agents may choose to exploit, or not, singularities in the environment (e.g. a particular element arbitrarily located in the environment).

Problem and Experimental Setting: the Two-suns Setup

Figure 4.1 provides a snapshot of 80 agents within the arena, where a particular landmark is present (located on the East side of the arena). We refer to this landmark as the sun. A population of autonomous agents is placed in an empty arena, and there is no environmental constraint except the pressure to wander around mating with one another. The sun is an intangible object that provides no advantage whatsoever -i.e. there is no energy in this setup. Two sensory inputs give the orientation (relative angle) and distance to the sun to the agent's controller. Once in a while (every 50 generations), the sun changes location from East to West (and back).

The motivation for this setup is to provide an environment where several possible behaviors are likely to emerge and might be observed. Indeed the sun may here be considered either as a distraction and ignored, or as an environmental feature from which to take advantage. Our hypothesis is that in the latter case we shall be able to observe behaviors at the level of the swarm, with possibly one, or several, emergent strategies. In fact we might expect that the sun will be considered as a compass and thus used as a mating location by some agents, even though there is no way for the agents to explicitly reach a consensus. Of course ospring of a particular genome are likely to conserve a given mating strategy, resulting in a more or less widespread behavioral consensus.

In order to evaluate the emergence of consensus two experimental parameters have been taken into account: population size and range of radio communication. Population sizes vary from 10 to 80 agents and radio communication takes three possible values: r = 64, r = 32 and r = 16, resulting in a total of 213 experimental settings. All experiments described in this section result from 24 independent runs for each parameter setting (i.e. a total of (213 * 24 =)5112 runs), performed on a cluster of PCs with two AMD Opteron dual-core 1.8GHz processors running Ubuntu Linux. Each experiment lasts for 150 generations and the sun switches location every 50 generations (either East or West of the arena). Detailed parameters used for experiments presented here are given in Table 4.1.

On a practical viewpoint, one experiment takes approx. 15 minutes to be performed using one core of a AMD Opteron dual-core 1.8GHz processor. The home-brew agent simulator roborobo is programmed in C++ and features basic robotic-inspired agent dynamics with friction-based collision (available at: https://code.google.com/p/roborobo/). This simulator is used for all the simulations presented in this thesis. The source code and parameters for all experiments presented here is available on-line in the Evolutionary Robotics Database1 .

Representation

Specications for the autonomous agents are inspired by a traditional robot conguration, with 8 proximity sensors arranged around the agent body and 2 motor outputs (translational and rotational speeds). Two additional setup dependent inputs are considered (utility explained in section 4.2.1). Each agent is controlled by a multi layer perceptron (MLP) with 5 hidden neurons, which means a total of 67 weights2 . Note that the mEDEA algorithm is independent of any particular control architecture implementation, even though Articial Neural Networks provide a convenient, exible and well-established representation formalism. Thus, in experiments, we will focus on the dynamics of the mEDEA algorithm rather than providing in-depth analysis of the particular internal properties of the evolved neural networks. The variation operator is a Gaussian mutation with one σ parameter: a small (resp. large) σ tends to produce similar (resp. dierent) ospring. This is a well known scheme from Evolution Strategies where continuous values are solely mutated using parameterized Gaussian mutation, where the σ parameter may be either xed, updated according to pre-dened heuristics or evolved as part of the genome. In the scope of this work we rely on self-adaptive mutation where σ is part of the genome [Beyer and Schwefel, 2002] (i.e. the full genome contains 68 real values).

As with other genome parameters, the σ value responds to environmental pressure: a genome survives in the population if it leads to ecient agent behavior and if it is able to produce comparable or tter ospring. In some cases this requires a ne tuning of existing genome parameters (i.e. local search), while in other cases it requires very dierent genomes (i.e. escaping local optima).

The current implementation of the σ update rule is achieved by introducing α, a σ update value, which is used to either decrease (σ new = σ old * (1α)) or increase (σ new = σ old * (1 + α)) the value of σ whenever a genome is transmitted. In the following, α is a predened value set prior to the experiment so that it is possible to switch from the largest (resp. smallest) σ value to the smallest (resp. largest) in a minimum of approx. 9 (resp. 13) iterations (i.e. there is a bias toward local search).

Results and Analysis

As a general overview, Figure 4.2 tracks the impact of population size and radio communication settings on evolutionary adaptation. As expected, smaller populations with a short radio communication distance are more prone to extinction. On the other hand, large populations produce a successful outcome which is independent of the communication range. A run is successful whenever at least one agent is still alive at the end of the last generation. In practice however, successful runs always feature healthy population (ie. most agents are alive). These graphs illustrate an abrupt phase transition in the parameter space (considering population size and radio communication length) before which agents do not survive (ie. mating becomes too dicult). The vast majority of all runs feature at least one consensus among the agents (this was expected, as mentioned in Section 4.2.1). There were remarkably few runs where no clear consensus could be identied: even the misc class included either transient behaviors shifting between dierent consensus or dierent kind of stable consensus, such as following walls and ignoring the sun. Also, looking at larger population sizes (i.e. ≥ 50 agents) results in observing 85% of the runs ending up with a unique consensus toward the sun for all agents. This tends to suggest that increasing population size introduces more stability in the evolutionary dynamics. We also conclude that a general agreement to go toward the sun is an ecient consensus in this scenario. This can be easily explained, as adopting this strategy is the best way for agents to meet at a precise and robust location in the environment, thus maximizing the genome's chances of survival. Distances vary between 0 (agent in the center of the environment) and 100 (agent in a corner). = 32). This is but one particular example of run leading to extinction and is displayed here for illustration purpose. In this run, the agents were actually able to reach a consensus for some time. However, the relatively low population and medium communication range created a context within which a series of unsuccessful mutation (around generation 120) could not be recovered from and quickly lead to complete extinction.

Summary

In this section we have shown a rst demonstration of the mEDEA algorithm presented in Section 4.1.

From a general perspective, we have highlighted the impact of the radius of communication, and the number of agents, on the survival of the population. The higher the radius of communication, and the higher the number of agents, the more likely the survival of the population.

Our results aren't restricted to the demonstration of a proof of concept, but give also answers to the questions relative to the emergence of consensus:

Emergence of consensus: When using an experimental set-up with an environmental singularity, we have been able to show the emergence of behavioral consensus. This conrms our hypothesis that consensus doesn't need to evolve explicitly, but can rely on the behavioral similarities between one genome and its ancestors.

Non-canonical consensus: Even if the consensus to move toward the sun was the most present among the evolutionary runs studied, other types of consensus have been observed such as going away from the sun.

Co-existence of consensus: In some cases multiple consensus have been shown to evolve and sustain in the population. However, this is possible only when the two sub-populations don't meet each other. If this condition isn't fulllled, one behavior will be favored by the population.

Transient consensus: In some of the runs studied transition between dierent types of consensus was observed.

Finally, thanks to the experiments presented in this section, we have show that a smaller radius of communication leads to more stable behavioral consensus.

Implementation on Real Robots

One of the main challenges in Evolutionary Robotics is to address the so called reality gap [Jakobi et al., 1995], i.e. going from simulation to the real world. We aim here at answering the following question: is the mEDEA algorithm robust to the reality gap ? In traditional Evolutionary Robotics, the reality gap refers to the validation of solutions, i.e. evolved control architecture with a specic behavior, in the real world [Brooks, 1992]. In this work the methodological step is somewhat dierent as the reality gap concerns the experimental validation of the process (the mEDEA algorithm). We are therefore looking at the comparison between evolutionary dynamics obtained in simulation and on real robots. This section presents the implementation of the mEDEA algorithm on real robots. To provide experimental validation within a real robot setup, the mEDEA algorithm has been implemented within a population of e-puck mobile robots extended with a Linux board, running at the Bristol Robotics Lab. In this section, the robotic environment is described, as well as considerations regarding implementing mEDEA in this context. Then, results from experimental trials are described and conclusions are drawn.

Technical Overview

Research on swarm robotics has gained much attention in recent decades as a novel biologicallyinspired approach to the coordination of large groups of relatively simple robots, following simple rules [START_REF] Dorigo | [END_REF][START_REF][END_REF]ahin and Wineld, 2008]. Generally, in order to carry out real robot experiments in research labs we require a robot which is small, reliable and inexpensive in order to minimise physical space and maintenance for running a relatively large number (several tens) of robots. Traditionally research labs have designed and built their own robot platforms for swarm robotics research, such as the Linuxbot [START_REF] Wineld | [END_REF], Alice [Caprari et al., 2002], Jasmine [START_REF] Kornienko | [END_REF] and Swarm-Bot [Gross et al., 2006a]. There are also a number of commercially available mobile robots suitable for swarm robotics research, such as the widely used Khepera II and III from K-Team, Lego Mindstorms from the Lego company and Create from iRobot. However, the open-hardware e-puck educational mobile robot developed at the École Polytechnique Fédérale de Lausanne (EPFL) has become very popular within the swarm robotics research community within the last three years [Mondada et al., 2009]. The e-puck combines small size it is about 7cm in diameter, 6cm tall and 660g weight with a simple and hence reliable design 3 .

Despite its small size the e-puck is rich in sensors and input-output devices.

The basic conguration 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. Bluetooth provides the facility for wirelessly uploading programs and general monitoring and debugging. All sensors and motors are processed and controlled with a dsPIC30F6014A microprocessor from Microchip. Extension sockets provide for connecting additional sensors or actuators.

In order to ease the porting of our algorithm to real robots, we relied on the Linux board for e-puck developped at BRL [Liu and Wineld, 2011]. An embedded Linux system is installed on this board as the primary operating system of the whole robot. Our algorithm is run on this board, while the lower level sensor processing and motor control is executed on the e-puck DSP. One of the key advantages is the introduction of the WiFi into the system to provide fast and topologically exible communication.

This also provides a convenient way for wirelessly accessing and controlling the robot. In terms of productivity and ease of use, the board also allows us to use a wide range of development tools in addition to the C/ASM language development environment. The linux board for e-puck oers not only enhanced processing power, memory and communications, but a powerful control architecture for the robot. For instance, it provides exibility in how programs may be compiled inside the robot natively (instead of cross-compiled on PC), with standard Linux tools and frameworks, including Player/Stage [Vaughan, 2008].

Figure 4.9 illustrates the modied e-puck robot and its environment. The primary function of the yellow `hat' at the top of the robot is to allow us to mount reective markers for the visual tracking system, but additionally the USB WiFi card (with its cover removed), is tted into a slot on the underside of the hat.

Programming, initializing, starting and stopping experimental runs of a large swarm of mobile robots, then monitoring and logging data from those runs, is problematical if it has to be done manually. However, with the Linux extended e-pucks and wireless networking, we have been able to set up a powerful infrastructure for programming, controlling and tracking swarm experiments much more conveniently. Figure 4.10 illustrates the overall structure of the experimental infrastructure.

Each e-puck robot is congured and identied with a static IP address. They connect to the LAN through a wireless router and can be accessed from any desktop computer connected to the network using the SSH protocol. A `swarm lab server' is congured as a central code repository and data logging pool for the swarm of robots. The server also functions as a router to bridge the swarm's wireless subnet and the local network. In addition, as there is no battery-backed real time clock (RTC) on the extension board, the server may provide a time server for synchronisation of the robots' clocks and time stamping log data.

3 The open-hardware design can be found at http://www.e-puck.org Each robot is uniquely identied by the visual tracking system from the pattern of reective markers mounted on the matrix pins of the yellow hat, as shown in Figure 4.9:center. The tracking system is connected to the local network and broadcasts the real-time position of each tracked robot through a standard TCP/IP port. We use the position tracking data for logging and post-analysis of experimental runs.

Implementing the Two-suns Experiment

In order to validate the mEDEA algorithm an experimental setting, strongly inspired by the twosuns setup described in section 4.2, was designed. A population of up to 20 robots is placed in a 280 cm * 230 cm empty arena. Limited-range communication is emulated by using a WiFi network combined with the Vicontracking system. An additional object is introduced into the arena and act as a landmark which is referred to as the sun: each robot in the simulation knows the sun's relative direction and distance thanks to the Viconsystem. The experimenter may arbitrarily change the sun's location from time to time during the experiment, switching the sun location from one end of the arena to the other. All experiments described in this section lasted for at least 30 min (duration of experiments was restricted due to the limited autonomy of the robots), and at least 25 generations (each generation lasts approx. 1 min and 10 sec, corresponding to 400 time steps this time is sucient 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 (cf. section 4.3.4).

Moreover, a set of technical issues were addressed, and are listed here along with their diagnosis and solution:

Lack of selection pressure:

diagnosis: given a small arena and few robots, it is likely that one robot can meet all other robots. This would imply that selection pressure is eliminated (see section 4.1).

solution: when the maximum number of robots is known it is possible to limit the number of genomes that can be imported within one agent so that N g < N p -1 (with N g the maximum size of the genome list size and N p the population size). In this particular setup, the genome list is arbitrarily limited to 17 for each robot, and is lled on a rst-metrst-served basis to enforce a pressure toward fast mating. Note that an extreme case would be to limit the genome list size to 1, i.e. the rst genome imported. However, the selection pressure would then be particularly aggressive, and may not be suitable for the current experimental setting which is already prone to high variability because of the small population.

Slow convergence:

diagnosis: because we are running physical robots in the real world, time becomes an expensive luxury. solution: we assume that the mEDEA algorithm is naturally robust to asynchronous generation count as it does not provide any survival advantage for any genome5 . Therefore no further modication is performed.

Results

An initial set of 21 experiments were conducted to explore the performance of mEDEA under various parameter settings: number of robots (from 9 to 20), generation duration, mutation values, communication radius, etc. Results from these preliminary experiments lead to several important conclusions. Firstly, the population size was found to be the most critical parameter: switching from 9 to 20 robots completely changed the observed outcome of the experiments as mEDEA clearly benets from larger populations (cf. section 4.1). Secondly, the communication radius was also identied as a key parameter: small radii (10 cm) implied versatile populations, with rare convergence toward specic behaviours while larger radii (20 cm or more) more often led to the emergence of more stable consensus within the population.

A practical conclusion is that the small number of robots available can at least be partially compensated by a larger communication radius. Indeed, experiments with a population of 20 robots and a communication radius of 10 cm would not result in more than 17 active robots at the same time while extending the radius to 20 cm regularly led to the whole population of robots being active at the same time. On the other hand, a population of 20 robots still remains relatively small with regards to experiments performed in simulation (see previous sections). A direct consequence is that in all experiments consensus were occasionally lost, switching from one kind of consensus (e.g. following the sun) to another (e.g. ignoring the sun).

Following these preliminary experiments, 8 experiments with 20 robots based on similar parameters were performed using the experimental settings described in section 4.3.2. Each experiment lasted from 30 to 45 min depending on the energy consumption. The sun was moved after approx. 25 minutes and emergence of consensus was studied both from camera recordings and experimental data recorded using the Vicontracking system as well as the internal data logs recorded by each robot. Figure 4.11 illustrates one of the 8 experiments run with similar settings using 19 robots6 . Both the emergence of consensus to go toward the sun (above) and the eect of changing the sun location (below) are visible on this gure. The images are extracted from a video summarising the main results from these experiments7 . The following issues are considered: the emergence of consensus over time, the number of active robots during the run, and robustness to environment changes. Figure 4.12 gives the number of active robots during the experiment. Figure 4.13 tracks the distance between each robot and the sun and is represented as a density map (or heat map, i.e. darker regions indicate the most represented distance value). Darker regions close to zero indicate that robots stand close to the sun, and are likely to be a good indication of the occurrence of sun-follower genomes in the population. Lastly, gure 4.14 features the weights (i.e. gene values) of the neural links connecting the sun-orientation and sundistance sensor values to the motor rotational value of each robot (later referred to as sun-orientation gene and sun-distance gene). The weight of the sun-orientation sensor input is particularly interesting as it provides a good indication of the possible correlation between the sun position and the robot behaviour, even though the exact nature of the correlation may be dicult to guess a priori (since motor outputs also depend on other values including sensors and NN weights).

From these data, it is possible to analyse the course of the experiment: t=[0sec,400sec]: 14 to 18 robots (g. 4.12) are active and a consensus to go toward the sun is emerging, while not exclusive (the dark region near 0 in g. 4.13); t=[400sec,800sec]: The consensus is suddenly lost at t=400sec (possibly because too few robots were involved). This can be observed in both g. 4.12) and g. 4.13. The number of active robots drops to 8 and we can also observe that the genotypic signature shown in g. 4.14 does indeed change with the disappearance of sun-orientation gene values around 0. t= [800sec,1400sec]: the number of active robots increases to the maximum of 19 robots, and is correlated with most robots being located near the sun (g. 4.13), possibly implying an even stronger consensus than before. Moreover, this remains stable over time until the sun location is changed at t=1400sec. t= [1400sec,2000sec]: Shortly after changing the sun location, the number of active robots suers from a short decrease (to 14 robots) followed a quick recovery (to 18 robots). This suggests good robustness in the population, an inference which is reinforced by looking at the two other gures: the robots slowly converge back to the sun and the genotypic signature remains unchanged. We can also observe that sun-follower genomes are likely to be correlated with sun-orientation gene values close to zero (but positive).

The 7 other experiments with similar settings provided comparable results. All the runs displayed the emergence of various types of consensus as well as occasional time periods in which no consensus could be identied. Also, changing the sun location had an important impact during experiments, with the vast majority of robots adopting the same go toward the sun consensus. This can be explained by the fact that sun-follower genomes spread while their robot hosts were moving toward the sun. The following general conclusions can be drawn from these experiments:

The robot restart procedure is mostly used in the initial generations, which implies the population becomes self-sustaining (i.e. there are enough encounters between robots to avoid requiring the restart procedure);

The largest number of simultaneously active robots was obtained with a population of sunfollowers (from 15 to 19 active robots having reached a consensus to go toward the sun).

Changing the sun location had dierent eects depending on the existence (or non-existence) of consensus in a population. Populations of robots ignoring the sun did not suer from such a change, while sun-follower populations rst suered (ie. some agents are lost and stop) from the sun changing location followed by a quick recovery. Implementation of the mEDEA algorithm within a population of robots reveals a number of technical issues unfamiliar to experiments in simulation. Together, they comprise the reality gap between simulation and real world experiments [Jakobi et al., 1995]. Here, the reality gap is studied from the perspective of the evolutionary dynamics observed during a trial. These issues are articulated as follows:

Proximity sensors are unreliable: the low quality of the infra-red sensors makes it very dicult 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, the proximity sensors can 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 Viconsystem for computing the local communication network based on distance between robots. While this approach was originally motivated by the lack of local robot-robot communication, 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 (average of ∼5% of robots lost per minute) but always recovered when moving away from one another.

On-board processing is slow: the combination of on-board 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).

Two conclusions can be drawn from these issues. Firstly, simulation and real world experiments do dier, as expected. Secondly, however, results from the experiments showed that mEDEA is remarkably ecient to cross the reality gap, as it manages to deal with all of the issues outlined above and still demonstrates interesting behavior that manages to survive in the environment. As a matter of fact, the most critical issue from these experiments in the real world is the small population size, whose importance was already discussed in Section 4.2 as it impacts the stability of the algorithm: larger populations display more stable behaviors, while very small populations (i.e. less than 20 robots in this context) are prone to extinction. Preliminary experiments using less than 10 robots have conrmed this analysis: few runs converged toward a behavioral consensus, and extinction was observed in some runs. In the present context, the negative eect of a small population was mainly counter-balanced by two modications: Large communication range: As shown in Section 4.2, on top of increasing the behavioral stability, larger communication radius reduce the risk of extinction. After preliminary experiments, the communication radius has been increased up to 20cm.

Restart mechanism: A restart procedure is triggered when a robots stands inactive for 5 consecutive generations. This mechanism aims at avoiding the extinction of the population, and explores possibly more promising region of the search space.

Summary and Conclusions

In this chapter the problem of self-adaptive maintenance of robots integrity in unknown environments has been addressed by the design of a new algorithm. This light-weight algorithm, termed mEDEA, is suitable for implementation within hardware/software setups with limited computational power such as robotic agents. The mEDEA algorithm has been tested both in simulation and on real worlds with regards to its ability to evolve successful strategies as well as achieving behavioral consensus.

In simulations, large groups of robots were shown to converge to stable, mostly unique, behavioral strategies. When using smaller populations size (i.e. facing similar environmental conditions with fewer resources), dissimilar strategies co-existing at the same time were observed in few simulations.

Experiments with real robots have illustrated the applicability of the algorithm to hardware implementation. Moreover, it has been shown that the mEDEA algorithm converges also to behavioral consensus in these conditions. However, due to dicult environmental conditions, co-existence of dissimilar behavioral consensus wasn't observed. To sum it up, it appears that one key element for the success of the algorithm is to run within a large enough population.

The experiments presented in this chapter provide a rst understanding of the global behavior of the mEDEA algorithm. In the next chapters, the mEDEA algorithm is evaluated in more challenging situations. The next chapter assess the performances of mEDEA in front of changing environments. The Chapter 6, is concerned by the use of mEDEA to optimize the population's global welfare rather than individuals' welfare.

Chapter 5

Robustness to Environmental Changes

In this chapter we address the following question: How to achieve self-adaptation for robots deployed in unknown and changing environments ? This class of problems typically arises when the environment remains unknown to the human designer until the population of agents is actually made operational in the real situation, and the environment changes during operation, without any indication on when and how these changes will impact the agent's strategies.

In robotic context, methods proposed so far to address this challenge can be divided in two main categories:

Design of ecient and reliable controllers: Multiple methods have been proposed to design ecient and reliable controllers for homogeneous group of robots [McLurkin and Smith, 2004;Pettinaro et al., 2005;Nembrini, 2005]. These methods are proposed to address the design of controllers suitable for a large range of tasks, without involving any learning mechanism.

Multiple authors have proposed new paradigms based on the observation of physical systems [Shimizu et al., 2003;Pugh and Martinoli, 2008], biological systems [START_REF] Schmickl | [END_REF], or hybrid of both [Meng et al., 2007]. The latest works in this eld known to us are challenging the robust coordination of heterogeneous groups of robots [Dorigo et al., 2012].

These design methods are useful if the human engineer has enough knowledge about the task at hand and the robots used. Another assumption is that the possible environmental changes are known beforehand. If all these conditions are met, the conception and test of a robust controller will still requires a deep investment from the human engineer.

Automatic design of controllers: Mutltiple contributions have been made to address the challenges of the autonomous design of robust controllers. Among them we have identied two categories. The rsts aim at learning the proper coordination of behaviors hand-designed by a human engineer [Parker, 2000;[START_REF] Joon Sun | [END_REF][START_REF] Dias | [END_REF]. These methods are robust to environmental changes and partial failure of the robots, but can be used only if the human engineer has enough knowledge about the task at hand. The seconds are challenging the autonomous design of robotic controllers without human intervention [Trianni et al., 2008]. However, within these methods the conception phase is often performed in simulation, which leads to the previously presented reality-gap problem (see Section 2.3). Moreover, using simulations during the design phase would imply the possibility to simulate environmental changes (which isn't the case here).

In all approaches reviewed above, a human engineer is mandatory, either to design the robots' controllers, or to design a reward function necessary to the autonomous design of controllers. Therefore, these methods can be used only if the environment is known to the human engineer before the deployment of the robots, which isn't the case considered here. As a consequence another method is needed to design continuously and autonomously controllers suitable to an environment unknown to the human engineer and possibly changing.

In this chapter experiments mEDEA is evaluated in unknown and possibly changing environments.

More specically, the resulting behaviors are studied both at the individual scale and population scale. A new environmental setup is presented in Section 5.1, and the results obtained are detailed in Section 5.2. The work presented here is based on our publication [START_REF] Bredeche | [END_REF].

5.1

Experimental Setting

5.1.1

The Problem: Surviving in a Dynamic Unknown Environment

As already stated in the previous chapter, no information whatsoever about the task and the environment at hand can be used to tailor the algorithm. Quite the opposite, the exact same algorithm is used in all cases without external intervention.

In practice, the experimental setting is based on the succession of two dierent experimental setups (which share few similarities in order to avoid populations' extinction). During one run no intervention whatsoever is performed on the agents (change of genome, restart of the algorithm, modication of the learning algorithm).

The two environmental setups are detailed hereafter:

1. The free-run setup:

Description: A population of autonomous mobile agents is immersed within an environment with few obstacles. As a consequence, an agent dies only if it was not able to meet at least one other agent -ie. the current genome is lost for sure as it does not get a chance to survive within any other agents.

Motivation: This setup makes it possible to evaluate the mechanisms of the mEDEA algorithm as environmental pressure should be limited. Some key behavioral elements should be learned during this phase that might be useful for the second environmental setup.

The energy setup:

Description: A set of energy resources (food items) is spread all over the environment, which can be harvested by the agents. Agents are endowed with an energy level, which depends on harvested food items and power consumption. If the energy level reaches 0, agent dies and genome information is lost. Moreover, harvested food items only grow back after a given number of iterations.

Motivation: In this setup, genomes also compete for agent resources but have to deal with environmental pressure as maximizing mating encounters may not be fully compatible with energy self-sustainability. The added constraints might put the agents in dicult situations as they have never been experienced before. However, the behaviors evolved in the rst experimental setup might be modied to the new experimental setting.

Implementation

Figure 5.1 shows the environment used for the experiment: a 2D arena with obstacles, possibly containing food items. The gure also illustrates 100 autonomous mobile agents loosely inspired from the ePuck mobile robot specications. These agents are similar to the ones used in the previous chapter:

Each agent has two motor outputs controlling the translational and rotational speed, and 8 proximity sensors arranged around the agent body, Each agent is controlled by a MLP with 5 hidden neurons,

The weights of the MLP are evolved locally by using mEDEA on each robots,

The variation operator is a Gaussian mutation whose σ parameter is added to the genome and increased or decreased randomly.

However, for this experiment three additional sensory inputs are considered: the angle and direction toward the nearest food item and the current energy level (which is set to a xed value in the free-ride setup). Note that these additional sensor values are useless in the rst setup, and may even be considered as distractors.

The full experimental setup considers starting with the free-run setup, and then suddenly switching to the energy setup after a pre-dened xed number of generations. In the meantime, agents are of course unaware of such a change in the environment and keep on running the same unchanged mEDEA algorithm. The whole experiment lasts for 150 generations, switching from the free-run setup to the energy setup at generation 75.

As said before, the energy level is not used during the free-run setup. During the course of evolution some agents may come to a halt because they did not meet any other agents, thus failing to import a new genome for use in the next generation. In the free-run setup, the agents without a genome remain still (or inactive, i.e. without genome), waiting for new genomes imported from active agents that eventually come into contact 1 .

In the energy setup, the agents can also become inactive because they ran out of energy during the energy setup (each agent can store a maximum of 400 energy units and consumes 1 unit/step, one generation lasts 400 steps, each harvested food item gives 100 units of energy). These agents remain stationary until the end of the current generation. After this time they are automatically relled with enough energy for surviving through slightly more than one generation, so that when an agent become active it has enough energy to reach a food item. These agents remain inactive, and wait for a new imported genome that may be used for the next generation. While the reviving procedure makes it possible to avoid progressive extinction, extinction is nevertheless possible whenever all agents in the population fail to meet any other agents during one generation, whatever the cause (bad exploratory or harvesting strategies).

Therefore, monitoring the number of active agents in a population provides a reliable indicator of the performance of the algorithm as external intervention is considered as impossible (except for energy rell if agent runs out of energy). Detailed parameters used for the experiment presented in the next section are given in Tables 5.1 and 5.2.

In order to provide a challenging environment, the energy setup is designed so that the number of food items in the environment depends on the actual number of active agents. A food item grows 1 Note that the simulation begins with each agent containing a randomly initialised genome. back whenever harvested, but only after some delay. If the number of active agents is less than half the population size, then delay regrow is set to 400 steps. However, if the number of active agents is between 50 and 100, then the delay linearly increases from 400 steps (fast regrowing) to 4000 steps (slow regrowing, aggressive environment), as follows: delay regrow = 72 * nb agents -3200.

Clearly the smaller the population the easier it is to harvest enough food items for survival. On the other hand, a 4000 steps regrow delay implies that a given food item is available only once every ten generations, which gives a setup of the utmost diculty. A population of 80 altruistic agents (i.e. agents harvesting only what is necessary) with perfect coordination (i.e. agents harvesting only when necessary) would not even be able to fully survive in this environment with these parameters.

Combining the regrow delay update scheme with the equation relating the required number of food items and population size leads to a quadratic equation with one positive solution. In this setup, the optimal population size is strictly below 80 agents. However, as soon as 50 agents are active the regrow delay increase quickly (72 iterations) for each new active agent, which makes this setup very aggressive when more than 50 agents are active.

In the particular setup described here, switching from a possibly ecient population of 100 agents from the free-run setup to the energy setup will have a possibly disastrous impact as the number of agents at the beginning of the second setup implies longer regrow delays.

All experiments have been run in the roborobo simulator already presented in Section 4.2.1.

Results and Analysis

The lack of explicit objective function makes it dicult to compare performance during the course of evolution. However, the two conicting motivations presented in Section 3.4 can be evaluated thanks to computationally cheap measures:

The evolutionary pressure for the survival of the agents aects the integrity of the swarm, and is therefore estimated thanks to the number of active agents. Moreover, the behavior evolved by the agents regarding this issue can be analyzed from the point of view of their energy balance (i.e. the dierence between the energy harvested, and the energy consumed by one agent during one generation).

The evolutionary pressure for a genome to duplicate itself will tend to create many mating opportunities between agents. Thus, the average number of imported genomes per generation gives a good hint of how the algorithm performs regarding this motivation. The σ mutation parameter provides also interesting informations: a low value results in the conservation of most of the genomes (even if it is suboptimal), a high value results in the creation of completely new behaviors.

Results

The four graphs in Figure 5.2 give a synthetic view of the results over 100 independent runs obtained with mEDEA on the experimental scenario described in the previous section. These graphs compile values of the selected parameters, or indicators, over generations: number of active agents, ratio of imported genomes per agent (normalized by the number of active agents), energy balance per agent, and σ mutation parameter values. In both setups, the number of active agents rises to reach stable average values, which show an increase in the capacity of the agents to survive in their environment. Moreover, this indicator drops after the switch of setup, and the recovers to a stable higher value. This shows the capacity of the mEDEA algorithm to address the pressure for the survival of agents in front of a changing environment. Moreover these observations illustrate the ability of mEDEA to maintain the integrity of an agent's swarm in changing environments. This interpretation is supported by the increasing value of the energy balance which is a key element for the survival of agents in the second setup.

The ratio of imported genomes increases in the rst setup, uctuates when the environment is switched, and then reaches back a stable level (this value is actually slightly increasing in the second part of the experiment). The strong uctuations are due to the small number of active agents right after the switch of environment. An increase in the number of imported genomes is interpreted as an increase in the mating opportunities which corresponds to the intrinsic motivation. Therefore, in this scenario, the mEDEA algorithm address the evolutionary pressure for genomes to duplicate themselves in the same time as the pressure for the survival of agents.

The Gaussian mutation parameter is the only indicator not really inuenced by the change of environmental setups (except for a slight increase in maximum values). The constant decrease of the σ parameter close to minimal values comes from two aspects: a)the σ update scheme is biased toward small values) b) slightly mutated genomes have a higher chance to produce coherent behaviors.

The ability to recover after a change of environment comes from the spread of one of the few surviving, yet t, genomes facing few competitors. This genome is later adapted to the environment by the process of mutation, mating and selection used also in the rst setup. Moreover, complete extinctions were observed after switching to the energy setup only in 3 of the 100 runs (results not shown).

While the results may vary among runs, with a great dierence between minimal and maximal values for each indicator, values between the upper and lower quartiles are remarkably close given the noise inherent in this kind of experiment.

Analysis of Single Runs

Examples of randomly chosen runs, limited to tracking the number of active agents, are given in Figure 5.3 for further illustration. These graphs highlight the course of evlution in both setups. In the free-run setup, the number of active agents is maximized up to the total number of agents.

However in the energy setup, the number of active agents is always oscillating between a low value (easy environments), and a high value (dicult environments). These oscillations are smoothed and shadowed in Figure 5.2 because of the large number of runs considered. The number of active agents oscillates around the stable solution for mEDEA in this experiment (i.e. a larger population cannot survive in the environment, while a smaller population does not exploit all available resources. The oscillations are essentially due to the design of the experiment. When the number of active agent is lower than 50, the environment is easy and a high number of agents become active. However, as soon as the number of active agent is higher than 50, the environment becomes much more dicult, and the number of active agents drops. The question of cooperation among agents, which could improve the population integrity, is studied in the next chapter.

The eciency of the algorithm can be observed by looking at the resulting behavioral strategies.

Examples of behaviors observed in both the free-run and energy setups are shown in Figures 5.4 (2) energy setup). Average success scores for each generation both histograms are the results of 1000+ battles. See text for details.

Quantitative Analysis

The results presented above must be interpreted with great caution. For example, the quality of the equilibrium between maximizing mating opportunity and coping with environmental constraints (i.e.

avoiding walls, avoiding collisions with other agents and harvesting) is dicult to estimate as such an equilibrium may (and appears to) imply sub-optimal values for both related indicators. In fact all interpretations provided so far rely on the assumption that values monitored in the experiment are actually correlated with genome survival.

In order to test this assumption an experimental setup is dened from the results obtained so far.

This setup is called the post-mortem battle experiment, or battle experiment, for short. The battle experiment is loosely inspired by competitive coevolution, where each individual competes against a hall-of-fame of the best individuals from every past generation [Rosin and Belew, 1996]. This is used to estimate a posteriori the tness rank of one individual (by a comparison mechanism) within all possible (or at least, all available) situations.

For the current experiment, one battle is achieved by randomly picking 10 generations from the same setup and extracting one random genome from each of these generations. Then, each genome is copied into ten dierent agents, resulting in 100 agents that are immersed in the same setup they evolved in. Variation is turned o, and evolution is re-launched. After 100 generations of random selection and replacement the number of copies of each genome is accounted for and used to compute a survival score. It is important to note that only the performance of the original genome is measured, since the mutation is turned o. As an example, one genome gets a maximal score if it succeeds in taking control of all the agents.

Average results over 1000 battles are given in Figure 5.6. In both setups genomes from later generations display better survival than early genomes. Moreover, battles on the second setup show Introduction

Denitions

In the literature, the terms cooperation and altruism are often found side by side. Both phenomena have been the focus of a particular attention from many research elds, including Game Theory [Fletcher and Zwick, 2007] and Biology [START_REF] Piliavin | [END_REF]. Both cooperative acts are performed either thanks to a social act (e.g. slime molds sacricing themselves to promote the reproduction of others when resources are scares), or the refraining from selshness (e.g. competition for light results in plants investing in growth rather than in productivity) [START_REF] Rankin | [END_REF].

However, a clear distinction is drawn between cooperation with mutual benet 1 [West et al., 2007] and strong altruism (termed altruism from now on) depending on the nature of the tness benet at the level of either the individual or the population [Lehmann and Keller, 2006b].

1 Cooperation is also sometimes used as a synonym for altruism (e.g. cooperation in the prisoner's dilemma corresponds to altruism [Sober, 1992]). In this chapter, we assume the restricted and well-accepted denition of cooperation as a behavior leading to mutual benet. Cooperation implies that a given individual benets from its behavior during its lifetime (called direct benet), either through direct or delayed (i.e. through repeated interactions) reciprocity. In these scenarios, the rise of free-riders within the population can be hindered thanks to the following mechanisms [Lima, 1989;West et al., 2007]:

Reciprocity: When agents use the reciprocity mechanism a cooperation between two agents is maintained as long as both agents continue to perform cooperative actions. As soon as one of the two agents behave selshly, the other agent will retaliate by displaying selsh behaviors. This approach is used to favor the emergence of cooperation in scenarios where interactions between individuals are repeated without nite time horizon. It is at the core of the tit-for-tat strategy [START_REF] Axelrod | [END_REF], and has been shown to evolve in articial systems under specic conditions [Trivers, 1971;Lima, 1989;Nowak and Sigmund, 1993;Suzuki and Akiyama, 2007].

Punishment: The repression of free rider's within groups is another mechanism proposed to increase the level of cooperation between agents [Frank, 2003]. Within this strategy, cooperating individuals have the opportunity to impose a ne to selsh ones. Therefore the evolution of cooperation relies on the knowledge of the previous agent's actions. Dierent works on this approach are reviewed in [Lehmann and Keller, 2006a].

Biological experiments on the evolution of cooperation are rare because of their length and diculty to set up. It is for example impossible to study various payos, or dierent tness mechanisms. However experiments on biological systems don't suer from modeling issues, and oer rst hand perspectives on the emergence of cooperation in nature [Dugatkin and Wilson, 1992].

Altruism

Altruism characterizes the sacrice of (part of) one own's tness for the benet of others. Therefore, an altruistic behavior benets other individuals and possibly has a positive impact on longer time-scale (e.g. more than a single lifetime). This can be illustrated by the death of Amoeba cells in order to favor the reproductions of others [Queller et al., 2003]. In altruistic contexts the mechanisms enforcing social behavior don't rely on lifetime benet, but on the longterm genetic advantage. Interactions between agents sharing altruistic genes are enforced in order to increase the survival rate of these genes.

This idea has been formalized under the name inclusive tness proposed by [Hamilton, 1964]. It is now widely accepted to account for the emergence of altruism: inclusive tness considers the tness of a particular individual to depend both on its own success and the success of its close relatives. The basic idea is to consider individuals as vehicles for genes. Therefore the welfare of a gene is considered rather than the sole interest of one individual/vehicle. Of course, sacricing one's vehicle depends on several parameters such as the expected tness loss (from sacrice) and benet (for other copies of the genome) as well as the genotypic relatedness of the individuals concerned (closer relatives may imply increased altruistic behaviors).

Hamilton formalized the relationship between cost, benet and relatedness in the following equation:

C/B < r (6.1)
The cost C is the amount of tness lost by an altruistic individual. The benet B is the amount of tness gained by the recipient that benets from the altruistic behavior. And r is the genotypic relatedness between the two individuals. This equation has been extensively studied since its rst introduction in 1964, and the methods to compute its parameters often discussed [Queller, 1992]. [Lehmann and Keller, 2006a] discuss this point based on recent contributions.

Multiple mechanisms favoring the evolution of higher level of altruism have been proposed since the pioneering work of Hamilton. All these mechanisms aim at increasing the likelihood of altruistic actions between closely related individuals. We are presenting here a partial review of the most recognized mechanisms.

Kin selection.

The term kin selection has been introduced by [Maynard Smith, 1964] to describe the mechanisms maximizing the inclusive tness of an individual. If an individual has a gene for altruism, its kins are likely to have it as well. Therefore, an altruistic individual willing to sacrice itself for closely related individuals may spread its gene for altruism through natural selection. [Sober, 1992] studies the impact of cost, benet and population size on the evolution of altruism in the iterated prisoner's dilemma. From these experiments, multiple conditions are presented, recalling the one found in the hamilton's rule. Multiple aspects of this mechanism have since then been studied in details, such as the impact of time [START_REF] Eshel | Partnership[END_REF], and group sizes [Leticia et al., 2004]. Moreover, this mechanism has also been studied in o-line ER by varying the genetic team composition and level of selection in public good dilemma experiments [Waibel et al., 2009]. Finally, mechanisms aiming at detecting kin are named kin recognition (cognitive process) and kin discrimination (observable behavioral pattern) [Byers and Beko, 1986;[START_REF] Ostrowski | [END_REF]. These mechanisms increase the eect of kin selection in the evolution of altruism, even if their utility in Biology is discussed [Tang-Martinez, 2001;Mateo, 2004].

Group selection.

The group selection mechanism is used to increase the likelihood of interactions between individuals with high level of altruism, without relying on the genotypic relatedness [Wynne-Edwards, 1986]. Groups are created randomly between altruistic and egoistic individuals and individuals can only interact between members of the same group. After a xed amount of time, the groups are dissolved and new random groups are formed. If groups are maintained too long, altruistic individuals will be wiped out. However, if specic constraints are respected, groups with higher ratio of altruistic individuals will grow faster than other groups. By reforming groups regularly, the most altruistic agents will benet from the growth of their group.

This theory is debated due to its similitudes with the kin selection mechanism, and its lack of realism with regards to biological systems. A review of the previous contributions to the study of this mechanism is given in [Frank, 2003], and the presentations of arguments relative to the surrounding controversy are presented in [West et al., 2007]. Currently, it is argued that this mechanism is equivalent to the kin selection mechanism [Queller, 1992;Rousset and Ronce, 2004].

Tag recognition.

The tag recognition mechanism is based on the perception of genotypic characteristic through phenotype's features [Holland, 1996]. Thanks to this association, individuals with similar inclination toward altruistic behavior can recognize each other, and have therefore a selective advantage to engage in altruistic behavior with each other. This mechanism is proposed as an explanation to high level of altruism in simple creatures lacking the capacity to recognize kins. Two similar instantiations of this mechanism have been proposed: the green beard eect (relying on sight), and the armpit eect (relying on smell).

The green beard eect has been described by [Hamilton, 1964] and famously named in [Dawkins, 1976]. Within this scheme two individuals recognize the cooperative tendency of the other thanks to a visible feature (a green beard for example). The armpit eect is a similar mechanism dubbed in [Dawkins, 1982] which doesn't rely on mere preference toward individuals having a specic feature, but toward similar individuals. In the thought experiment presented, Dawkins imagines animals using the odor of their own armpit as a basis to decide with which individuals they will collaborate. The closer the other individual armpit's odor, the more likely the cooperation.

One of the rst demonstration of tag mechanisms in a virtual environment has been proposed in [Nowak and Sigmund, 1998]. Since then, these mechanisms have been demonstrated in multiple contexts [START_REF] Riolo | [END_REF]Antal et al., 2009], and their stability in virtual environments has been demonstrated [Roberts and Sherratt, 2002;Spector et al., 2004;Spector and Klein, 2006]. Finally, both of these mechanisms have been observed in biological systems [Queller et al., 2003;Haig, 1996;[START_REF] Keller | [END_REF][START_REF] Hauber | [END_REF]Mateo and Johnston, 2000;Isles et al., 2001].

Environment viscosity.

The viscosity is an environmental parameter impacting the dispersion of agents (e.g. moving speed). Therefore an increased viscosity will result in the presence of related individuals close to each other, and thus enforce kin-selection. For example when goods produced by altruistic individuals benets locally to other individuals, an increased viscosity will favor the creation of cluster of altruistic agents. This mechanism originally presented in [Hamilton, 1964], has been demonstrated in multiple works [Wilson, 1980;Queller, 1985;Wilson, 1987;[START_REF][END_REF]Mitteldorf and Wilson, 2000]. However [Hauert and Doebeli, 2004] has recently criticized this approach by stating that small clusters can be more favorable for the emergence of altruism in specic setups.

6.1.2

The Tragedy of the Unmanaged Commons

The Tragedy of the Unmanaged Commons [Hardin, 1968;Hardin, 1994] is a particular kind of social dilemma arising when a population of individuals has access to a nite common resource pool. In this context, each individual may temporarily increase its benet through selsh behavior, but this inevitably leads to exhaust the common resource pool, ultimately ending with population extinction. For concerned individuals, one possible way to address this tragedy is to display altruistic behaviors.

The classic example features a pasture open to all, and herdsmen seeking their own interest. By owning as many cows as possible, each herdsman increases its personal benet without regards for the common pasture the cows harvest. This situation quickly leads to the overexploitation of the pasture, ending with cows dying from starvation. Pastures are only one out of many scenarios where the Tragedy of the Unmanaged Commons can happen: sh stocks and timber are other well-known study scenarios.

The Tragedy of the Unmanaged Commons has been widely studied in Evolutionary Biology [START_REF] Rankin | [END_REF], Economics [START_REF] Mankiw | Mankiw. Principles of economics[END_REF], and Historical geography [Diamond, 2005]. From a formal point of view, the Tragedy of the Unmanaged Commons appears in scenarios featuring a common good, which is characterized by two properties:

Non-excludable access: The resource is freely accessible to anyone. There is no physical restriction to access the resource, and no cost is associated to its access.

Rivalrous access: Once the resource has been consumed by an individual it doesn't exist anymore. However, this resource can regenerate, in the right conditions, and after a specic time.

The combination of these two properties imply a competition among individuals to access the resource. A hypothesis to explain the tragedy of the unmanaged common is the presence of freeriders [START_REF] Rankin | [END_REF]. Free-riders are selsh agents, taking advantage of the altruistic behavior of other agents. Since they are favored by natural selection, they out-grow altruistic agents and soon become the only type of agent in the population. At this point, the presence of only selsh agents will result in the overexploitation of the common good, leading to the Tragedy of the Unmanaged Commons.

In economics the solutions proposed to the Tragedy of the Unmanaged Commons are ranging from two extremes: the privatization of the common good, and the public management of the common good [Hardin, 1994]. The Tragedy of the Unmanaged Commons can also arise in evolutionary scenarios where agents compete for a resource in order to improve their tness. Altruistic behavior has been proposed as a solution to these scenarios [START_REF] Dionisio | [END_REF]].

6.2

Experimental Setup: Implementing the Tragedy of the Unmanaged Commons

In the remaining of this chapter, we will look for answers to the following questions:

Is it possible to evolve altruistic behaviors in mEDEA as a response to a scenario where the Tragedy of the Unmanaged Commons is bound to occur ?

What are the important properties to evolve altruism by the mEDEA algorithm ?

What are the mechanisms responsible for the evolution of altruistic behaviors ?

Is it possible to impact the level of altruism by modifying the local interactions between agents ?

Setup

In order to account for the existence of altruism, a foraging task has been dened where a population of autonomous agents must eat food items to maintain a positive energy level. The experimental setup used in this chapter is illustrated in Figure 6.1, with food items (circles), agents (small dots) and obstacles. The environment and task depends on the following elements:

Self-sustainability: foraging is necessary to survive, as each food items gives a small amount of battery energy. However, an agent's battery is limited to a maximum amount of energy, and foraging may end up in wasting resource.

Foraging behavior: an agent may choose to harvest all or part of a food item.

Re-grow rate: whenever a food item is harvested, it is removed from the environment until it grows back after some delay. The time to re-grow depends linearly on the quantity of energy harvested from the food item.

As a consequence, the environment features a common good (non-excludable but rivalerous access)

for which agents compete. In other words, in this setup the Tragedy of the Unmanaged Commons is bound to occur. The probability to observe the Tragedy of the Unmanaged Commons is dependent of the delay needed by a food item to grow back. A short re-grow delay will result in a high level of food available (low probability to observe the Tragedy of the Unmanaged Commons), while a long regrow delay will result in scarce resources (high probability to observe the Tragedy of the Unmanaged Commons). This is achieved by setting the maximum re-grow delay for a food item (EP Lag M ax , with EP as in Energy Point), which in turn will be used to compute on-the-y the re-grow delay of a food item that was just harvested (EP Lag ). This is described in Equation 6.2, which also takes into account the amount of energy harvested by an agent from the food item (E harvested ) and the amount of energy available in each food item (EP e M ax ). On the one hand, in the case where EP Lag M ax is equal to the duration of an evaluation, the re-grow delay of a food item (EP Lag ) will range between 0 (if no energy is harvested from the food item), to one generation (if all energy is harvested from the food item).

On the other hand, a short EP Lag M ax will result in a smaller range of variations of EP Lag .

EP Lag = E harvested /EP e M ax * EP Lag M ax (6.2)
Within this setup, it is expected that altruistic agents in dicult environments shall harvest the minimum amount of energy from each food items, therefore increasing the availability of the resource (short re-grow delay, no wasted energy). On the other hand, selsh behaviors are likely to be tted for small values of EP Lag M ax , but are expected to become more and more critical as the value of EP Lag M ax increases. All experiments are conducted with 100 robotic agents in the environment described and illustrated in the previous section. All agents are using the mEDEA algorithm (see Chapter 4). The environment contains 800 food items and an agent may harvest a maximum of 50 units from a food item. Each agent consumes 1 unit of energy per step, and can store up to 800 energy units (harvesting surplus is lost). If the agent's battery level drops to zero, the agent stops and its genome is lost. It remains then inactive for one generation without neither recording any genome nor transmitting any information. This is done to prevent the survival of poorly ecient strategies switching from one agent to another. The agent then switch to the listening state, for one generation, during which it doesn't move but records the genomes broadcasted within radio range by other robots. If the agent has received more than one genome during the listening state, a new controlling genome is chosen thanks to the random selection mechanism. Otherwise, the agent remains in listening state for one more generation. To sum it up, this is the exact same algorithm as was presented in the previous chapter.

The control architecture is a Multilayer Perceptron (MLP) with 5 hidden neurons, 11 inputs (8 proximity sensors, battery level and orientation/distance to the closest food item) and 3 outputs (left/right motor and proportion of energy to be harvested from a food item, if any). The weights of the MLP are decoded from the active genome of the agent. Each agent broadcasts a mutated copy of its own genome and receives genomes from neighbors within a limited range (roughly 1/10th of the length of the larger side of the environment). The mutation operator used in the mEDEA algorithm is dened as a gaussian mutation with a σ parameter. σ is included into the genome (i.e. similar to a self-adaptive Evolution Strategy) and ranges from 0.01 (low mutation rate) to 0.5 (large mutation rate), as presented in Section 4.2.2. Detailed parameters used for experiments presented here are given in Table 6.1.

Measuring altruism

In order to account for altruism, a measure for monitoring the cost of altruism for one foraging agent is dened. This corresponds to measuring the amount of energy that could be consumed when harvesting a food item, but which is actually not consumed by the agent. This is formally dened in Equation 6.3.

Cost = max(0, min(EP e M ax , r Emaxr Enow ) -E harvested ) (6.3)

Where EP e M ax is dened as before (i.e. maximal energy in a food item), r Emax is the maximal energy level of an agent, r Enow is the current energy level of the agent and E harvested is the energy harvested by the agent from the food item.

While a selsh agent shall have a cost of zero, an altruistic agent should be able to perform a trade-o between its altruistic nature and its survival needs. Therefore, the cost of altruism can be seen as the agent's level of sacrice which is continuous (a quantity of energy) rather than discrete (eat or dont eat).

Characterizing agents' behaviors

In order to characterize the behavior of the evolved behaviors (independently of their level of altruism), the area covered by one agent in one generation is measured. By this way a numerical value is associated to the movements performed by the agents. Thanks to this the variations in agents behaviors are observed for experimental setups. The agent movement is monitored within the environment, by counting the number of location visited. To do so, the environment is divided into cells, of resolutions 4x4 pixels. At the end of a generation, an approximation of the area covered by an agent is computed thanks to the Formula 6.4 (the formula is applied only on the grid of the concerned agent).

AreaCovered = #V isitedCells #Cells (6.4) 6.2.2

.3 Fixed levels of altruism

In order to investigate the impact of dierent level of altruisms an alternative setup is designed where the level of altruism is xed beforehand. In practice, this is done by assigning the energy harvested by an agent regardless of the output of its neural network. The energy harvested is linked to a xed cost of altruism set for the course of the experiment. Based on the xed cost (Cost F ixed ) the energy harvested (E harvested ) is computed thanks to the Formula 6.5.

E harvested = max(0, min(EP e M ax , r Emax -r Enow ) -Cost F ixed ) (6.5)
This formula is deduced from Formula 6.5, and the same notations are used.

Natural Emergence of Altruism

In this section we study the behavior evolved by mEDEA under dierent pressures of the environment. The goal is to evaluate whether the mEDEA algorithm is capable of evolving altruistic behavior, and to study the impact of environmental pressure on such evolutionary dynamics. A large set of experiments was performed under various environmental pressures by setting a specic value of EP Lag M ax for each run, ranging from 25 steps to regrow (easy environment) to 400 steps to regrow (dicult environment), for a total of 16 setups. For each setup (i.e. a xed value of EP Lag M ax ), at least 200 independent runs were performed (total of more than 3200 experiments) and the results

were aggregated to extract two indicators: the number of active agents, and the cost of altruism. In all experiments, the course of evolution is similar: the number of active agents quickly increases to a stable value while costs start from random values and stabilize to (possibly) positive values. While the increasing number of active agents is expected from evolutionary adaptation, the second observation is of primary importance regarding the possibility of altruistic behavior: a positive cost of altruism would imply that agents do not systematically harvest all possible energy from the food items.

Results are summarized in Figures 6.2 With stronger environmental pressures (larger values of EP Lag M ax ), the number of active agents decreases (pvalue < 2.2 * 10 -16 between EP Lag M ax = 25 and EP Lag M ax = 400), which conrms that the environment is becoming more and more challenging. Moreover, the number of extinguished runs is increasing with the environmental pressure, which shows the Tragedy of the Unmanaged Commons:

when the amount of food is reduced, the risk to deplete completely the resource is increased. The next question is to investigate the behaviors evolved by the surviving populations.

Altruistic behavior in the context of increasing environmental pressure can be observed by looking at the cost of altruism, which converges to a stable value, while the number of active agents decreases and the extinction rate increases (i.e. the limit for survival). Indeed, altruistic behaviors are rst observed with environment pressure EP Lag The greedy nature of the algorithm has been shown in easy environments: without environmental pressure, altruism does not emerge spontaneously. This shows a link between environmental pressure and the emergence of altruism. However, altruistic behaviors remain stable in the population even though the environmental pressure increases and the number of active agents starts to drop, implying limited correlation between the level of altruism and environmental pressure. These observations imply that some dynamics of mEDEA promote greedy strategies, while others linked to the environmental pressures (but not only) favor altruistic strategies.

Eect of Environmental Pressure

The characterization of the impact of evolved altruistic on the integrity of the group of robots, is necessary to further understand the phenomenon highlighted above. The harvesting strategy is one degree of freedom in the search space that can be exploited by the mEDEA algorithm. However, its importance with regards to the integrity of a group of robots remains to be evaluated. To investigate this, results obtained when mEDEA explicitly control part of the harvesting strategy (i.e. the Experiments are run in 14 dierent setups: 13 using xed costs of altruism (from egoist (Cost = 0) to extremely altruist (Cost = 45)), and one using an evolved harvesting strategy (as presented before). In order to observe results on a large range of environmental pressures experiments are run in environments where the pressure is at rst easy (EP Lag M ax = 25 iterations) until the 400000 th iteration, and then continuously increasing by step of 80 iterations every 4000 iterations (10 theoretical generations) until the extinction of the population. That is to say, at the 404000 th iteration the environmental pressure is equal to EP Lag M ax = 105 iterations , and at the 408000 th iteration the environmental pressure is equal to EP Lag M ax = 185 iterations. Only runs where extinctions occurred after the 400000 th iteration are taken in consideration. For each setup, at least 500 runs were performed (total of more than 7000 runs).

The Figure 6.4 shows the ratio of successful runs (number of successful runs divided by the total number of runs) for every environmental pressure, and every cost strategies. The Figure ?? shows the ratio of successful runs measured between environmental pressure EP Lag M ax = 5000 iterations and EP Lag M ax = 8100 iterations.

The benet of xed harvesting strategies for environmental pressure lower than EP Lag M ax = 4000 iterations is observed in Figure 6.4: evolving the harvesting strategy is one of the worst strategy tested (one of the strategy for which the ratio of successful run is the lowest). However, after the .5: Ratio of successful runs for dierent harvesting strategies (evolved and Cost between 0 and 45) measured when the pressure of the environment increases by step of 80 iterations every 4000 iterations (from an easy environmental pressure, i.e. EP Lag M ax = 25 iterations. Presentation of the ratios measured between EP Lag M ax = 5000 iterations and EP Lag M ax = 8100 iterations EP Lag M ax = 4000 iterations threshold, the evolved harvesting strategy becomes more and more successful in comparison with xed harvesting strategies. Figure 6.5 highlights the advantage of the evolved harvesting strategy at the highest environmental pressure. The only populations surviving in environmental pressures higher than EP Lag M ax = 7000 iterations are produced by the evolved harvesting strategy.

As a summary, on the one hand the added dimension in the search space reduces the performances of the mEDEA algorithm in easy environments. On the other hand this dimension seems to be necessary for mEDEA to deal with extremely high environmental pressure.

Altruism and Dispersion

Even when the harvesting uses a xed cost, other behavioral strategies can display altruistic behaviors, such as particular locomotion behavior. On the one hand, if an agent covers a large part of the environment, its actions will impact a large number of individuals, some of them not closely related. Therefore, altruistic actions have a small probability to increase signicantly the inclusive tness of the individuals. Nevertheless, an agent covering a large part of the environment has a high probability to transmit its genome. On the other hand, if an agent covers a small part of the environment, its actions will impact a small number of agents located within its vicinity. These agents are likely to use genomes closely related to the one of the considered agent. Therefore, an altruistic action will benet to relatives of this agent and increase its inclusive tness. It is therefore interesting to investigate if the mEDEA algorithm is using this possibility to regulate the level of altruism evolved.

The area covered by agents has been measured in three dierent setups: one where the harvesting strategy is xed to a strongly altruistic behavior (Cost = 40), one where the harvesting strategy is xed to a moderately altruistic behavior (Cost = 5), and one where the harvesting strategy is evolved by the mEDEA algorithm (dynamic cost). In the third setup, the cost of altruism evolved has also been measured. Experiments are performed in environments where the pressure is at rst easy (EP Lag M ax = 25 iterations) until the 400000 th iteration, and then continuously increasing by step of 80 iterations every 4000 iterations (10 theoretical generations) until the extinction of the population. Only runs for which the extinction occurs after the 400000 th iteration are taken in consideration. For each setup, at least 500 runs are performed (total of more than 1500 runs).

Figures 6.6(a), and 6.6(b) show respectively the area covered by agents when the harvesting strategy is xed to a moderately altruistic behavior and when the harvesting strategy is xed to a strongly altruistic behavior. Figures 6.7(a), and 6.7(b) show respectively the costs of altruisms and areas covered when the harvesting strategy is evolved by the mEDEA algorithm. Figure 6.7(b) shows clearly the impact of environmental pressures on the behaviors of agents when the harvesting strategy is evolving. When the environmental pressure increases (from the 400000 th iteration), the dispersion rates are always decreasing (pvalue < 0.05 for comparisons between iteration 400000 and all iterations from 560000). 6.6(a) shows similar evolutionary dynamics as the one displayed in Figure 6.7(b). Moreover dispersions rate of agents on the two last iterations of Figures 6.6(a) and 6.7(b) are similar (p-value > 0.05). This shows that the emergence of spatial behaviors is inuenced by the harvesting strategy, even if it is a xed one.

Following previous arguments, the highest level of altruism should be associated with spatial behaviors displaying small dispersion rates. However, higher levels of dispersion are associated with the highest level of altruism tested. Indeed, values displayed in Figure 6.6(b) are signicantly higher than the ones presented in Figure 6.7(b) from iteration 440000 (pvalue < 0.05).

An hypothesis to explain this dierence is the following. When a high level of altruism is used each agent harvest few energy from each energy point. As a consequence the inclusive tness of each agent can be hardly maximized. Therefore the success of a gene in the population is favored by its capacity to spread itself, that is to say to display spatial behavior with high dispersion rates.

In order to test this hypothesis the performance as the number of active agents is measured on each run. Figures 6.8(a), and 6.8(b) show the number of active agents respectively when the harvesting strategy is xed to a moderately altruistic behavior, and when the harvesting strategy is xed to a strongly altruistic behavior. Figure 6.9 shows the number of active agents when the harvesting strategy is evolved. On these gures, the number of active agents for a xed cost of 5 is similar to the number of active agents for an evolved cost at the latest iteration (p-value = 0.8821 for iteration 680000). However, the number of active agents is always lower when a xed cost of 40 is used (pvalue < 0.05 for every 6.3. Natural Emergence of Altruism 107 iterations). This dierence in the number of active agents conrms the hypothesis made. When highly altruistic behaviors are forced, the survival capacities of each agent are diminished. As a consequence spatial behaviors with small dispersion rates have a small inuence on the welfare of their relatives.

However spatial behaviors with large dispersion allow the transmission of their genomes to a large portion of the population.

In this section, the nature of locomotion behavior was studied and dispersion was shown as emerging from altruistic behaviors. When moderately altruistic behaviors are used (evolved or xed), locomotion strategies with small dispersion rates emerge as a consequence of the maximization of the inclusive tness by the mEDEA algorithm. Moreover, experiments have shown that when a (too) strong level of altruism is articially enforced agents are acting so as to minimize relatedness with other agents.

Eect of Environmental Setup

The environment itself has an impact in the selection pressure applied to the genomes by modifying the opportunity for two agents to meet. Researchers in evolutionary ecology have termed this property of the environment viscosity [Mitteldorf and Wilson, 2000]. A larger viscosity results in fewer genomes transmissions and higher level of relatedness between neighbor agents. It is therefore expected that a large environment viscosity will lead to the evolution of large level of altruism.

In order to test the inuence of the environment, the radius of communication is increased to its maximal value (that is to say greater than the diagonal of the environment). A large set of experiments is performed under various environmental pressures by setting a specic value of EP Lag M ax for each run, ranging from 25 steps (easy environment) to 400 steps (dicult environment), for a total of 16 setups. For each setup (i.e. a xed value of EP Lag M ax ), at least 200 independent runs were performed (for a total of more than 3200 experiments) and the results are aggregated to extract two indicators: the number of active agents, and the cost measure. The ratio of extinguished runs was also extracted (number of extinguished runs divided by the number of successful runs).

The aggregated results of the last 10 generations are summarized in Figures 6. 10, 6.11(a) and 6.11(b) (resp. ratio of extinguished runs, number of active agents, and cost measure).

Before analyzing the impact of diminishing environment viscosity on the level of altruism evolved, two elements can already be highlighted: Diculty of the tasks: Figure 6.10 shows that, for every environmental pressures greater than 50, the extinction rate is at least one order of magnitude lower than on Figure 6.2. This shows that the task is easier with a maximal radius of communication. This is coherent with the observations we made in Chapter 4, i.e. the radius of communication has a high impact on the selection pressure. A large radius of communication results in the transmission of one genome to every agents present in the population, therefore relaxing the pressure to ensure the Performance of the algorithm: The number of active agents displayed on Figure 6.11(a) is lower for larger radii of communication (pvalue < 2.2 * 10 -16 for every environmental pressures). This shows eectively that relaxing the pressure to propagate genomes impacts negatively the eciency of the algorithm.

When the environmental pressure is lower than EP Lag M ax = 200 the distinction between the level of altruism evolved with each communication radius can't be made with certainty (detailed statistical tests in Table 8.1 in annex). However, above this threshold the level of altruism evolved is always lower with the largest communication radius. This result tend to conrm our hypothesis on the impact of genotypic relatedness on the evolution of altruism by the mEDEA algorithm: large radii of communications impact negatively the relatedness between neighbor agents, thus reducing the impact of altruistic actions on inclusive tness.

Altruism and Relatedness

From the perspective of Hamilton's inclusive tness [Hamilton, 1964], closely related individuals tend to display larger levels of altruism. The intrinsic mechanisms in the algorithm, in particular conservative mutation, already imply a strong genotypic relation between one genome and its osprings. This close link between genomes in the population might explain the evolution of higher level of altruism.

In this section, mEDEA is modied in order to control the level of altruism thanks to genotypic relatedness.

As presented in Section 6.1.1, kin recognition is a mechanism used in articial and biological systems to increase the eect of kin selection. Kin recognition mechanism is implemented in mEDEA with few modications to the algorithm. The impact of such operator on the genotypic relatedness, and the evolution of altruistic behaviors is studied.

Eect of Kin-recognition

In practice, the random selection mechanism of mEDEA is replaced by a tournament selection [Miller and Goldberg, 1995] (also embedded in each agent). In this implementation the ranking is based on the genotypic (euclidian) distance between the previously active genome and the locally available genomes (the closer, the better). Thus the mEDEA algorithm is modied to: High transmission probability: When every genome has a high probability to be selected by at least one other agent in the next generation, each will propagate to a small number of agents. This leads to an increased heterogeneity in the population.

Low transmission probability: When few genomes are selected at the next generation, selected genomes will propagate to a high number of agents. Therefore, soon every agents will inherit from only one genome found a few generations earlier (homogeneous population).

The global probability of transmission is measured a posteriori by counting the number of generations to the Most Related Common Ancestor (MRCA), that is to say the rst ancestor from which all current genomes are inheriting. For example, in Figure 6.15, the genome G1 (generation N-3) is the MRCA of all genomes at the generation N, and the number of generations to the MRCA is 3. When the number of generation to the MRCA is low (few genomes propagate quickly in many agents), the selection pressure is high. Reciprocally, when the number of generation to the MRCA is high (many genomes propagate to few agents), the selection pressure is low.

The number of generations to the MRCA is computed for all successful experiments of each of the 16 setups and for both selection scheme (pure-random and kin-tournament selection). Figures 6. 16(a), and 6.16(b) shows the number of generations to the MRCA for the last 10 generations of all successful runs for each setup (i.e. after convergence to stable behaviors). Three main observations are drawn Therefore, kin-selection is expected to be an eective mechanism to explain the natural emergence of altruism. In our experiments, the natural kin-selection is faced with two dierent selection schemes:

Pure-random: With this selection scheme, a successful reproductive strategy is to meet as much agents as possible, i.e. cover a large proportion of the environment. In this context the selection pressure is low, which produces a relatively heterogeneous population. This means that the agents met don't share necessarily the same genes, so an altruistic act is likely to help a none related genome. In this context, the reproduction strategy goes against the altruistic pressure (leaving energy for its relatives).

Kin-tournament: With this selection scheme, a successful reproductive strategy is to remain in the same neighborhood in order to meet closely related agents (which are more likely to select the genome). This behavior results in high selection pressures and therefore in homogeneous populations. As a consequence, by being altruist an agent has a high probability to help its relatives and enhance the propagation of its own genes. The reproduction strategy goes then along the altruistic pressure.

Moreover, the impact of altruism's level on the performances of the algorithm has been assessed in The work presented in this thesis targets the self-adaptation of a population of robots to unknown and possibly changing environments. This problem is the rst step toward the maintenance of a robotic service necessary to perform tasks assigned by the human engineer. As environments considered remain largely unknown, the integrity of robots can't be optimized by the human engineer. Therefore, the maintenance of integrity has to be autonomously addressed by robots by relying solely on the pressure of the environment. These issues are formalized under a new class of problem termed Environment-driven Distributed Evolutionary Adaptation (EDEA).

The minimal set of mechanisms necessary to the resolution of this trade-o is implemented in an algorithm termed mEDEA. Performances of this algorithm have been evaluated in several environments, with dierent levels of challenge.

In Chapter 4, the mEDEA algorithm has been evaluated in a simple setup, in order to assess its ability to ensure robots integrity. In this context, the mEDEA algorithm evolves eciently behaviors to maintain the integrity of robots. In this context, the mEDEA is shown to converge toward behavioral consensus when large populations are considered. The applicability of the mEDEA algorithm on real robots has also been validated. Notably, evolutionary dynamics observed are similar to the ones obtained in simulation.

In Chapter 5, the robustness of mEDEA to unpredictable environmental changes has been tested. In this context mEDEA has shown the optimization of behaviors toward a maximization of robots' integrity. To do so, mEDEA achieves a trade-o between possibly antagonistic motivations from the genomes view point (survival of the robots, and spreading of the genome).

Finally, adversarial environments have been used to test the possibility to evolve altruistic behaviors with mEDEA (see Chapter 6). Experiments have shown that in the mEDEA algorithm, the selsh interest of genes may result in behaviors maximizing the global welfare of the group of robots through altruistic behaviors. The evolution of sub-optimal behaviors by the mEDEA algorithm have also been analyzed and explained by the importance of the locality of interactions.

Discussion

Limitations of the algorithm:

In order to ease the study of evolutionary dynamics displayed by the mEDEA algorithm, the following parameters have been xed: size of the radius of communication, evaluation duration and parameters of the controller architecture. The restriction of these parameters naturally hinder the variety of behaviors evolved by the mEDEA algorithm. Evolving or setting dierent values for these parameters may be necessary in particular contexts. This could be done by adding the parameters to the genome evolved (as it has been done with the σ parameter). Another way would be to add parameter tunning algorithms embedded in each robot [START_REF] Tabatabaee | [END_REF]. This requires further experiments to evaluate the sensitivity of each of these parameters.

Division of labor:

Scenarios where a high number of dierent tasks has to be performed in parallel constitute a dicult class of problem. One answer to this problem is the generalization of behaviors to multiple tasks. However such controllers might be too complex to be designed autonomously. The other way to solve this problem is the division of labor. In this context, groups of robots are divided into sub-groups, each optimized for the realization of a sub-task.

Within EDEA algorithms, the division of groups of robots in sub-groups (in order to specialize for the resolution of a task), could be seen as speciation. Preliminary experiments have shown the possibility for the mEDEA algorithm to evolve multiple species within one experiment. These experiments were based on the exploitation of multiple energy sources for the survival of agents. The evolution of species was possible depending on the degree of communication between agents. Three cases are dierentiated: allopatric, sympatric, and parapatric speciation. Allopatric speciation occurs when dierent species are physically separated one from another. This case is trivial from the point of view of the mEDEA algorithm, and multiple species have been evolved in control experiments.

Sympatric speciation occurs when one species divides in two species while the two remain in the same environment. This case is highly dicult to solve by the mEDEA algorithm as evolutionary dynamics naturally tend toward the homogeneity of the population. Preliminary experiments have shown that in a context where two energy sources are available (each able to sustain half of the population), the population will remain homogeneous and exploit only one source.

The parapatric speciation is a phenomenon occuring when species don't completely overlap, but have some interactions. This situation has been modeled in multiple experiments including xed and moving agents. Preliminary experiments have shown that parapatric speciation can evolve in a narrow range of environmental constraints in a setup with xed agents, and in few simulations in a setup with moving agents. Further experimentations will be performed to target the evolution of parapatric speciation.

Toward achieving tasks

In this thesis we have tackled the challenges raised by the evolution of behaviors targeting the survival of agents in unknown and possibly changing environments. This is a rst step to ensure the availability of robots whose nal goal is to address a task assigned by the human engineer.

The next step in the resolution of the global challenge is the maintenance of the quality of service. While the survival of robots is a required element to solve this problem, others problems have to be considered, such as for example the maintenance of a radio network. Indeed, the possibility to reach every robots of a group may be necessary to transmit new orders, or new informations essentials to the integrity of robots. Another additional problem is to ensure that robots are physically able to perform a task. A robot currently surviving in the environment but with an important tool broken, is as useless for the Evolutionary Algorithm as an inactive robot. The integration of services' constrains within EDEA algorithms can be performed by the ranking of solutions with regards to the quality of service. This mechanism would favor strategies providing a better quality of service among those able to ensure robot's integrity.

On top of ensuring the integrity of the swarm and maintaining the required quality of service from robots, the nal step is to actually solve a task assigned by the human engineer. This implies to integrate a bias from a human engineer in the so far autonomous selection process. This integration should solve a trade-o between selecting strategies good for the quality of service and strategies good to solve the task. This trade-o might actually be solved by the implementation of a decentralized version of a multi-objective algorithms such as NSGA-II [START_REF] Chair | [END_REF] within an EDEA algorithm. Another issue is the design of the representation scheme used to store a robot design. On the hand, this representation scheme should be able to store the multiple behaviors and design choice resulting from three dierent need (integrity, quality of service, resolution of a task). On the other hand, the representation should be simple enough to be manipulable by the evolutionary process embedded in each robot. If these two constraints are antagonist, a trade-o has to be set during the design of the representation scheme.

Perspectives 7.3.1 Communication

Application to the mEDEA algorithm In order to optimize the resolution of a task specied by the human engineer, the availability of robots has to be proposed as a service. The optimization of task requiring strong cooperation between robots, may benet from a robotic service with communication properties. However, in order to be ecient, this communication should be tailored to the robots, task and environment at hand. Therefore, communicative behaviors should be designed autonomously as part of solutions to maintain integrity. The use of communication by animals has been widely observed in dierent contexts, and multiple contributions have investigated for the conditions necessary to its evolution [Roberts and Sherratt, 2002;[START_REF] Mitri | [END_REF]. We provide here an overview of the conclusion drawn by these studies, and provide insight on the applicability of there founding in evolutionary robotics setup.

Biological interpretation A mechanism for the emergence of signals from cues has been proposed in [Tinbergen, 1964]: ritualization. This mechanism is based on the perception of cues by one agent involuntarily emitted by another agent. From this point the receiver evolves a reaction for this cue, and the emitter evolves a behavior for the impact the cue has on the receiver. The cue is then ritualized in a signal, and its impact on behaviors might be unrelated to its origin. This notion has been reinterpreted in the mind-reader/manipulator framework [START_REF] Krebs | [END_REF]. This notion is illustrated by two wolfs ghting against each other (for mating or food). The ght will escalate up to the point where one will bite the other. To do so, the attacking wolf has to bare it's teeth right before bitting. This can be considered as a clue given to other wolf which can read it in order to guide its next action (e.g. avoid, ee, attack). This means that the reaction to the bitting cue can evolve since it will provide a tness bonus to the wolf able to avoid a dangerous attacker. From this point, the tooth-baring by the attacker can be selected for the alteration of behavior it produces on the receiver. The tooth-baring is then considered as a signal since both the receiver's and emitter's response, have evolved because of there outcome.

In the mind-reader/manipulator framework, the emitter of the signal (tooth-baring) is considered as a manipulator since it manipulates the response of the other wolf thanks to its behavior. On the other side, the receiver of the signal is considered as a mind-reader since it read the intention of the rst wolf from its behavior. Therefore, even if wolfs are competing, the signaling can emerge from a an arm-race between mind-reader and manipulator.

In-silico experimentation From the best of our knowledge, ve works have studied the ritualization of clues into signals in virtual environments. [Quinn et al., 2002;Williams et al., 2008] are using setups where physical agents beneted directly from the evolution of communication (either the same genome in all agents, or the maximization of the tness function required a high level of communication). The work done in [Quinn, 2001] has been reproduced by [START_REF] Arranz | [END_REF], where Quinn's conclusion have been challenged. From the results obtained by [START_REF] Arranz | [END_REF], no ritualization emerges since the signal isn't amplied and repeated. The last contribution in [START_REF] Mitri | [END_REF] is concerned with the evolution of communication in adversarial environments. The results obtained have shown that when agents can control the intensity of cues emitted, they would reduce it. This evolutionary dynamic shows an absence of ritualization and therefore a tendency to inhibit communication in competitive scenarios.

From the previously exposed literature we can make the assumption that the ritualization of cues is a good explanation for the emergence of communication when agents have conicting interest in the biological world. However, experiments performed in competitive scenarios have shown the inhibition of cues rather than their ritualization. An hypothesis to explain these dierences is the lack of consideration of genotypic relatedness in virtual environments.

7.3.2

Toward New EDEA Algorithms

The mEDEA algorithm is a minimal demonstration of EDEA algorithms. As such, only the basic features have been implemented. Multiple aspects of this algorithm could be improved by relying on the contributions made to the ER eld. The list of contributions of possible interest to the design of better EDEA algorithms given here, isn't meant to be complete.

Covariance matrix

Covariance matrix have proved to be an ecient evolutionary method in the design of ES algorithms such as CMA-ES [Hansen, 2006]. This mechanism is based on the association of one mutation parameter σ for each dimension of the search space. The covariance matrix is updated based on the distribution of the best individual of a given generation. Thanks to this, mutations are preferably performed toward most promising parts of the search space. This algorithm has shown its eciency in a large range of problems [START_REF] Hansen | [END_REF][START_REF] Hansen | [END_REF]. Moreover its use doesn't require the tunning of parameters as they are all handled autonomously by the algorithm (except the population size).

The integration of covariance matrix mutation scheme in EDEA algorithms could reduce the number of generations required to nd suitable solutions. However its implementation might be a challenge as it requires evaluations of multiple solutions in comparable environments. In our context, the environment might change anytime, and the evaluation of two individuals may occur in dierent environments. As a consequence the implementation of such algorithm should be able to deal with highly noisy tness functions. In addition a decentralized avor of the algorithm should be used, in order to take advantage of the use of multiple robots.

Novelty mechanism

Evolutionary algorithms are known to evolve sub-optimal but simple behaviors in front of challenging tasks. The novelty mechanism is proposed as a way to promote the evolution of more complex solutions which might be more suited [START_REF] Lehman | [END_REF]. Authors' underlying goal is to observe open-ended evolution (as no particular area of the search space is targeted). The novelty mechanism is based on the selection of solutions able to show a behavior never seen before even if not better. It's success has been demonstrated in bipedal walking [START_REF] Lehman | [END_REF].

In complex environments the most basic behavior to maintain integrity might be too complex to be found by chance (bootstrap problem). The novelty mechanism may be then useful to promote genomes with original behaviors, until integrity can be ensured. However, the implementation of a novelty mechanism is challenging in the EDEA context, as comparison between multiple solutions in similar contexts should be provided. This challenge could be solved by maintaining a list of observed behavior individually within each robot, and then compute locally the novelty score of each genome received. The evaluation time necessary for the computation of a novelty score can be saved if a representation of the behavior expressed is sent along each genome.

Diversity mechanism

The diversity mechanism aims at addressing the common bootstrap problem in Evolutionary Algorithms. This problem is encountered when all solutions perform equally bad during the rst generations. When this situation arise the selection mechanism can't select the most promising behavior as all of them looks bad. The diversity mechanism proposed in [Mouret and Doncieux, 2009b] aim at conserving behaviorally dierent solutions until a solution signicantly above the others is found.

In the experiments performed with the mEDEA algorithm the bootstrap problem hasn't been observed, probably due to the choice of setups. Facing more challenging situation the bootstrap problem is bound to occur in EDEA problems. As a consequence the diversity mechanism could be a solution to address more challenging scenarios. Moreover the maintenance of diversity within the solutions used might help to cope faster with environmental changes.

Behavioral complexity

The addition of memory to robotic controllers might help in environments where the integrity depends on a sequence of tasks (e.g. pushing a button to open a door). This research track has been explored by works on recurrent networks such as Elman networks [Elman, 1990], and Echo State Network [Jaeger and Haas, 2004]. Another property useful to answer complex tasks is the use of modularity within one controller (functional or structural). Modularity is the clear identication of the localization of an element either functional or structural [Lipson, 2007]. This property allows the evolution to re-use lower level blocks to compose high level behaviors. It's positive impact on the evolution of robots' controller has been shown in [Mouret and Doncieux, 2008;Cazenille et al., 2012].

The implementation of controllers endowed with such properties might be challenging because of the computational limitation of robots. In order to face this challenge new implementations have to be designed, targeting similar properties but remaining suited to a use on real hardware.

7.3.3

A tool for Evolutionary Ecology

The evolutionary ecology eld studies the interplays between evolutionary history and ecological systems. The main questions targeted by this eld are the following [Fox et al., 2001]: understanding the condition in which natural selection operate, predicting whether and how the natural selection will favor a genotypic trait on others, understanding why a given phenotype inuence an agent's tness, and evaluate if phenotypic variations observed represent long-term outcome of evolutionary process.

Figure 1 . 1 :

 11 Figure 1.1: Representation of a behavior part of a subsomption architecture. From A Robust Layered Control System for a Mobile Robot (1986).

Figure 2 . 1 :

 21 Figure 2.1: Schematic representation of an Evolutionary Algorithm's concept.

  Recombination: Recombination operators are used on two or more individuals. They are used to recombine the genotype of multiple individuals in a new individual. The main incentive to use 2.1. Principles of Evolutionary Computation 23 this operator is to generate a new individual combining the strength of the original individuals. These variations are also based on stochastic operators.

Figure 2 . 2 :

 22 Figure 2.2: The experimental setup used with the real robot.

Figure 2 . 3 :

 23 Figure 2.3: The experimental set-up: the Cortex M3 board connected to Symbricator3d.

  Encapsulated and Distributed.

  solve all the challenges mentioned earlier, we propose a new method called Environmentdriven Distributed Evolutionary Adaptation (EDEA). The Table3.2 proposes a classication of the works reviewed in this thesis and highlight the positionning of the EDEA problem. EDEA methods are environment-driven algorithms aiming at ensuring the integrity of a group of robots based on the survival and reproduction abilities of each robot. That is to say, the more ecient is a strategy Chapter 3

  Figure 3.1: Illustration of EDEA principles.

Figure 4

 4 Figure 4.1: The two-suns setup: a swarm of agents is dropped into an empty environment where a sun is present (the circle on the left of the image). Each agent gets information about its distance and orientation with respect to the sun, but the sun itself gives no direct advantage whatsoever (e.g. no energy). Every 50 generations, the current sun disappears and another sun appears at the opposite end of the arena.

  Figure 4.2: Number of successful runs (out of 24, for each population size) for dierent values of radio communication length (r = 16, r = 32 or r = 64).A run is successful whenever at least one agent is still alive at the end of the last generation. In practice however, successful runs always feature healthy population (ie. most agents are alive). These graphs illustrate an abrupt phase transition in the parameter space (considering population size and radio communication length) before which agents do not survive (ie. mating becomes too dicult).

Figure 4 . 4 :

 44 Figure 4.4: Example of consensus toward the sun (extracted from one run with pop size = 29, r = 32).

Figure 4 . 5 :

 45 Figure 4.5: Example of consensus toward the side opposite to the sun (extracted from one run with pop size = 80, r = 32)

Figure 4 . 6 :

 46 Figure 4.6: Example of several simultaneous consensus during one run (extracted from one run with pop size = 30, r = 32)

Figure 4 . 7 :

 47 Figure 4.7: Example of a run where agents ignore the sun, except at the very end (extracted from one run with pop size = 26, r = 32)

Figure 4

 4 Figure 4.8: Example of run where the population faces extinction (extracted from one run with pop size = 24, r= 32). This is but one particular example of run leading to extinction and is displayed here for illustration purpose. In this run, the agents were actually able to reach a consensus for some time. However, the relatively low population and medium communication range created a context within which a series of unsuccessful mutation (around generation 120) could not be recovered from and quickly lead to complete extinction.

Figure 4

 4 Figure4.9: Left: e-puck Linux extension board with USB WiFi card (casing removed). Middle: An e-puck with Linux board tted in between the e-puck motherboard (lower) and the e-puck speaker board (upper). Also note the yellow `hat' which here serves three dierent functions: (1) it provides a matrix of pins for the reective spheres which allow the tracking system to identify and track each robot, and (2) it provides a mounting for the USB WiFi card which slots in horizontally (the wires connecting to the WiFi card are above the USB connector). Right: experimental swarm robotics arena with 10 Linux extended e-pucks.

Figure 4 .

 4 Figure 4.10: Experimental infrastructure for swarm robotics research based on the Linux extended e-puck. The Swarm Lab Server provides a data logging capability that combines and time stamps position tracking data collected by the Viconsystem with robot status and sensor data from the e-pucks via WiFi, into a log le for post-analysis of experimental runs.

Figure 4 .

 4 Figure 4.11: Illustration from the experiment described in the text. Above: emergence of consensus to go toward the sun. Below: impact of changing the sun location (caption 2 shows the human changing the sun location) and convergence of the robots to the new location.

Figure 4 .

 4 Figure 4.12: Number of active robots during a selected experiment. Small bars correspond to one of the robots restarting. The high bar corresponds to the sun location changing event.

Figure 4 .

 4 Figure 4.13: Distance of the robots to the sun at every time step during a selected experiment.Darker regions imply more robots are located at this particular distance from the sun. The high bar corresponds to the sun location changing event.

Figure 4 .

 4 Figure 4.14: Tracking the values for each robot at each generation of genes related to the sun orientation: NN weights connecting the sun's orientation to (a) agent rotational speed (sun-orientation gene) and (b) agent translation speed (sun-distance gene). The high bar corresponds to sun location changing event.

Figure 5

 5 Figure 5.1: Snapshot from the simulator with 100 agents. Yellow: food items. Red: agents, modeled after an e-puck robot. Blue: range of proximity sensors (the range of proximity sensors is reduced in this snapshot for visibility issues).

  Figure 5.2: Results over 100 runs for the change of environment experiment: number of active agent, size of genomes list, number of energy point harvested, σ mutation parameters

Figure 5 . 3 :

 53 Figure 5.3: Experimental results for four (randomly chosen) specic runs.

Figure 5

 5 Figure 5.4: Typical examples of agents' behavioral traces in the free-run setup. The square symbol shows the agent starting points. Agents are tested in environments with or without walls (i.e. black bars).

Figure 5 Figure 5

 55 Figure 5.5: Typical examples of agents' behavioral traces in the energy setup. The coloured traces account for the current energy level of the agent (see legend). The square symbol shows the agent starting points. Agents are tested in environments with or without walls.

Chapter 6 .

 6 Evolution of Altruistic BehaviorsCooperation.

Figure 6 . 1 :

 61 Figure 6.1: Snapshot from the simulator: food items (circles), agents (dots) and obstacles

  , 6.3(a) and 6.3(b) (resp. ratio of extinguished runs, number of active agents, and cost of altruism). A run is classied as successful if more than one agent is active at the 400000 th iteration (the last one), that is to say after 1000 theoretical generations. A theoretical generation is a generation in the classical sense of Evolutionary Algorithms (when the replacement of an old population is done synchronously). The number theoretical generations is obtained by dividing the number of iterations by the length of one lifetime. When the number of active agents drops to 0 before the last iteration, the run is labeled as extinguished. In order to obtain comparable results the same number of successful runs has been generated for each environmental pressure. However, for high environmental pressures, most of the runs are extinguished. The Figure6.2 shows the number of extinguished runs, divided by the number successful runs. The Figures 6.3(a) and 6.3(b) are produced by taking into consideration the last 10 generations of all successful runs for each setup (i.e. after convergence to stable behaviors).

  M ax = 100 (pvalue = 0.01857 between EP Lag M ax = 25 run for different environmental pressures

Figure 6 . 2 :

 62 Figure 6.2: Results with EP Lag M ax between 25 and 400: Extinction rate (data: value from each run)

  Figure 6.3: Results with EP Lag M ax between 25 and 400: a) Number of active agent (data: value from each run) ; b) Cost measure (data: median values from each run)

Figure 6

 6 Figure 6.4: Ratio of successful runs for dierent harvesting strategies (evolved and Cost between and 45) measured when the pressure of the environment increases by step of 80 iterations every iterations (from an easy environmental pressure, i.e. EP Lag M ax = 25 iterations)

  Figure 6.6: Area covered by agents measured when the pressure of the environment increases by step of 80 iterations every 4000 iterations from iteration 400000 (before the environmental pressure is EP Lag M ax = 25 iterations): a) With harvesting strategy xed to Cost = 5; b) With harvesting strategy xed to Cost = 40.

Figure

  Figure6.6(a) shows similar evolutionary dynamics as the one displayed in Figure6.7(b). Moreover dispersions rate of agents on the two last iterations of Figures 6.6(a) and 6.7(b) are similar (p-value > 0.05). This shows that the emergence of spatial behaviors is inuenced by the harvesting strategy, even if it is a xed one.Following previous arguments, the highest level of altruism should be associated with spatial behaviors displaying small dispersion rates. However, higher levels of dispersion are associated with the highest level of altruism tested. Indeed, values displayed in Figure6.6(b) are signicantly higher than the ones presented in Figure6.7(b) from iteration 440000 (pvalue < 0.05).An hypothesis to explain this dierence is the following. When a high level of altruism is used each agent harvest few energy from each energy point. As a consequence the inclusive tness of each agent can be hardly maximized. Therefore the success of a gene in the population is favored by its capacity to spread itself, that is to say to display spatial behavior with high dispersion rates.In order to test this hypothesis the performance as the number of active agents is measured on each run.Figures 6.8(a), and 6.8(b) show the number of active agents respectively when the harvesting strategy is xed to a moderately altruistic behavior, and when the harvesting strategy is xed to a strongly altruistic behavior. Figure6.9 shows the number of active agents when the harvesting strategy is evolved.

Figure 6 . 8 :

 68 Figure 6.8: Number of active agents measured when the pressure of the environment increases by step of 80 iterations every 4000 iterations from iteration 400000 (before the environmental pressure is EP Lag M ax = 25 iterations) : a) With harvesting strategy xed to Cost = 5; b) With harvesting strategy xed to Cost = 40.

Figure 6 . 9 :

 69 Figure 6.9: Number of active agents measured when the harvesting strategy evolves and the pressure of the environment increases by step of 80 iterations every 4000 iterations from iteration 400000 (before the environmental pressure is EP Lag M ax = 25 iterations)

  Figure 6.10: Results with EP Lag M ax between 25 and 400, and a communication radius of 1156 pixels: Extinction rate (data: value from each run)

Figure 6

 6 Figure 6.12: Results with EP Lag M ax between 25 and 400: a) Cost measure with kin-tournament selection scheme (data: median values from each run) ; b) Cost measure with pure random selection scheme (data: median values from each run)

  Figure 6.16: Results with EP Lag M ax = 200: a) Number of generations to the most related common ancestor when using kin-tournament selection scheme (data: median values from each run) ; b) Number of generations to the most related common ancestor when using pure random selection scheme (data: median values from each run)

  The sub-eld of Embodied Evolutionary Robotics (EE) is interested in the automatic design of controllers for large groups of robots. More precisely this eld is interested in problems where groups of robots have to evolve and perform tasks in complete autonomy, with similar constraints as on-line on-board methods (see Section 2.4.2), but with group of robots rather than a single robot.

		Chapter 3. Environment-driven Distributed Evolutionary Adaptation
	3.3.2	Embodied Evolutionary Robotics
	Evolutionary Robotics is an optimization method based on Evolutionary Computation methods that
	target the design robots' controllers (presented in Section 2.1). In this context, the behavior of a robot
	is optimized by modifying the parameters of its controller. All controllers considered are operating
	directly in continuous state and action spaces. Contributions to this eld have been reviewed in
	Chapter 2.

Table 3 .

 3 2: Classication of Embodied Evolution (EE), Open-ended Evolution in Articial Life (ALife)

Table 4

 4

	Parameter	Value
	arena width and length	1024 * 530 pixels
	sun location switch	every 50 generations
	lifetime (i.e. generation duration)	400 steps per generation
	population size	10 to 80 agents
	proximity sensor range	64 pixels
	radio broadcast signal	16, 32, and 64 pixels
	agent rotational velocity	0.52 rad/s
	agent translational velocity	2 pixels/step
	genome length	68 real values (67 MLP weights + σ)
	variation operator	Gaussian mutation with σ parameter
	σ minV alue	0.01
	σ maxV alue	0.5
	σ initialV alue	0.1
	α (ie. σ update parameter)	0.35

.1: Parameters for experiments.

Table 4 .

 4 2: Various types of consensus. behavioral level: each graph accounts for the nal (i.e. the last step of the last generation) positions of all agents from the 24 independent runs for each population size. Both agents' nal orientation and distance to the center of the arena are plotted. Distance and orientation are given with regards to an imaginary vector at the center of the arena (position (0,0)), facing North (i.e. upwards). Distance is normalized between 0 (center of the arena) and 100 (farthest possible location). As an example,

(orientation=West, distance=80) corresponds to an agent standing near, but not close to, the right border of the arena.

Graphs from Figure

4

.3 illustrate that in most experiments, the vast majority of agents stand very close to the sun (west, far away from center), and that the (few) remaining agents are located in the region of the arena opposite the sun with a preference for corners (either North-East-East or South-East-East, far away from the center). From these graphs, we can see that at least two kinds of consensus have emerged, which we will call: toward sun and away from sun. However, questions remain open as to the existence of other kinds of consensus and/or the possibly simultaneous occurrence of several types of consensus. These questions were addressed by taking a closer look at the experiments from the qualitative viewpoint (i.e. hand analysis of the logs) to identify the kind of consensus reached. Table

4

.2 summarizes the results and points to

Figures 4.4, 4.5, 4.6, 4.7, and 4

.8 for illustration purposes. Results shown in the table were aggregated by randomly sampling one run of each parameter setting and qualitatively evaluating the outcome of the simulation by a human expert.

  solution: the search space has been limited to a simple two-layer perceptron with no hidden layer, in contrast with previous experiments. Moreover, a large initial mutation rate is chosen. As few robots are available, large values of σ should promote the discovery of new solutions. Thus σ init is set to 0.1, σ max to 0.4 and σ min is xed at 0.05.

	Risk of extinction due to small populations:
	diagnosis: as shown in section 4.2 small populations are more prone to extinction, implying
	time consuming interventions from the human supervisor.

solution: a restart procedure is introduced into the algorithm. Whenever a robot stands inactive for 5 consecutive generations it simply picks a new genome with random values. This simple feature thus makes it possible to avoid extinction and start possibly from more promising regions in the search space.

Lack of global synchronisation:

diagnosis: generation count among robots cannot be synchronised on a global basis, resulting in robots with genomes from dierent generations.

Table 5

 5

	Parameter		Value
	arena width and length		1024 * 530 pixels
	free-run setup duration		75 generations
	energy setup duration		75 generations
	lifetime (i.e. generation duration)	400 steps per generation
	population size		100 agents
	agent diameter		1 pixel
	proximity sensor range		64 pixels
	radio broadcast signal		32 pixels
	agent rotational velocity		0.52 rad/s
	agent translational velocity		2 pixels/step
	genome length		79 real values (78 MLP weights + σ)
	variation operator		Gaussian mutation with σ parameter
	σ minV alue		0.01
	σ maxV alue		0.5
	σ initialV alue		0.1
	α (ie. σ update parameter)		0.35
	Table 5.1: Parameters for experiments.
	energy setup only:
	food items		2000
	food item diameter		10 pixels
	food item regrow delay	btw 400 and 4000 steps (see text)
	energy per food item		100 energy units
	agent energy consumption		1 energy unit per step
	agent maximum energy level		400 energy units
	agent initial energy level		400 energy units

.2: Parameters for experiments -Specic to the energy setup.

http://www.homelandsecuritynewswire.com/more-uavs-personnel-money-us-mexico-border-protection -Retrieved 12 December 2012

http://www.wowwee.com/en/products/tech/telepresence/rovio/rovio -Retrived 5 December 2012

http://www.irobot.com/us/robots/home/roomba.aspx -Retrieved 12 December 2012

http://www.sony.co.uk/support/en/hub/ERS -Retrieved 5 December 2012

http://www.cse.unsw.edu.au/help/students/robocup/robots.html -Retrieved 5 December 2012

http://ardrone2.parrot.com/ -Retrived 5 December 2012

http://www.aldebaran-robotics.com/en/ -Retrived 5 December 2012

http://www.robotis.com/xe/bioloid_en -Retrived 5 December 2012

http://mindstorms.lego.com/en-us/Default.aspx -Retrived 5 December 2012

http://www.kivasystems.com/ -Retrieved 12 December 2012

https://www.youtube.com/watch?v=1V9XUMCPGF8 -Retrieved 12 December 2012

http://www.nytimes.com/1990/08/29/business/business-technology-what-s-the-best-answer-it-ssurvival-of-the-fittest.html -Retrieved 6

December 2012

Chapter 2. Evolutionary Robotics

http://www.robotis.com/xe/bioloid_en -Retrieved 6 December 2012

EvAg[START_REF] Laredo | [END_REF], and the encapsulated on-line on-bard version of the (µ+1) algorithm[START_REF] Haasdijk | [END_REF]. This algorithm has since then been applied to the study of multi-cellular robots[START_REF] Weel | [END_REF], and the emergence of communication in cooperative tasks[Pineda et al., 2012].[García-Sánchez et al., 2012] have drawn a comparison between three algorithms of this eld :(µ + 1), (µ + 1) hybrid with EvAg, (µ + 1) hybrid with the MultiKulti transmission scheme[Araujo et al., 2008;Araujo and Merelo, 2011]. This work has highlighted the advantages brought by the transmission of genomes between the robots.Finally,[START_REF] Elfwing | [END_REF] study the use of learning algorithm in combination with encapsulated Evolutionary Algorithms. Here the learning algorithms sarsa(λ)[START_REF] Theodoridis | [END_REF] with potential based shaping rewards[START_REF] Ng | [END_REF] is used to learn a set of behavior. An encapsulated genetic algorithm similar to[START_REF] Usui | [END_REF] has been designed to evolve: a Neural Network in charge of selecting the behaviors, the learning parameters, and the shaping reward learning parameter. This work relies partly on an implicit function (a genome is removed from the genotypic pool if the virtual level of energy dropped under 0), partly on the environment pressure (new genomes received are randomly selected for evaluation).Discussion. The EE approaches reviewed in this section are designed to face the challenges meet in real hardware conditions.

Evolutionary Robotics Database: http://www.isir.fr/evorob_db/

10 input neurons ; 5 hidden neurons ; 2 output neurons ; 1 bias neuron. The bias neuron value is xed to 1.0 and projects onto all hidden and output neurons.

http://www.vicon.com

As a counter example, generation times do need to be equal across robots as longer generation times would lead to more opportunities for a genome to spread.

one robot was removed due to technical failure in a previous experiment.

Video publicly available at: http://www.youtube.com/watch?v=_ilRGcJN2nA -Retrieved 19 December 2012) 4.3. Implementation on Real Robots

Chapter 6. Evolution of Altruistic Behaviors

Acknowledgements / Remerciements

Graphs in the right column show agents' distances to the centre of the environment. The three pairs of graphs correspond respectively to experiments where the communication radius is set to 16 (rst row), 32 (second row) and 64 (third row). For each graph, darker regions in the graphs indicate the most commonly observed orientation/distance w.r.t. the centre at the end of experiment (y-axis) for each population size parameter (x-axis) with a given communication radius value (table rows) this representation scheme is commonly known as a heat map. Each row is the result of aggregation of 1704 independent runs.

the population recovers very quickly following environmental change, possibly to stable but limited strategies as the number of active agents is far from the maximum. Also, these histograms lack the misleading artifacts observed in previous graphs regarding the early generations in both setups: genomes from generation 0 do not benet anymore from uniform sampling of starting location, and genomes from generation 75 start with the same initial energy level as genomes from every other generation.

Summary and Conclusions

In this chapter, the robustness of the mEDEA algorithm has been assessed in front of unpredicted changes in the environment. Analysis of evolutionary dynamics have illustrated that the selection pressure foreseen in Chapter 4 eectively favors the selection of more ecient individuals. Surviving in aggressive environments may require more complex behavioral patterns than the ones studied here (such as coordination). Sharing similar concerns, previous works in collective intelligence and reinforcement learning have already stressed the issue of the price of anarchy [Wolpert and Tumer, 2001], ie. the cost of ecient selsh behavior with regards to population global welfare. Addressing this issue remains an open problem, especially if there is no explicit objective function to decompose.

In the next chapter, the possibility to evolve cooperative behaviors with mEDEA is tested.

Chapter 6

Evolution of Altruistic Behaviors

Altruistic behavior stresses the sacrice of one agent for the benet (in terms of survival) of other agents, without short term benet for the donor (during its lifetime). As such, it is a non trivial behavior reducing the individual welfare of an altruistic agent in order to enhance the population's welfare. Therefore the evolution of altruistic behaviors, notably by populations facing adversarial environments, is an important problem for algorithms targeting the population's integrity. This chapter aims at answering the following question: Is it possible to evolve altruistic behaviors with mEDEA ?

In order to study the evolution of altruism in mEDEA, a particular setup is presented which is inspired from the Tragedy of the Unmanaged Commons. The tragedy of the Unmanaged Commons is the consequence of the overexploitation of a common resource by a group of agents.

Altruistic behaviors and the tragedy of unmanaged commons are presented in more details in Section 6.1. The methods used to study the evolution of altruism are presented in Section 6.2. Finally, the evolution of altruistic behaviors by the mEDEA algorithm is studied in Sections 6.3 and 6.4.

6.1

Deterministically select the genome closest to the active genome Replace the active genome with a mutated selected genome Tournament selection combined with genotypic distance (termed kin-tournament from now on) makes it possible to introduce a kin recognition mechanism, where the parameter K modies the exploitation rate (the larger K, the more exploitative mEDEA is).

Experiments with a tournament size (K) of 3 (roughly corresponding to medium pressure toward kin selection in this setup) have been achieved with 16 setups, with the environmental pressure ranging from easy (EP Lag M ax = 25) to strong (EP Lag M ax = 400). For each setup, at least 200 successful runs were performed (total of more than 3200 experiments), and statistical test are computed with Mann-Whitley's Test to clearly establish the dierence in performance [Wilcoxon, 1945;[START_REF] Mann | [END_REF]. The costs of altruism evolved are presented in the Figure 6.12(a) by taking into consideration the last 10 generations of all successful runs for each setup (i.e. after convergence to stable behaviors). For comparison purpose the costs of altruism evolved when the pure-random selection scheme is used are recalled in Figure 6.12(b). In the same fashion, Figure 6.13(a) presents the number of active agents of the last 10 generations when using the kin-tournament selection scheme, and Figure 6.13(b) recall the number of active agents of the last 10 generations when the pure-random selection scheme is used. The ratio of extinguished run for every environmental pressures and both selection schemes are presented in Figure 6.14.

Performing kin recognition increases the level of altruism from the environmental pressure (pvalue < 0.003 for EP Lag M ax >= 150, see Table 8.2 in annex for detailed statistical tests). While the number of runs with extinctions is roughly similar (see Table 8.4 in annex for detailed statistical tests), kin recognition suers from a smaller number of active agents under low and high environmental pressures (see Table 8.3 in annex for detailed statistical tests).

Kin-recognition (implemented thanks to the kin-tournament mechanism) is shown to articially increase the already existing level of altruism, at the cost of a decreased overall performance with regards to individual survival. This shows that a modication in the agents' behavior impacts the evolution of behaviors observed at the scale of the population. It also highlights the importance of population homogeneity to the evolution of altruism.

Kin-recognition and Relatedness

By modifying the way genomes are selected, the kin-tournament selection operator is expected to eect the population homogeneity. It has also been considered that increased levels of altruism observed at higher environmental are linked to population homogeneity. Measuring the probability of transmission of one genome to the next generation can help to conrm the relation between population homogeneity and altruism. The rationale is as follow: from these graphs.

The selection pressure is similar in easy environment for both selection scheme (pvalue > 0.25), but highly dierent when the environment is becoming more dicult (pvalue < 10 -16 ). This conrms the impact of kin-recognition on the homogeneity of the population, which is expected to be the main explanation for the evolution of altruism.

Moreover, variations of altruism's levels (shown in Figure 6.12) are roughly correlated with the variations of selection pressures. This statement is supported by the following observations: a) when the selection pressure increases (from an environmental pressure of EP Lag M ax = 100 iterations), the level of altruism increases b) when the selection reaches a stable level (from an environmental pressure of EP Lag M ax = 200 iterations), the level of altruism reaches also a stable level. This conrms the link between population homogeneity and altruism when the environmental pressure increase.

Summary and Conclusions

In this chapter we have detailed how the mEDEA algorithm faces scenarios where the Tragedy of Unmanaged Commons occurs. The evolution of altruism has been seen as a solution, even if not optimal (in terms of number of active agent and ratio of successful runs) in the scenario tested.

In order to obtain a better understanding of the mEDEA algorithm and the reasons for the emergence of altruism, multiple measures on the individuals and their interactions have been performed while varying the selection forces at hand. Based on these experiments a clear explanation for the evolution of altruism can be drawn. A robotic scenario has been chosen where robots are using a limited front of a large range of environmental pressures. From these experiments two main cases are found:

Low environmental pressure: In this context it is usually better to x beforehand the harvesting strategy. Even if the xed cost of altruism chosen isn't the best one, the mEDEA algorithm will exploit behavioral strategies as another way to display altruism. Therefore, diminishing the number of possible behaviors will result in a simpler optimization task, without hindering the integrity capacities.

High environmental pressure: Evolving harvesting strategies leads to a higher adaptability in front of highly challenging environments. However this implies the resolution of a trade-o between harvesting strategy and behavioral strategy by the mEDEA algorithm. Experiments with increasing environmental pressures have shown the ability of the mEDEA algorithm to evolve such trade-o in dicult environments, which results in a higher probability to see the population survive.