One way to build large-scale autonomous systems is to develop an open multi-agent system using peer-to-peer architectures in which agents are not pre-engineered to work together and in which agents themselves determine the social norms that govern collective behaviour. The social norms and the agent interaction models can be described by Electronic Institutions such as those expressed in the Lightweight Coordination Calculus (LCC), a compact executable specification language based on logic programming and pi-calculus. Open multi-agent systems have experienced growing popularity in the multi-agent community and are expected to have many applications in the near future as large scale distributed systems become more widespread, e.g. in emergency response, electronic commerce and cloud computing. A major practical limitation to such systems is security, because the very openness of such systems opens the doors to adversaries for exploit existing vulnerabilities. This thesis addresses the security of open multi-agent systems governed by electronic institutions. First, the main forms of attack on open multi-agent systems are introduced and classified in the proposed attack taxonomy. Then, various security techniques from the literature are surveyed and analysed. These techniques are categorised as either prevention or detection approaches. Appropriate countermeasures to each class of attack are also suggested. A fundamental limitation of conventional security mechanisms (e.g. access control and encryption) is the inability to prevent information from being propagated. Focusing on information leakage in choreography systems using LCC, we then suggest two frameworks to detect insecure information flows: conceptual modeling of interaction models and language-based information flow analysis. A novel security-typed LCC language is proposed to address the latter approach. Both static (design-time) and dynamic (run-time) security type checking are employed to guarantee no information leakage can occur in annotated LCC interaction models. The proposed security type system is then formally evaluated by proving its properties. A limitation of both conceptual modeling and language-based frameworks is difficulty of formalising realistic policies using annotations. Finally, the proposed security-typed LCC is applied to a cloud computing configuration case study, in which virtual machine migration is managed. The secrecy of LCC interaction models for virtual machine management is analysed and information leaks are discussed.

Real-Time Strategy (RTS) is a sub-genre of strategy games which is running in real-time, typically in a war setting. The player use workers to gather resources, which in turn is used for creating new buildings, training combat units and build upgrades and research. The game is won when all buildings of the opponents have been destroyed. The numerous tasks that need to be handled in real-time can be very demanding for a player. Computer players (bots) for RTS games face the same challenges, and also have to navigate units in highly dynamic game worlds and deal with other low-level tasks such as attacking enemy units within fire range. This thesis is a compilation of nine papers. The first four papers deal with navigation in dynamic game worlds, which can be very complex and resource demanding. Typically it is solved by using pathfinding algorithms. We investigate an alternative approach based on Artificial Potential Fields and show how a PF based navigation system can be used without any need of pathfinding algorithms. In RTS games players usually have a limited visibility of the game world, known as Fog of War. Bots on the other hand often have complete visibility to aid the AI in making better decisions. In a paper we show that a Multi-Agent PF based bot with limited visibility can match and even surpass bots with complete visibility in some RTS scenarios. In the sixth paper we show how the bot can be extended and used in a full RTS scenario with base building and unit construction. This is followed by a paper where we propose a flexible and expandable RTS game architecture that can be modified at several levels of abstraction to test different techniques and ideas. The proposed architecture is implemented in the famous RTS game StarCraft, and we show how the high-level architecture goals of flexibility and expandability can be achieved. The last two papers present two studies related to gameplay experience in RTS games. In games players usually have to select a static difficulty level when playing against computer opponents. In the first study we use a bot that during runtime can adapt the difficulty level depending on the skills of the opponent, and study how it affects the perceived enjoyment and variation in playing against the bot. To create bots that are interesting and challenging for human players a goal is often to create bots that play more human-like. In the second study we asked participants to watch replays of recorded RTS games between bots and human players. The participants were asked to guess and motivate if a player was controlled by a human or a bot. This information was then used to identify human-like and bot-like characteristics for RTS game players.

