abstract: In order to deploy autonomous multi-robot teams for humanitarian demining in Colombia, two key problems need to be addressed. First, a robotic controller with limited power that can completely cover a dynamic search area is needed. Second, the Colombian National Army (COLAR) needs to increase its science, technology and innovation (STI) capacity to help develop, build and maintain such robots. Using Thangavelautham's (2012, 2017) Artificial Neural Tissue (ANT) control algorithm, a robotic controller for an autonomous multi-robot team was developed. Trained by a simple genetic algorithm, ANT is an artificial neural network (ANN) controller with a sparse, coarse coding network architecture and adaptive activation functions. Starting from the exterior of open, basic geometric grid areas, computer simulations of an ANT multi-robot team with limited time steps, no central controller and limited a priori information, covered some areas completely in linear time, and other areas near completely in quasi-linear time, comparable to the theoretical cover time bounds of grid-based, ant pheromone, area coverage algorithms. To mitigate catastrophic forgetting, a new learning method for ANT, Lifelong Adaptive Neuronal Learning (LANL) was developed, where neural network weight parameters for a specific coverage task were frozen, and only the activation function and output behavior parameters were re-trained for a new coverage task. The performance of the LANL controllers were comparable to training all parameters ab initio, for a new ANT controller for the new coverage task. To increase COLAR's STI capacity, a proposal for a new STI officer corps, Project ÉLITE (Equipo de Líderes en Investigación y Tecnología del Ejército) was developed, where officers enroll in a research intensive, master of science program in applied mathematics or physics in Colombia, and conduct research in the US during their final year. ÉLITE is inspired by the Israel Defense Forces Talpiot program. / Dissertation/Thesis / Doctoral Dissertation Applied Mathematics for the Life and Social Sciences 2019

Multi-agent robotic system have been proved to be more superior in undertaking functionalities, arduous or even impossible when performed by single agents. The increased efficiency in multi agent systems is achieved by the execution of the task in cooperative manner. But to achieve cooperation in multi agent systems, a good localization system is an important prerequisite. Currently, most of the multi-agent system rely on the use of the GPS to provide global positioning information which suffers great deterioration in performance in indoor applications, and also all to all communication between the agents will be required which is not efficient especially when the number of agents is large. In this regard, a real-time localization scheme is introduced which makes use of the robot’s on-board sensors and computational capabilities to determine the states of other agents in the multi agent system. This algorithm also takes the advantage of the swarming behaviour of the robots in the estimation of the states. This localization algorithm was found to produce more accurate agent state estimates as compared to a similar localization algorithm that does not take into account the swarming behaviour of the agents in simulations and real experiment involving two Unmanned Aerial Vehicles.

Le formalisme CSP (Problème de Satisfaction de Contraintes) permet de représenter de nombreux problèmes de manière simple et efficace. Cependant, une partie de ces problèmes ne peut être résolue de manière classique et centralisée. Les causes peuvent être diverses : temps de rapatriement des données prohibitif, sécurité des données non garantie, etc. Les CSP Distribués(DisCSP), domaine intersectant celui des SMA et des CSP, permettent de modéliser et de résoudre ces problèmes naturellement distribués. Les raisonnements intra-agent et inter-agents sont alors basés sur un ensemble de relations entre différentes variables. Les agents interagissent afin de construire une solution globale à partir des solutions locales. Nous proposons, dans ce travail, un algorithme de résolution de DisCSP nommé Distributed Backtracking with Sessions (DBS) permettant de résoudre des DisCSP où chaque agent dispose d’un problème local complexe. DBS a la particularité de ne pas utiliser de nogoods comme la majorité des algorithmes de résolution de DisCSP mais d’utiliser à la place des sessions. Ces sessions sont des nombres permettant d’attribuer un contexte à chaque agent ainsi qu’à chaque message échangé durant la résolution du problème. Il s’agit d’un algorithme complet permettant l’utilisation de filtres sur les messages échangés sans remettre en cause la preuvede complétude. Notre proposition est évaluée, dans les cas mono-variable et multi-variables par agents, sur différents benchmarks classiques (les problèmes de coloration de graphes distribués et les DisCSP aléatoires) ainsi que sur un problème d’exploration en environnement inconnu. / The CSP formalism (Constraint Satisfaction Problem) can represent many problems in a simple and efficient way. However, some of these problems cannot be solved in a classical and centralized way. The causes can be multiple: prohibitive repatriation time, unsecured data and so on. Distributed CSP (DisCSP), domain intersecting MAS and CSP, are used to model and to solve these problems. The intra-agent and inter-agent reasonning are so based on a set of relation between different variables. The agents interact in order to build a global solution from local solutions. We propose, in this work, an algorithm for solving DisCSP named Distributed Backtracking with Sessions (DBS) which allows to solve DisCSP where each agent owns a complex local problem. DBS has the particularity to not use nogoods like the majority of algorithms for solvingDisCSP but to use instead of sessions. These sessions are numbers which allow to assign a context to each agent and each message exchanged during the resolution of the problem. DBS is a complete algorithm which allows the use of filters on messages exchanged without affecting the proof of completeness. Our proposal is evaluated, for mono-variable and multi-variables per agents problems, on different classical benchmarks (distributed graph coloring problems and random DisCSP) and on an unknown environment exploration problem.

