Agent-based computing has attracted much attention as a promising technique for application domains that are distributed, complex and heterogeneous. Current research on multi-agent systems (MAS) has become mature enough to be applied as a technology for solving problems in an increasingly wide range of complex applications. The main formal architectures used to describe the relationships between agents in MAS are centralised and distributed architectures. In computational complexity theory, researchers have classified the problems into the followings categories: (i) P problems, (ii) NP problems, (iii) NP-complete problems, and (iv) NP-hard problems. A method for computing the solution to NP-hard problems, using the algorithms and computational power available nowadays in reasonable time frame remains undiscovered. And unfortunately, many practical problems belong to this very class. On the other hand, it is essential that these problems are solved, and the only possibility of doing this is to use approximation techniques. Heuristic solution techniques are an alternative. A heuristic is a strategy that is powerful in general, but not absolutely guaranteed to provide the best (i.e. optimal) solutions or even find a solution. This demands adopting some optimisation techniques such as Evolutionary Algorithms (EA). This research has been undertaken to investigate the feasibility of running computationally intensive algorithms on multi-agent architectures while preserving the ability of small agents to run on small devices, including mobile devices. To achieve this, the present work proposes a new Hybrid Multi-Agent Architecture (HMAA) that generates new heuristics for solving NP-hard problems. This architecture is hybrid because it is "semi-distributed/semi-centralised" architecture where variables and constraints are distributed among small agents exactly as in distributed architectures, but when the small agents become stuck, a centralised control becomes active where the variables are transferred to a super agent, that has a central view of the whole system, and possesses much more computational power and intensive algorithms to generate new heuristics for the small agents, which find optimal solution for the specified problem. This research comes up with the followings: (1) Hybrid Multi-Agent Architecture (HMAA) that generates new heuristic for solving many NP-hard problems. (2) Two frameworks of HMAA have been implemented; search and optimisation frameworks. (3) New SMA meeting scheduling heuristic. (4) New SMA repair strategy for the scheduling process. (5) Small Agent (SMA) that is responsible for meeting scheduling has been developed. (6) “Local Search Programming” (LSP), a new concept for evolutionary approaches, has been introduced. (7) Two types of super-agent (LGP_SUA and LSP_SUA) have been implemented in the HMAA, and two SUAs (local and global optima) have been implemented for each type. (8) A prototype for HMAA has been implemented: this prototype employs the proposed meeting scheduling heuristic with the repair strategy on SMAs, and the four extensive algorithms on SUAs. The results reveal that this architecture is applicable to many different application domains because of its simplicity and efficiency. Its performance was better than many existing meeting scheduling architectures. HMAA can be modified and altered to other types of evolutionary approaches.

Self-reconfigurable robotic systems are variable-morphology machines capable of changing their overall structure by rearranging the modules they are composed of. Individual modules are capable of connecting and disconnecting to and from one another, which allows the robot to adapt to changing environments. Optimally reconfiguring such systems is computationally prohibitive and thus in general self-reconfiguration approaches aim at approximating optimal solutions. Nonetheless, even for approximate solutions, centralized methods scale poorly in the number of modules. Therefore, the objective of this research is the development of decentralized self-reconfiguration methods for modular robotic systems. Building on completeness results of the centralized algorithms in this work, decentralized methods are developed that guarantee stochastic convergence to a given target shape. A game-theoretic approach lays the theoretical foundation of a novel potential game-based formulation of the self-reconfiguration problem. Furthermore, two extensions to the basic game-theoretic algorithm are proposed that enable agents to modify the algorithms' parameters during runtime and improve convergence times. The flexibility in the choice of utility functions together with runtime adaptability makes the presented approach and the underlying theory suitable for a range of problems that rely on decentralized local control to guarantee global, emerging properties. The experimental evaluation of the presented algorithms relies on a newly developed multi-robotic testbed called the "Robotarium" that is equipped with custom-designed miniature robots, the "GRITSBots". The Robotarium provides hardware validation of self-reconfiguration on robots but more importantly introduces a novel paradigm for remote accessibility of multi-agent testbeds with the goal of lowering the barrier to entrance into the field of multi-robot research and education.

