This thesis investigates logical formalizations of Castelfranchi and Falcone's (C&F) theory of trust [9, 10, 11, 12]. The C&F theory of trust defines trust as an essentially mental notion, making the theory particularly well suited for formalizations in multi-modal logics of beliefs, goals, intentions, actions, and time. Three different multi-modal logical formalisms intended for multi-agent systems are compared and evaluated along two lines of inquiry. First, I propose formal definitions of key concepts of the C&F theory of trust and prove some important properties of these definitions. The proven properties are then compared to the informal characterisation of the C&F theory. Second, the logics are used to formalize a case study involving an Internet forum, and their performances in the case study constitute grounds for a comparison. The comparison indicates that an accurate modelling of time, and the interaction of time and goals in particular, is integral for formal reasoning about trust. Finally, I propose a Horn fragment of the logic of Herzig, Lorini, Hubner, and Vercouter [25]. The Horn fragment is shown to be too restrictive to accurately express the considered case study.

This thesis focuses on deadbeat disturbance rejection for discrete-time linear multi-agent systems. The multi-agent systems, on which Spieser and Shams’ decentralized deadbeat output regulation problem is based, are extended by including disturbance agents. Specifically, we assume that there are one or more disturbance agents interacting with the plant agents in some known manner. The disturbance signals are assumed to be unmeasured and, for simplicity, constant. Control agents are introduced to interact with the plant agents, and each control agent is assigned a target plant agent. The goal is to drive the outputs of all plant agents to zero in finite time, despite the presence of the disturbances. In the decentralized deadbeat output regulation problem, two analysis schemes were introduced: targeting analysis, which is used to determine whether or not control laws can be found to regulate, not all the agents, but only the target agents; and growing analysis, which is used to determine the behaviour of all the non-target agents when the control laws are applied. In this thesis these two analyses are adopted to the deadbeat disturbance rejection problem. A new necessary condition for successful disturbance rejection is derived, namely that a control agent must be connected to the same plant agent to which a disturbance agent is connected. This result puts a bound on the minimum number of control agents and constraints the locations of control agents. Then, given the premise that both targeting and growing analyses succeed in the special case where the disturbances are all ignored, a new control approach is proposed for the linear case based on the idea of integral control and the regulation methods of Spieser and Shams. Preliminary studies show that this approach is also suitable for some nonlinear systems.

Software systems involving autonomous interacting software entities (or agents) present new challenges in computer science and software engineering. A particularly challenging problem is the engineering of various forms of interaction among agents. Interaction may be aimed at enabling agents to coordinate their activities, cooperate to reach common objectives, or exchange resources to better achieve their individual objectives. This thesis is concerned with negotiation: a process through which multiple self-interested agents can reach agreement over the exchange of scarce resources. In particular, I focus on settings where agents have limited or uncertain information, precluding them from making optimal individual decisions. I demonstrate that this form of bounded-rationality may lead agents to sub-optimal negotiation agreements. I argue that rational dialogue based on the exchange of arguments can enable agents to overcome this problem. Since agents make decisions based on particular underlying reasons, namely their interests, beliefs and planning knowledge, then rational dialogue over these reasons can enable agents to refine their individual decisions and consequently reach better agreements. I refer to this form of interaction as “interested-based negotiation.” (For complete abstract open document)

Most Artificial Intelligence (AI) work can be characterized as either ``high-level'' (e.g., logical, symbolic) or ``low-level'' (e.g., connectionist networks, behavior-based robotics). Each approach suffers from particular drawbacks. High-level AI uses abstractions that often have no relation to the way real, biological brains work. Low-level AI, on the other hand, tends to lack the powerful abstractions that are needed to express complex structures and relationships. I have tried to combine the best features of both approaches, by building a set of programming abstractions defined in terms of simple, biologically plausible components. At the ``ground level'', I define a primitive, perceptron-like computational unit. I then show how more abstract computational units may be implemented in terms of the primitive units, and show the utility of the abstract units in sample networks. The new units make it possible to build networks using concepts such as long-term memories, short-term memories, and frames. As a demonstration of these abstractions, I have implemented a simulator for ``creatures'' controlled by a network of abstract units. The creatures exist in a simple 2D world, and exhibit behaviors such as catching mobile prey and sorting colored blocks into matching boxes. This program demonstrates that it is possible to build systems that can interact effectively with a dynamic physical environment, yet use symbolic representations to control aspects of their behavior.

