Coordinating Agents in Organizations Using Social Commitments

One of the main challenges faced by the multi-agent community is to ensure the coordination of autonomous agents in open heterogeneous multi-agent systems. In order to coordinate their behaviour, the agents should be able to interact with each other. Social commitments have been used in recent years as an answer to the challenges of enabling heterogeneous agents to communicate and interact successfully. However, coordinating agents only by means of interaction models is difficult in open multi-agent systems, where possibly malevolent agents can enter at any time and violate the interaction rules. Agent organizations, institutions and normative systems have been used to control the way agents interact and behave. In this paper we try to bring together the two models of coordinating agents: commitment-based interaction and organizations. To this aim we describe how one can use social commitments to represent the expected behaviour of an agent playing a role in an organization. We thus make a first step towards a unified model of coordination in multi-agent systems: a definition of the expected behaviour of an agent using social commitments in both organizational and non-organizational contexts.     

Specification and testing of autonomous agents in e‐commerce systems

This paper presents a generic formal framework to specify and test autonomous e‐commerce agents. First, the formalism to represent the behaviour of agents is introduced. The corresponding machinery to define how implementations can be tested follows. Two testing approaches are considered. The first of them, which can be called active, is based on stimulating the implementation under test (IUT) with a test. The peculiarity is that tests will be defined as a special case of autonomous e‐commerce agent. The second approach, which can be called passive, consists of observing the behaviour of the tested agent in an environment containing other agents. As a case study the framework is applied to the e‐commerce system Kasbah. Copyright © 2005 John Wiley & Sons, Ltd.     

ADK: An Agent Development Kit Based on a Formal Design Model for Multi-Agent Systems

The advent of multi-agent systems has brought us opportunities for the development of complex software that will serve as the infrastructure for advanced distributed applications. During the past decade, there have been many agent architectures proposed for implementing agent-based systems, and also a few efforts to formally specify agent behaviors. However, research on narrowing the gap between agent formal models and agent implementation is rare. In this paper, we propose a model-based approach to designing and implementing intelligent agents for multi-agent systems (MAS). Instead of using formal methods for the purpose of specifying agent behavior, we bring formal methods into the design phase of the agent development life cycle. Specifically, we use the formalism called agent-oriented G-net model, which is based on the G-net formalism (a type of high-level Petri net), to serve as the high-level design for intelligent agents. Based on the high-level design, we further derived the agent architecture and the detailed design for agent implementation. To demonstrate the feasibility of our approach, we developed the toolkit called ADK (Agent Development Kit) that supports rapid development of intelligent agents for multi-agent systems and we discuss the role of inheritance in agent-oriented development. As a potential solution for automated software development, we summarize the procedure to generate a model-based design of application-specific agents. Finally, to illustrate an application built on ADK, we present an air-ticket trading example.     

A formal framework for multi-agent systems analysis and design

Agent based computing is generally intended for modeling and implementation of distributed complex problems. Despite the existence of many applications, the problem of rational engineering of multi-agent systems remains complex and difficult. The purpose of this paper can be summarized within two claims. First, we aim at providing an approach that gives some guidelines for specifying and designing multi-agent systems. Secondly, we focus on the formalisms as a language for describing the models produced in each development process phases. These seem to be straightforward, while the development of multi-agent systems is still done, in most cases, without using methods and formal modeling such as those generally used in object oriented software. We illustrate this approach by specifying an example based upon a specific agent architecture.     

Enabling run-time composition and support for heterogeneous pervasive multi-agent systems

User needs-driven and computer-supported development of pervasive heterogeneous and dynamic multi-agent systems remains a great challenge for agent research community. This paper presents an innovative approach to composing, validating and supporting multi-agent systems at run-time. Multi-agent systems (MASs) can and should be assembled quasi-automatically and dynamically based on high-level user specifications which are transformed into a shared and common goal–mission. Dynamically generating agents could also be supported as a pervasive service. Heterogeneity of MASs refers to diverse functionality and constituency of the system which include mobile as well as host associated software agents. This paper proposes and demonstrates on-demand and just-in-time agent composition approach which is combined with run-time support for MASs. Run-time support is based on mission cost-efficiency and shared objectives which enable termination, generation, injection and replacement of software agents as the mission evolves at run-time. We present the formal underpinning of our approach and describe the prototype tool – called eHermes, which has been implemented using available agent platforms. Analysis and results of evaluating eHermes are presented and discussed.     

Learning collaboration strategies for committees of learning agents

