An abstract knowledge based approach to diagnosis and recovery of plan failure in multi-agent systems

Open multi-agent systems (MAS) are decentralised and distributed systems that consist of a large number of loosely coupled autonomous agents. In the absence of centralised control they tend to be difficult to manage, especially in an open environment, which is dynamic, complex, distributed and unpredictable. This dynamism and uncertainty in an open environment gives rise to unexpected plan failures. In this paper we present an abstract knowledge based approach for the diagnosis and recovery of plan action failures. Our approach associates a sentinel agent with each problem solving agent in order to monitor the problem solving agent’s interactions. The proposed approach also requires the problem solving agents to be able to report on the status of a plan’s actions.Once an exception is detected the sentinel agents start an investigation of the suspected agents. The sentinel agents collect information about the status of failed plan abstract actions and knowledge about agents’ mental attitudes regarding any failed plan. The sentinel agent then uses this abstract knowledge and the agents’ mental attitudes, to diagnose the underlying cause of the plan failure. The sentinel agent may ask the problem solving agent to retry their failed plan based on the diagnostic result.     

Models and methods for plan diagnosis

We consider a model-based diagnosis approach to the diagnosis of plans. Here, a plan performed by some agent(s) is considered as a system to be diagnosed. We introduce a simple formal model of plans and plan execution where it is assumed that the execution of a plan can be monitored by making partial observations of plan states. These observed states are used to compare them with states predicted based on (normal) plan execution. Deviations between observed and predicted states can be explained by qualifying some plan steps in the plan as behaving abnormally. A diagnosis is a subset of plan steps qualified as abnormal that can be used to restore the compatibility between the predicted and the observed partial state. Besides minimum and subset minimal diagnoses, we argue that in plan-based diagnosis maximum informative diagnoses should be considered as preferred diagnoses, too. The latter ones are diagnoses that make the strongest predictions with respect to partial states to be observed in the future. We show that in contrast to minimum diagnoses, finding a (subset minimal) maximum informative diagnosis can be achieved in polynomial time. Finally, we show how these diagnoses can be found efficiently if the plan is distributed over a number of agents.     

Multi-agent plan based information gathering

The evolution of the Web has encouraged the development of new Information Gathering techniques. Artificial Intelligence techniques, such as Planning, have also been used for Information Gathering in order to go beyond merely retrieving Web data. Planning has been used traditionally to generate a sequence of actions that specify how information sources should be accessed. In this paper, planning is used mainly for integrating information found in heterogeneous sources. For instance, two different Web sources about flight and train travels, can be represented by two different planning operators, which will be subsequently combined and integrated by a single plan. We have found that a Multi-Agent framework is very appropriate to implement our technique. In order to evaluate our approach empirically, it has been applied to a tourism domain (MAPWEB-ETOURISM), whose purpose is to help a customer to plan his/her trips. In this domain, several specialized Web agents have been used to query travel Web sources, whose results are subsequently integrated by a planning agent to build complete travel solutions. Experimental results show that, by means of integration, more solutions can be found than by using single information sources or even travel meta-searchers. Also, (MAPWEB-ETOURISM) can find new types of solutions by integrating information gathered from heterogeneous Web sources (i.e. flights and trains).     

Industrial deployment of multi-agent technologies: review and selected case studies

This paper reports on industrial deployment of multi-agent systems and agent technology. It provides an overview of several application domains and an in-depth presentation of four specific case studies. The presented applications and deployment domains have been analyzed. The analysis indicates that despite strong industrial involvement in this field, the full potential of the agent technology has not been fully utilized yet and that not all of the developed agent concepts and agent techniques have been completely exploited in industrial practice. In the paper, the key obstacles for wider deployments are listed and potential future challenges are discussed.     

Applications and environments for multi-agent systems

This paper addresses multi agent system (MAS) environments from an application perspective. It presents a structured view on environment-centric MAS applications. This comprises three base configurations, which MAS applications may apply directly or combine into a composite configuration. For each configuration, the paper presents key issues, requirements and opportunities (e.g. time management issues, real-world augmentation opportunities and state snapshot requirements). Thus, the paper delineates what environment technology may implement to serve MAS applications. Sample applications illustrate the configurations. Next, electronic institutions provide an example of an environment technology, addressing norms and laws in an agent society, already achieving some maturity. In comparison, application-domain specific environment technologies still are in embryonic stages.     

Design and implementation of a secure multi-agent marketplace

A multi-agent marketplace, MAGNET (Multi-AGent Negotiation Testbed), is a promising solution for conducting online combinatorial auctions. The trust model of MAGNET is somewhat different from other on-line auction systems since the marketplace, which mediates all communications between agents, acts as a partially trusted third party. We identify the security vulnerabilities of MAGNET and present a solution that overcomes these weaknesses. Our solution makes use of three different existing technologies with standard cryptographic techniques: a publish/subscribe system to provide simple and general messaging, time-release cryptography to provide guaranteed non-disclosure of the bids, and anonymous communication to hide the identity of the bidders until the end of the auction. Using these technologies, we successfully minimize the trust on the market as well as increase the security of the whole system. The protocol that we have developed can be adapted for use by other agent-based auction systems, that use a third party to mediate transactions.     

