Evolution of cooperation in collective adaptive systems (including swarm robotics)

Proposé par: nicolas BREDECHE
Directeur de thèse: nicolas BREDECHE
Directeur de thèse: nicolas BREDECHE
Unité de recherche: UMR 7222 Institut des Systèmes Intelligents et de Robotique

Domaine: Sciences et technologies de l'information et de la communication


Advisor #1 / directeur : Nicolas Bredeche, ISIR/UPMC (nicolas.bredeche@isir.upmc.fr)

Advisor #2 / co-directeur : Jean-Baptiste André, ENS (jeanbaptisteandre@gmail.com)

Mots clés : évolution de la coopération, robotique en essaim, robotique évolutionniste, coopération mutualiste, choix du partenaire

Keywords : evolution of cooperation, swarm robotics, evolutionary robotics, mutualistic cooperation, partner choice

An important challenge in collective systems, whether natural (e.g. : group of hunters) or artificial (e.g. : swarm robotics), is to understand how they are able to adapt in a decentralized manner to novel environmental conditions. Individuals in these systems must be able to acquire new behaviors autonomously (through natural evolution or learning), and they must be able to do so in an open-ended manner, to deal with potentially entirely novel environments.

However, decentralized adaptation poses an important scientific problem as nothing guarantees that adaptive mechanisms taking place at the individual level lead to the establishment of behaviors that are adaptive at the collective level : collective adaptation does not always follow from individual adaptation. First of all, many collectively efficient behaviors require the coordinated action of several individuals, and cannot be reached by the independent improvement of each individual separately. Second, and worst, individual adaptations can even harm, rather than help, collective efficiency if individuals have externalities for each other (e.g. if they enter into competition with one another, if they can underinvest into a collective good, etc.), in which case decentralized individual adaptation shall lead to a reduction of performance of the entire system.

Ever since Darwin, evolutionary biologists have acknowledged and studied this problem [1]. They have proposed various mechanisms through which collectively efficient outcomes (so-called cooperative outcomes) can be reached via individual adaptation [2-6]. Identifying the conditions in which individual adaptation can, or cannot, generate collectively efficient outcomes is indeed important to understand the origin of cooperation in biology, but it is also key to the design of practical solutions for open-ended adaptation in collective artificial systems such as swarm robotics [7,8].

The objective of this thesis will be to explore (at least) one important potential solution to this problem known from evolutionary biology : the role of reputation [9-11]. We will explore whether socially efficient outcomes are more easily reached by individual adaptation, when individuals can recognize others and are informed of their past behavior (their reputation). To this end, we will use evolutionary robotics [12], that is : the artificial evolution of embodied agents, in order to provide an accurate simulation of interactions between individuals.

Evolutionary robotics has originally been proposed as an optimisation method to automate the design process of the decision-making control architectures for complex problems, including those met in collective robotics. It also provides a very convenient framework to extend classical models used in evolutionary game theory with the ability to model and simulate the mechanistic aspects underlying cooperation, such as physical coordination between individuals.


The main goal of this thesis is to better understand the acquisition of cooperative behaviours. This is a central question in evolutionary biology. While cooperative between related individuals (e.g. : members of the same family) is relatively well understood, this is not the case when individuals cooperate while pursuing their own objective (e.g. : maximising hunting success, where cooperation may imply sharing). So far, real world observation are limited in time as observing even bacterial evolution takes year, and theoretical models grasp a abstract representation under hypothesis which may lead to miss important feature. The approach followed in this these, using evolutionary robotics as a modelling and simulation tool, offer a unique way to introduce a more realistic genotype-to-phenotype mapping that appears as critical for studying cooperation [5]. The targeted venues for results obtained during this thesis will be major publications in computational biology and biology (such as Plos Computational Biology or PNAS).

Beyond contributions to evolutionary biology, contributions done in this thesis will also benefit to collective and swarm robotics. In particular, we will focus on embodied evolution, a sub-class of evolutionary robotics algorithms dedicated to distributed on-line learning in open environments. Embodied evolution are so far quite limited with respect to learning cooperative behaviours, except under strong hypotheses, and could greatly benefit from the ability to use reputation obtained by estimating the quality of a particular partner or consensus obtained through distributed interactions.

Ouverture à l'international

Le doctorant sera intégré à l’équipe AMAC de l’ISIR (UPMC), et participera au projet collaboratif européen "DREAM" (H2020-FETPROACT, http://robotsthatdream.org), en particulier dans le work package sur l’apprentissage social et collectif.

Remarques additionnelles

Bibliographie :

[1] Williams, G. C. (1966). Adaptation and natural selection : a critique of some current evolutionary thought. book, Princeton University Press.

[2] Hamilton, W. D. (1964). The genetical evolution of social behaviour, I & II. J Theor Biol, 7, 1–52.

[3] Axelrod, R., & Hamilton, W. D. (1981). The evolution of cooperation. Science, 211(4489), 1390–1396. article.

[4] Leimar, O., & Hammerstein, P. (2010). Cooperation for direct fitness benefits. Philosophical Transactions of the Royal Society B-Biological Sciences, 365(1553), 2619–2626.

[5] Bernard, A., André, J.-B., & Bredeche, N. (2016). To Cooperate or Not to Cooperate : Why Behavioural Mechanisms Matter. PLOS Computational Biology, 12(5), e1004886.

[6] Skyrms, B. (2004). The stag hunt and the evolution of social structure. book, Cambridge : Cambridge University Press.

[7] Bayindir, L., & Sahin, E. (2007) A Review of Studies in Swarm Robotics. Turk J Elec Engin, 15(2), 115–147.

[8] Rubenstein, M., Cornejo, A., & Nagpal, R. (2014) Programmable self-assembly in a thousand-robot swarm. Science, 345(6198), 795–799.

[9] Trivers, R. L. (1971). The evolution of reciprocal altruism. Quarterly Review of Biology, 46, 35–57. article.

[10] Nowak, M. A., & Sigmund, K. (1998). Evolution of indirect reciprocity by image scoring. Nature, 393(6685), 573–577. article.

[11] André, J.-B. (2010). The evolution of reciprocity : social types or social incentives ? The American Naturalist, 175(2), 197–210.

[12] Doncieux S., Bredeche N., Mouret J.-B., Eiben A.E. Evolutionary Robotics : What, Why, and Where to. Frontiers in Robotics and AI, Volume 2, number 4, 2015.

Se connecter

Attention! Moteur de recherche efficace!
EDITE de Paris | SPIP | Remarques | Se connecter | Plan du site | Suivre la vie du site Atom 1.0 | | | Facebook | Twitter | LinkedIn