En ce qui concerne la hiérarchie de contrôle des micro-réseaux, la coordination des contrôleurs locaux est obligatoire aux niveaux secondaire et tertiaire. Au lieu d'utiliser une unité centrale comme approche conventionnelle, dans ce travail, des schémas distribués sont considérés. Les approches distribuées ont récemment fait l'objet d'une attention particulière en raison de leurs avantages en termes de fiabilité, d'évolutivité et de sécurité. Le système multi-agents est une technique avancée dont les propriétés les rendent aptes à servir de base à la construction de systèmes de contrôle distribués modernes. La thèse porte sur la conception d'agents visant à distribuer des algorithmes de contrôle et d'optimisation dans des micro-réseaux avec un déploiement en ligne réaliste sur une plate-forme Hardware-in-the-Loop. Sur la base de l'architecture à trois couches fournie par micro-réseaux, une plate-forme de laboratoire avec configuration Hardware-in-the-Loop est construite au niveau du système. Cette plateforme comprend deux parties : (1) un simulateur numérique en temps réel permet de simuler en temps réel des micro-réseaux de cas de test avec des contrôleurs locaux ; et (2) un cluster de Raspberry PI représente le système multi-agent fonctionnant dans un réseau de communication physique épars. Un agent est un programme en Python exécuté sur un seul Raspberry PI qui permet de transférer des données à ses voisins et d’effectuer des calculs selon des algorithmes de manière distribuée.Dans la thèse, nous appliquons les algorithmes distribués pour les niveaux de contrôle secondaire et tertiaire. Les contrôles secondaires distribués dans un micro-réseau îloté sont présentés selon deux approches d'algorithme de consensus à temps fini et d'algorithme de consensus moyen avec les améliorations des performances. Une extension de la plate-forme avec la Power Hardware-in-the-Loop et la communication basée sur la norme IEC 61850 est traitée pour rapprocher le déploiement des agents des applications industrielles. Au niveau de contrôle supérieur, les agents exécutent la méthode des multiplicateurs à sens alternatif pour déterminer les points de fonctionnement optimaux des systèmes de micro-réseaux en état d'îlot et de connexion au réseau. Les objectifs de contrôle secondaire et tertiaire sont atteints dans un cadre unique qui est rarement mentionné dans d'autres études.Dans l'ensemble, l'agent est explicitement étudié et déployé dans des conditions réalistes pour faciliter l'application des algorithmes distribués pour le contrôle hiérarchique dans les micro-réseaux. Cette recherche constitue une étape supplémentaire qui rapproche les algorithmes distribués de l'implémentation sur site. / In terms of the control hierarchy of microgrids, the coordination of local controllers is mandatory in the secondary and tertiary levels. Instead of using a central unit as conventional approaches, in this work, distributed schemes are considered. The distributed approaches have been taken attention widely recently due to the advantages of reliability, scalability, and security. The multi-agent system is an advanced technique having properties that make them suitable for acting as a basis for building modern distributed control systems. The thesis focuses on the design of agents aiming to distributed control and optimization algorithms in microgrids with realistic on-line deployment on a Hardware-in-the-loop platform. Based on the provided three-layer architecture of microgrids, a laboratory platform with Hardware-in-the-loop setup is constructed in the system level. This platform includes two parts: (1) a digital real-time simulator uses to simulate test case microgrids with local controllers in real-time; and (2) a cluster of hardware Raspberry PIs represents the multi-agent system operating in a sparse physical communication network. An agent is a Python-based program run on a single Raspberry PI owing abilities to transfer data with neighbors and computing algorithms to control the microgrid in a distributed manner.In the thesis, we apply the distributed algorithms for both secondary and tertiary control level. The distributed secondary controls in an islanded microgrid are presented in two approaches of finite-time consensus algorithm and average consensus algorithm with the improvements in performances. An extension of the platform with Power Hardware-in-the-Loop and IEC 61850-based communication is processed to make the deployment of agents closer to industrial applications. On the top control level, the agents execute the Alternating Direction Method of Multipliers to find out the optimal operation points of microgrid systems in both islanded and grid-connect state. The secondary and tertiary control objectives are achieved in a single framework which is rarely reported in other studies.Overall, the agent is explicitly investigated and deployed in the realistic conditions to facilitate applications of the distributed algorithms for the hierarchical control in microgrids. This research gives a further step making the distributed algorithms closer to onsite implementation.

