A multiagent network for peer norm enforcement

In a multiagent system where norms are used to regulate the actions agents ought to execute, some agents may decide not to abide by the norms if this can benefit them. Norm enforcement mechanisms are designed to counteract these benefits and thus the motives for not abiding by the norms. In this work we propose a distributed mechanism through which agents in the multiagent system that do not abide by the norms can be ostracised by their peers. An ostracised agent cannot interact anymore and looses all benefits from future interactions. We describe a model for multiagent systems structured as networks of agents, and a behavioural model for the agents in such systems. Furthermore, we provide analytical results which show that there exists an upper bound to the number of potential norm violations when all the agents exhibit certain behaviours. We also provide experimental results showing that both stricter enforcement behaviours and larger percentage of agents exhibiting these behaviours reduce the number of norm violations, and that the network topology influences the number of norm violations. These experiments have been executed under varying scenarios with different values for the number of agents, percentage of enforcers, percentage of violators, network topology, and agent behaviours. Finally, we give examples of applications where the enforcement techniques we provide could be used.     

Agent communication and artificial institutions

In this paper we propose an application-independent model for the definition of artificial institutions that can be used to define open multi-agent systems. Such a model of institutional reality makes us able also to define an objective and external semantics of a commitment-based Agent Communication Language (ACL). In particular we propose to regard an ACL as a set of conventions to act on a fragment of institutional reality, defined in the context of an artificial institution. Another contribution of the work presented in this paper is an operational definition of norms, a crucial component of artificial institutions. In fact in open systems interacting agents might not conform to the specifications. We regard norms as event-driven rules that when are fired by events happening in the system create or cancel a set of commitments. An interesting aspect of our proposal is that both the definition of the ACL and the definition of norms are based on the same notion of commitment. Therefore an agent capable of reasoning on commitments can reason on the semantics of communicative acts and on the system of norms.     

Identifying prohibition norms in agent societies

In normative multi-agent systems, the question of “how an agent identifies norms in an open agent society” has not received much attention. This paper aims at addressing this question. To this end, this paper proposes an architecture for norm identification for an agent. The architecture is based on observation of interactions between agents. This architecture enables an autonomous agent to identify prohibition norms in a society using the prohibition norm identification (PNI) algorithm. The PNI algorithm uses association rule mining, a data mining approach to identify sequences of events as candidate norms. When a norm changes, an agent using our architecture will be able to modify the norm and also remove a norm if it does not hold in the society. Using simulations of a park scenario we demonstrate how an agent makes use of the norm identification framework to identify prohibition norms.     

GoCo: planning expressive commitment protocols

This article addresses the challenge of planning coordinated activities for a set of autonomous agents, who coordinate according to social commitments among themselves. We develop a multi-agent plan in the form of a commitment protocol that allows the agents to coordinate in a flexible manner, retaining their autonomy in terms of the goals they adopt so long as their actions adhere to the commitments they have made. We consider an expressive first-order setting with probabilistic uncertainty over action outcomes. We contribute the first practical means to derive protocol enactments which maximise expected utility from the point of view of one agent. Our work makes two main contributions. First, we show how Hierarchical Task Network planning can be used to enact a previous semantics for commitment and goal alignment, and we extend that semantics in order to enact first-order commitment protocols. Second, supposing a cooperative setting, we introduce uncertainty in order to capture the reality that an agent does not know for certain that its partners will successfully act on their part of the commitment protocol. Altogether, we employ hierarchical planning techniques to check whether a commitment protocol can be enacted efficiently, and generate protocol enactments under a variety of conditions. The resulting protocol enactments can be optimised either for the expected reward or the probability of a successful execution of the protocol. We illustrate our approach on a real-world healthcare scenario.     

Constraint satisfaction as a tool for modeling and checking feasibility of multiagent commitments