An integrated trust and reputation model for open multi-agent systems

Trust and reputation are central to effective interactions in open multi-agent systems (MAS) in which agents, that are owned by a variety of stakeholders, continuously enter and leave the system. This openness means existing trust and reputation models cannot readily be used since their performance suffers when there are various (unforseen) changes in the environment. To this end, this paper presents FIRE, a trust and reputation model that integrates a number of information sources to produce a comprehensive assessment of an agent’s likely performance in open systems. Specifically, FIRE incorporates interaction trust, role-based trust, witness reputation, and certified reputation to provide trust metrics in most circumstances. FIRE is empirically evaluated and is shown to help agents gain better utility (by effectively selecting appropriate interaction partners) than our benchmarks in a variety of agent populations. It is also shown that FIRE is able to effectively respond to changes that occur in an agent’s environment.     

Robust homogenization and consensus of nonlinear multi-agent systems

In this paper, we consider consensus of a group of heterogeneous agents with nonlinear dynamics in the presence of system uncertainties. It requires that all agent states reach an agreement which is governed by specified reference dynamics. However, the reference dynamics do not generate a specific reference trajectory for feedback regulation for any agent. For this purpose, the proposed controller integrates two fundamental actions, homogenization and consensus, concurrently. On one hand, it asymptotically regulates each individual (heterogeneous, nonlinear, and uncertain) agent dynamics to the common reference dynamics using a robust homogenization technique; on the other hand, it aligns agent trajectories, asymptotically governed by the common reference dynamics, to consensus through network cooperation. The effectiveness of the controller is verified in the rigorous proof and numerical simulation.     

Event-based consensus of multi-agent systems with general linear models

In this paper, the event-based consensus problem of general linear multi-agent systems is considered. Two sufficient conditions with or without continuous communication between neighboring agents are presented to guarantee the consensus. The advantage of the event-based strategy is the significant decrease of the number of controller updates for cooperative tasks of multi-agent systems involving embedded microprocessors with limited on-board resources. The controller updates of each agent are driven by properly defined events, which depend on the measurement error, the states of its neighboring agents and an arbitrarily small threshold. It is shown that the controller updates for each agent only trigger at its own event time instants. A simulation example is presented to illustrate the theoretical results.     

An evolutionary approach to deception in multi-agent systems

Understanding issues of trust and deception are key to designing robust, reliable multi-agent systems. This paper builds on previous work which examined the use of auctions as a model for exploring the concept of deception in such systems. We have previously described two forms of deceptive behaviour which can occur in a simulated repeated English auction. The first of these types of deception involves sniping or late bidding, which not only allows an agent to conceal its true valuation for an item, but also potentially allows it to win an item for which it may not possess the highest valuation. The second deceptive strategy involves the placing of false bids which are designed to reduce an opponent’s potential profit. In this work we examine the potential shortcomings of those two strategies and investigate whether or not their individual strengths can be combined to produce a successful hybrid deceptive strategy.     

Exception representation and management in open multi-agent systems

One of the major issues in dealing with exceptions in open multi-agent systems (MAS) is lack of uniform representation of exceptions and their shared semantics. In the absence of a uniform framework different business organizations may use different representations for the same exception or may interpret the same exception in different ways. In order to address this issue we apply an ontological approach as a uniform way of representing and interpreting exceptions in cross-organizational settings. This helps agents from different organizations interpret exceptional situations in an unambiguous way and exchange exception related information using standard structures. We believe that an exception ontology along with a domain ontology increases the open MAS reliability and also enhances its fault tolerance capability. The proposed ontology is built using the ontological support provided by the JADE agent framework and exception diagnoses agents are implemented using the JACK™ agent framework.     

Distributed learning and cooperative control for multi-agent systems

This paper presents an algorithm and analysis of distributed learning and cooperative control for a multi-agent system so that a global goal of the overall system can be achieved by locally acting agents. We consider a resource-constrained multi-agent system, in which each agent has limited capabilities in terms of sensing, computation, and communication. The proposed algorithm is executed by each agent independently to estimate an unknown field of interest from noisy measurements and to coordinate multiple agents in a distributed manner to discover peaks of the unknown field. Each mobile agent maintains its own local estimate of the field and updates the estimate using collective measurements from itself and nearby agents. Each agent then moves towards peaks of the field using the gradient of its estimated field while avoiding collision and maintaining communication connectivity. The proposed algorithm is based on a recursive spatial estimation of an unknown field. We show that the closed-loop dynamics of the proposed multi-agent system can be transformed into a form of a stochastic approximation algorithm and prove its convergence using Ljung’s ordinary differential equation (ODE) approach. We also present extensive simulation results supporting our theoretical results.     

