In the recent world championships of the simulated RoboCup league the winning teams possessed low level behaviours, such as kick and pass, that were close to perfection. In order to improve a team's performance you will need, beside perfect low level behaviours, a good management of the team. We present a model for managing a team in the simulated RoboCup league. The model is based on techniques used by the recent winners in the league and allows you to get a well coordinated team of agents striving for a common goal. The model supports different formations in different situations, which contributes to a dynamic team play, where the players can adjust to their opponents and other factors like time left and goal difference. For example if the game is near the end and the team is loosing a more risky and aggressive tactic is chosen.

För att ta reda på hur väl en Multi-Agent-Systems-bot kan stå sig mot andra, icke-MAS-bottar, så har vi implementerat en bot till brädspelet Arimaa. Botten är implementerad i C++ och den kan spela mot andra bottar, eller människor, genom Arimaas officiella hemsida. Syftet har varit att skapa en fullfjädrad bot som både klarar av att spela korrekt, och att spela bra. För att ta reda på om MAS är en bra designfilosofi för Arimaa så har vi utmanat ett antal av de bottar som andra människor skapat och lagt upp på hemsidan. Alla bottarna har under tiden de legat uppe blivit rankade genom tävlingar och utmaningar och flera av dessa har tävlat om stora pengar, vilket betyder att människor har lagt mycket tid på dem. Efter ett stort antal matcher mot andra bottar så har vi kommit fram till att Arimaa är ett väldigt svårt spel att koda bottar till. Vi lyckades bara slå några av de sämsta bottarna på hemsidan men MAS visar stor potential och vi tror att man kan göra väldigt avancerade bottar med det. Jämfört med de bästa bottarna så är vår väldigt snabb och minneseffektiv. Man borde absolut experimentera mer.

Multi-agent systems are increasingly popular for modeling distributed environments that are highly complex and dynamic such as e-commerce, smart buildings, and smart grids. Often in open multi-agent systems, agents interact with other agents to meet their own goals. Trust is considered significant in multi-agent systems to make interactions effectively, especially when agents cannot assure that potential partners share the same core beliefs about the system or make accurate statements regarding their competencies and abilities. This work describes a trust model that augments fuzzy logic with Q-learning, and a suspension technique to help trust evaluating agents select beneficial trustees for interaction in uncertain, imprecise, and the dynamic multi-agent systems. Q-Learning is used to evaluate trust on the long term, fuzzy inferences are used to aggregate different trust factors and suspension is used as a short-term response to dynamic changes. The performance of the proposed model is evaluated using simulation. Simulation results indicate that the proposed model can help agents select trustworthy partners to interact with. It has a better performance compared to some of the popular trust models in the presence of misbehaving interaction partners. When interactions are based on trust, trust establishment mechanisms can be used to direct trustees, instead of trustors, to build a higher level of trust and have a greater impact on the results of interactions. This work also describes a trust establishment model for intelligent agents using implicit feedback that goes beyond trust evaluation to outline actions to guide trustees (instead of trustors). The model uses the retention of trustors to model trustors’ behaviours. For situations where tasks are multi-criteria and explicit feedback is available, we present a trust establishment model that uses a multi-criteria approach to help trustees to adjust their behaviours to improve their perceived trust and attract more interactions with trustors. The model calculates the necessary improvement per criterion when only a single aggregated satisfaction value is provided per interaction, where the model attempts to predicted both the appropriate value per criteria and its importance. Then we present a trust establishment model that integrates the two major sources of information to produce a comprehensive assessment of a trustor’s likely needs in multi-agent systems. Specifically, the model attempts to incorporates explicit feedback, and implicit feed-back assuming multi-criteria tasks. The proposed models are evaluated through simulation, we found that trustees can enhance their trustworthiness, at a cost, if they tune their behaviour in response to feedback (explicit or implicit) from trustors. Using explicit feedback with multi-criteria tasks, trustees can emphasize on important criterion to satisfy need of trustors. Trust establishment based on explicit feedback for multi-criteria tasks, can result in a more effective and efficient trust establishment compared to using implicit feedback alone. Integrating both approaches together can achieve a reasonable trust level at a relatively lower cost.