MOTL/O embodies the MOTL paradigm and models organizational adaptation. We report progress on developing computational tools for systematically altering organizational components. This adds a novel dimension to MOTL (Hexmoor, et.al., 2008). This extension is necessary to allow communities of agents or robots to reconfigure their organizational structure in response to changes in the environment. Traditional approach of a hierarchical command and control (C2) structure is ineffective (Alberts & Hayes, 2003). Recently, an edge organization has been proposed as a more suitable alternative Command and control structure in the current information age, due to its empowerment of the edge members, better shared awareness among all the members in the organization, interoperability and most importantly, agility and adaptability to dynamic situations (Chang, 2005). We will explore principled mechanisms for converting a hierarchical organization to an edge type organization. Other than structural differences, organizations differ in information flow network and information sharing strategies. We move toward a solution for organizational adaptation. Beyond current project, many other types of organizational adaptation are possible and require much further research that we anticipate for our future work. This task will lay the foundation for automatic organizational adaptation. This report begins by outlining related work and background in section 2. In section 3 we

The problem of searching for objects of interest occurs in important applications ranging from rescue, security, transportation, to medicine. With the increasing use of autonomous vehicles as search platforms, there is a need for fast algorithms that can generate search plans for multiple agents in response to new information. In this dissertation, we develop new techniques for automated generation of search plans for different classes of search problems. First, we study the problem of searching for a stationary object in a discrete search space with multiple agents where each agent can access only a subset of the search space. In these problems, agents can fail to detect an object when inspecting a location. We show that when the probabilities of detection only depend on the locations, this problem can be reformulated as a minimum cost network optimization problem, and develop a fast specialized algorithm for the solution. We prove that our algorithm finds the optimal solution in finite time, and has worst-case computation performance that is faster than general minimum cost flow algorithms. We then generalize it to the case where the probabilities of detection depend on the agents and the locations, and propose a greedy algorithm that is 1/2-approximate. Second, we study the problem of searching for a moving object in a discrete search space with multiple agents where each agent can access only a subset of a discrete search space at any time and agents can fail to detect objects when searching a location at a given time. We provide necessary conditions for an optimal search plan, extending prior results in search theory. For the case where the probabilities of detection depend on the locations and the time periods, we develop a forward-backward iterative algorithm based on coordinate descent techniques to obtain solutions. To avoid local optimum, we derive a convex relaxation of the dynamic search problem and show this can be solved optimally using coordinate descent techniques. The solutions of the relaxed problem are used to provide random starting conditions for the iterative algorithm. We also address the problem where the probabilities of detection depend on the agents as well as the locations and the time periods, and show that a greedy-style algorithm is 1/2-approximate. Third, we study problems when multiple objects of interest being searched are physically scattered among locations on a graph and the agents are subject to motion constraints captured by the graph edges as well as budget constraints. We model such problem as an orienteering problem, when searching with a single agent, or a team orienteering problem, when searching with multiple agents. We develop novel real-time efficient algorithms for both problems. Fourth, we investigate classes of continuous-region multi-agent adaptive search problems as stochastic control problems with imperfect information. We allow the agent measurement errors to be either correlated or independent across agents. The structure of these problems, with objectives related to information entropy, allows for a complete characterization of the optimal strategies and the optimal cost. We derive a lower bound on the performance of the minimum mean-square error estimator, and provide upper bounds on the estimation error for special cases. For agents with independent errors, we show that the optimal sensing strategies can be obtained in terms of the solution of decoupled scalar convex optimization problems, followed by a joint region selection procedure. We further consider search of multiple objects and provide an explicit construction for adaptively determining the sensing actions.

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.

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.

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