This thesis explores how multi-agent-based simulation can be used for transport policy analysis. Transport policies are often used as a means to reach governmental goals, such as environmental targets to reduce the impact of transportation. To predict how transportation is influenced by policies, public authorities often make use of simulation models. A structured review of such models is made focussing on important transport chain characteristics. We argue that to properly predict the actual environmental, economic, and logistical effects of transport policies, the logistical decisions made in transport chains must be modelled appropriately. Such decisions, e.g., concern the choice of producer and traffic mode, planning of transportation, production, and terminal handling. The review concludes that models currently used for transport policy analysis fail to capture many of these characteristics. We argue that agent-based models have the potential to include these aspects since they are able to explicitly model the actual decision making in transport chains. We have identified a set of generic roles in transport chains where each role is responsible for certain decisions. A multi-agent-based simulator, TAPAS, has been developed in which these roles are modelled as agents. Thus, the decision making in transport chains and its influence by the application of transport policies are captured. The decisions lead to the execution of the logistical operations which in turn have consequences on the logistics, economic, and environmental performance. The usage of TAPAS is illustrated by presenting two scenarios based on realworld transport chains. Simulation experiments of the scenarios have been performed where different types of transport policies are introduced. The simulation results are analysed, e.g., by comparing the results to similar studies and by sensitivity analysis of input parameters. To facilitate the validation and generalisation of simulation results we suggest making use of typical transport chains and roles characterised by, e.g., product type and geographical locations. The type of studies that TAPAS can support are described and compared to studies typically made with traditional models. Transport policies which are relevant to examine are described and their potential influence on transport chains are analysed. The possible usage of TAPAS is discussed and related to different types of users. Public authorities can, e.g., use TAPAS to complement studies using traditional models. This can improve the accuracy of the simulation results by the inclusion of more logistical aspects. Large companies are another type of user which, e.g., can use TAPAS to analyse new market segments, such as new product types or new consumers, where historical data is not available.

This thesis proposes a holistic and hierarchical architecture to Multi-agent System design, in order to resolve the collaboration problem in diabetic healthcare system. A diabetic healthcare system is a complex and social system in the case that it involves many actors and interrelations. Collaborations among various healthcare actors are vital to the quality of diabetic healthcare. The collaboration problem is manifested by the problems of accessibility and interoperability. To support the collaboration in diabetic healthcare as such a complex and social system, the MAS must have corresponding social entities and relationships. Therefore, it is assumed that theories explaining social activity can be applied to design of MAS. Activity Theory, specifically its holistic triangle model from Engström and hierarchy thinking, provides theoretical supports to the design of individual agent architecture and MAS coordination mechanism. It is argued that the holistic and hierarchical aspects should be designed in a MAS when applied to the healthcare setting. The diabetic healthcare system is analyzed on three levels based on the hierarchy thinking. The collaboration problem is analyzed and resolved via MAS coordination. Based on the holistic activity model in Activity Theory, Müller’s Vertical Layered Architecture is re-conceptualized in the Control Unit and Knowledge Base design. It is also argued that autonomy, adaptivity and persona should be especially focused when designing the interaction between an agent system and human users. This study has firstly identified some important social aspects and the technical feasibility of embedding those identified social aspects in agent architecture design. Secondly, a MAS was developed to illustrate how to apply the proposed architecture to design a MAS to resolve the collaboration problem in diabetic healthcare system. We have designed and implemented an agent system – IMAS (Integrated Multi-agent System) to validate the research questions and contributions. IMAS system provides real time monitoring, diabetic healthcare management and decision supports to the diabetic healthcare actors. A user assessment has been conducted to validate that the quality of the current diabetic healthcare system can be improved with the introduction of IMAS.

