The concept of Normative Systems can be used in the scope of MultiAgent 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.
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 Systems. 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, others 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 specifications 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 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 forwardchaining 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 implemented 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 capable 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 (deontic) 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
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 scenario: 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.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).
icates and constants taken from an ontology O, and the logical connectives {¬, ∨, ∧}.
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
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
expresiveness, 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 [
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 (inactive 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 target 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 becomes 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. no longer hold, lead to a violation of the norm. Finally the deadline condition fδ respresents 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
maintenance conditions is as expressive as conditional deontic statements with deadlines as the
ones in [
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. 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[
A set of counts-as rules is denoted as C. Although the definition of counts-as in [
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)} 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 composed 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
adapt the semantics for normative states from [
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 deactivated state is also not depicted because it corresponds in this case to the Fulfilled state. Definition 6. A Normative Monitor MI for an institution I is a tuple MI = I, S, IS, V S, F S where
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
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
interpreter or engine [
Semantics of production systems
In this paper we use a simplified version of the semantics for production systems
introduced in [
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. (1) (2) (3) (4) (5) (7) i, s, is, vs, f s, e
Event processed:
ei = α, p i, e i+1 i, s ∪ {p}, is, vs, f s, e
i+1
Counts-as rule activation: Counts-as rule deactivation:
Norm instantiation:
Norm instance violation: ∃n = f A, fM , fD, w ∈ N ∧ ¬∃n
N, R, P, C, O, s, is, vs, f s, e ∈ N, n n ∧ n, Θ ∈/ is ∧ ∃Θ, ∃f ∈ F (s), f ≡ Θ(fA)
N, R, P, C, O, s, is ∪ {n, Θ}, vs, f s, e ∃n = f A, fM , fD, w ∈ N ∧ n, Θ ∈ is ∧ n, Θ ¬(∃Θ, ∃f ∈ F (s), f ≡ Θ(fM ) ∧ Θ ⊆ Θ ) ∧ N R = N, R, P, C, O, s, is, vs, f s, e N, R, P, C, O, s, (is − {n, T heta vs ∪ {n, Θ }, f s, e ∈/ vs∧ n n n , Θ
}) ∪ N R,
Norm instance fulfilled:
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 ∈
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+). – 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.
p+ matches with WM and p− dismatches with WM, where WM is a minimal subset of WM, and T |= σ(c).
P, WM0, R , 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, deactivation, 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 violated 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}
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)}
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, Θ)}
For example, if f = (p1(x) ∧ p2(y) ∧ ... ∧ pi(z)) ∨ ... ∨ (q1(w) ∧ q2(x) ∧ ... ∧ qj (y)), then the initial facts to be in WM0 will be:
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 = is:
WMI := nn∈Nn repair(n, n )
N, R, P, C, O ∪ n= fA,fM ,fD,w ∈N (WMn ∪ WMfA ∪ WMfM ∪ WMfD ) ∪
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 substitution set of the activation of the rule. Following the previous example: rfh1c = p1(x) ∧ p2(y) ∧ ... ∧ pi(z) ⇒ ∅, {holds(f1, {x, y, z})} rfh2c = q1(w) ∧ q2(x) ∧ ... ∧ qi(y) ⇒ ∅, {holds(f2, {w, x, y})} Similarly as in Definition 14:
n= fA,fM ,fD,w ∈N ( f∈{fA,fM ,fD} rfhc) ∪
I = N, R, P, C, O is:
RIhc := 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 ), ∀Θ , Θ ⊆ Θ
A prototype of our normative reasoner has been implemented as a DROOLS program.
DROOLS is an open-source Object-Oriented rule engine for declarative reasoning in
Java [
Event(a : asserter, p : content) then
insertLogical(p); end rule "counts-as activation" when
CountsAs(g1 : gamma1, g2 : gamma2, s : context) Holds(formula == g1, theta : substitution) Holds(formula == s, theta2 : substitution) not Holds(formula == g2, substitution == theta) then
Formula f; f = g2.substitute(theta); insert(f); end rule "counts-as deactivation" when
CountsAs(g1 : gamma1, g2 : gamma2, s : context) Holds(formula == g1, theta : substitution) not Holds(formula == s, theta2 : substitution) Holds(formula == g2, substitution == theta) f : Formula(content == g2, grounding == theta) then
retract(f); end rule "norm instance violation" when ni : Instantiated(n : norm, theta : substitution) Maintenance(norm == n, f : formula) not (SubsetEQ(theta2 : subset, superset == theta) and Holds(formula == f, substitution == theta2))
Repair(norm == n, n2 : repairNorm) then retract(ni); insert(new Violated(n, theta)); insert(new Instantiated(n2, theta)); end rule "norm instance fulfillment" when
Deactivation(n : norm, f : formula) ni : Instantiated(norm == n, theta : substitution) SubsetEQ(theta2 : subset, superset == theta)
Holds(formula == f, substitution == theta2) then retract(ni); insert(new Fulfilled(n, theta)); end rule "norm instance violation repaired" when ni : Violated(n : norm, theta : substitution) Repair(norm == n, n2 : repairNorm)
Fulfilled(norm == n2, substitution == theta) then
retract(ni); end rule "subseteq" when
Holds(f : formula, theta : substitution) rule "norm instantiation" Holds(f2 : formula, theta2 : substitution) when eval(theta.containsAll(theta2)) Activation(n : norm, f : formula) Holds(formula == f, theta : substitution) then 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
In DROOLS we can represent facts by adding them to the knowledge base as
objects of the class Predicate. Predicates are dynamically imported from standardised
Description Logic OWL-DL ontologies into Java objects using the tool OWL2Java[
DROOLS 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
independent 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
institutional definitions we currently use are based on an extension of the XML language
presented in [
The base rules (see Definitions 13 and 16) has been quite straightforward and the translation is almost literal. The contents of the reusable DROOLS file is shown in Figure 4. The last rule of the Figure is the declarative implementation of the predicate
the cases of norm instance violation and fulfillment. In our implementation in Drools, substitution instances are implemented as Set<Value> objects, where Value is a tuple String, Object .
The rest of the rules (see Definitions 15) are automatically generated from the institutional specifications and inserted into the DROOLS 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<Value> theta = new Set<Value>(); 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<Value> theta = new Set<Value>(); theta.add(new Value("D", D)); insert(new Holds(g1.getClause(0), theta)); end
The initial working memory is also automatically generated by inserting objects (facts) into the DROOLS 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));
The implementation of rule-based norm operationalisation has already been explored
in previous research. Some approaches [
Other recent approaches like [
[
We solve these issues by combining a normative language [
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 [
Mere syntactical translations are usually misleading in the sense that rule language
specific constructs are commonly used, constraining reusability [
DROOLS 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 conditions, and to perform an analysis on the algorithmic complexity of our implementation.
This work has been partially supported by the FP7-215890 ALIVE project. J. Va´zquezSalceda’s work has been also partially funded by the Ramo´n y Cajal program of the Spanish Ministry of Education and Science.