<p>The main goal of this thesis is the creation o f the tool agent-oriented programming tool AJA. AJA is the acronym for Adaptable Java Agents. AJA consists o f two programming languages:<br />- A higher-level language used for the description of the main agent parts. This language is called HADL, which is the acronym for Higher Agent Definition Language.<br />- A lower-level language used for the programming o f the agent parts defined in HADL. This language is called Java+. It is actually Java enriched with the constructs for accessing higher-level agent parts defined in HADL.<br />A translator from AJA to Java is implemented in the practical part o f the thesis. AJA agents have the following features: - Agent communicates with other agents using a construct called negotiation. The messages sent can be encrypted or digitally signed in order to ensure the security of the system. - Agent possesses adaptable&nbsp; parameters and neural nets that adapt themselves when the environment changes.<br />- Agent has reflexes, which are the reactive component o f the agent architecture.<br />- Agent can perform its actions parallel. Actions execution is synchronized.<br />- Agent is accessible via Internet, because it acts as a simple HTTP server. People can use this way to communicate with an agent.<br />- Agent has Java Swing based graphical user interface. Its owner uses this interface to communicate with the agent.<br />- Because o f the fact that Java-i- language extends Java, it is possible to use all useful Java features in the implementation o f AJA agents (e.g. JDBC for the database access). The thesis also presents an original approach of integrating artificial intelligence techniques, such as neural nets, with a programming language. Having the artificial intelligence components as a part of the programming language runtime environment makes their use straightforward. A programmer uses the language constructs that are implemented using the artificial intelligence<br />without the need for understanding their background and theory.<br />The thesis contains eight chapters and three appendixes. In the first chapter, an overview of agents and multi-agent systems is given. The second chapter surveys existing agent-oriented programming languages and tools. The third chapter introduces AJA and describes the architecture of AJA agents. The syntax and semantics o f AJA languages HADL and Java+ is described in the fourth chapter. The fifth chapter presents adaptable AJA constructs in more details. To demonstrate and test the created tool, a case-study multi-agent system has been implemented in AJA. There are four personal digital assistant agents in the system. The sixth chapter describes the example agents and positively evaluates the tool. In the seventh chapter the related work and tools are analyzed and compared to AJA. The last chapter concludes the thesis. The first appendix describes the implementation details of the AJA to Java translator. The second appendix is a guide for the installation and usage of the implemented AJA to Java translator. Finally, the third<br />appendix describes step by step how to translate, compile, run, and use the example agents. The thesis contains many references, which include almost all the most important and the most actual papers in the field. The reference list can be found at the end o f the thesis.</p> / <p>Glavni doprinos doktorske teze je napravljeni alat za programiranje agenata AJA . AJA - Adaptabilni Java Agenti je jezički alat za programsku implementaciju agenata Sastoji se od dva programska jezika:<br />- Jezik vi&scaron;eg nivoa kojim se opisuju glavne kom ponente agenta. Ovaj jezik se naziva HADL - Higher Agent Definition Language.<br />- Jezik nižeg nivoa koji služi za implementaciju pojedinih komponenti agenta specificiranih HADL jezikom . Ovaj jezik se najava Java+, jer je on zapravo programski jezik Java obogaćen konstrukcijama pomoću kojih je moguće pristupati komponentama agenta, definisanim u jezik u HADL.<br />AJA agent poseduje sledeće osobine:<br />- Sigurna kom unikacija sa drugim A JA agentim a koristeći mehanizam pregovaranja, &scaron;ifrovanje i digitalno potpisivanje poruka.<br />- Mogućnost adaptiranja na promene u okruženju u kom se nalazi, koristeći neuralne mreže i adaptabilne parametre.<br />- Reaktivnost zasnovana n a kom ponenti zvanoj refleks.<br />- Paralelno izvr&scaron;avanje akcija agenta u z njihovu internu sinhronizaciju.<br />- D ostupnost agenta preko Interneta. Agent se pona&scaron;a kao jednostavan HTTP server. Na ovaj način se drugim osobama omogućuje da komuniciraju sa agentom .<br />- G rafički korisnički interfejs zasnovan n a Java Swing tehnologiji<br />- Po&scaron;to se u program iranju agenta koristi Java+, moguće je uposliti sve pogodnosti Jave, kao &scaron;to su na primer pristup bazama podataka koristeći JDBC , rad sa multimedijalnim sadržajem , itd.<br />U tezi je predstavljen i originalni pristup integrisanja tehnika ve&scaron;tačke inteligencije sa program skim jezikom . U građujući kom ponente ve&scaron;tačke inteligencije u izvr&scaron;nu okolinu je z ik a čini n jihovo kori&scaron;ćenje veom a jednostavnim . Programer ne mora da bude ekspert iz ve&scaron;tačke inteligencije a da pri tome koristi konstrukcije jezika koje su implementirane pomoću ve&scaron;tačke inteligencije. AJA specifikacija agenta se sastoji od HADL i Java+ delova. U tezi je implementiran prevodioc kojim se A JA specifikacija prevodi u skup klasa programskog jezika Java. Implementiran je i jedan multi-agentski sistem kojim se praktično pokazuje kori&scaron;ćenje i mogućnosti napravljenog alata D oktorska teza sadrži i detaljan pregled oblasti o agentskpj m etodologiji. O n a kruni&scaron;e vi&scaron;egodi&scaron;nji rad kandidata i njegovog mentora u ovoj sve značajnijoj oblasti računarstva.<br />Teza sadrži o sam glava i tri dodatka. U prvoj glavi se opisuje oblast agenata i m ulti-agentskih sistem a. Pregled postojećih agentskih program skih jezik a i alata se daje u drugoj glavi. O pis A JA agenata i njihove arhitekture je dat u trećoj glavi teze. Četvrta glava se bavi sintaksom i sem antikom oba A JA jezika: H A D L -a i Jave+. Adaptabilni elem enti A JA agenata se opisuju u petoj glavi. U &scaron;estoj glavi je opisan m ulti-agentski sistem koji j e ujed n o i prim er prim ene A JA alata. A JA se sa drugim postojećim agentskim alatim a upoređuje u sedm oj glavi. Osma glava sadrži zaključak. N a kraju se u tri dodatka detaljno opisuju im plem entacija prevodioca A JA -e u Javu, instalacija prevodioca i kori&scaron;ćenje napravljenog m ulti-agentskog sistema respektivno. U doktorskom radu su kori&scaron;ćene i navedene brojne reference kojim a su obuhvaćeni gotovo svi najznačajniji i najaktuelniji radovi iz oblasti multi-agentskih sistema. Lista referenci je navedena na kraju teze.</p>