This report describes a method to control the density distribution of a large number of autonomous agents. The approach is based on the fact that there are a large number of agents in the system, and hence the time evolution of the probabilistic density distribution of agents can be described as a Markov chain. The main contribution of this paper is the synthesis of a Markov matrix which will guide the multi-agent system density to a desired steady-state density distribution, in a probabilistic sense, while satisfying some motion and safety constraints. Also, an adaptive density control method based on real time density feedback is introduced to synthesize a time-varying Markov ma- trix, which leads to better convergence to the desired density distribution. Finally, a decentralized density computation method is described. This method guarantees that all agents will have a best, and common, density estimate in a finite, with an explicit bound, number of communication updates. / text

Les systèmes multi-agents sont des systèmes dans lesquels des entités logiciellesappelées agents interagissent de façon autonome dans des environnements partagés. Ces dernièresannées, de nombreuses recherches sur les organisations multi-agents ont été menées etdivers modèles organisationnels ont été proposés. Cependant, ils n'offrent pas de solution pourune gestion effective de la problématique d'ouverture dans des organisations multi-agents normatives.Dans cette thèse, nous nous sommes intéressées à l'étude de cette problématique etdonc à la spécification des besoins relatifs à la mise en oeuvre de l'ouverture au sein d'organisationmulti-agent. Nous avons ainsi identifié trois propriétés caractéristiques de cette problématique: l'interopérabilité d'une organisation avec son environnement extérieur et interne, lagestion des entrées / sorties et la gestion du contrôle et de la régulation des agents. Pour répondreà ces propriétés, nous avons proposé un langage de modélisation d'organisation (OML)MOISE qui est une extension de Moise+. MOISE permet de spécifier de façon explicite lesprocessus d'entrée / sortie dans une organisation et notamment les exigences relatives auxmissions, buts, et rôles de l'organisation. Nous avons également proposé une infrastructure degestion d'organisation (OMI) ORA4MAS qui s'inspire du méta-modèle Agents et Artifacts(A&A). Nous avons défini le concept d'artefact organisationnel pour implémenter les fonctionnalitéscorrespondant aux spécifications du langage MOISE. Nos propositions ont été illustréesavec une spécification d'organisation de gestion de la construction d'un édifice. La miseen oeuvre des propriétés d'ouverture a été expérimentée avec la gestion des processus d'entrée/ sortie des agents, la négociation des clauses de contrat, la coordination des coopérations desagents à la réalisation des buts de construction d'un édifice, le contrôle des comportements desagents relativement aux normes de l'organisation ainsi que leur régulation.

Multi-agent systems represent a group of agents that cooperate to solve common tasks in a dynamic environment. Multi-agent control systems have been widely studied in the past few years. The control of multi-agent systems relates to synthesizing control schemes for systems which are inherently distributed and composed of multiple interacting entities. Because of the wide applications of multi-agent theories in large and complex control systems, it is necessary to develop a framework to simplify the process of developing control schemes for multi-agent systems. <br /><br /> In this study, a framework is proposed for the distributed control and coordination of multi-agent systems. In the proposed framework, the control of multi-agent systems is regarded as achieving decentralized control and coordination of agents. Each agent is modeled as a Coordinated Hybrid Agent (CHA) which is composed of an intelligent coordination layer and a hybrid control layer. The intelligent coordination layer takes the coordination input, plant input and workspace input. After processing the coordination primitives, the intelligent coordination layer outputs the desired action to the hybrid layer. In the proposed framework, we describe the coordination mechanism in a domain-independent way, as simple abstract primitives in a coordination rule base for certain dependency relationships between the activities of different agents. The intelligent coordination layer deals with the planning, coordination, decision-making and computation of the agent. The hybrid control layer of the proposed framework takes the output of the intelligent coordination layer and generates discrete and continuous control signals to control the overall process. In order to verify the feasibility of the proposed framework, experiments for both heterogeneous and homogeneous Multi-Agent Systems (MASs) are implemented. In addition, the stability of systems modeled using the proposed framework is also analyzed. The conditions for asymptotic stability and exponential stability of a CHA system are given. <br /><br /> In order to optimize a Multi-Agent System (MAS), a hybrid approach is proposed to address the optimization problem for a MAS modeled using the CHA framework. Both the event-driven dynamics and time-driven dynamics are included for the formulation of the optimization problem. A generic formula is given for the optimization of the framework. A direct identification algorithm is also discussed to solve the optimization problem.

