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 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.

Internet es, tal vez, el avance científico más relevante de nuestros días. Entre otras cosas, Internet ha permitido la evolución de los paradigmas de computación tradicionales hacia el paradigma de computaciónn distribuida, que se caracteriza por utilizar una red abierta de ordenadores. Los sistemas multiagente (SMA) son una tecnolog a adecuada para abordar los retos motivados por estos sistemas abiertos distribuidos. Los SMA son aplicaciones formadas por agentes heterog eneos y aut onomos que pueden haber sido dise~nados de forma independiente de acuerdo con objetivos y motivaciones diferentes. Por lo tanto, no es posible realizar ninguna hip otesis a priori sobre el comportamiento de los agentes. Por este motivo, los SMA necesitan de mecanismos de coordinaci on y cooperaci on, como las normas, para garantizar el orden social y evitar la aparici on de conictos. El t ermino norma cubre dos dimensiones diferentes: i) las normas como un instrumento que gu a a los ciudadanos a la hora de realizar acciones y actividades, por lo que las normas de nen los procedimientos y/o los protocolos que se deben seguir en una situaci on concreta, y ii) las normas como ordenes o prohibiciones respaldadas por un sistema de sanciones, por lo que las normas son medios para prevenir o castigar ciertas acciones. En el area de los SMA, las normas se vienen utilizando como una especi caci on formal de lo que est a permitido, obligado y prohibido dentro de una sociedad. De este modo, las normas permiten regular la vida de los agentes software y las interacciones entre ellos. La motivaci on principal de esta tesis es permitir a los dise~nadores de los SMA utilizar normas como un mecanismo para controlar y coordinar SMA abiertos. Nuestro objetivo es elaborar mecanismos normativos a dos niveles: a nivel de agente y a nivel de infraestructura. Por lo tanto, en esta tesis se aborda primero el problema de la de nici on de agentes normativos aut onomos que sean capaces de deliberar acerca / Criado Pacheco, N. (2012). Using Norms To Control Open Multi-Agent Systems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/17800 / Palancia

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

<div>In recent years, the collective behaviors in nature have motivated rapidly expanding research efforts in the control of multi-agent systems. A multi-agent system is composed of multiple interacting subsystems (agents). In order to seek approaches that respect the network nature of multi-agent systems, distributed algorithms has recently received a significant amount of research attention, the goal of which is allowing multi-agent systems to accomplish global objectives through only local coordination. </div><div> Under this scope, we consider three major problems in this dissertation, namely, distributed computation, distributed optimization, and the resilience of distributed algorithms. First, for distributed computation, we devise distributed algorithms for solving linear equations, which can eliminate the initialization step for agents; converge to the minimum $l_1$ and $l_2$ solutions of under-determined linear equations; achieve ultimate scalability inters of agents' local storage and local states. Second, for distributed optimization, we introduce a new method for algorithm discretization so that the agents no longer have to carefully choose their step-size. We also introduce a new distributed optimization approach that can achieve better convergence rate with lower bandwidth requirement. Finally, for the resilience of distributed algorithms, we propose a new approach that allow normal agents in the multi-agent system to automatically isolate any false information from malicious agents without identification process. Though out the dissertation, all mentioned results are theoretically guaranteed and numerically validated.</div>

This thesis is concerned with the problem of planning paths for autonomous cars through a smart traffic intersection. In this thesis, we describe existing concepts for solving this problem and discuss the possibilities of approaching intersection problems theoretically. Then, we choose one specific approach and design a declarative model for solving the problem. We use that model to perform a series of theoretical experiments to test the throughput and the quality of intersection paths described by different graphs. After that, we translate theoretical plans to actions for real robots and run it. In these experiments, we measure the degree of robots desynchronization and performance success of the plans based on the collision rate. We also describe how to improve action translation to achieve better performance than that for real robots following the straightforward plans.