Game theoretical applications for multi-agent systems

We consider game-theoretic principles for design of cooperative and competitive (non-cooperative self-interested) multi-agent systems. Using economic concepts of tâtonnement and economic core, we show that cooperative multi-agent systems should be designed in games with dominant strategies that may lead to social dilemmas. Non-cooperative multi-agent systems, on the other hand, should be designed for games with no clear dominant strategies and high degree of problem complexity. Further, for non-cooperative multi-agent systems, the number of learning agents should be carefully managed so that solutions in the economic core can be obtained. We provide experimental results for the design of cooperative and non-cooperative MAS from telecommunication and manufacturing industries.     

A multi-agent legal recommender system

Infonorma is a multi-agent system that provides its users with recommendations of legal normative instruments they might be interested in. The Filter agent of Infonorma classifies normative instruments represented as Semantic Web documents into legal branches and performs content-based similarity analysis. This agent, as well as the entire Infonorma system, was modeled under the guidelines of MAAEM, a software development methodology for multi-agent application engineering. This article describes the Infonorma requirements specification, the architectural design solution for those requirements, the detailed design of the Filter agent and the implementation model of Infonorma, according to the guidelines of the MAAEM methodology.     

Digital blush: towards shame and embarrassment in multi-agent information trading applications

This paper explores the possibility of, and potential for, using a socio-cognitive theory of shame and embarrassment in agent-agent socio-economic interaction. We use this theory to specify an idea of digital blush, i.e. a representation of the state of embarrassment of an agent according to an evaluation of its behaviour by its peers. Through a detailed worked example, we demonstrate how digital blush offers a higher-level, finer-grained control of/over agent behaviour than typically strict, rule-based security mechanisms. We propose digital blush both as a computational device for self-regulation in certain types of multi-agent information trading applications, and, by representing an agents shame and embarrassment through some form of status visualisation, discuss its potential as a socio-technical device for affecting presence, especially in what we refer to as socio-cognitive grids.     

Self-stabilizing defeat status computation: dealing with conflict management in multi-agent systems

The role of argumentation in supporting various forms of interaction among possibly conflicting autonomous agents has been explicitly recognized in the literature. In argumentation, conflict management is carried out by the formal process of defeat status computation. In this paper we consider the generalization of this process to a distributed setting. We show that significant stabilization problems may arise even in relatively simple cases. A fundamental negative result is then proved: no general self-stabilizing algorithm exists for distributed defeat status computation, indicating that self-stabilizing algorithms for this problem can be defined only under specific conditions. Accordingly, we focus on two cases: an algorithm tailored to a specific family of inference graphs, that include only rebutting defeaters, and an algorithm that applies to any inference graph, also including undercutting defeaters, but may provide (cautiously) incorrect results for some nodes. For both algorithms the worst-case round complexity is analyzed and it is proved that no algorithms with lower complexity exist for the same tasks.     

A connection between formation infeasibility and velocity alignment in kinematic multi-agent systems

In this paper, a feedback control strategy that achieves convergence of a multi-agent system to a desired formation configuration is proposed for both the cases of agents with single integrator and nonholonomic unicycle-type kinematics. When inter-agent objectives that specify the desired formation cannot occur simultaneously in the state space the desired formation is infeasible. It is shown that under certain assumptions, formation infeasibility forces the agents’ velocity vectors to a common value at steady state. This provides a connection between formation infeasibility and flocking behavior for the multi-agent system. We finally also obtain an analytic expression of the common velocity vector in the case of formation infeasibility.     

Minimization of the effect of noisy measurements on localization of multi-agent autonomous formations

This paper considers the problem of reduction of self-localization errors in multi-agent autonomous formations when only distance measurements are available to the agents in a globally rigid formation. It is shown that there is a relationship between different selections of anchors, agents with exactly known positions, and the error induced by measurement error on localization solution. This fact is exploited to develop a mechanism to select anchors in order to minimize the effects of inter-agent distance measurement errors on localization solution. Finally, some simulation results are presented to demonstrate the optimal anchor selection for a particular general class of formations, the globally rigid formations.     

Learning in multi-agent systems: a case study of construction claims negotiation

The ability of agents to learn is of growing importance in multi-agent systems. It is considered essential to improve the quality of peer to peer negotiation in these systems. This paper reviews various aspects of agent learning, and presents the particular learning approach—Bayesian learning—adopted in the MASCOT system (multi-agent system for construction claims negotiation). The core objective of the MASCOT system is to facilitate construction claims negotiation among different project participants. Agent learning is an integral part of the negotiation mechanism. The paper demonstrates that the ability to learn greatly enhances agents' negotiation power, and speeds up the rate of convergence between agents. In this case, learning is essential for the success of peer to peer agent negotiation systems.