We study distributed estimation of dynamic random fields observed by a sparsely connected network of agents/sensors. The sensors are inexpensive, low power, and they communicate locally and perform computation tasks. In the era of large-scale systems and big data, distributed estimators, yielding robust and reliable field estimates, are capable of significantly reducing the large computation and communication load required by centralized estimators, by running local parallel inference algorithms. The distributed estimators have applications in estimation, for example, of temperature, rainfall or wind-speed over a large geographical area; dynamic states of a power grid; location of a group of cooperating vehicles; or beliefs in social networks. The thesis develops distributed estimators where each sensor reconstructs the estimate of the entire field. Since the local estimators have direct access to only local innovations, local observations or a local state, the agents need a consensus-type step to construct locally an estimate of their global versions. This is akin to what we refer to as distributed dynamic averaging. Dynamic averaged quantities, which we call pseudo-quantities, are then used by the distributed local estimators to yield at each sensor an estimate of the whole field. Using terminology from the literature, we refer to the distributed estimators presented in this thesis as Consensus+Innovations-type Kalman filters. We propose three distinct types of distributed estimators according to the quantity that is dynamically averaged: (1) Pseudo-Innovations Kalman Filter (PIKF), (2) Distributed Information Kalman Filter (DIKF), and (3) Consensus+Innovations Kalman Filter (CIKF). The thesis proves that under minimal assumptions the distributed estimators, PIKF, DIKF and CIKF converge to unbiased and bounded mean-squared error (MSE) distributed estimates of the field. These distributed algorithms exhibit a Network Tracking Capacity (NTC) behavior – the MSE is bounded if the degree of instability of the field dynamics is below a threshold. We derive the threshold for each of the filters. The thesis establishes trade-offs between these three distributed estimators. The NTC of the PIKF depends on the network connectivity only, while the NTC of the DIKF and of the CIKF depend also on the observation models. On the other hand, when all the three estimators converge, numerical simulations show that the DIKF improves 2dB over the PIKF. Since the DIKF uses scalar gains, it is simpler to implement than the CIKF. Of the three estimators, the CIKF provides the best MSE performance using optimized gain matrices, yielding an improvement of 3dB over the DIKF. Keywords: Kalman filter, distributed state estimation, multi-agent networks, sensor networks, distributed algorithms, consensus, innovation, asymptotic convergence, mean-squared error, dynamic averaging, Riccati equation, Lyapunov iterations, distributed signal processing, random dynamical systems.

This work focuses on the autonomous exploration of unknown areas by a swarm of mobile robots, referred to as agents. When an emergency happens within a building, it is dangerous to send human responders to search the area for hazards and victims. This motivates the need for autonomous agents that are able to coordinate with each other to explore the area as fast as possible. We investigate this problem from an algorithmic, rather than a robotics point of view, and thus abstract away from practical problems, such as obstacle detection and navigation over rough terrain. Our focus is on distributed algorithms that can cope with the following challenges: the topology of the area is typically unknown, communication between agents is intermittent and unreliable, and agents are not aware of their location in indoor environments. In order to address these challenges, we adopt the stigmergy approach, that is, we assume that the area is instrumented with small inexpensive sensors (called tags) and agents coordinate indirectly with each other by reading and updating the state of local tags. We propose three novel distributed algorithms that allow agents to explore unknown areas by coordinating indirectly through a tag-instrumented environment. In addition, we propose two mechanisms for discovering evacuation routes from critical points in the area to emergency exits. Agents are able to combine the tasks of area exploration and evacuation route discovery in a seamless manner. We study the proposed algorithms analytically, and evaluate them empirically in a custom-built simulation environment in a variety of scenarios. We then build a real testbed of agents and tags, and investigate practical mechanisms that allow agents to detect and localise nearby tags, and navigate toward them. Using the real testbed, we derive realistic models of detection, localisation and navigation errors, and investigate how they impact the performance of the proposed exploration algorithms. Finally, we design fault-tolerant exploration algorithms that are robust to these errors and evaluate them extensively in a simulation environment.

