Norm Compliance of Rule-Based Cognitive Agents

1 Introduction and Background

A significant research effort in MAS combine two perspectives [Broersen et al., 2002; Dastani et al., 2005; Dignum, 1999; van der Torre et al., 2008]: (a) a classical (BDI-like) cognitive model of agents; (b) a model of agents' behavior based on normative concepts. This combination leads to an account of agents' deliberation in terms of the interplay between mental attitudes and normative factors such as obligations.

In this approach agents' reasoning is typically embedded in rule-based non-monotonic systems, as one significant problem concerns the cases where the agent's intentions are in conflict with obligations.

If intentions prevail over obligations, this poses the question of agents' norm compliance. There are two strategies to get compliance in MAS. First, norm compliance is achieved by design, i.e., by stating that rules supporting the derivation of obligations always prevail over rules supporting conflicting intentions [Broersen et al., 2002; Governatori and Rotolo, 2008]. Second, compliance is ensured by stating that violations should result in sanctions or other normative effects [Governatori and Rotolo, 2009], as norms cannot limit in advance agents' behavior, but provide soft constraints which can be violated [Boella and van der Torre, 2004].

There are pros and cons in both approaches. But, independently of this, a research issue is still overlooked in the literature: what's the relation between norm compliance and intention reconsideration? Most of the existing models of intentional systems view the reconsideration of intentions as either a costly computational process or mainly dependent on the dynamics of beliefs [Singh, 1991; Rao and Georgeff, 1991; Shoham, 1993; Meyer et al., 1999; Wooldridge, 2000; Lorini, 2007; Lorini and Herzig, 2008]. Decision making in most agent systems is composed of two main activities like deliberation (deciding what intentions to achieve) and means/ends This paper explores how different types of intention reconsiderations can be modeled by applying techniques from revision theory to an extension of Defeasible Logic (DL) which embeds modalities for obligations and intentions [Governatori and Rotolo, 2008; Governatori et al., 2009] and alsothis is another novelty-makes use of path labels to keep track of the reasoning chains leading to "illegal" intentions.

The layout of the paper is as follows. Section 2 presents the extension of DL with path labels to reason about intentions and obligations; the purpose is to develop a formalism able to handle intention reconsideration when intentions conflict with obligations. Section 3 recalls a classification between different types of intentions and then shows how different techniques from revision theory can used in the proposed logical framework.

2 The Logical Framework

In line with [Governatori and Rotolo, 2008; Governatori et al., 2009] we develop a constructive account of the modalities O and I corresponding to obligations and intentions: rules for these concepts are thus meant to devise suitable logical conditions for introducing modalities. For example, rules such as a1, . . . , an ⇒O b and d1, . . . , dn ⇒I e if applicable, will allow for deriving Ob and Ie, meaning the former that b is obligatory, the latter that e is an intention of an agent.

In our language, for X ∈ {O,I}, strict rules have the form φ1, . . . ,φn →X ψ. Defeasible rules have the form φ1, . . . ,φn ⇒X ψ. A rule of the form φ1, . . . ,φn ❀X ψ is a defeater. Strict rules support indisputable conclusions whenever their antecedents, too, are indisputable; defeasible rules can be defeated by contrary evidence; defeaters cannot lead to any conclusion but are used to defeat some defeasible rules by producing evidence to the contrary.

Definition 1 (Language). Let Prop be a set of propositional atoms, Mod = {O,I}, and Lbl be a set of labels. The sets defined below are the smallest ones closed under the given construction conditions:

Literals

If q is a literal, ∼q denotes the complementary literal (if q is a positive literal p then ∼q is ¬p; and if q is ¬p, then ∼q is p);

Modal literals

Rules Rul =Rul X s ∪Rul X d ∪Rul X dft , where X ∈ {I,O}, s.t.

We use some obvious abbreviations, such as superscripts for the rule mode (I,O), subscripts for the type of rule, and Rul[φ ] for rules whose consequent is φ , for example:

