This thesis proposes and tests a recursive, adpative, and computationally inexpensive method for partitioning real-number spaces. When tested for proof-of-concept on both one- and two- dimensional classification and control problems, the Fern algorithm was found to work well in one dimension, moderately well for two-dimensional classification, and not at all for two-dimensional control. Testing ferns as pure discretizers - which would involve a secondary discrete learner - has been left to future work. / text

In online shopping buyers do not have enough information about sellers and cannot inspect the products before purchasing them. To help buyers find reliable sellers, online marketplaces deploy Trust and Reputation Management (TRM) systems. These systems aggregate buyers’ feedback about the sellers they have interacted with and about the products they have purchased, to inform users within the marketplace about the sellers and products before making purchases. Thus positive customer feedback has become a valuable asset for each seller in order to attract more business. This naturally creates incentives for cheating, in terms of introducing fake positive feedback. Therefore, an important responsibility of TRM systems is to aid buyers find genuine feedback (reviews) about different sellers. Recent TRM systems achieve this goal by selecting and assigning credible advisers to any new customer/buyer. These advisers are selected among the buyers who have had experience with a number of sellers and have provided feedback for their services and goods. As people differ in their tastes, the buyer feedback that would be most useful should come from advisers with similar tastes and values. In addition, the advisers should be honest, i.e. provide truthful reviews and ratings, and not malicious, i.e. not collude with sellers to favour them or with other buyers to badmouth some sellers. Defining the boundary between dishonest and honest advisers is very important. However, currently, there is no systematic approach for setting the honesty threshold which divides benevolent advisers from the malicious ones. The thesis addresses this problem and proposes a market-adaptive honesty threshold management mechanism. In this mechanism the TRM system forms a feedback system which monitors the current status of the e-marketplace. According to the status of the e-marketplace the feedback system improves the performance utilizing PID controller from the field of control systems. The responsibility of this controller is to set the the suitable value of honesty threshold. The results of experiments, using simulation and real-world dataset show that the market-adaptive honesty threshold allows to optimize the performance of the marketplace with respect to throughput and buyer satisfaction.

Consensus is a central issue in designing multi-agent systems (MASs). How to design control protocols under certain communication topologies is the key for solving consensus problems. This thesis is focusing on investigating the consensus protocols under different scenarios: (1) The second-order system dynamics with Markov time delays; (2) The Euler-Lagrange dynamics with uniform and nonuniform sampling strategies and the event-based control strategy. Chapter 2 is focused on the consensus problem of the multi-agent systems with random delays governed by a Markov chain. For second-order dynamics under the sampled-data setting, we first convert the consensus problem to the stability analysis of the equivalent error system dynamics. By designing a suitable Lyapunov function and deriving a set of linear matrix inequalities (LMIs), we analyze the mean square stability of the error system dynamics with fixed communication topology. Since the transition probabilities in a Markov chain are sometimes partially unknown, we propose a method of estimating the delay for the next sampling time instant. We explicitly give a lower bound of the probability for the delay estimation which can ensure the stability of the error system dynamics. Finally, by applying an augmentation technique, we convert the error system dynamics to a delay-free stochastic system. A sufficient condition is established to guarantee the consensus of the networked multi-agent systems with switching topologies. Simulation studies for a fleet of unmanned vehicles verify the theoretical results. In Chapter 3, we propose the consensus control protocols involving both position and velocity information of the MASs with the linearized Euler-Lagrange dynamics, under uniform sampling and nonuniform sampling schemes, respectively. Then we extend the results to the case of applying the centralized event-triggered strategy, and accordingly analyze the consensus property. Simulation examples and comparisons verify the effectiveness of the proposed methods. / Graduate / 0548

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)

A multi-agent system consists of a collection of agents that interact with each other to fulfil their tasks. Individual agents can have different motivations for engaging in interactions. Also, agents can possibly recognise the goals of the other participants in the interaction. To successfully interact, an agent should exhibit the ability to balance reactivity, pro-activeness (autonomy) and sociability. That is, individual agents should deliberate not only on what they themselves know about the working environment and their desires, but also on what they know about the beliefs and desires of the other agents in their group. Multi-agent systems have proven to be a useful tool for modelling and solving problems that exhibit complex and distributed structures. Examples include real-time traffic control and monitoring, work-flow management and information retrieval in computer networks. There are two broad challenges that the agent community is currently investigating. One is the development of the formalisms for representing the knowledge the agents have about their actions, goals, plans for achieving their goals and other agents. The second challenge is the development of the reasoning mechanisms agents use to achieve autonomy during the course of their interactions. Our research interests lie in a model for the interactions among the agents, whereby the behaviour of the individual agents can be specified in a declarative manner and these specifications can be made executable. Therefore, we investigate the methods that effectively represent the agents' knowledge about their working environment (which includes other agents), to derive unrealised information from the agents' knowledge by considering that the agents can obtain only a partial image of their working environment. The research also deals with the logical reasoning about the knowledge of the other agents to achieve a better interaction. Our approach is to apply the notions of modality and non-monotonic reasoning to formalise and to confront the problem of incomplete and conflicting information when modelling multi-agent systems. The approach maintains the richness in the description of the logical method while providing an efficient and easy-to-implement reasoning mechanism. In addition to the theoretical analysis, we investigate n-person argumentation as an application that benefits from the efficiency of our approach.

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.