Within the field of multi-agent systems theory, we study the problems of consensus and pursuit-evasion. In our study of the consensus problem, we first provide some theoretical results and then consider the problem of consensus on SO(3) or attitude synchronization. In Chapter 2, for agents with states in R^m, we present two theorems along the lines of Lyapunov’s second method that, under different conditions, guarantee asymptotic state consensus in multi-agent systems where the interconnection topologies are switching. The first theorem is formulated by using the states of the agents in the multi-agent system, whereas the second theorem is formulated by using the pairwise states for pairs of agents in the multi-agent system. In Chapter 3, the problem of consensus on SO(3) for a multi-agent system with directed and switching interconnection topologies is addressed. We provide two different types of kinematic control laws for a broad class of local representations of SO(3). The first control law consists of a weighted sum of pairwise differences between positions of neighboring agents, expressed as coordinates in a local representation. The structure of the control law is well known in the consensus community for being used in systems of agents in the Euclidean space, and here we show that the same type of control law can be used in the context of consensus on SO(3). In a later part of this chapter, based on the kinematic control laws, we introduce torque control laws for a system of rigid bodies in space and show that the system reaches consensus when these control laws are used. Chapter 4 addresses the problem of consensus on SO(3) for networks of uncalibrated cameras. Under the assumption that each agent uses a camera in order to measure its rotation, we prove convergence to the consensus set for two types of kinematic control laws, where only conjugate rotation matrices are available for the agents. In these conjugate rotations, the rotation matrix can be seen as distorted by the (unknown) intrinsic parameters of the camera. For the conjugate rotations we introduce distorted versions of well known local parameterizations of SO(3) and show consensus by using control laws that are similar to the ones in Chapter 3, with the difference that the distorted local representations are used instead. In Chapter 5, we study the output consensus problem for homogeneous systems of agents with linear continuous time-invariant dynamics. We derive control laws that solve the problem, while minimizing a cost functional of the control signal. Instead of considering a fixed communication topology for the system, we derive the optimal control law without any restrictions on the topology. We show that for all linear output controllable homogeneous systems, the optimal control law uses only relative information but requires the connectivity graph to be complete and in general requires measurements of the state errors. We identify cases where the optimal control law is only based on output errors. In Chapter 6, we address the multi-pursuer version of the visibility pursuit-evasion problem in polygonal environments. By discretizing the problem and applying a Mixed Integer Linear Programming (MILP) framework, we are able to address problems requiring so called recontamination and also impose additional constraints, such as connectivity between the pursuers. The proposed MILP formulation is less conservative than solutions based on graph discretizations of the environment, but still somewhat more conservative than the original underlying problem. It is well known that MILPs, as well as multi-pursuer pursuit-evasion problems, are NP-hard. Therefore we apply an iterative Receding Horizon Control (RHC) scheme, where a number of smaller MILPs are solved over shorter planning horizons. The proposed approach is illustrated by a number of solved examples. / <p>QC 20140327</p>

Using teams of autonomous, heterogeneous robots to operate in dangerous environments has a number of advantages. Among these are cost-effectiveness and the ability to spread out skills among team members. The nature of operating in dangerous domains means that the risk of loss is higher---teams will often lose members and must acquire new ones. In this work, I explore various recruitment strategies for the purpose of improving an existing framework for team management. My additions allow robots to more actively acquire new teams members and assign tasks among other robots on a team without the intervention of a team leader. I evaluate this framework in simulated post-disaster environments where the risk of robot loss is high and communications are often unreliable. My results show that in many scenarios, active recruitment strategies provide significant performance benefits. / February 2017

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal.