Le but de nos travaux est de définir des algorithmes permettant de simuler les déplacements de piétons dans un environnement urbain, en temps réel, et de manière crédible. Les modèles existants pour ce type d'exercice sont développés suivant deux types d'approches : microscopiques - les piétons sont modélisés comme des agents autonomes - et macroscopiques - les piétons sont considérés comme soumis à des lois d'écoulement. Selon nous, ces deux approches ne s'opposent pas, mais se complètent mutuellement. Aussi nous inspirons-nous des jeux de congestion et des SMA pour proposer une formulation générique du problème de déplacement de piétons. Nous introduisons la notion de ressource de navigation, décrite comme une région de l'espace que les agents utilisent pour atteindre leurs objectifs, et via lesquelles ils interagissent pour estimer leurs dépenses énergétiques, et nous proposons une stratégie de déplacement basée sur les heuristiques taboues. Le concept d'environnement issu du paradigme SMA s'avère adapté pour appréhender la complexité de la simulation. L'environnement est vu comme un composant indépendant et ontologiquement différent des agents. Une partie de la dynamique de la simulation est ainsi déléguée à l'environnement sans altérer l'autonomie des agents, ce qui favorise la crédibilité des résultats et le passage à l'échelle. Nous comparons notre modèle avec un modèle microscopique standard via plusieurs scénarii de simulation et montrons que notre modèle produit des résultats plus crédibles du point de vue d'un observateur extérieur et plus proches des études empiriques connues du déplacement des piétons. / In this work, we focus on real-time simulation of autonomous pedestrians navigation. Existing models for this purpose tend to diverge on whether to build on pedestrians' characteristics and local interactions - microscopic approaches - or to focus on pedestrians' flow regardless of individual characteristics - macroscopic approaches. Our position is that the two approaches should not be separated. Thus, we introduce a Macroscopic-Influenced Microscopic approach which aims at reducing the gap between microscopic and macroscopic approaches by providing credible walking paths for a potentially highly congested crowd of autonomous pedestrians. Our approach originates from a least-effort formulation of the navigation task, which allows us to consistently account for congestion at every levels of decision. We use the multi-agent paradigm and describe pedestrians as autonomous and situated agents who plan dynamically for energy efficient paths, and interact with each other through the environment. The navigable space is considered as a set of contiguous resources that agents use to build their paths. We emulate the dynamic path computation for each agent with an evolutionary search algorithm that implement a tabu search heuristic, especially designed to be executed in real-time and autonomously. We have compared an implementation of our approach with a standard microscopic model, against low-density and high density scenarios, with encouraging results in terms of credibility and scalability. We believe that microscopic models could be easily extended to embrace our approach, thus providing richer simulations of potentially highly congested crowd of autonomous pedestrians.