We use A(r) to denote the set {φ1, . . . , φn} of antecedents of the rule r, and C(r) to denote the consequent ψ of the rule r.

An agent theory is the knowledge base which is used to reason about the agent's intentions and their interplay with a set of normative rules regulating the agent's deliberation.

Definition 2 (Agent Theory). An agent theory D is a structure (F,R O,R I ,≻) where (i) F ⊆ Lit∪ModLit is a finite set of facts; (ii) R O ⊆Rul O is a finite set of obligation rules; (iii) R I ⊆Rul I is a finite set of intention rules; (iv) ≻ is an acyclic (superiority) relation over (R I ×R I )∪(R O ×R O).

Definition 3. Apath based on an agent theoryD is a structure

where αlw , 1 ≤ w ≤ j -1 and 1w ≤ lw ≤ nw, is either a literal, modal literal, or a rule, such that j ≥0. If j ≥1, then

• either
• ω =-r where r ∈ R O ∪R I ; or
• ω ∈R O sd ∪ R I sd such that, if j =1 then A(ω) = /0; or
• if ω ∈ R O sd ∪ R I sd and j > 1, then ∀b ∈ A(ω) ∃αk j-1 such that either
• ∗ if b ∈Lit, then αk j-1 = b ∈ F, or
• ∗ if b=Xl ∈ModLit, then either αk j-1 = b ∈ F or l =C(αk j-1 ) : αk j-1 ∈ R X sd ;
• sd such that ∀b ∈ A(αxt )
• ∀αxt , 1<t ≤ j-1, αxt ∈R O sd ∪R I ∃αyt-1 such that either
• if b ∈Lit, then αyt-1 = b ∈ F, or

An empty path is a path where j = 0. A broken path is a path where ω = -r. A rule r occurs in a path iff r = αlw , or r = ω.

Example: if d ∈ F and we have the following rules

then we can obtain, e.g., the path [z,d]1[r,t]2[s,u]3[w]4.

Proofs are sequences of literals and modal literals together with the so-called proof tags +Δ, -Δ, +∂ and -∂. These tags can be labeled by modalities and paths: the modality indicates the mode of the conclusion (if it is an intention or an obligation), the path keeps track of the facts and rules used to obtain it. Hence, if X ∈ {O,I}, given an agent theory D, +Δ X Lq means that literal q is provable as modalized with X (e.g., Oq, if X = O) in D using the facts and strict rules in the path L, -Δ X Lq means that it has been proved in D that q is not definitely provable in D, +∂ X L q means that q is defeasibly provable as modalized with X in D using the facts and rules in L , and -∂ X L q means that it has been proved in D that q is not defeasibly provable in D. We will clarify later the structure of paths in the case of the negative proof tags.

Definition 4. Given an agent theory D, a proof in D is a linear derivation, i.e, a sequence of labelled formulas of the type +Δ X Lq, -Δ X Lq, +∂ X Lq and -∂ X Lq, where the proof conditions defined in the rest of this section hold.

Definition 5. Let D be an agent theory. Let # ∈ {Δ,∂} and X ∈ {O,I}, L be any path based on D, and P = (P(1), . . . ,P(n)) be a proof in D. A literal q is #L-provable in P if there is a line P(m), 1 ≤m≤ n, of P s.t. either

1. q is a modal literal Xp and P(m) =+# X L p or
2. q is a modal literal ¬Xp and P(m) =-# X L p.

A literal q is #L -rejected in P if there is a line P(m) of P s.t.

1. q is a modal literal Xp and P(m) =-# X L p, or
2. q is a modal literal ¬Xp and P(m) =+# X L p.

The definition of Δ X describes just forward (monotonic) chaining of strict rules: given 1 ≤ j ≤ n

(1.2.2) a is ΔL [α j ]-provable.

The path supporting q is built step by step by including the rules and facts used to obtain it. In the case of negative proof tags, any path involved is in fact empty, since there is no reasoning chain supporting q. See also Proposition 1 below.