In this work we present the problem of multi-agent path-finding with dynamic obstacles, a generalisation of multi-agent path-finding (MAPF) in which the environment contains randomly-moving dynamic obstacles. This generalisation can be though of as an abstraction of incomplete knowledge of the environment or as a simplification of the multi-agent path-finding where we do not include all agents in the cooperative planner. We adapt three planning algorithms for MAPF to work in an environment with dy- namic obstacles: Local-Repair A* (LRA*), Windowed Hierarchical Cooper- ative A* (WHCA*) and Operator Decomposition with Independence Detec- tion (OD/ID). In addition, we propose two heuristics for these algorithms in dynamic environments: Path Rejoining and Obstacle Predictor. In our experiments, we find that LRA* and WHCA* are best suited for the dy- namic environment. The Path Rejoining heuristic is successful in improving run-times at a small cost in makespan. Obstacle Prediction is capable of lowering the number of times a plan has to be found, but the overhead of our implementation outweighs any performance benefits in most cases. 1

In the past two decades, multi-agent systems (MAS) have emerged as a new paradigm for conceptualizing large and complex distributed software systems. A multi-agent system view provides a natural abstraction for both the structure and the behavior of modern-day software systems. Although there were many conceptual frameworks for using multi-agent systems, there was no well established and widely accepted method for modeling multi-agent systems. This dissertation research addressed the representation and analysis of multi-agent systems based on model-oriented formal methods. The objective was to provide a systematic approach for studying MAS at an early stage of system development to ensure the quality of design. Given that there was no well-defined formal model directly supporting agent-oriented modeling, this study was centered on three main topics: (1) adapting a well-known formal model, predicate transition nets (PrT nets), to support MAS modeling; (2) formulating a modeling methodology to ease the construction of formal MAS models; and (3) developing a technique to support machine analysis of formal MAS models using model checking technology. PrT nets were extended to include the notions of dynamic structure, agent communication and coordination to support agent-oriented modeling. An aspect-oriented technique was developed to address the modularity of agent models and compositionality of incremental analysis. A set of translation rules were defined to systematically translate formal MAS models to concrete models that can be verified through the model checker SPIN (Simple Promela Interpreter). This dissertation presents the framework developed for modeling and analyzing MAS, including a well-defined process model based on nested PrT nets, and a comprehensive methodology to guide the construction and analysis of formal MAS models.