<p>With the increasing availability of data and the rise of networked systems such as autonomous vehicles, drones, and smart girds, the application of data-driven, machine learning methods with multi-agents systems have become an important topic. In particular, reinforcement learning has gained a lot of popularity due to its similarities with optimal control, with the potential of allowing us to develop optimal control systems using only observed data and without the need for a model of a system's state dynamics. In this thesis work, we explore the application of reinforcement learning with multi-agents systems, which is known as multi-agent reinforcement learning (MARL). We have developed algorithms that address some challenges in the cooperative setting of MARL. We have also done work on better understanding the convergence guarantees of some known multi-agent reinforcement learning algorithms, which combine reinforcement learning with distributed consensus methods. And, with the aim of making MARL better suited to real-world problems, we have also developed algorithms to address some practical challenges with MARL and we have applied MARL on a real-world problem.</p> <p>In the first part of this thesis, we focus on developing algorithms to address some open problems in MARL. One of these challenges is learning with output feedback, which is known as partial observability in the reinforcement learning literature. One of the main assumptions of reinforcement learning in the singles agent case is that the agent can fully observe the state of the plant it is controlling (we note the “plant" is often referred to as the “environment" in the reinforcement learning literature. We will use these terms interchangeably). In the single agent case this assumption can be reasonable since it only requires one agent to fully observe its environment. In the multi-agent setting, however, this assumption would require all agents to fully observe the state and furthermore since each agent could affect the plant (or environment) with its actions, the assumption would also require that agent's know the actions of other agents. We have also developed algorithms to address practical issues that may arise when applying reinforcement learning (RL) or MARL on large-scale real-world systems. One such algorithm is a distributed reinforcement learning algorithm that allows us to learn in cases where the states and actions are both continuous and of large dimensionality, which is the case for many real-world applications. Without the ability to handle continuous states and actions, many algorithms require discretization, which with high dimensional systems can become impractical. We have also developed a distributed reinforcement learning algorithm that addresses data scalability of RL. By data scalability we mean how to learn from a very large dataset that cannot be efficiently processed by a single agent with limited resources.</p> <p>In the second part of this thesis, we provide a finite-sample analysis of some distributed reinforcement learning algorithms. By finite-sample analysis, we mean we provide an upper bound on the squared error of the algorithm for a given iteration of the algorithm. Or equivalently, since each iteration uses one data sample, we provide an upper bound of the squared error for a given number of data samples used. This type of analysis had been missing in the MARL literature, where most works on MARL have only provided asymptotic results for their proposed algorithms, which only tells us how the algorithmic error behaves as the number of samples used goes to infinity. </p> <p>The third part of this thesis focuses on applications with real-world systems. We have explored a real-world problem, namely transactive energy systems (TES), which can be represented as a multi-agent system. We have applied various reinforcement learning algorithms with the aim of learning an optimal control policy for this system. Through simulations, we have compared the performance of these algorithms and have illustrated the effect of partial observability (output feedback) when compared to full state feedback.</p> <p>In the last part we present some other work, specifically we present a distributed observer that aims to address learning with output feedback by estimating the state. The proposed algorithm is designed so that we do not require a complete model of state dynamics, and instead we use a parameterized model where the parameters are estimated along with the state.</p>

A software agents based manufacturing scheduling module for Advanced Planning and Scheduling (APS) is presented. The problem considered is scheduling of jobs with multiple operations, distinct operation processing times, arrival times, and due dates in a job shop environment. Sequence dependent setups are also considered. The additional constraints of material and resource availability are also taken into consideration. The scheduling is to be considered in integration with production planning. The production plans can be changed dynamically and the schedule is to be generated to reflect the appropriate changes. The design of a generic multi-agent framework which is domain independent along with algorithms that are used by the agents is also discussed. / Master of Science

In persistent monitoring tasks, cooperating mobile agents are used to monitor a dynamically changing environment that cannot be fully covered by a stationary team of agents. The exploration process leads to the discovery of various "points of interest" (targets) to be perpetually monitored. Through an optimal control approach, the first part of this dissertation shows that in a one-dimensional mission space the solution can be reduced to a simpler parametric problem. The behavior of agents under optimal control is described by a hybrid system which can be analyzed using Infinitesimal Perturbation Analysis (IPA) to obtain an on-line solution. IPA allows the modeling of virtually arbitrary stochastic effects in target uncertainty and its event-driven nature renders the solution scalable in the number of events rather than the state space. The second part of this work extends the results of the one-dimensional persistent monitoring problem to a two-dimensional space with constrained agent mobility. Under a general graph setting, the properties of the one-dimensional optimal control solution are largely inherited. The solution involves the design of agent trajectories defined by both the sequence of nodes to be visited and the amount of time spent at each node. A class of distributed threshold-based parametric controllers is proposed to reduce the computational complexity. These parameters are optimized through an event-driven IPA gradient-based algorithm and yield optimal controllers within this family of threshold-based policies. The performance of the threshold-based parametric controller is close to that of the optimal controller derived through dynamic programming and its computational complexity is smaller by orders of magnitude. Although effective, the aforementioned optimal controls are established on the assumption that agents are all connected via a centralized controller which is energy-consuming and unreliable in adversarial environments. The third part of this work extends the previous controls by developing decentralized controllers which distribute functionality to the agents so that each one acts upon local information and sparse communication with neighbors. The complexity of decentralization for persistent monitoring problems is significant given agent mobility and the overall time-varying graph topology. Conditions are identified and a decentralized framework is proposed under which the centralized solution can be exactly recovered in a decentralized event-driven manner based on local information -- except for one event requiring communication from a non-neighbor agent.