The field of swarm robotics has been growing fast over the last few years. Using a swarm of simple and cheap robots has advantages in various tasks. Apart from performance gains on tasks that allow for parallel execution, simple robots can also be smaller, enabling them to reach areas that can not be accessed by a larger, more complex robot. Their ability to cooperate means they can execute complex tasks while offering self-organised adaptation to changing environments and robustness due to redundancy. In order to keep individual robots simple, a control algorithm has to keep expensive communication to a minimum and has to be able to act on little information to keep the amount of sensors down. The number of sensors and actuators can be reduced even more when necessary capabilities are spread out over different agents that then combine them by cooperating. Self-organised differentiation within these heterogeneous groups has to take the individual abilities of agents into account to improve group performance. In this thesis it is shown that a homogeneous group of versatile agents can not be easily replaced by a heterogeneous group, by separating the abilities of the versatile agents into several specialists. It is shown that no composition of those specialists produces the same outcome as a homogeneous group on a clustering task. In the second part of this work, an adaptation mechanism for a group of foragers introduced by Labella et al. (2004) is analysed in more detail. It does not require communication and needs only the information on individual success or failure. The algorithm leads to self-organised regulation of group activity depending on object availability in the environment by adjusting resting times in a base. A possible variation of this algorithm is introduced which replaces the probabilistic mechanism with which agents determine to leave the base. It is demonstrated that a direct calculation of the resting times does not lead to differences in terms of differentiation and speed of adaptation. After investigating effects of different parameters on the system, it is shown that there is no efficiency increase in static environments with constant object density when using a homogeneous group of agents. Efficiency gains can nevertheless be achieved in dynamic environments. The algorithm was also reported to lead to higher activity of agents which have higher performance. It is shown that this leads to efficiency gains in heterogeneous groups in static and dynamic environments.

This dissertation demonstrates, in a non-semantic information-theoretic framework, how the principles of 'maximisation of relevant information' and 'information parsimony' can guide the adaptation of an agent towards agent-agent interaction. Central to this thesis is the concept of digested information; I argue that an agent is intrinsically motivated to a.) process the relevant information in its environment and b.) display this information in its own actions. From the perspective of similar agents, who require similar information, this differentiates other agents from the rest of the environment, by virtue of the information they provide. This provides an informational incentive to observe other agents and integrate their information into one's own decision making process. This process is formalized in the framework of information theory, which allows for a quantitative treatment of the resulting effects, specifically how the digested information of an agent is influenced by several factors, such as the agent's performance and the integrated information of other agents. Two specific phenomena based on information maximisation arise in this thesis. One is flocking behaviour similar to boids that results when agents are searching for a location in a girdworld and integrated the information in other agent's actions via Bayes' Theorem. The other is an effect where integrating information from too many agents becomes detrimental to an agent's performance, for which several explanations are provided.

As multi-agent systems (MAS) have become more mature and systems in general have become more distributed, it is necessary for those who want to build large scale systems to consider, in some computational depth, how agents can communicate in large scale, complex and distributed systems. Currently, some MAS systems have been developed to use an abstract specification language for argumentation. This as a basis for agent communication; to provide effective decision support for agents and yield better agreements. However, as we build complete MAS that involve argumentation, there is a need to produce concrete implementations in which these abstract specifications are realised via protocols coordinating agent behaviour. This creates a gap between standard argument specification and deployment of protocols. This thesis attempts to close this gap by using a combination of automated synthesis and verification methods. More precisely, this thesis proposes a means of moving rapidly from argument specification to protocol implementation using an extension of the Argument Interchange Format (AIF is a generic specification language for argument structure) called a Dialogue Interaction Diagram (DID) as the dialogue game specification language and the Lightweight Coordination Calculus (LCC is an executable specification language used for coordinating agents in open systems) as an implementation language. The main contribution of this research is to provide approaches for enabling developers of dialogue game argumentation systems to use specification languages (in our case AIF/DID) to generate agent protocol systems that are capable of direct implementation on open infrastructures (in our case LCC).