In swarm robotics, the control of a group of robots is often fully distributed and does not rely on any leader. In this thesis, we are interested in understanding how to design collective decision making processes in such groups. Our approach consists in taking inspiration from nature, and especially from self organization in social insects, in order to produce effective collective behaviors in robot swarms. We have devised four robotics experiments that allow us to study multiple facets of collective decision making. The problems on which we focus include cooperative transport of objects, robot localization, resource selection, and resource discrimination. <p><p>We study how information is transferred inside the groups, how collective decisions arise, and through which particular interactions. Important properties of the groups such as scalability, robustness, and adaptivity are also investigated. We show that collective decisions in robot swarms can effectively arise thanks to simple mechanisms of imitation and amplification. We experimentally demonstrate their implementation with direct or indirect information transfer, and with robots that can distinguish the available options partially or not at all. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

To evaluate voting rules, it would be good to know what universe election outcomes are drawn from. Election theorists have postulated that elections might be drawn from various stochastic preference models, including the IC and IAC conditions, but these models induce empirically contradicted predictions. We use two distinct data sets, FairVote and German Politbarometer survey. Based on the data information, we suggest approaches that differ from those probabilistic models to better approximate the actual data in Chapter 3 and 4. Chapter 5 applies the spatial model for four-candidate in a three-dimensional setting. We also offer a significant gap between the actual and simulated data under the IAC conditions by comparing their statistical characteristics. / Doctor of Philosophy / Through the 1884 Third Reform Act, the plurality rule (or first-past-the-post system) runs to elect parliament members for the first time. More than a hundred years passed after the Act, and election theorists have suggested various alternatives, the plurality rule is the second most used rule worldwide for national elections for now. One main reason is that researchers do not reach an agreement on the best alternative rule. Theorists have evaluated different voting rules under probabilistic assumptions, but real-world examples contradict the predictions of these models. In this dissertation, we suggest different approaches provide a better approximation to the actual data. In Chapter 3 and 4, we go backward: analyze how voters of each preference order are distributed in real data first, then set a model for estimating the frequency of paradox. In chapter 5, we extend an existing model with higher dimensionality. Then using the model, we offer empirical evidence showing the gap between the actual and simulated data under a popular probabilistic model.

In everyday situations individuals make decisions. For example, a tourist usually chooses a crowded or recommended restaurant to have dinner. Perhaps it is an individual decision, but the observed pattern of decision-making is a collective phenomenon. Collective behaviour emerges from the local interactions that give rise to a complex pattern at the group level. In our example, the recommendations or simple copying the choices of others make a crowded restaurant even more crowded. The rules of interaction between individuals are important to study. Such studies should be complemented by biological experiments. Recent studies of collective phenomena in animal groups help us to understand these rules and develop mathematical models of collective behaviour. The most important communication mechanism is positive feedback between group members, which we observe in our example. In this thesis, we use a generic experimentally validated model of positive feedback to study collective decision-making. The first part of the thesis is based on the modelling of decision-making associated to the selection of feeding sites. This has been extensively studied for ants and slime moulds. The main contribution of our research is to demonstrate how such aspects as "irrationality", speed and quality of decisions can be modelled using differential equations. We study bifurcation phenomena and describe collective patterns above critical values of a bifurcation points in mathematical and biological terms. In the second part, we demonstrate how the primitive unicellular slime mould Physarum Polycephalum provides an easy test-bed for theoretical assumptions and model predictions about decision-making. We study its searching strategies and model decision-making associated to the selection of food options. We also consider the aggregation model to investigate the fractal structure of Physarum Polycephalum plasmodia. / <p>Fel serie i tryckt bok /Wrong series in the printed book</p>