Example 1. Consider the following agent theory:

Let us work on the proof conditions for Δ. The obligation Oa does not trigger any rule. The fact Ib triggers r1 (condition (1.1)): hence we obtain +Δ I [Ib][r1]c. Now, using proof condition (1.2), we trigger r2 to get +Δ I [Ib][r1][r2]a.

Consider now proof conditions for ∂ X : given 1 ≤ j ≤ n,

If P(n+1) =+∂ X L [α1, . . . , αn][r]q then (1) +Δ X L [α1, . . . , αn][r]q or (2) (2.1) -Δ X X ∼q ∈ P[1..n] and (2.2) ∃x ∈ R X sd [q] : (2.2.1) x = r and (2.2.2) ∀a ∈A(r) (2.2.2.1) a ∈ F, or (2.2.2.2) a is ∂L[αj]-provable, and (2.3) ∀s ∈ R X [∼q] either ∃a ∈ A(s): a is ∂Y -rejected, or (2.3.1) ∃t ∈ R X [q]: ∀a ∈ A(r) a is ∂Z -provable and t ≻ s. If P(n+1) =-∂ X L [α1, . . . , αn][r]q then (1) -Δ X L [α1, . . . , αn][r]q and (2) (2.1) +Δ X X ∼q ∈ P[1..n] or (2.2) ∀x ∈ R X sd [q] either (2.2.1) x ̸= r, or (2.2.2) ∃a ∈ A(r): (2.2.2.1) a ̸∈ F, and (2.2.2.2) a is ∂L[αj]-rejected, or (2.3) ∃s ∈ R X [∼q]: ∀a ∈ A(s) a is ∂Y [s]-provable, and (2.3.1) ∀t ∈ R X [q], ∃a ∈ A(r): a is ∂Z -rejected or t ̸≻ s, where [r] = [-r] if ∀a ∈ A(r) a ∈ F, or a is ∂L [α j ]-provable.

To show that a literal q is defeasibly provable with the mode X we have two choices: (a) We show that q is already definitely provable; or (b) We need to argue using the defeasible part of an agent theory D. For this second case, some (sub)conditions must be satisfied: First, we need to consider possible reasoning chains in support of ∼q with the mode X, and show that ∼q is not definitely provable with that mode (2.1 above). Second, we require that there must be a strict or defeasible rule with mode X for q which can be applied (2.2 above). Third, we must consider the set of all rules which are not known to be inapplicable and which permit to get ∼q with the mode X (2.3 above). Essentially, each such a rule s attacks the conclusion q. For q to be provable, s must be counterattacked by a rule t for q with the following properties: t must be applicable and must prevail over s. Thus each attack on the conclusion q must be counterattacked by a stronger rule. In other words, r and the rules t form a team (for q) that defeats the rules s. The mechanism for handling paths is basically the one for definite conclusions. The only difference is that here we can have broken paths when a rule is made applicable but is defeated by a stronger rule: in this case, the path keeps track of the defeated rule r, which is marked as -r.

• Proposition 1. (a) For -Δ: if condition (1) holds, then L [α1, . . .αn][r] is an empty path.
• (b) For -∂: if condition (2.2) holds, then L[α1, . . .αn][r] is an empty path;
• (c) For -∂: if condition (2.3) holds and L[α1, . . .αn][r] is broken, then rule r is applicable.

Sketch. Consider the case (a): if condition (1) holds, this means that there is no path and proof supporting q, and so L[α1, . . .αn][r] must be empty. The same argument applies to the case (b). Consider case (c): here, by construction there is a path and a proof supporting the antecedents of r, even though any r is defeated. Hence r is applicable.

Example 2. Let us expand the theory in Example 1:

