My thesis investigates fault tolerance for cooperative agent systems that have some equivalent of self-replication and self-death. Utilizing biologically-inspired mechanisms, I increase multi-agent system robustness for faulty agents when it is unknown exactly which agent is malfunctioning. It is important to determine new ways to increase robustness of a system, as otherwise it cannot be guaranteed to function in all situations and thus cannot be relied upon. Robustness of a system allows agents to recover from errors and thus function continuously, an increasingly important trait as agent systems are deployed in real world scenarios such as sensor networks or surveillance systems where faulty or malicious nodes could disrupt application performance. To achieve robustness, there must either be prevention of all errors, or a technique for recovering from errors after they have occurred. My thesis creates a new fault tolerance mechanism inspired by cancer biology to remove faulty agents, and then re-applies the developed technique to study the removal of biological cancer cells in simulation.

A distributed non-hierarchical metacognitive architec- ture is one in which all meta-level reasoning compo- nents are subject to meta-level monitoring and manage- ment by other components. Such metacognitive distri- bution can support the robustness of distributed IT sys- tems in which humans and artificial agents are partic- ipants. However, robust metacognition also needs to be context-aware and use diversity in its reasoning and analysis methods. Both these requirements mean that an agent evaluates its reasoning within a “bigger picture” and that it can monitor this global picture from multi- ple perspectives. In particular, social context-awareness involves understanding the goals and concerns of users and organisations. In this paper, we first present a conceptual architecture for distributed metacognition with context-awareness and diversity. We then consider the challenges of apply- ing this architecture to autonomic management systems in scenarios where agents must collectively diagnose and respond to errors and intrusions. Such autonomic systems need rich semantic knowledge and diverse data sources in order to provide the necessary context for their metacognitive evaluations and decisions.

One of the critical factors for a successful cooperative relationship in a supply chain partnership is trust. Many real-world applications, such as Supply Chain Management (SCM), can be modeled using multi-agent systems. One shortcoming of current SCM models is that their trust models are ad hoc and do not have a strong theoretical basis. As a result, they are unable to model subtleties in agent behavior that can be used to build a more accurate trust model. We propose a trust model for SCM that is grounded in probabilistic game theory. In this model, trust can be gained through direct interactions and/or by asking for information from other trustworthy agents. We will use this model to simulate and study supply chain market behavior.

We study several classes of interactive assistants from the points of view of decision theory and computational complexity. We first introduce a special class of POMDPs called hidden-goal MDPs (HGMDPs), which formalize the problem of interactively assisting an agent whose goal is hidden and whose actions are observable. In spite of its restricted nature, we show that optimal action selection in finite horizon HGMDPs is PSPACE-complete even in domains with deterministic dynamics. We then introduce a more restricted model called helper action MDPs (HAMDPs), where the assistant’s action is accepted by the agent when it is helpful, and can be easily ignored by the agent otherwise. We show classes of HAMDPs that are complete for PSPACE and NP along with a polynomial time class. Furthermore, we show that for general HAMDPs a simple myopic policy achieves a regret, compared to an omniscient assistant, that is bounded by the entropy of the initial goal distribution. A variation of this policy is also shown to achieve worst-case regret that is logarithmic in the number of goals for any goal distribution.

Distributed constraint optimization (DCOP) problems are a popular way of formulating and solving agent-coordination problems. A DCOP problem is a problem where several agents coordinate their values such that the sum of the resulting constraint costs is minimal. It is often desirable to solve DCOP problems with memory-bounded and asynchronous algorithms. We introduce Branch-and-Bound ADOPT (BnB-ADOPT), a memory-bounded asynchronous DCOP search algorithm that uses the message-passing and communication framework of ADOPT (Modi, Shen, Tambe, & Yokoo, 2005), a well known memory-bounded asynchronous DCOP search algorithm, but changes the search strategy of ADOPT from best-first search to depth-first branch-and-bound search. Our experimental results show that BnB-ADOPT finds cost-minimal solutions up to one order of magnitude faster than ADOPT for a variety of large DCOP problems and is as fast as NCBB, a memory-bounded synchronous DCOP search algorithm, for most of these DCOP problems. Additionally, it is often desirable to find bounded-error solutions for DCOP problems within a reasonable amount of time since finding cost-minimal solutions is NP-hard. The existing bounded-error approximation mechanism allows users only to specify an absolute error bound on the solution cost but a relative error bound is often more intuitive. Thus, we present two new bounded-error approximation mechanisms that allow for relative error bounds and implement them on top of BnB-ADOPT.