Collective decision making can be seen as a means of designing and understanding swarm robotics systems. While decision-making is generally conceived as the cognitive ability of individual agents to select a belief based only on their preferences and available information, collective decision making is a decentralized cognitive process, whereby an ensemble of agents gathers, shares, and processes information as a single organism and makes a choice that is not attributable to any of its individuals. A principled selection of the rules governing this cognitive process allows the designer to define, shape, and foresee the dynamics of the swarm.We begin this monograph by introducing the reader to the topic of collective decision making. We focus on artificial systems for discrete consensus achievement and review the literature of swarm robotics. In this endeavor, we formalize the best-of-n problem—a generalization of the logic underlying several cognitive problems—and define a taxonomy of its possible variants that are of interest for the design of robot swarms. By leveraging on this understanding, we identify the building-blocks that are essential to achieve a collective decision addressing the best-of-n problem: option exploration, opinion dissemination, modulation of positive feedback, and individual decision-making mechanism. We show how a modular perspective of a collective decision-making strategy allows for the systematic modeling of the resulting swarm performance. In doing so, we put forward a modular and model-driven design methodology that allows the designer to study the dynamics of a swarm at different level of abstractions. Successively, we employ the proposed design methodology to derive and to study different collective decision-making strategies for the best-of-n problem. We show how the designed strategies can be readily applied to different real-world scenarios by performing two series of robot experiments. In the first series, we use a swarm of 100 robots to tackle a site-selection scenario; in the second series, we show instead how the same strategies apply to a collective perception scenario. We conclude with a discussion of our research contributions and provide futuredirection of research. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

Les déplacements collectifs se manifestent souvent de façon spectaculaire et intriguent tant les amateurs de la nature que les chercheurs. Comment émergent ces formes spectaculaires et comment la cohésion des groupes est elle assurée ? Si de nombreux travaux ont été consacrés à l'identification des règles permettant la cohésion dans les groupes en mouvement, plus rares sont ceux consacrés aux transitions entre les états d'arrêt et de déplacement. Cette thèse traite des mécanismes comportementaux impliqués dans les prises de décisions collectives et la dynamique de transition de tels évènements chez le mouton Merinos (Ovis aries). Nous proposons de nouvelles hypothèses sur la modulation des interactions entre individus par des effets spatiaux dans des groupes de grande taille. Nous proposons un modèle spatio-temporel reproduisant nos résultats expérimentaux sur les départs, les déplacements collectifs et les arrêts de groupes de taille croissante et permettant d'explorer les décisions collectives dans des conditions nouvelles. Les résultats expérimentaux et théoriques per- mettent d'améliorer la compréhension des mécanismes individuels à l'origine des décision collectives permettant de maintenir ou non la cohésion des groupes. / Collective movements often involve very spectacular displays that fascinate nature lovers and researchers. How do such amazing patterns appear and how group cohesion can be maintained ? If many studies were carried out to decipher the rules underlying cohesion for groups in movement, there is a lack of works adressing the transitions involved in collective movements : departures and stops. This thesis adresses the behavioural mechanisms involved in the collective decision-making processes oc- curing in such transitions in Merino sheep (Ovis aries) groups. We propose some new kinds of spatial hypotheses that can account for the way interactions between individuals are locally modulated in large groups where individuals cannot have an access to the global information of all individuals. We developed a novel spatiotemporal model of sheep collective motion that reproduces the experimental observations and allows to explore the outcomes of collective decisions in various conditions. The experimental and theoretical results increase the understanding of the individual mechanisms that produce collective decisions allowing to maintain group cohesion.

A swarm intelligence system is a type of multiagent system with the following distinctive characteristics: (i) it is composed of a large number of agents, (ii) the agents that comprise the system are simple with respect to the complexity of the task the system is required to perform, (iii) its control relies on principles of decentralization and self-organization, and (iv) its constituent agents interact locally with one another and with their environment. <p><p>Interactions among agents, either direct or indirect through the environment in which they act, are fundamental for swarm intelligence to exist; however, there is a class of interactions, referred to as "interference", that actually blocks or hinders the agents' goal-seeking behavior. For example, competition for space may reduce the mobility of robots in a swarm robotics system, or misleading information may spread through the system in a particle swarm optimization algorithm. One of the most visible effects of interference in a swarm intelligence system is the reduction of its efficiency. In other words, interference increases the time required by the system to reach a desired state. Thus, interference is a fundamental problem which negatively affects the viability of the swarm intelligence approach for solving important, practical problems.<p><p>We propose a framework called "incremental social learning" (ISL) as a solution to the aforementioned problem. It consists of two elements: (i) a growing population of agents, and (ii) a social learning mechanism. Initially, a system under the control of ISL consists of a small population of agents. These agents interact with one another and with their environment for some time before new agents are added to the system according to a predefined schedule. When a new agent is about to be added, it learns socially from a subset of the agents that have been part of the system for some time, and that, as a consequence, may have gathered useful information. The implementation of the social learning mechanism is application-dependent, but the goal is to transfer knowledge from a set of experienced agents that are already in the environment to the newly added agent. The process continues until one of the following criteria is met: (i) the maximum number of agents is reached, (ii) the assigned task is finished, or (iii) the system performs as desired. Starting with a small number of agents reduces interference because it reduces the number of interactions within the system, and thus, fast progress toward the desired state may be achieved. By learning socially, newly added agents acquire knowledge about their environment without incurring the costs of acquiring that knowledge individually. As a result, ISL can make a swarm intelligence system reach a desired state more rapidly. <p><p>We have successfully applied ISL to two very different swarm intelligence systems. We applied ISL to particle swarm optimization algorithms. The results of this study demonstrate that ISL substantially improves the performance of these kinds of algorithms. In fact, two of the resulting algorithms are competitive with state-of-the-art algorithms in the field. The second system to which we applied ISL exploits a collective decision-making mechanism based on an opinion formation model. This mechanism is also one of the original contributions presented in this dissertation. A swarm robotics system under the control of the proposed mechanism allows robots to choose from a set of two actions the action that is fastest to execute. In this case, when only a small proportion of the swarm is able to concurrently execute the alternative actions, ISL substantially improves the system's performance. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