A main issue in cooperation in multi-agent systems is how an agent decides in which situations is better to cooperate with other agents, and with which agents does the agent cooperate. Specifically in this paper we focus on multi-agent systems composed of learning agents, where the goal of the agents is to achieve a high accuracy on predicting the correct solution of the problems they encounter. For that purpose, when encountering a new problem each agent has to decide whether to solve it individually or to ask other agents for collaboration. We will see that learning agents can collaborate forming committees in order to improve performance. Moreover, in this paper we will present a proactive learning approach that will allow the agents to learn when to convene a committee and with which agents to invite to join the committee. Our experiments show that learning results in smaller committees while maintaining (and sometimes improving) the problem solving accuracy than forming committees composed of all agents.     

Using Domain-Independent Exception Handling Services to Enable Robust Open Multi-Agent Systems: The Case of Agent Death

This paper addresses a simple but critical question: how can we create robust multi-agent systems out of the often unreliable agents and infrastructures we can expect to find in open systems contexts? We propose an approach to this problem based on distinct exception handling (EH) services that enact coordination protocol-specific but domain-independent strategies to monitor agent systems for problems (‘exceptions’) and intervene when necessary to avoid or resolve them. The value of this approach is demonstrated for the ‘agent death’ exception in the Contract Net protocol; we show through simulation that the EH service approach provides substantially improved performance compared to existing approaches in a way that is appropriate for open multi-agent systems.     

Gossip-Based Self-Organising Agent Societies and the Impact of False Gossip

The objective of this work is to demonstrate how cooperative sharers and uncooperative free riders can be placed in different groups of an electronic society in a decentralised manner. We have simulated an agent-based open and decentralised P2P system which self-organises itself into different groups to avoid cooperative sharers being exploited by uncooperative free riders. This approach encourages sharers to move to better groups and restricts free riders into those groups of sharers without needing centralised control. Our approach is suitable for current P2P systems that are open and distributed. Gossip is used as a social mechanism for information sharing which facilitates the formation of groups. Using multi-agent based simulations we demonstrate how the adaptive behaviour of agents lead to self-organisation. We have tested with varying the gossip level and checked its impact in the system’s behaviour. We have also investigated the impact of false gossip in this system where gossip is the medium for information sharing which leads to self-organisation.     

一种基于社会承诺的Agent组织模型OMSC

多Agent领域所面临的一个重大的挑战是解决开放异质的多Agent系统中自治Agent间的协调问题。多Agent为了协调它们之间的活动,需要进行交互。社会承诺作为一种通信和交互机制,为自治的多Agent提供了一种协调的途径。然而,仅靠交互难以实现多Agent间的协调。Agent组织作为一种协调模型可以有效地控制多Agent间的交互与合作。论文将社会承诺和Agent组织两种协调机制相结合,提出一种基于社会承诺的Agent组织模型OMSC,分析了Agent如何用社会承诺进行推理以及基于社会承诺的多Agent系统并给出了一个实例,为多Agent间的协调提供了一种新的方法。     

Formal verification of a pervasive messaging system

As ubiquitous computing becomes a reality, its applications are increasingly being used in business-critical, mission-critical and even in safety-critical, areas. Such systems must demonstrate an assured level of correctness. One approach to the exhaustive analysis of the behaviour of systems is formal verification, whereby each important requirement is logically assessed against all possible system behaviours. While formal verification is often used in safety analysis, it has rarely been used in the analysis of deployed pervasive applications. Without such formality it is difficult to establish that the system will exhibit the correct behaviours in response to its inputs and environment. In this paper, we show how model-checking techniques can be applied to analyse the probabilistic behaviour of pervasive systems. As a case study we apply this technique to an existing pervasive message-forwarding system, Scatterbox. Scatterbox incorporates many typical characteristics of pervasive systems, such as dependence on sensor reliability and dependence on context. We assess the dynamic temporal behaviour of the system, including the analysis of probabilistic elements, allowing us to verify formal requirements even in the presence of uncertainty in sensors. We also draw some tentative conclusions concerning the use of formal verification for pervasive computing in general.     

A first-order coalition logic for BDI-agents

Coalition logic (CL) enables us to model the strategic abilities and specify what a group of agents can achieve whatever the other agents do. However, some rational mental attitudes of the agents are beyond the scope of CL such as the prestigious beliefs, desires and intentions (BDI) which is an interesting and useful epistemic notion and has spawned substantial amount of studies in multi-agent systems. In this paper, we introduce a first-order coalition BDI (FCBDI) logic for multi-agent systems, which provides a semantic glue that allows the formal embedding and interaction of BDI, coalition and temporal operators in a first-order language. We further introduce a semantic model based on the interpreted system model and present an axiomatic system that is proved sound and complete with respect to the semantics. Finally, it is shown that the computational complexity of its model checking in finite structures is PSPACE-complete.     

Emergence and refinement

Emergent behaviour—system behaviour not determined by the behaviours of system components when considered in isolation—is commonplace in multi-agent systems, particularly when agents adapt to environmental change. This article considers the manner in which Formal Methods may be used to authenticate the trustworthiness of such systems. Techniques are considered for capturing emergent behaviour in the system specification and then the incremental refinement method is applied to justify design decisions embodied in an implementation. To demonstrate the approach, one and two-dimensional cellular automata are studied. In particular an incremental refinement of the ‘glider’ in Conway’s Game of Life is given from its specification.     