Since the defeasible part of the theory cannot affect the derivation obtained using the monotonic part, which is the same of Example 1, the definite conclusions do not change. The fact Ib triggers r4, which conflicts with r3; if r3 could prevail, we would have -∂ O[-r3]e, but this is not the case since r4 is stronger than r3, thus leading to +∂ O[Ib][r4]e. The fact d makes r5 applicable, and so +∂ I [d][r5]¬e. The rule r6 is always applicable, thus supporting +∂ I [r6]¬e. Finally, from the Ib and the last two conclusions we obtain +∂ O[d][r5,Ib][r7]f and +∂ O[r6,Ib]f .

Definition 6. Given an agent theory D, D ⊢ ±# X l (i.e., ±# X l is a conclusion of D), where # ∈ {Δ, ∂} and X ∈ {c,O, I}, iff there is a proof P = (P(1), . . . ,P(n)) in D such that P(n) = ±# X l .

Definition 7. Given a theory D, the universe of D (U D ) is the set of all the atoms occurring in D; the extension of D (E D ), is defined as follows:

where for X ∈ {I,O}

3 Compliance and Revising Intentions

3.1 Conceptual Background

Suppose the agent's intentions conflict with some obligations. If we assume that obligations are unchangeable, the possibility to avoid violations relies on the possibility to handle rules for intentions.

As we argued elsewhere [Governatori and Rotolo, 2008; Governatori et al., 2009], we can conceptually distinguish between different types of intentions: unchangeable intentions, strong intentions and weak intentions. The first type corresponds in our logic to intentional facts of an agent theory (elements of F), the second type to definite conclusions (+Δ I ), the third to defeasible conclusions (+∂ I ). Unchangeable intentions cannot be reconsidered in any case (see [Governatori et al., 2009] for a discussion on this issue). To give up a strong intention we have necessarily to change (revise) the theory (i.e., we have to modify the strict rules), while we can abandon a weak intention if we have an exception to it without having to change the theory. To illustrate this point let us consider the following rules:

Suppose the same connections are expressed as defeasible rules:

In both cases we obtain Ib given a as a fact. However if both a and c are given then from (1) we get an inconsistency, since definite conclusions cannot be blocked and we have to revise the theory. If we use belief revision to change the theory then we have to remove r1 from the theory. A consequence of this operation is that we are no longer able to derive Ib from a. An alternative would be to use base revision instead of belief revision. If this strategy is taken then r1 is changed into

Again, it is not possible to obtain Ib from a. To derive it we have to supplement the theory with the information whether c or ¬c is definitely the case, increasing then the cognitive burden on the agent.

If the same information were encoded as weak intentions, as in (2), then we would not suffer from the above drawback, since (2) prevents the conclusion of an inconsistency (in case we do not specify that r′2 is stronger than r1, we are not able to conclude Ib nor I¬b). Indeed, the defeasibility of weak intentions makes it possible to block the application of the intention to the particular case without reconsidering it. This is in agreement with [Bratman, 1987]. This way the amount of deliberation required for intention re-consideration can be minimized to some extent.

Unfortunately, if the first and compelling purpose is to make agents compliant, not in all cases the defeasibility of intentions is the solution. Indeed, if a theory containing (2) allows for deriving Ob, there is no way to recover, unless we change the theory.

3.2 A Simple Model

Let us first formally characterize the notion of compliance to a norm:

Definition 8 (Rule Fulfilment and Violation). An agent theory D = (F,R O,R I ,≻) fulfil a rule r ∈ R O sd iff, if D ⊢ +∂ O LC(r), then, either

• if C(r) is a positive literal l (r is a conditional obligation), then there is an Y such that D⊢+∂ I Y l, or
• if C(r) is a negative literal ¬l (r is a conditional prohibition) for any L, D⊢-∂ I Ll or D⊢+∂ I L¬l.

D violates the rule r whenever D does not fulfil r. D is compliant iff D does not violate any rule in it.

As we briefly discussed in Section 3.1, an option to recover from violations and reinstate compliance is to revise intentions by using AGM techniques. This idea looks natural (see e.g. [Cawsey et al., 1993; Lorini, 2007]). However, it is far from obvious how to do it in DL. Fortunately, AGM fundamental operations have been defined for propositional DL in [Billington et al., 1999].