Cette thèse concerne l’étude des débats argumentatifs entre plusieurs agents artificiels. Notre travail est motivé par les difficultés qui surgissent quand un nombre important d’utilisateurs interagissent et débattent sur le Web, en échangeant des arguments sur différents sujets. Ces difficultés se situent au niveau de la représentation des connaissances des agents impliqués dans le débat, de la représentation du débat, de la façon de tirer les conclusions du débat, de l'évaluation de la qualité du débat, de la définition des protocoles spécifiques d'interaction, et de l'étude des stratégies des agents qui souhaitent atteindre un but précis via le débat. La contribution de cette thèse consiste donc en: a) la modélisation d'un débat argumentatif entre plusieurs agents, la modélisation des expertises de ces derniers, et l'agrégation des opinions des différents experts sur différentes parties d'un débat; b) l'apport d'une aide à l'agent responsable de la gestion d'un débat donné, la proposition d'une méthode permettant d'évaluer la qualité des débats argumentatifs en fonction de la confiance que l'on peut avoir en leurs conclusions, ainsi que la proposition de solutions permettant d'améliorer la qualité des débats dont les conclusions ne sont pas clairement établies; c) l'apport d'une aide permettant aux agents qui participent à un débat argumentatif de déterminer quels arguments placer dans le débat, l'étude des systèmes argumentatifs munis d'une structure dynamique, l'étude des moyens disponibles permettant à un agent d'influencer un système dynamique afin d'atteindre son but, l'étude des modifications minimales permettant à un agent d’atteindre un objectif donné, l'étude des stratégies argumentatives basées sur ce changement minimal; d) la définition, l'étude et l'évaluation des protocoles argumentatifs multi-agents, ainsi que la définition de protocoles de différents types (1) basés sur une évaluation numérique d'arguments et (2) basés sur des extensions d'arguments, l'utilisation des différentes techniques pour assurer la cohérence d'un débat tout en laissant une liberté d'expression aux agents, et enfin un grand nombre d'expérimentations (sur des débats) permettant de tester différentes stratégies et de les évaluer en fonction de différents critères. / In this thesis multi-agent argumentation debates are studied. Our work is motivated by the issues which are raised when a large number of users interact and debate on the Web, by exchanging arguments on various topics. These issues are raised on the levels of representing the debating users' knowledge, representing the debate, computing the debate's conclusions, evaluating the debate's quality, defining specific protocols for user interaction, and studying debate strategies which users employ in order to achieve particular goals. This thesis' contribution consists in: a) proposing a way to model a multi-agent argumentation debate where the participants have different types of expertise, and proposing a way to aggregate their opinions; b) offering support to the agent who is arbitrating a debate, proposing a way to evaluate the quality of a debate on the basis of how confident we can be on its conclusions, and proposing solutions for improving the quality of a debate which lacks definite conclusions; c) offering support to the debating agents in order to determine which arguments they should put forward, studying dynamic argumentation systems, studying the potential ways in which an agent can influence a dynamic argumentation system in order to achieve his goal, studying the minimal change allowing an agent to achieve his goal, studying several argumentation strategies based on minimal change; d) defining, studying and evaluating multi-agent argumentation protocols, defining protocols of different types (1) based on numerical argument evaluation and (2) based on argument extensions, using different techniques to ensure a debate's coherence while ensuring some liberty of expression to the agents, and finally performing an important number of experiments (on debates) in order to test various strategies and evaluate them with respect to specific criteria.