L'objet de cette thèse (bi-disciplinaire, en informatique et sciences politiques) est l'étude de phénomènes d'influence dans des situations de prise de décision collective, impliquant plusieurs sujets interdépendants, ce qui amène à considérer des domaines dits combinatoires. L'importance de ces phénomènes d'influence est observée depuis de nombreuses années dans différents domaines (dont les sciences politiques), mais leur modélisation reste peu développée jusqu'à présent. En se basant sur un modèle existant intégrant la prise en compte de l'influence à un langage de représentation des préférences ordinal, le premier travail de cette thèse a été d'identifier des schémas d'influences pouvant survenir, entre sujets et/ou agents différents. Une deuxième contribution de cette thèse est la prise en compte de domaines partiels (permettant de représenter contraintes exogènes et abstentions, par exemple), une nécessité dans les situations envisagées. De même, différents modèles visant à capturer l'influence simultanée de plusieurs agents sont présentés et discutés. Dans un deuxième temps, l'exemple des votes au conseil de sécurité del'ONU est utilisé: l'occurence de ces schémas est envisagée à l'aide d'une analyse qualitative de différentes séquences de votes (sciences politiques), et de la recherche d'indices de schémas similaires dans les données de vote accessibles. Enfin, le modèle est mobilisé dans le cadre d'une simulation multi-agents (réalisée en Netlogo), et visant à tester différentes réformes envisagées du conseil de sécurité. / Influence study in combinatorial and collective decision-making, is an interdisciplinary research area combining computer science and social science, especially artificial intelligence and collective decision-making. Influence has long been studied, for instance in political science, but in the context of combinatorial and collective decision-making, this calls for a study of how influences works among multi-agents and multi-issues, how influences and decision-making are interleaved, and how the structures of influence among agents and issues produce an effect. In the thesis, we mainly performed three aspects of work:Firstly, build complex models of influence based on preference representation languages and social influence models, proposed a series of new patterns of influence to better describe the complex influences in real-world situation, and discussed a series of theoretical problems of influencing and influenced structure, influence from more than one origins, and influence with abstentions and constraints. We then test the models of influence from an exemplary perspective for interdisciplinary study, from both social science and computer science paradigms, by both qualitative case studies approach and quantitative matching algorithms approach, to provide an evaluation for the models of influence.Finally, we use the models of influence to perform agent-based simulations, by the example UN Security Council voting. We design those experiments from both social and computer science perspectives, implement it in Netlogo, and discuss the interleaved effects between new cases of influence and different SC reform schemes.

