This paper is a contribution to the formalisation of Thagard’s coherence theory. The term coherence is defined as the quality or the state of cohering, especially a logical, orderly, and aesthetically consistent relationship of parts. A coherent set is interdependent such that every element in it contributes to the coherence. We take Thagard’s proposal of a coherence set as that of maximising satisfaction of constraints between elements and explore its use in normative multiagent systems. In particular, we interpret coherence maximisation (...) as a decision-making criterion for norm adoption. We first provide a general coherence framework with the necessary computing tools. Later we introduce a proof-theoretic characterisation of a particular type of coherence, namely the deductive coherence based on Thagard’s principles, and derive a mechanism to compute coherence values between elements in a deductive coherence graph. Our use of graded logic helps us to incorporate reasoning under uncertainty, which is more realistic in the context of multiagent systems. We then conduct a case study where agents deliberate about norm adoption in a multiagent system where there is competition for a common resource. We show how a coherence-maximising agent decides to violate a norm guided by its coherence. (shrink)

We define a multi-modal version of Computation Tree Logic (CTL) by extending the language with path quantifiers $E^\delta $ and $E^\delta $ where δ denotes one of finitely many dimensions, interpreted over Kripke structures with one total relation for each dimension. As expected, the logic is axiomatised by taking a copy of a CTL axiomatisation for each dimension. Completeness is proved by employing the completeness result for CTL to obtain a model along each dimension in turn. We also show that (...) the logic is decidable and that its satisfiability problem is no harder than the corresponding problem for CTL. We then demonstrate how Normative Systems can be conceived as a natural interpretation of such a multi-dimensional CTL logic. (shrink)

We define a multi-modal version of Computation Tree Logic (ctl) by extending the language with path quantifiers E δ and A δ where δ denotes one of finitely many dimensions, interpreted over Kripke structures with one total relation for each dimension. As expected, the logic is axiomatised by taking a copy of a ctl axiomatisation for each dimension. Completeness is proved by employing the completeness result for ctl to obtain a model along each dimension in turn. We also show that (...) the logic is decidable and that its satisfiability problem is no harder than the corresponding problem for ctl. We then demonstrate how Normative Systems can be conceived as a natural interpretation of such a multi-dimensional ctl logic. (shrink)

Multi-agent systems where the agents are developed by parties with competing interests, and where there is no access to an agent’s internal state, are often classified as ‘open’. The members of such systems may inadvertently fail to, or even deliberately choose not to, conform to the system specification. Consequently, it is necessary to specify the normative relations that may exist between the members, such as permission, obligation, and institutional power. We present a framework being developed for executable specification of open (...) multi-agent systems. We adopt a bird’s eye view of these systems, as opposed to an agent’s perspective whereby it reasons about how it should act. This paper is devoted to the presentation of various examples from the NetBill protocol formalised in terms of institutional power, permission and obligation. We express the system specification in the Event Calculus and execute the specification by means of a logic programming implementation. We also give several example formalisations of sanctions for dealing with violations of permissions and obligations. We distinguish between an open multi-agent system and the procedure by which an agent enters and leaves the system. We present examples from the specification of a role-management protocol for NetBill, and demonstrate the interplay between such a protocol and the corresponding multi-agent system. (shrink)

To adequately deal with unpredictable and dynamic environments, normative frameworks typically deployed in mechanisms for modifying the norms at runtime are crucial. We present the syntax and operational semantics of programming constructs to facilitate runtime norm modification, allowing a programmer to specify when and how the norms may be changed by external agents or by the normative mechanism. The norms take on the form of conditional obligations and prohibitions, instantiating obligations and prohibitions. We present rule-based constructs for runtime modification of (...) the norms and their instances, and a mechanism for automatically updating the instances when their underlying norms change. Moreover, we investigate a mechanism for avoiding norm conflicts. (shrink)