The first step is thus to extend [Billington et al., 1999]'s notions of expansion and contraction to cover DL with modalities, which is trivial. Consider an agent theory D and suppose we want to expand the extension of D with c = Ip1, . . . , Ipn:

where

Thus, we add rules that prove p1, . . . pn as intentions; these rules are always applicable and are strictly stronger than any possibly contradicting rules. This solution looks useful to deal with many cases of violation.

Example 3. Consider the following theory D.

Here we obtain, among other conclusions, +∂ O[a][r1][r2]c. To be compliant, we should be able to derive that c is intended, but this is not possible. We have here that

-∂ I [a][r1][-r4]c. What we can do is to expand D with Ic by simply adding a rule w and applying (4). Since this operation satisfies AGM postulates for expansion [Billington et al., 1999], this guarantees that Ic is added to the positive extension of D. Hence, we obtain +∂ I [w]c and make D compliant.

Let us define the procedure explained in Example 3.

Definition 9 (Positive Revision). Let D= (F,R O,R I ,≻) be an agent theory. If D violates the rules r1, . . . ,rn ∈ R O , then D+c where c = Ip1, . . . ,Ipn such that C(r1) = p1, . . . ,C(rn) = pn.

Let us adjust [Billington et al., 1999]'s definition of contraction. Here, too, we trivially extends [Billington et al., 1999]'s. If we want to contract c = Ip1, . . . ,Ipn in D, then:

(5) blocks the proof of Ip1, . . . ,Ipn. It is ensured that at least one of the Ipis will not be derived. The new rules in R I′ are such that, if all but one Ipi have been obtained, a defeater with head ∼pj is triggered. The defeaters are not weaker than any other rules, so the defeater cannot be "counterattacked" by another rule, and pj will not be proven as an intention.

Example 4. Consider the following theory D.

We obtain, among other conclusions, +∂ O[a][r1][r2]c. To be compliant, we should derive that Ic, but we obtain the opposite through r3. More precisely, we get +∂ I [Id][r3]¬c. What we can do is to contract Id by simply adding a defeater s :❀I ¬c and thus applying (5). Since this operation satisfies AGM postulates for contraction [Billington et al., 1999], this guarantees that Id is removed from the positive extension of D and added to the negative extension.

Definition 10 (Negative Revision). Let D = (F,R O,R I , ≻) be an agent theory. If D violates the rules r1, . . . ,rn ∈ R O , then D-c where c = Ip1, . . . ,Ipn such that C(r1) = ¬p1, . . . ,C(rn) = ¬pn.

Definitions 9 and 10 guarantee to recover from violations, are very simple, and directly exploit techniques and results from [Billington et al., 1999]. Also, they do not make any essential use of paths, which sometimes may look cumbersome. However, they have two serious drawbacks: (a) They work only on the defeasible part of agent theories, and so cannot be used to recover from violations when these are caused by strong intentions (see the discussion in Section 3.1); (b) They apply only to the last rule of the reasoning chains supporting "illegal" intentions.

To overcome the above difficulties, DL with paths is useful.

3.3 Refinements: Using Paths

The advantage of using paths is that we can easily identify (i) which rules have been violated, and (ii) which rules for intentions have determined the violation of an obligation.

Let us see when Definitions 9 and 10 clearly fail while DL with paths succeeds.

Example 5 (Strong Intentions). Consider this theory:

We have two reasons for the violation of r2 (indeed, we obtain +∂ O[Ib][r2]c). In fact, we can derive +Δ I [a][r1]¬c and +Δ I [Ib][r3,a][r4]¬c. Since strict rules cannot be defeated, the only solution is rule removal. Hence, we have to operate over r1 but we are free to remove either r3 or r4. For example, if we prefer not to remove r4, we will successfully get compliance by removing r1 and only r3.