With the help of rapidly advancing communication technology, control systems are increasingly integrated via communication networks. Networked control systems (NCSs) bring significant advantages such as flexible and scalable structures, easy implementation and maintenance, and efficient resources distribution and allocation. NCSs empowers to finish some complicated tasks using some relatively simple systems in a collaborated manner. However, there are also some challenges and constraints subject to the imperfection of communication channels. In this thesis, the stabilization problems and the performance limitation problems of control systems subject to networked-induced constraints are studied. Overall, the thesis mainly includes two parts: 1) Consensus and consensusability of multi-agent systems (MASs); 2) Delay margins of NCSs. Chapter 2 and Chapter 3 deal with the consensus problems of MASs, which aim to properly design the control protocols to ensure the state convergence of all the agents. Chapter 4 and Chapter 5 focus on the consensusability analysis, exploring how the dynamics of the agents and the networked induced constraints impact the overall systems for achieving consensus. Chapter 6 pays attention to the delay margins of discrete-time linear time-invariant (LTI) systems, studying how the dynamics of the plants limit the time delays that can be tolerated by LTI controllers. In Chapter 2, the leader-following consensus problem of MASs with general linear dynamics and arbitrary switching topologies is considered. The MAS with arbitrary switching topologies is formulated as a switched system. Then the leaderfollowing consensus problem is transformed to the stability problem of the corresponding switched system. A necessary and sufficient consensus condition is derived. The condition is also extended to MASs with time-varying delays. In Chapter 3, the consensus problem of MASs with general linear dynamics is studied. Motivated by the multiple-input multiple-output (MIMO) communication technique, a general framework is considered in which different state variables are exchanged in different independent communication topologies. This novel framework could improve the control system design flexibility and potentially improve the system performance. Fully distributed consensus protocols are proposed and analyzed for the settings of fixed and switching multiple topologies. The protocols can be applied using only local information. And the control gains can be designed depending on the dynamics of the individual agent. By transforming the overall MASs into cascade systems, necessary and sufficient conditions are provided to guarantee the consensus under fixed and switching state-variables-dependent topologies, respectively. Chapter 4 investigates the consensusability problem for MASs with time-varying delays. The bounded delays can be arbitrarily fast time-varying. The communication topology is assumed to be undirected and fixed. Considering general linear dynamics under average state protocols, the consensus problem is then transformed into a robust control problem. Sufficient frequency domain criteria are established in terms of small-gain theorem by analyzing the delay dependent gains for both continuoustime and discrete-time systems. The controller synthesis problems can be solved by applying the frequency domain design methods. The consensusablity problem of general linear MASs considering directed topologies are explored from a frequency domain perspective in Chapter 5. By investigating the properties of Laplacian spectra, a consensus criterion is established based on the stability of several complex weighted closed-loop systems. Furthermore, for singleinput MASs, frequency domain consensusability criteria are proposed on the basis of the stability margins, which depend on the H∞ norm of the complementary sensitivity function determined by the agents’ unstable poles. The corresponding design procedure is also developed. Chapter 6 studies the delay margin problem of discrete-time LTI systems. For general LTI plants with multiple unstable poles and nonminimum phase zeros, we employ analytic function interpolation and rational approximation techniques to derive bounds on delay margins. Readily computable and explicit lower bounds are found by computing the real eigenvalues of a constant matrix, and LTI controllers can be synthesized based on the H∞ control theory to achieve the bounds. The results can be also consistently extended to the case of systems with time-varying delays. For first-order unstable plants, we also obtain bounds achievable by proportionalintergral- derivative (PID) controllers, which are of interest to PID control design and implementation. It is worth noting that unlike its continuous-time counterpart, the discrete-time delay margin problem being considered herein constitutes a simultaneous stabilization problem, which is known to be rather difficult. While previous work on the discrete-time delay margin led to negative results, the bounds developed in this chapter provide instead a guaranteed range of delays within which the delayed plants can be robustly stabilized, and in turn solve the special class of simultaneous stabilization problems in question. Finally, in Chapter 7, the thesis is summarized and some future research topics are also presented. / Graduate

In order to succeed, it is imperative that all e-commerce systems include an effective and reliable trust and reputation modeling system. This is particularly true of decentralized e-commerce systems in which autonomous software engage in commercial transactions. Many researchers have sought to overcome the complexities of modeling a subjective, human concept like trust, resulting in several trust and reputation models. While these models each present a unique offering and solution to the problem, several issues persist. Most of the models require direct experience in the e-commerce system in order to make effective trust decisions. This leaves new agents and agents who only casually use the e-commerce system vulnerable. Additionally, the reputation ratings of agents who are relatively new to the system are often indistinguishable from scores for poorly performing agents. Finally, more tactics to defend against agents who exploit the characteristics of the open, distributed system for their own malicious needs are required. To address these issues, a new metric is devised and presented: seniority. Based on agent age and activity level within the e-commerce system, seniority provides a means of judging the credibility of other agents with little or no prior experience in the system. As the results of experimental analysis reveals, employing a reputation model that uses seniority provides considerable value to agents who are new agents, casual buyer agents and all other purchasing agents in the e-commerce system. This new metric therefore offers a significant contribution toward the development of enhanced and new trust and reputation models for deployment in real-world distributed e-commerce environments.

This thesis explores the uses of a multi-agent system(MAS) for procedural content generation(PCG) in the Generative Design in Minecraft (GDMC) competition. The generatorconstructed is capable of surveying the terrain and determining where to start building a roadnetwork. Extendor and connector agents build the road network used for the settlement. Aplotting agent surveys the area around the created roads for plots appropriate for buildinghouses. A house building agent then generates basic buildings on these plots. Finally afurniture agent places furniture in these buildings. The result of the thesis shows that thegenerator is capable of generating an interesting road network that is appropriate to its terrain.The buildings have potential but are lacking in form of adaptability to the current biome andbuildings are overall too similar to be interesting, causing it to get low scores in the userstudy and competition. The generator was entered to the GDMC-competition in 2021 where itplaced 17th of 20th place.