Commitments are being used to specify interactions among autonomous agents in multiagent systems. Various formalizations of commitments have shown their strength in representing and reasoning on multiagent interactions. These formalizations mostly study commitment lifecycles, emphasizing fulfillment of a single commitment. However, when multiple commitments coexist, fulfillment of one commitment may have an effect on the lifecycle of other commitments. Since agents generally participate in more than one commitment at a time, it is important for an agent to determine whether it can honor its commitments. These commitments may be the existing commitments of the agent as well as any prospective commitments that the agent plans to participate in. To address this, we develop the concept of commitment feasibility, i.e., whether it is possible for an agent to fulfill a set of commitments all together. To achieve this we generalize the fulfillment of a single commitment to the feasibility of a set of commitments. We then develop a solid method to determine commitment feasibility. Our method is based on the transformation of feasibility into a constraint satisfaction problem and use of constraint satisfaction techniques to come up with a conclusion. We show soundness and completeness of our method and illustrate its applicability over realistic cases.     

A coherence maximisation process for solving normative inconsistencies

Norms can be used in multi-agent systems for defining patterns of behaviour in terms of permissions, prohibitions and obligations that are addressed to agents playing a specific role. Agents may play different roles during their execution and they may even play different roles simultaneously. As a consequence, agents may be affected by inconsistent norms; e.g., an agent may be simultaneously obliged and forbidden to reach a given state of affairs. Dealing with this type of inconsistency is one of the main challenges of normative reasoning. Existing approaches tackle this problem by using a static and predefined order that determines which norm should prevail in the case where two norms are inconsistent. One main drawback of these proposals is that they allow only pairwise comparison of norms; it is not clear how agents may use the predefined order to select a subset of norms to abide by from a set of norms containing multiple inconsistencies. Furthermore, in dynamic and non-deterministic environments it can be difficult or even impossible to specify an order that resolves inconsistencies satisfactorily in all potential situations. In response to these two problems, we propose a mechanism with which an agent can dynamically compute a preference order over subsets of its competing norms by considering the coherence of its cognitive and normative elements. Our approach allows flexible resolution of normative inconsistencies, tailored to the current circumstances of the agent. Moreover, our solution can be used to determine norm prevalence among a set of norms containing multiple inconsistencies.     

Specification and Verification of Agent Interaction using Social Integrity Constraints

In this paper we propose a logic-based social approach to the specification and verification of agent interaction. We firstly introduce integrity constraints about social acts (called Social Integrity Constraints) as a formalism to express interaction protocols and to give a social semantics to the behavior of agents, focusing on communicative acts. Then, we discuss several possible kinds of verification of agent interaction, and we show how social integrity constraints can be used to verify some properties in this respect. We focus our attention on static verification of compliance of agent specifications to interaction protocols, and on run-time verification, based on agents' observable behavior. We adopt as a running example the NetBill security transaction protocol for the selling and delivery of information goods.     

Consensus problems in networks of agents with double-integrator dynamics and time-varying delays

In this article, we consider consensus problems in networks of agents with double-integrator dynamics and non-uniform time-varying delays. The agent dynamics is adopted as a typical point mass model based on Newton's law. Without assuming that the weighting factors in the information update schemes are non-negative, we propose two protocols such that both the state and the velocity of agents achieve consensus. An equivalent reduced-order system is introduced to analyse the convergence of the protocols. Some necessary and (or) sufficient conditions for consensus are established in terms of linear matrix inequalities. Simulation results are provided that demonstrate the effectiveness of our theoretical results.     

MaNEA: A distributed architecture for enforcing norms in open MAS

Norms have been promoted as a coordination mechanism for controlling agent behaviours in open MAS. Thus, agent platforms must provide normative support, allowing both norm-aware and non-norm-aware agents to take part in MAS that are controlled by norms. In this paper, the most relevant proposals on the definition of norm enforcement mechanisms are analyzed. These proposals present several drawbacks that make them unsuitable for open MAS. In response to these problems, this paper describes a new Norm-Enforcing Architecture aimed at controlling norms in open MAS. Specifically, this architecture supports the creation and deletion of norms on-line as well as the dynamic activation and expiration of instances. Finally, it can dynamically adapt to different scale MAS. The efficiency of this architecture has been experimentally evaluated and the results are shown in this paper.     