Cette thèse présente un modèle multi-agent du marché du travail. Le modèle reproduit le fonctionnement du marché tant au niveau agrégé, qu'au niveau des principales catégories de main-d'œuvre, sur la base des décisions d'agents hétérogènes, entreprises et individus, qui interagissent. Les décisions reposent sur des calculs de profits et d'utilités et se font dans un contexte de rationalité limitée. La structure théorique sous-jacente sur laquelle repose les mécanismes décisionnels est le concept de \textit{recherche}. Nous appliquons ce cadre de modélisation pour étudier le marché du travail français en 2011. Le modèle est à l'échelle de 1/4700. Il est très détaillé au niveau des institutions du marché du travail qui ont une influence sur les décisions des agents. Le modèle est ensuite calibré par un algorithme puissant de façon à reproduire un grand nombre de cibles importantes du marché du travail. Le modèle ainsi calibré permet de faire émerger une comptabilité cohérente des flux bruts des individus entre les principaux états : emploi (avec la distinction CDD et CDI), chômage et inactivité. La simulation des flux permet de faire émerger différents schémas de mobilité et de caractériser la nature du marché du travail. Nous reproduisons la part importante de contrats à durée déterminée parmi les embauches et nous mettons en évidence la dualité du marché du travail français. La prise en compte des effets d'éviction de certaines catégories d'agents (les jeunes par exemple) par d'autres catégories d'agent est un des apports du modèle pour l'analyse du marché du travail. Nous avons enfin étudié une série de politiques économiques suivant différents indicateurs. Nous montrons qu'il est difficile de trouver une politique publique qui donne de bons résultats pour tous les critères et qui est bénéfique à la fois pour toutes les entreprises et tous les individus. Tout est affaire de compromis et de choix politique. / This thesis presents an agent-based model of the labor market. The model simulates the market at the aggregate level and at the level of the principal manpower categories, on the basis of the decisions of heterogenous agents, firms and individuals, who interact. These decisions rely on computations of profits and utilities in a context of bounded rationality. The theoretical structure that underlies the decisions is the search concept. We apply this framework to the case of France in 2011. The model is at a scale of 1/4700. It is fairly detailed on the institutions of the labor market which constrain the agents’ decisions. Subsequently, it is calibrated by a powerful algorithm to reproduce a large number of variables of interest. The calibrated model presents a coherent accounting system of the gross flows of the individuals between the main states, employment, distinguishing open ended contracts and fixed duration contracts, unemployment and inactivity. The simulation of the gross flows enables us to analyse the patterns of mobility and to characterize the nature of the labor market under study, reproducing the high proportion of the fixed duration contracts in the hiring flows, and it points to a dualism of the French labor market. Modeling crowding out of some categories of workers (for instance the youths) by others is then a main contribution of the model to the labor market analysis. Finally, we study economic policies according to various indicators. We show that it is difficult to find a public policy which provides good results for all criteria and which is beneficial both for firms and individuals. It is all a question of compromise and political choice.