Definition 11 (Rule Removal). Let D= (F,R O,R I ,≻) be an agent theory. For each r ∈ R O sd such that the paths L1, . . .Ln are the ones based on D such that D ⊢ +Δ I L1p, . . . ,D ⊢ +Δ I Ln p and D ⊢ +∂ O Y C(r), where C(r) = ¬p, the theory D-X is such that

• X = {w1, . . . ,wm} is the smallest set of rules in R I such that, for each k ∈ {1, . . . ,n}, there is at least a wj ∈ X that occurs in Lk,
• R I-X =R I -X, and
• F-X =F, R O-X =R O , and ≻-X=≻.

Let us work on weak intentions only. The following definition proposes intention retraction for DL with paths by exploiting the contraction of intentions as framed in (5).

Definition 12 (Contraction with Paths). Let D = (F, R O, R I ,≻) be an agent theory. For each r ∈ R O sd such that the paths L1, . . .Ln are the ones based on D such that D ⊢ +∂ I L1 p, . . . , D ⊢ +∂ I Ln p and D ⊢ +∂ O Y C(r), where C(r) = ¬p, the theory D♭p = (F,R O,R I′ ,≻′ ) is such that

• (i) R I′ =R I ∪{s :❀I ∼q}∪{t :❀I ∼x},
• (ii) ≻′=≻ - [{rk ≻ s|rk ∈ R I [∼C(s)], rk occurs in Lk ∀k ∈ {1, . . . , n}}∪{w ≻ t | for each path M[-w] based on D such that C(w) = x, either x = p or w occurs in Lk ∀k ∈ {1, . . . , n}}].

Example 6 (Paths). Consider the following agent theory:

Like in Example 5, we obtain +∂ O[Ib][r2]c. We also derive +∂ I [a][r1]¬c and +∂ I [Ib][r3,a][r4]¬c, which violate rule r2. Definition 12 allow us to add, for example, a defeater for c which is stronger than r1 and another defeater for ¬d which is stronger than r3. Hence, as we have already seen in Example 5, Definition 12 does not only provide tools to affect the rules r1 and r4 that directly prove illegal intentions, but also rules preceding them in the involved path (e.g., r3).

Proposition 2 (Success). Let D= (F,R O,R I ,≻) be an agent theory. If, for each r ∈ R O sd we have D ⊢ +∂ O Y C(r), where C(r) = ¬p, and for the paths L1, . . .Ln based on D

Sketch. Case (a): By construction, Definition 11 guarantees that at least one strict intention rule is removed in every path based on D supporting Ip.

Case (b): An inspection of the proof conditions for ∂ shows that Definition 12 successfully blocks the derivation of Ip, unless it is derived using only strict rules. Notice that condition (ii) in Definition 12 ensures that, in case the attacks made by the defeaters s activate other (previously defeated) rules supporting Ip, these last potential derivations are made unsuccessful.

4 Summary and FutureWork

In this paper we presented an extension of DL with path labels to reason about intentions and obligations The formalism was able to handle intention reconsideration when the agent's intentions conflict with obligations. In particular, we showed that the reconsideration of different types of intentions can be modeled using different techniques from revision theory.

This is a preliminary step towards modeling intention reconsideration in DL. A number of open issues should be addressed. First: according to [Governatori and Rotolo, 2010] if I violate a norm r but I comply with an obligation which is meant to compensate the violation of r, I am still compliant. In [Dastani et al., 2005] we introduced the operator ⊗ to handle compensations in a version of DL with modalities but without paths. What happens if we combine ⊗ with DL with paths? Second: in [Governatori and Rotolo, 2008] we showed that the extensions of agent theories, in some modal versions of DL, can be computed in linear time. We will have to check whether this is preserved in the new logic. Third: we have to investigate the properties of the new operations over agent theories. In particular, we have to better study how to minimize changes. Finally: another possibility is not to revise the set of rules for intention, but to change rule priorities [Governatori et al., 2010]. Also this question is left to a future research.

Acknowledgments

This paper benefited from conversations with Guido Governatori and Leon van der Torre. Another version of it was presented at the RuleML 2011 symposium [Rotolo, 2011].