A Logical Model for Agent Communication Languages

The current ACL proposals show some shortcomings with respect to the definition of their semantics. Our paper aims at tackling those issues by defining an ACL semantics as a specification of the analytical effects of agent communicative acts. We analyze agent communication in terms of concepts taken from Speech Act Theory, as several researchers have already done, but move away from the mainstream view of artificial agent research, as we define communicative acts in terms of changes at the level of social relationship between agents. We take commitment to be a primitive concept underlying the social dimension of multiagent systems, and define a basic artificial institution whose aim is to provide agents with the means to affect the commitment network that binds them to each other.     

Dual Norms and Image Decomposition Models

Following a recent work by Y. Meyer, decomposition models into a geometrical component and a textured component have recently been proposed in image processing. In such approaches, negative Sobolev norms have seemed to be useful to modelize oscillating patterns. In this paper, we compare the properties of various norms that are dual of Sobolev or Besov norms. We then propose a decomposition model which splits an image into three components: a first one containing the structure of the image, a second one the texture of the image, and a third one the noise. Our decomposition model relies on the use of three different semi-norms: the total variation for the geometrical component, a negative Sobolev norm for the texture, and a negative Besov norm for the noise. We illustrate our study with numerical examples.     

The cognitive legacy of norm simulation

The comprehension of norms in complex social systems is one of the most active fields of research in agent-based modelling. This is faced with the challenge to comprehend the recursive interaction between inter- and intra-agent processes. In this article, a comparative analysis of selected cases of normative agent architectures will be given based on a review of theories of norms in the social sciences. This allows to identify the prerequisites for a representation of the cognitive processes of norm recognition. As yet, there is no unequivocal concept for the design of normative agents. Different approaches are compared along the line of different theoretical accounts.     

A Logical Analysis of the Relationship between Commitment and Obligation

In this paper, we analyze the relationship between commitment and obligation from a logical viewpoint. The principle of commitment implying obligation is proven in a specific logic of action preference which is a generalization of Meyer's dynamic deontic logic. In the proposed formalism, an agent's commitment to goals is considered as a special kind of action which can change one's deontic preference andone's obligation to take some action is based on the preference and the effects of the action. In this logic, it is shown that an agent has the obligation to take any action which is necessary for achieving as many committed goals as possible. The semantics of our logic is based on the possible world models for the dynamic logic of actions. A binary preference relation between possible worlds is associated with the model. Then the preference between actions are determined by comparing that of their consequences. According to the semantics, while the preference will influence the agent's choice of action, commitment is a kind of action that will change the agent's preference. Thus we can show how obligations arise from commitments via updating of deontic preference. The integrated semantics make it possible to express and reason about the mutual relationship among these mental attitudes in a common logic. This revised version was published online in August 2006 with corrections to the Cover Date.     

基于描述任务逻辑的群体组织协同关系模型

群体组织模型是深入研究群体协同行为的基础,而现有的组织模型大多集中在对Agent组织的结构或个体低层指令级的交互上,不能描述组织高层的动态任务交互。提出一个新的群体组织协同关系模型GRNA。该模型包含两个子模型:认知模型和交互模型。认知模型构建于领域本体之上,为GRNA模型提供准确的术语定义;交互模型则基于描述任务逻辑理论,反映了群体的任务协同语义。实例分析表明,GRNA支持对群体规范和能力的描述,提供了组织任务可完成性的可判定的推理服务,能够描述组织的高层任务交互语义。     

Norm驱动的网格工作流状态机模型