Les premières étapes d'une conception fiabiliste impliquent la formulation de critères de performance et de contraintes de fiabilité d'une part, et le choix d'une représentation des incertitudes d'autre part. Force est de constater que, le plus souvent, des aspects de performance ou de fiabilité conditionnant la solution optimale ne seront pas connus ou seront négligés lors des premières phases de conception. De plus, les techniques de réduction des incertitudes telles que les tests additionnels et la reconception ne sont pas pris en compte dans les calculs de fiabilité initiaux. Le travail exposé dans ce manuscrit aborde la conception optimale de systèmes sous deux angles : 1) le compromis entre performance et coût généré par les tests supplémentaires et les reconceptions et, 2) l'identification de multiples solutions optimales (dont certaines locales) en tant que stratégie contre les erreurs initiales de conception. Dans la première partie de notre travail, une méthodologie est proposée pour estimer l'effet sur la performance et le coût d'un produit d'un test supplémentaire et d'une éventuelle reconception. Notre approche se base, d'une part, sur des distributions en probabilité des erreurs de calcul et des erreurs expérimentales et, d'autre part, sur une rêgle de reconception a priori. Ceci permet d'estimer a posteriori la probabilité et le coût d'un produit. Nous montrons comment, à travers le choix de politiques de prochain test et de re-conception, une entreprise est susceptible de contrôler le compromis entre performance et coût de développement.Dans la seconde partie de notre travail, nous proposons une méthode pour l'estimation de plusieurs solutions candidates à un problème de conception où la fonction coût et/ou les contraintes sont coûteuses en calcul. Une approche pour aborder de tels problèmes est d'utiliser un métamodèle, ce qui nécessite des évaluations de points en diverses régions de l'espace de recherche. Il est alors dommage d'utiliser cette connaissance seulement pour estimer un optimum global. Nous proposons une nouvelle approche d'échantillonnage à partir de métamodèles pour trouver plusieurs optima locaux. Cette méthode procède par partitionnement adaptatif de l'espace de recherche et construction de métamodèles au sein de chaque partition. Notre méthode est testée et comparée à d'autres approches d'optimisation globale par métamodèles sur des exemples analytiques en dimensions 2 à 6, ainsi que sur la conception d'un bouclier thermique en 5 dimensions. / The initial stages of reliability-based design optimization involve the formulation of objective functions and constraints, and building a model to estimate the reliability of the design with quantified uncertainties. However, even experienced hands often overlook important objective functions and constraints that affect the design. In addition, uncertainty reduction measures, such as tests and redesign, are often not considered in reliability calculations during the initial stages. This research considers two areas that concern the design of engineering systems: 1) the trade-off of the effect of a test and post-test redesign on reliability and cost and 2) the search for multiple candidate designs as insurance against unforeseen faults in some designs. In this research, a methodology was developed to estimate the effect of a single future test and post-test redesign on reliability and cost. The methodology uses assumed distributions of computational and experimental errors with re-design rules to simulate alternative future test and redesign outcomes to form a probabilistic estimate of the reliability and cost for a given design. Further, it was explored how modeling a future test and redesign provides a company an opportunity to balance development costs versus performance by simultaneously designing the design and the post-test redesign rules during the initial design stage.The second area of this research considers the use of dynamic local surrogates, or surrogate-based agents, to locate multiple candidate designs. Surrogate-based global optimization algorithms often require search in multiple candidate regions of design space, expending most of the computation needed to define multiple alternate designs. Thus, focusing on solely locating the best design may be wasteful. We extended adaptive sampling surrogate techniques to locate multiple optima by building local surrogates in sub-regions of the design space to identify optima. The efficiency of this method was studied, and the method was compared to other surrogate-based optimization methods that aim to locate the global optimum using two two-dimensional test functions, a six-dimensional test function, and a five-dimensional engineering example.

This thesis deals with a problem of choosing the most suitable agent for a new data mining task not yet seen by the agents. The metric is proposed on the data mining tasks space, and based on this metric similar tasks are identified. This set is advanced as an input to a program evolved by means of genetic programming. The program estimates agents performance on the new task from both the time and error point of view. A JADE agent is implemented which provides an interface allowing other agents to obtain estimation results in real time.

Title: Disruption of movement or cohesion of groups through individuals Author: Jiří Vejmola Department: Department of Theoretical Computer Science and Mathematical Logic Supervisor of the master thesis: Mgr. Roman Neruda, CSc., Institute of Computer Science of the ASCR, v. v. i. Abstract: Just a few of informed and like-minded individuals, guides, are needed to lead otherwise naive group. We look at some of the possible changes that can be caused by the presence of another informed individual with different intentions, an intruder. It is implied that he cannot cause anything significant under normal circumstances. To counter that and to increase his chances of success we intruduce a new parameter - credibility. We explore how it changes the overall behaviour. We show that by applying it to the intruder his influence over others increases. This in turn makes naive individuals more willing to follow him. We show that if the right conditions are met he can eventually become the one who leads the group. Keywords: multi-agent system, swarm intelligence, emergence, credibility