Consensus occurs within a multi-agent system when every agent is in agreement about the value of some particular state. For example, the color of an LED, the position or magnitude of a vector, a rendezvous location, the most recent state of data within a database, or the identity of a leader are all states that agents might need to agree on in order to execute their tasking. The task of the decentralized consensus problem for multi-agent systems is to design an algorithm that enables agents to communicate and exchange information such that, in finite time, agents are able to form a consensus without the use of a centralized control mechanism. The primary goal of this research is to introduce and provide supporting evidence for Stochastic Local Observation/Gossip (SLOG) algorithms as a new class of solutions to the decentralized consensus problem for multi-agent systems that lack a centralized controller, with the additional constraints that agents act asynchronously, information is discrete, and all consensus options are equally preferable to all agents. Examples of where these constraints might apply include the spread of social norms and conventions in artificial populations, rendezvous among a set of specific locations, and task assignment. This goal is achieved through a combination of theory and experimentation. Information propagation process and an information propagation algorithm are derived by unifying the general structure of multiple existing solutions to the decentralized consensus problem. They are then used to define two classes of algorithms that spread information across a network and solve the decentralized consensus problem: buffered gossip algorithms and local observation algorithms. Buffered gossip algorithms generalize the behavior of many push-based solutions to the decentralized consensus problem. Local observation algorithms generalize the behavior of many pull-based solutions to the decentralized consensus problem. In the language of object oriented design, buffered gossip algorithms and local observation algorithms are abstract classes; information propagation processes are interfaces. SLOG algorithms combine the transmission mechanisms of buffered gossip algorithms and local observation algorithms into a single "hybrid" algorithm that is able to push and pull information within the local neighborhood. A common mathematical framework is constructed and used to determine the conditions under which each of these algorithms are guaranteed to produce a consensus, and thus solve the decentralized consensus problem. Finally, a series of simulation experiments are conducted to study the performance of SLOG algorithms. These experiments compare the average speed of consensus formation between buffered gossip algorithms, local observation algorithms, and SLOG algorithms over four distinct network topologies. Beyond the introduction of the SLOG algorithm, this research also contributes to the existing literature on the decentralized consensus problem by: specifying a theoretical framework that can be used to explore the consensus behavior of push-based and pull-based information propagation algorithms; using this framework to define buffered gossip algorithms and local observation algorithms as generalizations for existing solutions to the decentralized consensus problem; highlighting the similarities between consensus algorithms within control theory and opinion dynamics within computational sociology, and showing how these research areas can be successfully combined to create new and powerful algorithms; and providing an empirical comparison between multiple information propagation algorithms.

No / Large-scale behavioral simulations are widely used to study real-world multi-agent systems. Such programs normally run in discrete time-steps or ticks, with simulated space decomposed into domains that are distributed over a set of workers to achieve parallelism. A distinguishing feature of behavioral simulations is their frequent and high-volume group migration, the phenomenon in which simulated objects traverse domains in groups at massive scale in each tick. This results in continual and significant load imbalance among domains. To tackle this problem, traditional load balancing approaches either require excessive load re-profiling and redistribution, which lead to high computation/communication costs, or perform poorly because their statically partitioned data domains cannot reflect load changes brought by group migration. In this paper, we propose an effective and low-cost load balancing scheme, named Inc-part, based on a key observation that an object is unlikely to move a long distance (across many domains) within a single tick. This localized mobility property allows one to efficiently estimate the load of a dynamic domain incrementally, based on merely the load changes occurring in its neighborhood. The domains experiencing significant load changes are then partitioned or merged, and redistributed to redress load imbalance among the workers. Experiments on a 64-node (1,024-core) platform show that Inc-part can attain excellent load balance with dramatically lowered costs compared to state-of-the-art solutions.