动态的网格环境赋予了网格工作流新的特征。从而进一步增加了工作流程的不确定性和复杂性．提出了Norm驱动的网格工作流状态机模型——GridWSM,利用Norm丰富的语义表达能力和适于描述复杂系统的特征来描述网格工作流系统中任务的动态调度,并利用其推理功能来完善Norm描述、检验Norm的语义冲突,不仅确保了Norm描述的完备性,而且反映了工作流程的实时变化,为系统仿真提供了理论基础．模型的原型系统NormTools验证了网格排序流程的Norm描述,检查出所有的错误．     

Time-bound negotiation framework for electronic commerce agents

For efficient and informative coordination of agents especially in electronic commerce environment, a time-bound agent negotiation framework is proposed utilizing a time-based commitment scheme. By attaching commitment duration to agent messages, the traditional contract net protocol is extended to a time-bound negotiation framework (TBNF). The proposed negotiation framework has a new message type which allows for parties to agree upon the extension of a commitment duration, and a novel commitment concept in the form of negative commitment. The semantics of the messages with the commitment duration are interpreted, and then the three typical negotiation protocols are formally defined and compared — nothing-guaranteed protocol, acceptance-guaranteed protocol, and finite-time guarantee protocol — which can be incorporated into TBNF. The TBNF should provide a background for efficient and effective electronic commerce negotiation while accommodating each agent's adaptive negotiation strategy.     

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

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

Organisational adaptation of multi-agent systems in a peer-to-peer scenario

Organisations in multi-agent systems (MAS) have proven to be successful in regulating agent societies. Nevertheless, changes in agents’ behaviour or in the dynamics of the environment may lead to a poor fulfilment of the system’s purposes, and so the entire organisation needs to be adapted. In this paper we focus on endowing the organisation with adaptation capabilities, instead of expecting agents to be capable of adapting the organisation by themselves. We regard this organisational adaptation as an assisting service provided by what we call the Assistance Layer. Our generic Two Level Assisted MAS Architecture (2-LAMA) incorporates such a layer. We empirically evaluate this approach by means of an agent-based simulator we have developed for the P2P sharing network domain. This simulator implements 2-LAMA architecture and supports the comparison between different adaptation methods, as well as, with the standard BitTorrent protocol. In particular, we present two alternatives to perform norm adaptation and one method to adapt agents’ relationships. The results show improved performance and demonstrate that the cost of introducing an additional layer in charge of the system’s adaptation is lower than its benefits.     

Coordination Tools for MAS Development and Deployment

One of the most critical issues in the engineering of multi-agent systems (MAS) is the inadequacy of the available tools for MAS development and deployment. As we assume interaction as a first-class issue in MAS, tools are particularly required to monitor and debug inter-agents aspects, such as interaction protocols, coordination policies, social norms, and environment constraints. Since we claim that the definition of such tools is a basic research issue, in this paper we aim to identify the main requirements for development and deployment tools within an effective agent infrastructure. Focusing on agent interaction aspects, we take tuple-based coordination infrastructures--in particular the TuCSoN technology and tools--as our reference, and discuss the role of tools in a simple case study: the development and deployment of a well-known agent interaction protocol, the Contract Net.     

A Geometric Semantics for Dialogue Game Protocols for Autonomous Agent Interactions

Formal dialogue games studied by philosophers since the time of Aristotle have recently found application in Artificial Intelligence as the basis for protocols for interactions between autonomous software agents. For instance, game protocols have been proposed for agent dialogues involving team formation, persuasion, negotiation and deliberation. There is yet, however, no formal, mathematical theory of dialogue game protocols with which to compare two protocols or to study their formal properties. In this paper,¹ we present preliminary work towards such a theory, in which we develop a geometric semantics for these protocols and, with it, define a notion of equivalence between two protocols. We then demonstrate an algebraic property of protocol equivalence, and use this to show the non-equivalence of two similar generic protocols. We also explore the relationship between finite and infinite dialogues, motivated by the Ehrenfeucht-Fraïssé games of model theory. Our results have implications for the design and evaluation of agent dialogue-game protocols.