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.
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.
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.
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 L O with predicates and constants taken from an ontology O, and the logical connectives {¬, ∨, ∧}. The set of all possible well-formed formulas of L O is denoted as wf f (L O ) and we assume that each formula from wf f (L O ) is normalised in Disjunctive Normal Form (DNF). Formulas in wf f (L O ) 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 Θ = {x 1 ← t 1 , x 2 ← t 2 , ..., x i ← t i } as the substitution of the terms t 1 , t 2 , ..., t i for variables x 1 , x 2 , ..., x i in a formula f ∈ wf f (L O ).
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 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 [12]:
f D respectively represent the activation, maintenance, and deactivation conditions of the norm, f δ , f w 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 (inactive norms can be discarded from the monitoring process until they become active again). The activation condition f A 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 instance 3 The target condition f w 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 f D 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 f M defines the conditions that, when 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 driving 4 ; 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 [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 δ → ¬f M , since the maintenance condition expresses more than the deadline alone) and between the target and the deactivation condition (i.e., f w → f D , since the deactivation condition 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]):
, where E a 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:
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 s t at a specific point of time t as the set of predicates holding at that specific moment, where s t ⊆ 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 (L O ) 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 (L O ), 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 erson 1 } 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 erson 1 , role(Driver), enacts(P erson 1 , Driver)}
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 V S, each of them containing norm instances {�n i , Θ j �, �n i � , Θ j � �, ..., �n i �� , Θ j �� �}. We adapt the semantics for normative states from [11]: Definition 5. Norm Lifecycle: Let ni = �n, Θ� be a norm instance, where n = �f A , f M , f D , 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:
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 deactivated state is also not depicted because it corresponds in this case to the Fulfilled state. The set Γ of possible configurations of a Normative Monitor M I 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 -α ∈ P5 , 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 M I is defined by �Γ, E, �� where -E is the set of all possible events e = �α, p�
The inference rules for the transition relation � are depicted in Figure 2.
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 [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).
In this paper we use a simplified version of the semantics for production systems introduced 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 Event processed: ei = �α, p� ���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 ���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:
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:
Norm instance fulfilled:
Norm instance violation repaired: ∃n, n � ∈ N ∧ n � n � ∧ �n, Θ� ∈ vs ∧ n � n � ∧ �n � , Θ� ∈ f s ���N, R, P, C, O�, s, is, vs, f s�, e� � ���N, R, P, C, O�, s, is, vs − {�n, Θ�}, f s�, e� -A set of positive or negative patterns p = p + ∪ p − where a pattern is a term p i ∈ T (F, X ) and a negated pattern is denoted ¬p i . 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 = {r i } 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 = {a i } 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, WM 0 , R�, where R is a set of production rules over H = �P, X �.
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: P I := O ∪ {activated, maintained, deactivated, violated, instantiated, f ulf illed, event, repair, holds, has clause, countsas}
The initial working memory WM 0 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 = �f A , f M , f D , w�, these bindings will be:
WM n := {activation(n, f A ), maintenance(n, f M ), deactivation(n, f D )} As we assume the formulas from wf f (L O ) to be in DNF form: Definition 13. We can interpret a formula as a set of conjunctive clauses f = {f 1 , f 2 , ..., f N }, of which only one of these clauses f i holding true is necessary for f holding true as well:
For example, if f = (p 1 (x) ∧ p 2 (y) ∧ ... ∧ p i (z)) ∨ ... ∨ (q 1 (w) ∧ q 2 (x) ∧ ... ∧ q j (y)), then the initial facts to be in WM 0 will be:
WM 0 := � f � ∈f has clause(f, f � ) = {has clause(f, f 1 ), ..., has clause(f, f 2 )} 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 WM I for an institution I = �N, R, P, C, O� is:
The rule for the detection of a holding formula is defined as r hc f = �f � ⇒ ∅, {holds(f, σ)}, where we denote as �f � the propositional content of a formula f ∈ wf f (L O ) 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: r hc f1 = p 1 (x) ∧ p 2 (y) ∧ ... ∧ p i (z) ⇒ ∅, {holds(f 1 , {x, y, z})} r hc f2 = q 1 (w) ∧ q 2 (x) ∧ ... ∧ q i (y) ⇒ ∅, {holds(f 2 , {w, x, y})} Similarly as in Definition 14: Definition 15. The set of rules R hc I for detection of holding formulas for an institution I = �N, R, P, C, O� is:
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): r e = event(α, p) ⇒ ∅, {�p�} Rule for counts-as rule activation (2):
Rule for counts-as rule deactivation (3):
Rule for norm instantiation (4):
Rule for norm instance violation (5):
Rule for norm instance fulfillment (6):
Rule for norm instance violation repaired (7):
Definition 17. Following Definitions 13, 15 and 16, the set of rules for an institution I = �N, R, P, C, O� are: R I := R hc I ∪ {r h , r e , r ca , r cd , r ni , r nv , r nf , r nr } Definition 18. The production system PS I for an institution I will be, from Definitions 12, 14 and 17: PS I := �P I , WM I , R I �
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 [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.
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 [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: 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 [12].
The base rules (see Definitions 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 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. 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 constructs 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 modified 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 straightforward. 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 statements.
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 presented in this paper uses logic conditions that determine the state of a norm (active, 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 changing 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 JESS, DROOLS, SOAR or PROVA. In most of these systems rules are syntactically and semantically similar, 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.
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. 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.