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.

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>

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.

The aim of this work is design, implementation and experimental evaluation of distributed algorithms for planning actions of a team of cooperative autonomous agents. Particular algorithms require different amount of communication. In the work, the related research on Monte-Carlo tree search algorithm, its parallelization and distributability and algorithms for distributed coordination of autonomous agents. Designed algorithms are tested in the environment of the game of Ms Pac-Man. Quality of the algorithms is tested in dependence on computational time, the amount of communication and the robustness against communication failures. Particular algorithms are compared according to these characteristics. Powered by TCPDF (www.tcpdf.org)

The thesis deals with the study of the computer worm meeting several criteria (it should be fully distributed, decentralized and stealthy). These conditions lead to anonymity, longevity and better security of our worm. After presenting the recently used architectures and new technologies we analyse the known implementations. We propose the solutions with the new design together with the possible ways of improvements. In the next chapter we study biological concepts suitable for the new replication mode, where we implement the key concepts of functionality in a higher programming language. At design we have considered as important to be platform independent, so it is possible for the worm to spread in almost every computer environment, in dependence of implementation of the required modules. Powered by TCPDF (www.tcpdf.org)

Autonomic Computing (AC) aims at solving the problem of managing the rapidly-growing complexity of Information Technology systems, by creating self-managing systems. In this thesis, we have surveyed the progress of the AC field, and studied the requirements, models and architectures of AC. The commonly recognized AC requirements are four properties - self-configuring, self-healing, self-optimizing, and self-protecting. The recommended software architecture is the MAPE-K model containing four modules, namely - monitor, analyze, plan and execute, as well as the knowledge repository. In the modern software marketplace, Java Management Extensions (JMX) has facilitated one function of the AC requirements - monitoring. Using JMX, we implemented a package that attempts to assist programming for AC features including socket management, logging, and recovery of distributed computation. In the experiments, we have not only realized the powerful Java capabilities that are unknown to many educators, we also illustrated the feasibility of learning AC in senior computer science courses.

This report describes a distributed approach to social filtering based on the agent metaphor. Firstly, previous approaches are described, such as cognitive filtering and social filtering. Then a couple of previously implemented systems are presented and then a new system design is proposed. The main goal is to give the requirements and design of an agent-based system that recommends web-documents. The presented approach combines cognitive and social filtering to get the advantages from both techniques. Finally, a prototype implementation called WebCondor is described and results of testing the system are reported and discussed.

[pt] Sistemas multi-agentes são sociedades com agentes autônomos e heterogêneos que podem trabalhar em conjunto para alcançar objetivos similares ou totalmente diferentes. Quando falhas acontecem enquanto algum agente de software tenta alcançar seus objetivos, torna-se importante entender porque tais falhas acontecem e o que pode ser feito para remediar tais problemas. Considerando o ambiente distribuído, dinâmico e a natureza dos sistemas multi-agentes, é importante definir os requisitos necessários para realizar diagnósticos das falhas e recomendações de planos alternativos para agentes que desejam alcançar seus objetivos. Assim, esta dissertação propõe soluções para os principais desafios de criar um sistema que realize diagnósticos e proveja recomendações sobre execuções de agentes. Além disso, o trabalho propõe um framework híbrido de diagnóstico e recomendação que provê suporte para tais desafios. A partir do framework, instâncias de diferentes domínios podem ser criadas, como, por exemplo, aplicações baseadas em computação ubíqua e diferentes diagnósticos e recomendações podem ser providas. / [en] Multi-agent systems are societies with autonomous and heterogeneous agents that can work together to achieve similar or different goals. Agents executing in such systems may not be able to achieve their goals due to failures during system execution. When an agent tries to achieve its desired goals, but faces failures during execution, it becomes important to understand why such failures occurred and what can be done to remedy the problem. The distributed, dynamic and nature of multi-agent systems calls for a new form of failure handling approach to address its unique requirements, which involves both diagnosing specific failures and recommending alternative plans for successful agent execution and goal attainment. We discuss solutions to the main challenges of creating a system that can perform diagnoses and provide recommendations about agent executions to support goal attainment, and propose a hybrid diagnostic-recommendation framework that provides support for methods to address such challenges. From the framework, instances of different domains can be created, such as, applications based on ubiquitous computing and different diagnoses and recommendations can be provided.