Ce doctorat trouve son origine dans la compréhension des prises de décision et des comportements collectifs des animaux. Comment ces derniers parviennent-ils à effectuer des choix collectivement ? Comment les membres d’un groupe procèdent-ils pour synchroniser leurs comportements spatialement et temporellement ? Mon principal objectif a été de dégager, lors des déplacements collectifs et du fur rubbing chez le capucin moine, les évènements décisionnels dépendants de processus anonymes de ceux dépendants de processus liés à l’identité des individus et à leur réseau de relations sociales au sein du groupe. Dans les prises de décision collective relatives aux déplacements, les membres du groupe sont influencés dans leurs choix par leur identité sociale mais aussi par des mécanismes anonymes, de type mimétique. Le fur rubbing est également un comportement collectif dont les mécanismes sous-jacents incluent une dépendance interindividuelle de type mimétique. Des mécanismes similaires mettant en jeu des interactions entre individus basées sur des règles comportementales simples se retrouvent dans chacun des phénomènes collectifs étudiés. Ces résultats sont les premiers à démontrer l’émergence de prises de décision collective à partir de telles interactions anonymes dans un groupe de primates non humains. Ils permettent de faire le lien entre choix individuels et comportement collectif et de mieux concevoir comment un groupe de primates peut se coordonner, maintenir sa cohésion spatiale et synchroniser ses activités./How do animals reach collective consensus? How do group members spatially and temporally synchronise their behaviour? My main purpose was to demonstrate the respective roles of anonymous processes (contagion, mimetism) and individual-dependent processes (hierarchical rank, age, sex, kin, social relationships) in collective decision-making. During decision-making relating to collective movements, group members’ decisions depend on their social identity (individual-dependent mechanism) as well as anonymous processes. Fur rubbing is also a collective behaviour involving interindividual dependence with mimetic underlying mechanisms. We found similar mechanisms, involving interindividual interactions according to simple behavioural rules, in both collective phenomenon studied. These results are the first to demonstrate the emergence of collective decision-making based on anonymous interactions in a group of non human primates. They help to understand the link between individual choices and collective behaviour and to appreciate how a social group of primates maintain its spatial cohesion and synchronize its activities.

En se basant sur le principe organisationnel des deux types d’ensembles politiques rencontrés au Bénin, le but de cette recherche est d’explorer un ou des modèles conjoints, classiques et coutumiers, de participation en vue de promouvoir une démocratie participative plus proche des citoyens. Trois échelons spatiaux ont constitué le terrain de la recherche : l’Afrique, le Bénin centre et les milieux proches des anciennes royautés. La documentation et les données d’observations et d’entrevues ont été analysées par la démarche de théorisation ancrée et l’appréhension des phénomènes socio-spatiaux. Des quatre modèles originaux avec les critères endogènes d’appréciation de la participation mis en évidence et caractérisés dans les cultures du Bénin, deux, Togbésso-Hon-Togbassa et Daŋnou, émergent comme représentatifs des exigences d’une démocratie avec des formes territorialisées de la participation. La mise en perspective de la participation au Bénin avec les États d’Afrique montre une bonne performance qui le fait référencer comme le plus performant pour ses procédures et pratiques et comme source d’inspiration de mise en place des dispositifs participatifs dans le palmarès des grandes démocraties. Ses deux instruments de la décision, l’analyse participative et l’audience publique, restent perfectibles. La première, une innovation intéressante à encadrer, limite la participation à des acteurs choisis selon des critères généralement non énoncés. L’audience publique reste insatisfaisante par son inadéquation à la production de la décision collective et un modèle antinomique de la pensée politique africaine qui vise le consensus dans une démarche inclusive à essence délibérative sous forme de palabre. Fondement de la démocratie participative, la palabre offre le soubassement pour un modèle synergique basé sur les principes de délibération collective, d’offre de l’initiative de la décision au citoyen, de l’invitation aux débats et de l’écoute active (DROIE), d’un dispositif décisionnel flexible et adapté, au centre duquel se trouvent la délibération, le huis clos, la validation populaire et la reddition de compte, le recours et la réparation ainsi que le contrôle de qualité de la décision, essentiels à la gestion, et structurants à l’évaluation environnementale. / Based upon the organizational principle of two types of political entities found in Benin, the purpose of this research is to explore one or several joint, classic and traditional participation models in order to promote a participative democracy closer to citizens. Three spatial scales have been used for the field research: Africa, central Benin and communities close to ancient kingdoms. Documents and data generated through observation and interviews were analyzed using grounded theory principles and ”appréhension des phénomènes socio-spatiaux”. Among the four original models including endogenous criteria for assessing participation which correspond to Benin’s cultures, two – Togbésso-Hon-Togbassa and Daŋnou – appear as properly suited to meet the requirements of a democracy with territorialized forms of participation. When participation in Benin is compared with that of other African States, its good performance elevates it as a reference in terms of effectiveness of procedures and practices. As such, Benin has become a source of inspiration for implementation of participatory mechanisms within major democracies. Both its decision making instruments – namely participatory analysis and public hearing – may still be perfected. The first of the two –an interesting innovation which nonetheless deserves to be highlighted – limits participation to players selected according to criteria which generally remain implicit. Conversely, public hearing remains unsatisfactory by inadequately allowing the production of collective decision making, as well as by instituting a model in contradiction with African political thought, which rather seeks consensus through an inclusive and deliberative approach known as ”la palabre”. At the founding of participative democracy, “la palabre” provides a synergistic, flexible and responsive model based on the DROIE principles for decision making, at the center of which prevail deliberation, ”le huis clos”, popular validation and reporting, use and repair, as well as quality control of decision. All of these are essential as much to management as to the structure of environmental assessment.