We present DCL-PC: a logic for reasoning about how the abilities of agents and coalitions of agents are altered by transferring control from one agent to another. The logical foundation of DCL-PC is CL-PC, a logic for reasoning about cooperation in which the abilities of agents and coalitions of agents stem from a distribution of atomic Boolean variables to individual agents -- the choices available to a coalition correspond to assignments to the variables the coalition controls. The basic modal constructs of DCL-PC are of the form `coalition C can cooperate to bring about phi'. DCL-PC extends CL-PC with dynamic logic modalities in which atomic programs are of the form `agent i gives control of variable p to agent j'; as usual in dynamic logic, these atomic programs may be combined using sequence, iteration, choice, and test operators to form complex programs. By combining such dynamic transfer programs with cooperation modalities, it becomes possible to reason about how the power of agents and coalitions is affected by the transfer of control. We give two alternative semantics for the logic: a `direct' semantics, in which we capture the distributions of Boolean variables to agents; and a more conventional Kripke semantics. We prove that these semantics are equivalent, and then present an axiomatization for the logic. We investigate the computational complexity of model checking and satisfiability for DCL-PC, and show that both problems are PSPACE-complete (and hence no worse than the underlying logic CL-PC). Finally, we investigate the characterisation of control in DCL-PC. We distinguish between first-order control -- the ability of an agent or coalition to control some state of affairs through the assignment of values to the variables under the control of the agent or coalition -- and second-order control -- the ability of an agent to exert control over the control that other agents have by transferring variables to other agents. We give a logical characterisation of second-order control.

Anticipating the actions of others is key to coordinating joint activities. We propose the notion of anticipatory action and perception for for robots acting with humans. We describe four systems in which anticipation has been modeled for human-robot interaction; two in a teamwork setting, and two in a human-robot joint performance setting. In evaluating the effects of anticipatory agent activity, we find in one study that anticipation aids in team efficiency, as well as in the perceived commitment of the robot to the team and its contribution to the team's fluency and success. In another study we see anticipatory action and perception affect the human partner's sense of team fluency, the team's improvement over time, the robot’s contribution to the efficiency and fluency, the robot's intelligence, and the robot’s adaptation to the task. We also find that subjects working with the anticipatory robot attribute more human qualities to the robot, such as gender and intelligence.

Representing human behavior and cognition, from individuals to societies, presents a range of challenges to the modeling and simulation community. A common thread through many of these challenges is formulating an authentic representation of time. Many of the issues related to time representation, from the sequencing of cognitive decision processes and information processing, to communication and interaction between agents, to the longer term time scales associated with ideas such as belief revision, remain open research areas throughout the community. The inherent variability between human subjects makes generalization difficult even with data from designed experiments. Discrete event simulation (DES) provides a well-documented alternative to time-step simulation and shows potential for applications across the domain of human behavior representation. This paper provides an overview of a modular discrete event framework for social simulation, along with the social and behavioral theories underlying the currently implemented modules. We discuss the practical challenges presented by time in the representation of human cognition, and provide a case study analysis of the output of the discrete event social simulation.

In this paper we describe an original computational model for solving different types of Distributed Constraint Satisfaction Problems (DCSP). The proposed model is called Controller-Agents for Constraints Solving (CACS). This model is intended to be used which is an emerged field from the integration between two paradigms of different nature: Multi-Agent Systems (MAS) and the Constraint Satisfaction Problem paradigm (CSP) where all constraints are treated in central manner as a black-box. This model allows grouping constraints to form a subset that will be treated together as a local problem inside the controller. Using this model allows also handling non-binary constraints easily and directly so that no translating of constraints into binary ones is needed. This paper presents the implementation outlines of a prototype of DCSP solver, its usage methodology and overview of the CACS application for timetabling problems.

We propose a formal framework that supports a model of agent-based Virtual Organisations (VOs) for service grids and provides an associated operational model for the creation of VOs. The framework is intended to be used for describing different service grid applications based on multiple agents and, as a result, it abstracts away from any realisation choices of the service grid application, the agents involved to support the applications and their interactions. Within the proposed framework VOs are seen as emerging from societies of agents, where agents are abstractly characterised by goals and roles they can play within VOs. In turn, VOs are abstractly characterised by the agents participating in them with specific roles, as well as the workflow of services and corresponding contracts suitable for achieving the goals of the participating agents. We illustrate the proposed framework with an earth observation scenario.