=Paper=
{{Paper
|id=None
|storemode=property
|title=Normative Monitoring: Semantics and Implementation
|pdfUrl=https://ceur-ws.org/Vol-627/coin_1.pdf
|volume=Vol-627
|dblpUrl=https://dblp.org/rec/conf/mallow/Alvarez-NapagaoAVD10
}}
==Normative Monitoring: Semantics and Implementation==
https://ceur-ws.org/Vol-627/coin_1.pdf
Normative Monitoring:
Semantics and Implementation
Sergio Alvarez-Napagao1 , Huib Aldewereld2 ,
Javier Vázquez-Salceda1 , and Frank Dignum2
1
Universitat Politècnica de Catalunya
{salvarez,jvazquez}@lsi.upc.edu
2
Universiteit Utrecht
{huib,dignum}@cs.uu.nl
Abstract. The concept of Normative Systems can be used in the scope of Multi-
Agent Systems to provide reliable contexts of interactions between agents where
acceptable behaviour is specified in terms of norms. Literature on the topic is
growing rapidly, and there is a considerable amount of theoretical frameworks
for normative environments, some in the form of Electronic Institutions. Most of
these approaches focus on regulative norms rather than on substantive norms, and
lack a proper implementation of the ontological connection between brute events
and institutional facts. In this paper we present a formalism for the monitoring of
both regulative (deontic) and substantive (constitutive) norms based on Structural
Operational Semantics, its reduction to Production Systems semantics and our
current implementation compliant to these semantics.
1 Introduction
In recent years, several researchers have argued that the design of multi-agent systems
(MAS) in complex, open environments can benefit from social abstractions in order
to cope with problems in coordination, cooperation and trust among agents, problems
which are also present in human societies. One of such abstractions is Normative Sys-
tems. Research in Normative Systems focuses on the concepts of norms and normative
environment (which some authors refer to as institutions) in order to provide normative
frameworks to restrict or guide the behaviour of (software) agents. The main idea is
that the interactions among a group of (software) agents are ruled by a set of explicit
norms expressed in a computational language representation that agents can interpret.
Although some authors only see norms as inflexible restrictions to agent behaviour, oth-
ers see norms not as a negative, constraining factor but as an aid that guides the agents’
choices and reduces the complexity of the environment, making the behaviour of other
agents more predictable.
Until recently, most of the work on normative environments works with norm spec-
ifications that are static and stable, and which will not change over time. Although this
may be good enough from the social (institutional) perspective, it is not appropriate
from the agent perspective. During their lifetime, agents may enter and leave several
interaction contexts, each with its own normative framework. Furthermore they may be
operating in contexts where more than one normative specification applies. So we need
1
mechanisms where normative specifications can be added to the agents’ knowledge
base at run-time and be practically used in their reasoning, both to be able to interpret
institutional facts from brute ones (by using constitutive norms to, e.g. decide if killing
a person counts as murder in the current context) and to decide what ought to be done
(by using regulative norms to, e.g. prosecute the murderer). In this paper we propose to
use production systems to build a norm monitoring mechanism that can be used both
by agents to perceive the current normative state of their environment, and for these
environments to detect norm violations and enforce sanctions. Our basic idea is that an
agent can configure, at a practical level, the production system at run-time by adding
abstract organisational specifications and sets of counts-as rules.
In our approach, the detection of normative states is a passive procedure consisting
in monitoring past events and checking them against a set of active norms. This type
of reasoning is already covered by the declarative aspect of production systems, so
no additional implementation in an imperative language is needed. Using a forward-
chaining rule engine, events will automatically trigger the normative state - based on
the operational semantics - without requiring a design on how to do it.
Having 1) a direct syntactic translation from norms to rules and 2) a logic imple-
mented in an engine consistent with the process we want to accomplish, allows us to
decouple normative state monitoring from the agent reasoning. The initial set of rules
we have defined is the same for each type of agent and each type of organisation, and
the agent will be able to transparently query the current normative state at any moment
and reason upon it. Also this decoupling helps building third party/facilitator agents ca-
pable of observing, monitoring and reporting normative state change or even enforcing
behaviour in the organisation.
In this paper we present a formalism for the monitoring of both regulative (de-
ontic) and substantive (constitutive) norms based on Structural Operational Semantics
(Section 2), its reduction to Production Systems semantics (Section 3) and our current
implementation compliant to these semantics (Section 4). In Section 5 we compare with
other related work and provide some conclusions.
2 Formal Semantics
In this section we discuss the formal semantics of our framework. First, in section 2.1,
we give the semantics of institutions as the environment specifying the regulative and
constitutive norms. Then, in section 2.2, we describe the details of how this institution
evolves over time based on events, and how this impacts the monitoring process. This
formalisation will be used in section 3 as basis of our implementation.
Through this paper, we will use as an example the following simplified traffic sce-
nario:
1. A person driving on a street is not allowed to break a traffic convention.
2. In case (1) is violated, the driver must pay a fine.
3. In a city, to exceed 50kmh counts as breaking a traffic convention.
2
2.1 Preliminary definitions
Before giving a formal definition of institutions (see definition 4), we first define the
semantics of the regulative and constitutive norms part of that institution (in definitions
1 and 3, respectively).
We assume the use of a predicate based propositional logic language LO with pred-
icates and constants taken from an ontology O, and the logical connectives {¬, ∨, ∧}.
The set of all possible well-formed formulas of LO is denoted as wf f (LO ) and we
assume that each formula from wf f (LO ) is normalised in Disjunctive Normal Form
(DNF). Formulas in wf f (LO ) can be partially grounded, if they use at least one free
variable, or fully grounded if they use no free variables.
In this paper we intensively use the concept of variable substitution. We define a
substitution instance Θ = {x1 ← t1 , x2 ← t2 , ..., xi ← ti } as the substitution of the
terms t1 , t2 , ..., ti for variables x1 , x2 , ..., xi in a formula f ∈ wf f (LO ).
We denote the set of roles in a normative system as the set of constants R, where
R ⊂ O, and the set of participants as P , where each participant enacts at least one role
according to the ontology O.
As our aim is to build a normative monitoring mechanism that can work at real time,
special care has been made to choose a norm language which, without loss of expre-
siveness, has operational semantics that can then be mapped into production systems.
Based in our previous work and experience, our definition of norm in an extension of
the norm language presented in [12]:
Definition 1. A norm n is a tuple n = �fA , fM , fδ , fD , fw , w�, where
– fA , fM , fδ , fD , fw ∈ wf f (LO ), w ∈ R,
– fA , fM , fD respectively represent the activation, maintenance, and deactivation
conditions of the norm, fδ , fw are the explicit representation of the deadline and
target of the norm, and
– w is the subject of the norm.
In order to create an optimal norm monitor it is important to know which norms
are active at each point in time, as only those are the ones that have to be traced (in-
active norms can be discarded from the monitoring process until they become active
again). The activation condition fA specifies when a norm becomes active. It is also the
main element in the norm instantiation process: when the conditions in the activating
condition hold, the variables are instantiated, creating a new norm instance3 The tar-
get condition fw describes the state that fulfills the norm (e.g. if one is obliged to pay,
the payment being made fulfills the obligation). The deactivating condition fD defines
when the norm becomes inactive. Typically it corresponds to the target condition (e.g.,
fulfilling the norm instance deactivates that instance of the norm), but in some cases it
also adds conditions to express other deactivating scenarios (e.g., when the norm be-
comes deprecated). The maintenance condition fM defines the conditions that, when
3
One main differentiating aspect of our formalisation is that we include variables in the norm
representation and we can handle multiple instantiations of the same norm and track them
separately.
3
no longer hold, lead to a violation of the norm. Finally the deadline condition fδ resp-
resents one or several deadlines for the norm to be fulfilled.
An example of a norm for the traffic scenario (”A person driving on a street is not
allowed to break a traffic convention”) would be formalised as follows
n1 :=�enacts(X, Driver) ∧ is driving(X),
¬traf f ic violation(X),
⊥,
¬is driving(X),
is driving(X) ∧ ¬traf f ic violation(X),
Driver�,
The activating condition states that each time an event appears where an individual
enacting the Driver role drives (‘is driving), then a new instance of the norm becomes
active; the maintenance condition states that the norm will not be violated while no
traffic convention is violated; this norm has no deadline, it is to apply at all times an
individual is driving; the norm instance deactivates when the individual stops driving4 ;
the target of this norm is that we want drivers not breaking traffic conventions; finally
the subject of the norm is someone enacting the Driver role.
It is important to note here that, although our norm representation does not explicitly
include deontic operators, the combination of the activation, deactivation and mainte-
nance conditions is as expressive as conditional deontic statements with deadlines as the
ones in [3]. It is also able to express unconditional norms and maintenance obligations
(i.e. the obligation to keep some conditions holding for a period of time). To show that
our representation can be mapped to conditional deontic representations, let us express
the semantics of the norm in definition 1 in terms of conditional deontic statements.
Given relations between the deadline and maintenance condition (that is, fδ → ¬fM ,
since the maintenance condition expresses more than the deadline alone) and between
the target and the deactivation condition (i.e., fw → fD , since the deactivation condi-
tion specifies that either the norm is fulfilled or something special has happened), we
can formalise the norms of definition 1 as the equivalent deontic expression (using the
formalism of [3]): fA → [Ow (Ew fw ≤ ¬fM ) U fD ], where Ea p means that agent a
sees to it that (stit) p becomes true and U is the CTL∗ until operator. Intuitively, the
expression states that after the norm activation, the subject is obliged to see to it that the
target becomes true before the maintenance condition is negated (either the deadline is
reached or some other condition is broken) until the norm is deactivated (which is either
when the norm is fulfilled or has otherwise expired).
Since we are not reasoning about the (effects of) combinations of norms, we will not
go into further semantical details here. The semantics presented in this deontic reduction
are enough for understanding the monitoring process that is detailed in the remainder
of the paper.
A set of norms is denoted as N . We define as violation handling norms those norms
that are activated automatically by the violation of another norm:
4
Although the norm is to apply at all times an individual is driving, it is better to deactivate the
norm each time the individual stops driving, instead to keep it active, to minimize the number
of norm instances the monitor needs to keep track at all times.
4
Definition 2. A norm n� = �fA� , fM �
, fδ� , fD
�
, fw� , w� � is a violation handling norm of
n = �fA , fM , fδ , fD , fw , w�, denoted as n � n� iff fA ∧ ¬fM ∧ ¬fD ≡ fA�
Violation handling norms are special in the sense that they are only activated when
another norm is violated. They are used as sanctioning norms, if they are to be fulfilled
by the norm violating actor (e.g., the obligation to pay a fine if the driver broke a traffic
sign), or as reparation norms, if they are to be fulfilled by an institutional actor (e.g. the
obligation of the authorities to fix the broken traffic sign).
A norm is defined in an abstract manner, affecting all possible participants enacting
a given role. Whenever a norm is active, we will say that there is a norm instance
ni = �n, θ� for a particular norm n and a substitution instance Θ.
We define the state of the world st at a specific point of time t as the set of predicates
holding at that specific moment, where st ⊆ O, and we will denote S as the set of
all possible states of the world, where S = P(O). We will call expansion F (s) of a
state of the world s as the minimal subset of wf f (LO ) that uses the predicates in s in
combination of the logical connectives {¬, ∨, ∧}.
One common problem for the monitoring of normative states is the need for an
interpretation of brute events as institutional facts, also called constitution of social
reality[8]. The use of counts-as rules helps solving this problem. Counts-as rules are
multi-modal statements of the form [c](γ1 → γ2 ), read as “in context c, γ1 counts-as
γ2 ”. In this paper, we will consider a context as a set of predicates, that is, as a possible
subset of a state of the world:
Definition 3. A counts-as rule is a tuple c = �γ1 , γ2 , s�, where γ1 , γ2 ∈ wf f (LO ),
and s ⊆ O.
A set of counts-as rules is denoted as C. Although the definition of counts-as in [8]
assumes that both γ1 and γ2 can be any possible formula, in our work we limit γ2 to a
conjunction of predicates for practical purposes.
Definition 4. Following the definitions above, we define an institution as a tuple of
norms, roles, participants, counts-as rules, and an ontology:
I = �N, R, P, C, O�
An example of I for the traffic scenario would be formalised as follows:
N :={�enacts(X, Driver) ∧ is driving(X),
¬traf f ic violation(X), ⊥, ¬is driving(X),
is driving(X) ∧ ¬traf f ic violation(X), Driver�,
�enacts(X, Driver) ∧ is driving(X) ∧ traf f ic violation(X),
�,
paid f ine(X), Driver�}
R :={Driver}, P :={P erson1 }
C :={�exceeds(D, 50), traf f ic violation(D), is in city(D)�}
O :={role, enacts, is driving, is in city,
exceeds, traf f ic violation, is driving, paid f ine,
P erson1 , role(Driver), enacts(P erson1 , Driver)}
5
2.2 Normative Monitor
In this section we present a formalisation of normative monitoring based on Structural
Operational Semantics.
From the definitions introduced in section 2.1, a Normative Monitor will be com-
posed of the institutional specification, including norms, the current state of the world,
and the current normative state.
In order to track the normative state of an institution at any given point of time, we
will define three sets: an instantiation set IS, a fulfillment set F S, and a violation set
V S, each of them containing norm instances {�ni , Θj �, �ni� , Θj � �, ..., �ni�� , Θj �� �}. We
adapt the semantics for normative states from [11]:
Definition 5. Norm Lifecycle: Let ni = �n, Θ� be a norm instance, where n = �fA , fM , fD , w�,
and a state of the world s with an expansion F (s). The lifecycle for norm instance ni
is defined by the following normative state predicates:
activated(ni) ⇔ ∃f ∈ F (s), Θ(fA ) ≡ f
maintained(ni) ⇔ ∃Θ� , ∃f ∈ F (s), Θ� (fM ) ≡ f ∧ Θ� ⊆ Θ
deactivated(ni) ⇔ ∃Θ� , ∃f ∈ F (s), Θ� (fD ) ≡ f ∧ Θ� ⊆ Θ
instantiated(ni) ⇔ ni ∈ IS
violated(ni) ⇔ ni ∈ V S
f ulf illed(ni) ⇔ ni ∈ F S
where IS is the instantiation set, F S is the fulfillment set, and V S is the violation
set, as defined above.
For instance, for norm n1, the lifecycle is represented in Figure 1. The maintained
state is not represented as it holds in both the activated and fulfilled states. The de-
activated state is also not depicted because it corresponds in this case to the Fulfilled
state.
Fig. 1: Lifecycle for norm n1 in the traffic scenario: (I)nactive, (A)ctivated, (V)iolated,
(F)ulfilled
Definition 6. A Normative Monitor MI for an institution I is a tuple MI = �I, S, IS, V S, F S�
where
6
– I = �N, R, P, C, O�,
– S = P(O),
– IS = P(N × S × Dom(S)),
– V S = P(N × S × Dom(S)), and
– F S = P(N × S × Dom(S)).
The set Γ of possible configurations of a Normative Monitor MI is Γ = I × S ×
IS × V S × F S.
However, the definition above does not take into account the dynamic aspects of
incoming events affecting the state of the world through time. To extend our model
we will assume that there is a continuous, sequential stream of events received by the
monitor:
Definition 7. An event e is a tuple e = �α, p�, where
– α ∈ P 5 , and
– p ∈ F and is fully grounded.
We define E as the set of all possible events, E = P(P × F )
Definition 8. The Labelled Transition System for a Normative Monitor MI is defined
by �Γ, E, �� where
– E is the set of all possible events e = �α, p�
– � is a transition relation such that � ⊆ Γ × E × Γ
The inference rules for the transition relation � are depicted in Figure 2.
3 Monitoring with production systems
In our approach, practical normative reasoning is based on a production system with
an initial set of rules implementing the operational semantics described in Section 2.2.
Production systems are composed of a set of rules, a working memory, and a rule in-
terpreter or engine [2]. Rules are simple conditional statements, usually of the form
IF a THEN b, where a is usually called left-hand side (LHS) and b is usually called
right-hand side (RHS).
3.1 Semantics of production systems
In this paper we use a simplified version of the semantics for production systems intro-
duced in [1].
Considering a set P of predicate symbols, and an infinite set of variables X , where
a fact is a ground term, f ∈ T (P), and WM is the working memory, a set of facts, a
production rule is denoted if p, c remove r add a, or
5
α is considered to be the asserter of the event. Although we are not going to use this element
in this paper, its use may be of importance when extending or updating this model.
7
Event processed:
ei = �α, p�
(1)
���i, s, is, vs, f s�, ei �, ei+1 � � ��i, s ∪ {p}, is, vs, f s�, ei+1 �
Counts-as rule activation:
∃Θ, ∃f ∈ F (s), ∃�γ1 , γ2 , si � ∈ C, si ⊆ s ∧ Θ(γ1 ) ≡ f ∧ Θ(γ2 ) ∈ /s
(2)
���N, R, P, C, O�, s, is, vs, f s�, e� � ���N, R, P, C, O�, s ∪ {Θ(γ2 )}, is, vs, f s�, e�
Counts-as rule deactivation:
∃Θ, ∃f ∈ F (s), ∃�γ1 , γ2 , si � ∈ C, si �⊆ s ∧ Θ(γ1 ) ≡ f ∧ Θ(γ2 ) ∈ s
(3)
���N, R, P, C, O�, s, is, vs, f s�, e� � ���N, R, P, C, O�, s − {Θ(γ2 )}, is, vs, f s�, e�
Norm instantiation:
∃n = �fA , fM , fD , w� ∈ N ∧ ¬∃n ∈ N, n� � n ∧ �n, Θ� ∈
�
/ is ∧ ∃Θ, ∃f � ∈ F (s), f � ≡ Θ(fA )
���N, R, P, C, O�, s, is, vs, f s�, e� � ���N, R, P, C, O�, s, is ∪ {�n, Θ�}, vs, f s�, e�
(4)
Norm instance violation:
∃n = �fA , fM , fD , w� ∈ N ∧ �n, Θ� � ∈ is ∧ �n, Θ� � ∈ / vs∧
�
¬(∃Θ, ∃f � ∈ F (s), f � ≡ Θ(fM ) ∧ Θ ⊆ Θ� ) ∧ N R = n�n� �n� , Θ� �
���N, R, P, C, O�, s, is, vs, f s�, e� � ���N, R, P, C, O�, s, (is − {�n, T heta� �}) ∪ N R,
vs ∪ {�n, Θ� �}, f s�, e�
(5)
Norm instance fulfilled:
∃n = �fA , fM , fD , w� ∈ N ∧ �n, Θ� � ∈ is ∧ ∃Θ, ∃f � ∈ F (s), f � ≡ Θ(fD ) ∧ Θ ⊆ Θ�
���N, R, P, C, O�, s, is, vs, f s�, e� � ���N, R, P, C, O�, s, is − {�n, Θ� �}, vs, f s ∪ �n, Θ� ��, e�
(6)
Norm instance violation repaired:
∃n, n� ∈ N ∧ n � n� ∧ �n, Θ� ∈ vs ∧ n � n� ∧ �n� , Θ� ∈ f s
(7)
���N, R, P, C, O�, s, is, vs, f s�, e� � ���N, R, P, C, O�, s, is, vs − {�n, Θ�}, f s�, e�
Fig. 2: Inference rules for the transition relation �
p, c ⇒ r, a,
consisting of the following components:
– A set of positive or negative patterns p = p+ ∪ p− where a pattern is a term pi ∈
T (F, X ) and a negated pattern is denoted ¬pi . p− is the set of all negated patterns
and p+ is the set of the remaining patterns
– A proposition c whose set of free variables is a subset of the pattern variables:
V ar(c) ⊆ V ar(p).
– A set r of terms whose instances could be intuitively considered as intended to be
removed from the working memory when the rule is fired, r = {ri }i∈Ir , where
V ar(r) ⊆ V ar(p+ ).
8
– A set a of terms whose instances could be intuitively considered as intended to
be added to the working memory when the rule is fired, a = {ai }i∈Ia , where
V ar(a) ⊆ V ar(p).
Definition 9. A set of positive patterns p+ matches to a set of facts S and a substitution
σ iff ∀p ∈ p+ , ∃t ∈ S, σ(p) = t. Similarly, a set of negative patterns p− dismatches a
set of facts S iff ∀¬p ∈ p− , ∀t ∈ S, ∀σ, σ(p) �= t.
A production rule p ⇒ r, a is (σ, WM� )-fireable on a working memory WM when
p matches with WM� and p− dismatches with WM, where WM� is a minimal subset
+
of WM, and T |= σ(c).
Definition 10. The application of a (σ, WM� )-fireable rule on a working memory WM
leads to the new working memory WM�� = (WM − σ(r)) ∪ σ(a).
Definition 11. A general production system PS is defined as PS = �P, WM0 , R�,
where R is a set of production rules over H = �P, X �.
3.2 Reduction
In order to formalise our Normative Monitor as a production system, we will need to
define several predicates to bind norms to their conditions: activation, maintenance, de-
activation, and to represent normative state over norm instances: violated, instantiated,
and fulfilled. We will also use a predicate for the arrival of events: event, and a predicate
to represent the fact that a norm instance is a violation handling norm instance of a vi-
olated instance: repair. For the handling of the DNF clauses, we will use the predicates
holds and has clause.
Definition 12. The set of predicates for our production system, for an institution I =
�N, R, P, C, O�, is:
PI := O ∪ {activated, maintained, deactivated,
violated, instantiated, f ulf illed, event, repair,
holds, has clause, countsas}
The initial working memory WM0 should include the institutional specification
in the form of the formulas included in the counts-as rules and the norms in order
to represent the possible instantiations of the predicate holds, through the use of the
predicate has clause.
First of all, we need to have the bindings between the norms and their formulas
available in the working memory. For each norm n = �fA , fM , fD , w�, these bindings
will be:
WMn := {activation(n, fA ), maintenance(n, fM ), deactivation(n, fD )}
As we assume the formulas from wf f (LO ) to be in DNF form:
Definition 13. We can interpret a formula as a set of conjunctive clauses f = {f1 , f2 , ..., fN },
of which only one of these clauses fi holding true is necessary for f holding true as
well:
rh := has clause(f, f � ) ∧ holds(f � , Θ) ⇒ ∅, {holds(f, Θ)}
9
For example, if f = (p1 (x) ∧ p2 (y) ∧ ... ∧ pi (z)) ∨ ... ∨ (q1 (w) ∧ q2 (x) ∧ ... ∧ qj (y)),
facts to be in WM0 will be:
then the initial �
WM0 := f � ∈f has clause(f, f � ) = {has clause(f, f1 ), ..., has clause(f, f2 )}
Also, we have to include the set of repair norms by the use of the predicate repair,
and the counts-as definitions by the use of the predicate countsas.
Definition 14. The initial working memory WMI for an institution I = �N, R, P, C, O�
is:
�n∈N �
WMI := n�n� repair(n, n ) ∪
�
n=�f ,f ,f ,w�∈N (WMn ∪ WMfA ∪ WMfM ∪ WMfD ) ∪
� A M D
c=�γ1 ,γ2 ,s�∈C ({countsas(γ1 , γ2 , s)} ∪ WMγ1 ∪ WMs )
The rule for the detection of a holding formula is defined as rfhc = �f � ⇒ ∅, {holds(f, σ)},
where we denote as �f � the propositional content of a formula f ∈ wf f (LO ) which
only uses predicates from O and the logical connectives ¬ and ∧, and σ as the substitu-
tion set of the activation of the rule. Following the previous example:
rfhc1 = p1 (x) ∧ p2 (y) ∧ ... ∧ pi (z) ⇒ ∅, {holds(f1 , {x, y, z})}
rfhc2 = q1 (w) ∧ q2 (x) ∧ ... ∧ qi (y) ⇒ ∅, {holds(f2 , {w, x, y})}
Similarly as in Definition 14:
Definition 15. The set of rules RIhc for detection of holding formulas for an institution
� C, O� is:
I = �N, R, P, � � �
RIhc := n=�fA ,fM ,fD ,w�∈N ( f ∈{fA ,fM ,fD } rfhc ) ∪ c=�γ1 ,γ2 ,s�∈C ( f ∈γ1 rfhc )
By using the predicate holds as defined above, we can translate the inference rules
from Section 2.2. Please note that the rules are of the form p, c ⇒ r, a as shown in
Section 3.1. However, as we only need the c part to create a constraint proposition in
the rules for norm instance violation and fulfillment, c is omitted except for these two
particular cases.
Definition 16. Translated rules (see Figure 2)
Rule for event processing (1):
re = event(α, p) ⇒ ∅, {�p�}
Rule for counts-as rule activation (2):
rca = countsas(γ1 , γ2 , c) ∧ holds(γ1 , Θ) ∧ holds(c, Θ� ) ∧ ¬holds(γ2 , Θ)
⇒ ∅, {Θ(�γ2 �)}
Rule for counts-as rule deactivation (3):
rcd = countsas(γ1 , γ2 , c) ∧ holds(γ1 , Θ) ∧ ¬holds(c, Θ� ) ∧ holds(γ2 , Θ)
⇒ {Θ(�γ2 �)}, ∅
Rule for norm instantiation (4):
rni = activation(n, f ) ∧ holds(f, Θ) ∧ ¬instantiated(n, Θ) ∧ ¬repair(n� , n)
⇒ ∅, {instantiated(n, Θ)}
Rule for norm instance violation (5):
rnv = instantiated(n, Θ)∧maintenance(n, f )∧¬holds(f, Θ� )∧repair(n, n� ),
∀Θ� , Θ� ⊆ Θ
10
Fig. 3: Architecture of the D ROOLS implementation
⇒ {instantiated(n, Θ)}, {violated(n, Θ), instantiated(n� , Θ)}
Rule for norm instance fulfillment (6):
rnf = deactivation(n, f )∧instantiated(n, Θ)∧subseteq(Θ� , Θ)∧holds(f, Θ� ),
Θ� ⊆ Θ
⇒ {instantiated(n, Θ)}, {f ulf illed(n, Θ)}
Rule for norm instance violation repaired (7):
rnr = violated(n, Θ) ∧ repair(n, n� ) ∧ f ulf illed(n� , Θ� )
⇒ {violated(n, Θ)}, ∅
Definition 17. Following Definitions 13, 15 and 16, the set of rules for an institution
I = �N, R, P, C, O� are:
RI := RIhc ∪ {rh , re , rca , rcd , rni , rnv , rnf , rnr }
Definition 18. The production system PS I for an institution I will be, from Defini-
tions 12, 14 and 17:
PS I := �PI , WMI , RI �
4 Implementation
A prototype of our normative reasoner has been implemented as a D ROOLS program.
D ROOLS is an open-source Object-Oriented rule engine for declarative reasoning in
Java [14]. Its rule engine is an implementation of the forward chaining inference Rete
algorithm [4]. The use of Java objects inside the rule engine allows for portability and
an easier communication of concepts with the reasoning of agents coded in Java.
11
rule "holds"
when
HasClause(f : formula, f2 : clause)
Holds(formula == f2, theta : substitution)
rule "norm instance violation"
then
when
insertLogical(new Holds(f, theta));
ni : Instantiated(n : norm, theta : substitution)
end
Maintenance(norm == n, f : formula)
not (SubsetEQ(theta2 : subset, superset == theta)
rule "event processed"
and Holds(formula == f, substitution == theta2))
when
Repair(norm == n, n2 : repairNorm)
Event(a : asserter, p : content)
then
then
retract(ni);
insertLogical(p);
insert(new Violated(n, theta));
end
insert(new Instantiated(n2, theta));
end
rule "counts-as activation"
when
rule "norm instance fulfillment"
CountsAs(g1 : gamma1, g2 : gamma2, s : context)
when
Holds(formula == g1, theta : substitution)
Deactivation(n : norm, f : formula)
Holds(formula == s, theta2 : substitution)
ni : Instantiated(norm == n, theta : substitution)
not Holds(formula == g2, substitution == theta)
SubsetEQ(theta2 : subset, superset == theta)
then
Holds(formula == f, substitution == theta2)
Formula f;
then
retract(ni);
f = g2.substitute(theta);
insert(new Fulfilled(n, theta));
insert(f);
end
end
rule "norm instance violation repaired"
rule "counts-as deactivation"
when
when
ni : Violated(n : norm, theta : substitution)
CountsAs(g1 : gamma1, g2 : gamma2, s : context)
Repair(norm == n, n2 : repairNorm)
Holds(formula == g1, theta : substitution)
Fulfilled(norm == n2, substitution == theta)
not Holds(formula == s, theta2 : substitution)
then
Holds(formula == g2, substitution == theta)
retract(ni);
f : Formula(content == g2, grounding == theta)
end
then
retract(f);
rule "subseteq"
end
when
Holds(f : formula, theta : substitution)
rule "norm instantiation"
Holds(f2 : formula, theta2 : substitution)
when
eval(theta.containsAll(theta2))
Activation(n : norm, f : formula)
then
Holds(formula == f, theta : substitution)
insertLogical(new SubsetEQ(theta2, theta));
not Instantiated(norm == n, substitution == theta)
end
not Repair(n2 : norm, repairNorm == n)
then
insert(new Instantiated(n, theta));
end
Fig. 4: Translation of base rules to D ROOLS
12
In D ROOLS we can represent facts by adding them to the knowledge base as ob-
jects of the class Predicate. Predicates are dynamically imported from standardised De-
scription Logic OWL - DL ontologies into Java objects using the tool OWL2Java[17], as
subclasses of a specifically designed Predicate class. The following shows an example
of the insertion of enacts role(p, Driver) into the knowledge base to express that p
(represented as object p of the domain and instantiating a participant) is in fact enacting
the role driver:
ksession.insert(new Enacts(p, Driver.class));
D ROOLS programs can be initialised with a rule definition file. However, its working
memory and rule base can be modified at run-time by the Java process that is running
the rule engine. We take advantage of this by keeping a fixed base, which is a file with
fixed contents implementing the rules from Definition 13 and 16, which are indepen-
dent of the institution, and having a parser for institutional definitions that will feed the
rules from Definition 15, which are dependent on the institution (see Figure 3). The in-
stitutional definitions we currently use are based on an extension of the XML language
presented in [12].
The base rules (see Definitions 13 and 16) has been quite straightforward and the
translation is almost literal. The contents of the reusable D ROOLS file is shown in Fig-
ure 4. The last rule of the Figure is the declarative implementation of the predicate
SubsetEQ to represent the comparison of substitutions instances Θ ⊆ Θ� , needed for
the cases of norm instance violation and fulfillment. In our implementation in Drools,
substitution instances are implemented as Set objects, where Value is a tuple
�String, Object�.
The rest of the rules (see Definitions 15) are automatically generated from the in-
stitutional specifications and inserted into the D ROOLS rule engine. An example of two
generated rules for the traffic scenario is shown in Figure 5.
rule "N1_activation_1"
when
n : Norm(id == "N1")
Activation(norm == n, f : formula)
Enacts(X : p0, p1 == "Driver")
IsDriving(p0 == X)
then
Set theta = new Set();
theta.add(new Value("X", X));
insert(new Holds(f.getClause(0), theta));
end
rule "C1_1"
when
c : CountsAs(g1 : gamma1)
Exceeds(D : p0, 50 : p1)
then
Set theta = new Set();
theta.add(new Value("D", D));
insert(new Holds(g1.getClause(0), theta));
end
Fig. 5: Rules for the traffic scenario
13
The initial working memory is also automatically generated by inserting objects
(facts) into the D ROOLS knowledge base following Definition 14. An example for the
traffic scenario is also shown in Figure 6. Please note that this is not an output of the
parser, but a representation of what it would execute at run-time.
ksession.insert(norm1);
ksession.insert(norm2);
ksession.insert(new Repair(norm1, norm2));
ksession.insert(new Activation(norm1, fn1a));
ksession.insert(new Maintenance(norm1, fn1m));
ksession.insert(new Deactivation(norm1, fn1d));
ksession.insert(new HasClause(fn1a, fn1a1));
ksession.insert(new HasClause(fn1m, fn1m1));
ksession.insert(new HasClause(fn1d, fn1d1));
/* ...same for norm2... */
ksession.insert(new CountsAs(c1g1, c1g2, c1s));
ksession.insert(new HasClause(c1g1, c1g11));
ksession.insert(new HasClause(c1g2, c1g21));
ksession.insert(new HasClause(c1s, c1s1));
Fig. 6: Facts for the traffic scenario
5 Conclusions and Related Work
The implementation of rule-based norm operationalisation has already been explored
in previous research. Some approaches [13,15] directly define the operationalisation of
the norms as rules of a specific language, not allowing enough abstraction to define
norms at a high level to be operationalised in different rule engine specifications. [5]
introduces a translation scheme, but it is bound to Jess by using specific constructs of
this language and it does not support constitutive norms.
Other recent approaches like [6] define rule-based languages with expressive con-
structs to model norms, but they are bound to a proper interpreter and have no grounding
on a general production system, requiring the use of an intentionally crafted or mod-
ified rule engine. For example, in [7,9], obligations, permissions and prohibitions are
asserted as facts by the execution of the rules, but the actual monitoring is out of the
base rule engine used.
[16] introduces a language for defining an organisation in terms of roles, norms,
and sanctions. This language is presented along with an operational semantics based on
transition rules, thus making its adoption by a general production system straightfor-
ward. Although a combination of counts-as rules and sanctions is used in this language,
it is not expressive enough to support regulative norms with conditional deontic state-
ments.
We solve these issues by combining a normative language [12] with a reduction to
a representation with clear operational semantics based on the framework in [11] for
deontic norms and the use of counts-as rules for constitutive norms. The formalism pre-
sented in this paper uses logic conditions that determine the state of a norm (active,
14
fulfilled, violated). These conditions can be expressed in propositional logic and can
be directly translated into LHS parts of rules, with no special adaptation needed. The
implementation of the operational semantics in a production system to get a practical
normative reasoner is thus straightforward. This allows agents for dynamically chang-
ing its institutional context at any moment, by feeding the production system with a new
abstract institutional specification.
Our intention is not to design a general purpose reasoner for normative agents, but
a practical reasoner for detecting event-driven normative states. This practical reasoner
can then be used as a component not only by normative agents, but also by monitors
or managers. Normative agents should deal with issues such as planning and future
possibilities, but monitors are focused on past events. For such a practical reasoner,
the expressivity of actions languages like C+ is not needed, and a simple yet efficient
solution is to use production systems, as opposed to approaches more directly related
to offline verification or model checking, such as [10].
Mere syntactical translations are usually misleading in the sense that rule language
specific constructs are commonly used, constraining reusability [13,5,7]. However, as
we have presented in this paper a reduction to a general version of production system
semantics, any rule engine could fit our purposes. There are several production system
implementations available, some widely used by the industry, such as J ESS, D ROOLS,
S OAR or P ROVA. In most of these systems rules are syntactically and semantically sim-
ilar, so switching from one to the other would be quite simple. As production systems
dynamically compile rules to efficient structures, they can be used as well to validate
and verify the consistency of the norms. As opposed to [7,9], our reduction ensures that
the whole monitoring process is carried out entirely by a general production system,
thus effectively decoupling normative state detection and agent reasoning.
D ROOLS is an open-source powerful suite supported by JBoss, the community, and
the industry, and at the same time it is lightweight enough while including key features
that we are or will be using in future work, As an advantage over other alternatives, it
includes features relevant to our topic, e.g. event processing, workflow integration. Its
OO approach makes it easy to be integrated with imperative code (Java), and OWL-DL
native support is expected in a short time.
Our implementation is already being used in several use cases with large amounts of
events and it is available at http://ict-alive.svn.sf.net/viewvc/ict-alive/
OrganisationLevel/trunk/Monitoring/ under a GPL license. As future
work we expect to extend the semantics in order to support first-order logic norm condi-
tions, and to perform an analysis on the algorithmic complexity of our implementation.
Acknowledgements
This work has been partially supported by the FP7-215890 ALIVE project. J. Vázquez-
Salceda’s work has been also partially funded by the Ramón y Cajal program of the
Spanish Ministry of Education and Science.
15
References
1. Cirstea, H., Kirchner, C., Moossen, M., Moreau, P.E.: Production Systems and Rete Algo-
rithm Formalisation. Tech. Rep. ILOG, INRIA Lorraine, INRIA Rocquencourt, Manifico
(2004)
2. Davis, R., King, J.: An overview of production systems. Tech. rep., Stanford Artificial Intel-
ligence Laboratory, Report No. STAN-CS-75-524 (1975)
3. Dignum, F., Broersen, J., Dignum, V., Meyer, J.J.: Meeting the Deadline: Why, When and
How. In: Formal Approaches to Agent-Based Systems, Lecture Notes in Computer Science
3228, pp. 30–40. Springer Berlin / Heidelberg (2005)
4. Forgy, C.L.: Rete: A fast algorithm for the many pattern/many object pattern match problem.
Artificial Intelligence 19(1), 17–37 (1982)
5. Garcı́a-Camino, A., Noriega, P., Rodrı́guez-Aguilar, J.A.: Implementing norms in electronic
institutions. In: Proceedings of the fourth international joint conference on Autonomous
agents and multiagent systems. pp. 667–673. Utrecht, Netherlands (2005)
6. Garcı́a-Camino, A., Rodrı́guez-Aguilar, J.A., Sierra, C., Vasconcelos, W.: Constraint rule-
based programming of norms for electronic institutions. Autonomous Agents and Multi-
Agent Systems 18(1), 186–217 (2009)
7. Governatori, G.: Representing business contracts in RuleML. International Journal of Coop-
erative Information Systems 14(2-3), 181–216 (2005)
8. Grossi, D.: Designing invisible handcuffs: Formal investigations in institutions and organi-
zations for multi-agent systems. Thesis, Universiteit Utrecht (2007)
9. Hübner, J.F., Boissier, O., Bordini, R.H.: Normative programming for organisation manage-
ment infrastructures. In: Workshop on Coordination, Organization, Institutions and Norms
in Agent Systems in Online Communities (COIN@MALLOW 2009) (2009)
10. Kyas, M., Prisacariu, C., Schneider, G.: Run-time monitoring of electronic contracts. In:
Proceedings of 6th International Symposium on Automated Technology for Verification and
Analysis, Lecture Notes in Computer Science 5311, pp. 397–407. Springer Berlin / Heidel-
berg (2008)
11. Oren, N., Panagiotidi, S., Vázquez-Salceda, J., Modgil, S., Luck, M., Miles, S.: Towards a
formalisation of electronic contracting environments. In: Coordination, Organizations, In-
stitutions and Norms in Agent Systems IV, Lecture Notes in Computer Science 5428, pp.
156–171. Springer Berlin / Heidelberg (2009)
12. Panagiotidi, S., Vázquez-Salceda, J., Alvarez-Napagao, S., Ortega-Martorell, S., Willmott,
S., Confalonieri, R., Storms, P.: Intelligent Contracting Agents Language. In: Proceedings of
the Symposium on Behaviour Regulation in Multi-Agent Systems (BRMAS 2008) at AISB
2008. vol. 1, p. 49. Aberdeen, Scotland (2008)
13. Paschke, A., Dietrich, J., Kuhla, K.: A Logic Based SLA Management Framework. In: Pro-
ceedings of the 4th Semantic Web Conference (ISWC 2005). pp. 68–83. Galway, Ireland
(2005)
14. Proctor, M., Neale, M., Frandsen, M., Jr., S.G., Tirelli, E., Meyer, F., Verlaenen, K.: Drools
documentation. JBoss (2008)
15. Strano, M., Molina-Jimenez, C., Shrivastava, S.: A rule-based notation to specify executable
electronic contracts. In: Proceedings of the International Symposium on Rule Representa-
tion, Interchange and Reasoning on the Web (RuleML2008), Lecture Notes in Computer
Science 5321, pp. 81–88. Springer Berlin / Heidelberg (2008)
16. Tinnemeier, N., Dastani, M., Meyer, J.J.: Roles and norms for programming agent organiza-
tions. In: Proc. of 8th Int. Conf. on Autonomous Agents and Multiagent Systems (AAMAS
2009). vol. 1, pp. 121–128. Budapest, Hungary (2009)
17. Zimmermann, M.: OWL2Java (2009)
16