Le développement et l’utilisation de systèmes complexes multi-utilisateurs, ou encore la mise en réseau de systèmes d’observation ou d’information pose des problèmes complexes de partage de ressources entre les utilisateurs. La particularité de ces systèmes, impliquant plusieurs utilisateurs humains ou entités organisationnelles est que le partage des ressources doit satisfaire les préférences souvent antagonistes des utilisateurs et répondre à des exigences d’équité. Ce travail de thèse a pour objet l’étude des problèmes de partage de ressources indivisibles entre des agents ayant des préférences complexes sur ces ressources.Nous nous intéressons plus particulièrement à la modélisation de problèmes de partage en univers risqué.En effet, dans de nombreux problèmes d’allocation de ressources réels, la part revenant réellement à chaque agent après le partage de la ressource dépend de facteurs exogènes. C’est le cas par exemple dans les systèmes d’observation (satellitaires, capteurs embarqués,...), dans lesquels la réalisation d’une requête donnée dépend non seulement des conditions climatiques sur le secteur à observer, mais aussi du bon fonctionnement du capteur, de l’absence de brouillage du signal, etc. L’introduction de risque dans les problèmes de partage implique la redéfinition des notions classiques de choix social (utilité, absence d’envie, ...), et l’agrégation collective des préférences des agents s’en trouve compliquée. Au cours de ce travail de thèse, nous nous sommes tout d’abord intéressés à l’étude de cette extension au risque du formalisme associé aux problèmes de partage classiques : nous proposons un modèle simple de problèmes de partages de biens indivisibles en présence de risque, toutefois assez général pour rester proche des applications réelles considérées, et nous introduisons une extension générale des méthodes d’évaluation non risquées pour de tels partages. La seconde partie de ce travail de thèse porte sur l’algorithmique associée à ces problèmes, dont la résolution est notablement complexifiée par la présence de ressources risquées. Pour plusieurs critères d’évaluation (choisis car visant à garantir une certaine équité des solutions qu’ils suggèrent), nous proposons des algorithmes de résolution exacte et approchée des problèmes de partage associés. / The development and use of complex multi-user systems, or the networking of observation ou information systems raises complex resource allocation problems. The particularity of these systems, which involve several human users or organisational entities, rests in the fact that the share of resources must satisfy the often conflicting preferences of users and comply with equity exigences. This thesis deals with the problem of fairly allocating indivisible goods to a set of agents having complex preferences over these goods.We are more particularly interested in the modeling of fair allocation problems in a risky setting. In numerous real-world resource allocation problems, the actual share each agent receives after the allocation often depends on exogenous factors. This is for instance the case with the observation systems (satellites, embedded sensons, etc.) where the realisation of a request not only depends on weather conditions over the observation area, but also on the potential sensor malfunction, on the absence of jamming of the signal, etc. Introducing the risk in allocation problems implies the redefinition of classical social choice notions such as utility or envy-freeness for instance, and the collective aggregation of agents preferences becomes more complicated. We have studied in this thesis the extension of allocation problem formalism to a risky setting : we present a simple model for risky indivisible goods allocation problems, yet general enough to encompass most of the real-world applications, and we introduce a general extension of risk-free evalution methods for such allocations. The second part of the work concerns the algorithmical issues related to theses problems, whose resolution is significantly complexified because of the risky setting. Forseveral evaluation criteria (selected for the equity of the solutions they suggest) we present both exact and approached resolution algorithms for the related allocation problems.