Within artificial intelligence and the philosophy of mind,there is considerable disagreement over the relationship between anagent's body and its capacity for intelligent behavior. Some treatthe body as peripheral and tangential to intelligence; others arguethat embodiment and intelligence are inextricably linked. Softwareagents–-computer programs that interact with software environmentssuch as the Internet–-provide an ideal context in which to studythis tension. I develop a computational framework for analyzingembodiment. The framework generalizes the notion of a body beyondmerely having a physical presence. My analysis sheds (...) light oncertain claims made about the relevance of the body to intelligence,as well as on embodiment in software worlds. (shrink)

In this paper we present a new model for the requirements analysis of a system. This is a new model based on the multiagent systems paradigm with the aim to support the requirements analysis phase of systems design. This model offers a structured approach to requirements analysis, based on conceptual models defined following a visual modeling language, called dependence networks. The main elements of this visual language are the agents with their goals, capabilities and facts, similarly to the TROPOS methodology (...) [11]. The normative component is present both in the ontology and in the conceptual metamodel, associating agents to roles they play inside the system and a set of goals, capabilities and facts proper of these roles. This improvement allows to define different types of dependence networks, called dynamic dependence networks and conditional dependence networks, representing the different phases of the requirements analysis of the system. This paper presents a requirements analysis model based on normative concepts such as obligation and institution. Our model is a model of semiformal specification featured by an ontology, a meta-model, a graphical notation and a set of constraints. Our model, moreover, allows the definition of the notion of coalition for the different kinds of network. (shrink)

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. (shrink)

Since it was first proposed by Moses, Shoham, and Tennenholtz, the social laws paradigm has proved to be one of the most compelling approaches to the offline coordination of multiagent systems. In this paper, we make four key contributions to the theory and practice of social laws in multiagent systems. First, we show that the Alternating-time Temporal Logic (atl) of Alur, Henzinger, and Kupferman provides an elegant and powerful framework within which to express and understand social laws for multiagent systems. (...) Second, we show that the effectiveness, feasibility, and synthesis problems for social laws may naturally be framed as atl model checking problems, and that as a consequence, existing atl model checkers may be applied to these problems. Third, we show that the complexity of the feasibility problem in our framework is no more complex in the general case than that of the corresponding problem in the Shoham–Tennenholtz framework (it is np-complete). Finally, we show how our basic framework can easily be extended to permit social laws in which constraints on the legality or otherwise of some action may be explicitly required. We illustrate the concepts and techniques developed by means of a running example. (shrink)

The analysis of how social conventions emerge and become established is rightly viewed as a significant study of great relevance to models of legal and social systems. Such conventions, however, do not operate in a monotonic fashion, i.e. the fact that a convention is recognised and complied with at some instant is no guarantee it will continue to be so indefinitely. In total rules and protocols may evolve, with or without the consent of individual members of the society, even to (...) the extent that some cease to be observed or effective. In this paper we examine a framework for examining such changes in behavioural conventions that uses a proposed “taxonomy of social conventions” as the basis of a qualitative model deriving from value-based argument systems. (shrink)

A single global authority is not sufficient to regulate heterogenous agents in multiagent systems based on distributed architectures, due to idiosyncratic local situations and to the need to regulate new issues as soon as they arise. On the one hand institutions should be structured as normative systems with a hierarchy of authorities able to cope with the dynamics of local situations, but on the other hand higher authorities should be able to delimit the autonomy of lower authorities to issue valid (...) norms. In this paper, we study the interplay of obligations and strong permissions in the context of hierarchies of authorities using input/output logic, because its explicit norm base facilitates reasoning about norm base maintenance, and it covers a variety of conditional obligations and permissions. We combine the logic with constraints, priorities and hierarchies of authorities. In this setting, we observe that Makinson and van der Torre’s notion of prohibition immunity for permissions is no longer sufficient, and we introduce a new notion of permission as exception and a new distinction between static and dynamic norms. We show how strong permissions can dynamically change an institution by adding exceptions to obligations, provide an explicit representation of what is permitted to the subjects of the normative system and allow higher level authorities to limit the power of lower level authorities to change the normative system. (shrink)