In Multi-Agent Systems consisting of intelligent agents that interact with one another, where the agents are software entities which represent individuals or organizations, it is important for the agents to be equipped with trust evaluation models which allow the agents to evaluate the trustworthiness of other agents when dishonest agents may exist in an environment. Evaluating trust allows agents to find and select reliable interaction partners in an environment. Thus, the cost incurred by an agent for establishing trust in an environment can be compensated if this improved trustworthiness leads to an increased number of profitable transactions. Therefore, it is equally important to design effective trust establishment models which allow an agent to generate trust among other agents in an environment. This thesis focuses on providing improvements to the designs of existing and future trust establishment models. Robust trust establishment models, such as the Integrated Trust Establishment (ITE) model, may use dynamically updated variables to adjust the predicted importance of a task’s criteria for specific trustors. This thesis proposes a cluster-based approach to update these dynamic variables more accurately to achieve improved trust establishment performance. Rather than sharing these dynamic variables globally, a model can learn to adjust a trustee’s behaviours more accurately to trustor needs by storing the variables locally for each trustor and by updating groups of these variables together by using data from a corresponding group of similar trustors. This work also presents a generalized trust establishment model architecture to help models be easier to design and be more modular. This architecture introduces a new transaction-level preprocessing module to help improve a model’s performance and defines a trustor-level postprocessing module to encapsulate the designs of existing models. The preprocessing module allows a model to fine-tune the resources that an agent will provide during a transaction before it occurs. A trust establishment model, named the Generalized Trust Establishment Model (GTEM), is designed to showcase the benefits of using the preprocessing module. Simulated comparisons between a cluster-based version of ITE and ITE indicate that the cluster-based approach helps trustees better meet the expectations of trustors while minimizing the cost of doing so. Comparing GTEM to itself without the preprocessing module and to two existing models in simulated tests exhibits that the preprocessing module improves a trustee’s trustworthiness and better meets trustor desires at a faster rate than without using preprocessing.

In the study of multi-agent systems (MASs), cooperative control is one of the most fundamental issues. As it covers a broad spectrum of applications in many industrial areas, there is a desire to design cooperative control protocols for different system and network setups. Motivated by this fact, in this thesis we focus on elaborating consensus protocol design, via model predictive control (MPC), under two different scenarios: (1) general constrained linear MASs with bounded additive disturbance; (2) linear MASs with input constraints underlying distributed communication networks. In Chapter 2, a tube-based robust MPC consensus protocol for constrained linear MASs is proposed. For undisturbed linear MASs without constraints, the results on designing a centralized linear consensus protocol are first developed by a suboptimal linear quadratic approach. In order to evaluate the control performance of the suboptimal consensus protocol, we use an infinite horizon linear quadratic objective function to penalize the disagreement among agents and the size of control inputs. Due to the non-convexity of the performance function, an optimal controller gain is difficult or even impossible to find, thus a suboptimal consensus protocol is derived. In the presence of disturbance, the original MASs may not maintain certain properties such as stability and cooperative performance. To this end, a tube-based robust MPC framework is introduced. When disturbance is involved, the original constraints in nominal prediction should be tightened so as to achieve robust constraint satisfaction, as the predicted states and the actual states are not necessarily the same. Moreover, the corresponding robust constraint sets can be determined offline, requiring no extra iterative online computation in implementation. In Chapter 3, a novel distributed MPC-based consensus protocol is proposed for general linear MASs with input constraints. For the linear MAS without constraints, a pre-stabilizing distributed linear consensus protocol is developed by an inverse optimal approach, such that the corresponding closed-loop system is asymptotically stable with respect to a consensus set. Implementing this pre-stabilizing controller in a distributed digital setting is however not possible, as it requires every local decision maker to continuously access the state of their neighbors simultaneously when updating the control input. To relax these requirements, the assumed neighboring state, instead of the actual state of neighbors, is used. In our distributed MPC scheme, each local controller minimizes a group of control variables to generate control input. Moreover, an additional state constraint is proposed to bound deviation between the actual and the assumed state. In this way, consistency is enforced between intended behaviors of an agent and what its neighbors believe it will behave. We later show that the closed-loop system converges to a neighboring set of the consensus set thanks to the bounded state deviation in prediction. In Chapter 4, conclusions are made and some research topics for future exploring are presented. / Graduate / 2021-03-31