Specifying distributed multi-agent systems in chemical reaction metaphor

This paper presents an application of Chemical Reaction Metaphor (CRM) in distributed multi-agent systems (MAS). The suitability of using CRM to model multi-agent systems is justified by CRM's capacity in specifying dynamic features of multi-agent systems. A case study in an agent-based e-learning system (course material updating) demonstrates how the CRM based language, Gamma, can be used to specify the architectures of multi-agent systems. The effectiveness of specifying multi-agent systems in CRM from the view point of software engineering is further justified by introducing a transformational method for implementing the specified multi-agent systems. A computation model with a tree-structured architecture is proposed to base the design of the specified multi-agent system during the implementation phase. A module language based on the computation model is introduced as an intermediate language to facilitate the translation of the specification of multi-agent systems. The multicast networking technology pragmatizes the implementation of communications and synchronization among distributed agents. The paper also discusses the feasibility of implementing an automatic translation from the Gamma specification to a program in the module language. This work is supported by University of Houston-Downtown Organized Research Committee.     

Automated Game Analysis via Probabilistic Model Checking: a case study

It has been recognised for some time that there are close links between the various logics developed for the analysis of multi-agent systems and the many game-theoretic models developed for the same purpose. In this paper, we contribute to this burgeoning body of work by showing how a probabilistic model checking tool can be used for the automated analysis of game-like multi-agent systems in which both agents and environments can act with uncertainty. Specifically, we show how a variation of the well-known alternating offers negotiation protocol of Rubinstein can be encoded as a model for the PRISM model checker and its behaviour analysed through automatic verification of probabilistic CTL's properties.     

Semantical considerations on intention dynamics for BDI agents

The BDI paradigm is a powerful means for constructing intelligent agents in terms of their beliefs, desires, and intentions. For this paradigm to bear its full potential, it must incorporate considerations from rationality. This paper develops a set of postulates for intelligent agents who deliberate about their intentions and actions. However, even simple postulates can lead to paradoxical results when formalized naively. We propose an approach based on temporal possibility and action that avoids those problems. This approach incorporates a formal model based on branching time in which a probabilistic analysis of choice can be captured. In this manner, the intuitions of the BDI paradigm can be reconciled with those of rational agency.     

Competing agents in agent-mediated institutions

Social processes and agent interaction always take place in a specific context. A school of thought in social studies analyses them in the framework of institutions. We present in this paper the notion ofagentmediated institutions and show how it is relevant for multi-agent systems (MAS) in general and, more specifically, for MAS that include human agents and software agents involved in socioeconomic interactions. We show how the social interactions of human and software agents taking place in the Cohabited Mixed-Reality Information Spaces (COMRIS) project can be described as such an institution, the Conference Centre institution.     

Modelling a Society of Simple Agents: From Conceptual Specification to Experimentation

Much research concerning the design of multi-agent systems (at a conceptual level) addresses complex agents that exhibit complex interaction patterns. Due to this complexity, it is difficult to perform rigorous experimentation. On the other hand, systematic experimental work regarding behaviour of societies of more simple agents, while reporting valuable results, often lacks conceptual specification of the system under consideration. In this paper, the compositional multi-agent modelling framework DESIRE is not only successfully used to develop a conceptual specification of the simple agents discussed by A. Cesta, M. Miceli and P. Rizzo (Lecture Notes in Artificial Intelligence, vol. 1038, Springer-Verlag: Berlin, pp. 128–138, 1996), but also to simulate the behaviour in a dynamical environment. In the DESIRE framework, a conceptual specification, which provides a high-level view of an agent, has enough detail for automatic prototype generation. The prototype implementation of the con-ceptual specification of the simple agents has been used to replicate, and extend, one of the experiments reported by Cesta et al.     

A general criterion and an algorithmic framework for learning in multi-agent systems

We offer a new formal criterion for agent-centric learning in multi-agent systems, that is, learning that maximizes one’s rewards in the presence of other agents who might also be learning (using the same or other learning algorithms). This new criterion takes in as a parameter the class of opponents. We then provide a modular approach for achieving effective agent-centric learning; the approach consists of a number of basic algorithmic building blocks, which can be instantiated and composed differently depending on the environment setting (for example, 2- versus n-player games) as well as the target class of opponents. We then provide several specific instances of the approach: an algorithm for stationary opponents, and two algorithms for adaptive opponents with bounded memory, one algorithm for the n-player case and another optimized for the 2-player case. We prove our algorithms correct with respect to the formal criterion, and furthermore show the algorithms to be experimentally effective via comprehensive computer testing.