-This paper presents ongoing work in the formal definition and implementation of a normative framework in Answer Set Programming. The framework uses as basis an existing action language and enriches it with a formal definition of norms (implementing standard deontic operators such as obligations and permissions). Properties of a norm's lifecycle such as active, inactive, violated are specified. We argue that such properties can serve as a reasoning basis for the agent's cycle. A partial implementation of the framework is then presented. An example is used in order to illustrate the application of the principles presented.
The field of normative systems is an active area where researchers try to find formalisations and mechanisms to model and reason about normative statements. There is a lot of formal work on the formalisation of norms, typically based in variants of monadic or dyadic Deontic Logic. In this way, normative systems predefine the desired behaviour in terms of deontic concepts (obligations, prohibitions, permissions), which typically are extended with other concepts such as deadlines, violations and sanctions. But there is few work on how to bring these theories into practice.
One of the main barriers for the use of deontic-like
formalisations is the lack of operational semantics [
Other attempts focus on extending existing operational
formalisms with some normative concepts. These attempts
mainly concern the design of action languages based on the
effects of axioms and drawing inferences from the axioms and
concentrate on ways of reasoning about actions. [
We are aware of the work in [
In the last two decades, one of the most successful logic
programming approach has been Answer Set Programming
(ASP) [
In this paper (Figure 1) we propose, based on a previous
normative formalisation [
Generic rules over the interpretation of norms, the interpretation of the action language and planning rules defined with respect to the action language might be added on top of the previous in order to be able to extract information over the agent’s state, know the possible actions to take, predict possible violations and foresee future paths. Our interest and focus can be summarised in the following four:
Currently, the three first of the above are implemented while the fourth and equally interesting issue is under research. In this paper we are aiming to provide the functionality of the aforementioned as well as some preliminary planning rules. We argue that the implemented layers leave further space for future research over the agent’s planning capabilities and behavioural choices.
The rest of the paper is structured as follows. Section II defines the stable model semantics which is the basis for Answer Set Programming. In section III we present a simple motivating example which supports our work while in section IV we detail the action and normative language used and define formal properties of the framework with respect to the aforementioned. A partial implementation of the action and normative language in Answer Set Programming is provided in sections V and VI and parts of the motivating example presented in the beginning are cited in section VIII. We conclude in section IX and summarise future work.
A signature L is a finite set of elements that we call atoms. A literal is either an atom a, called positive literal; or the negation of an atom not a, called negative literal. Given a set of atoms fa1; :::; ang, we write not fa1; :::; ang to denote the set of atoms fnot a1; :::; not ang. A normal clause, C, is a clause of the form a
b1; : : : ; bn; not bn+1; : : : ; not bn+m where a and each of the bi are atoms for 1 i n + m. In a slight abuse of notation we will denote such a clause by the formula a B+ [ not B where the set fb1; : : : ; bng will be denoted by B+, and the set fbn+1; : : : ; bn+mg will be denoted by B . We define a normal program P , as a finite set of normal clauses.
If the body of a normal clause is empty, then the clause is known as a fact and can be denoted just by a : or simply a. We write LP , to denote the set of atoms that appear in the clauses of P . We denote by HEAD(P ) the set faja B+; not B 2 P g.
The stable model semantics was defined in terms of the
so called Gelfond-Lifschitz reduction [
Let P be any normal program. For any set S LP , let P S be the definite program obtained from P by deleting (i) each rule that has a formula not l in its body with l 2 S, and then (ii) all formulae of the form not l in the bodies of the remaining rules.
Clearly P S does not contain not. Hence S is a stable model of P if and only if S is a minimal model of P S .
In order to illustrate this definition let us consider the following example:
Let S = fbg and P be the following logic program: b not a. b >.
c not b. c a.
We can see that P S is:
b >. c a.
Notice that P S has three models: f g b , fb; cg and fa; b; cg.
Since the minimal model amongst these models is fbg, we can say that S is a stable model of P .
III. EXAMPLE
The focus of interest of this example is to show how a contract and a set of instantiated norms over the repair of a car operate within the domain and normative environment implemented in ASP. Such a case is useful to demonstrate how reasoning and planning over the norms defined in a contract can be done throughout its execution.
Our scenario is as follows: Two actors, a Repair Company and a Client create a contract (RepairContract) over the repair of a broken car. Initially, the Client takes the car to the Repair Company. Once the car is there, the Repair Company has to repair it. Whenever it is repaired, the Client has to pay a previously agreed price. Once the car is repaired, the client has the right to make a complaint.
Figure 2 depicts a pseudo-diagram including the interesting states that the process will go into.
The focus of interest of this example is to show how the norms of an electronic contract (explicitly expressed as clauses in the contract) can be mapped into ASP rules and, in a combination with an appropriate action language, to reason over, plan future actions and detect violations within the agent’s scope.
The action description in our approach is done as in most
action description languages. In this work we use the
formalisation of [
Thus the alphabet of the action language A consists of two nonempty disjoint sets of symbols F and A. They are called the set of fluents and the set of actions. Fluents express the property of an object in a state of the world. A fluent or fluent literal (e.g. car_at_shop) is a positive literal or a strongly negated literal (a fluent preceded by :). A state is a collection of fluents. We say a fluent f holds in a state if f 2 . We say a fluent literal :f holds in if f 62 .
An action domain description D within the action language A consists of effect propositions of the following form: a causes f if p1; :::; pn; :q1; :::; :qr (4:1) where a is an action in A, f is a fluent literal in F (also called postcondition of the action a) and p1; :::; pn; q1; :::; qr are fluents (also called preconditions of the action a) in F .
We assume a set of initial observations O that consists of value propositions of the following form: f after a1; :::; am (4:2) where f is a fluent literal and a1; :::; am are actions. Intuitively that means that f will hold after the execution of a1; :::; am.
When a1; :::; am is an empty sequence then we write: initially f
(4:3) We also condense a set of value propositions of the form {initially f1; :::; initially fn} by initially f1; :::; fn
(4:4) The role of effect propositions is to define a transition function from states and actions to states. Given a domain description D, such a transition function should satisfy the following properties. For all actions , fluents g, and states : if D includes an effect proposition of the form (4.1) where f is the fluent g and p1; :::; pn; :q1; :::; :qr hold in then g 2 ( ; ); if D includes an effect proposition of the form (4.1) where f is a negative fluent literal :g and p1; :::; pn; :q1; :::; :qr hold in then g 62 ( ; ); if D does not include such effect propositions then g 2 ( ; ) iff g 2 ;
If such a transition function exists, then we say that D is consistent, and refer to its transition function by D. Given a consistent domain description D the set of observations O is used to determine the states corresponding to the initial situation, referred to as the initial states and denoted by 0. While D determines a unique transition function, an O may not always lead to a unique initial state.
We say 0 is an initial state corresponding to a consistent domain description D and a set of observations O, if for all observations of the form (4.2) in O, the fluent literal f holds in the state ( m; ( m 1; ::: ( 1; 0):::)) (We will denote this state by [ m; :::; 1] 0). We then say that ( 0; D) satisfies O.
Given a consistent domain description D and a set of observations O, we refer to the pair ( D; 0) where D is the transition function of D and 0 is an initial state corresponding to (D, O) as a model of (D, O). We say (D, O) is consistent if it has a model and say it is complete if it has a unique model.
We say a consistent domain description D in the presence of a set of observations O entails a query Q of the form (4.2) if for all initial states corresponding to (D, O), the fluent literal f holds in the state [ m; :::; 1] 0]. We denote this as D j=O Q.
Example 1: let’s assume frepair(Actor); set of fluents
that the set pay(Actor);
to our example, of actions A = complain(Actor)g, the F = fcar_at_shop; repaired(Actor); paid(Actor); complained(Actor)g and that the domain description consists of the following: repair(Actor) causes repaired(Actor) if car_at_shop pay(Actor) causes paid(Actor) complain(Actor) causes complained(Actor)
O = finitially car_at_shop; :repaired(rc); : paid(cl); : complained(cl)g. 2 A set of observations O is said to be initial state complete, if O only consists of propositions of the form (4.3) and for all fluents, either initially f is in O, or initially : f is in O, but not both.
Norms (clauses) express agreements between parties in the
form of deontic statements. In order to express the clauses we
have adopted a variation [
Since norms may have normative force only in certain
situations, they are associated with an activation condition.
Norms are thus typically abstract, and are instantiated when
the norm’s activation condition holds. Once a norm has been
instantiated, it remains active, irrespective of its activation
condition, until a specific expiration condition holds. When
the expiration condition occurs, the norm is assumed no
longer to have normative force. Independent of these two
conditions is the norm’s normative goal, which is used
to identify when the norm is violated (in the case of an
obligation), or what the agent is actually allowed to do
(in the case of a permission). Obligations and permissions
are the two norm types on which our framework focuses.
For every norm there is a maintenance condition which, if
does not hold while the norm is active then a violation is
considered to be taking place. Finally, for every norm there
exists another one (violation norm) indicating what happens
if it gets violated. Such properties of norms with respect to a
normative environment are implemented in section VI.
We assume a set of norms DS. A norm N in DS is
represented as a tuple of the form [
N ormT ype 2 {obligation, permission}
DeonticStatement is an action a in the set of actions
Anorm subset of A
an ActivatingCondition is of the type:
k1; :::; kn; :l1; :::; :ln, where k1; :::; kn; l1; :::; ln are
fluents in F
a DisactCondition is of the type:
u1; :::; un; :v1; :::; :vn, where u1; :::; un; v1; :::; vn
are fluents in F
a M aintenanceCondition is of the type:
w1; :::; wn; :z1; :::; :zn, where w1; :::; wn; z1; :::; zn
are fluents in F
a Actor is the actor responsible for the deontic statement
The definition and semantics of permissions are not trivial.
For example, it is dubious whether their existence can
be assumed within the context of an environment without
obligations. In [
Example 2: Figure 3 depicts the formal representation of the deontic statements within the contract of the example presented in the third section. 2
Below we give some definitions with respect to the action language and the deontic statements. Let a norm N be in the form of (4.5) and be a state.
N is activated in iff k1; :::; kn; :l1; :::; :ln hold in . We denote this as D j=DS; O; activated(N ). In the contrary case, N is not activated. We denote this as D j=DS; O; :activated(N ).
N is disactivated in iff u1; :::; un; :v1; :::; :vn hold in . We denote this as D j=DS; O; disactivated(N ). In the contrary case, N is not disactivated. We denote this as D j=DS; O; :disactivated(N ).
N is violated in iff at least one of w1; :::; wn; :z1; :::; :zn does not hold in . We denote this as D j=DS; O; violated(N ). In the contrary case, N is not violated. We denote this as D j=DS; O; :violated(N ). Queries with respect to norms consist of value propositions of the form: activated(N ) after a1; :::; am disactivated(N ) after a1; :::; am violated(N ) after a1; :::; am (4:6) where N is a deontic statement of the form (4.5), and a1; :::; am are actions in A.
We say a consistent domain description D in the presence of a set of observations O and a set of norms DS entails a query Q of the form (4.6) if for all initial states 0 corresponding to (D,O) the proposition activated(N ); disactivated(N ); violated(N ) holds respectively in the state [ m; :::; 1] 0. We denote this as D j=DS; O Q.
Example 3: Let’s assume the set of actions A, the set of fluents F and the set of observations O in example 1 and the set of norms DS in example 2. O is an initial state complete. Then the initial state corresponding to (D; O) will be
0 = finitially car_at_shop; :repaired(rc); : paid(cl); : complained(cl)g.
D j=DS; O activated(NRC2) since activated(NRC2) holds in the state [repair(rc)] 0.
D j=DS; O activated(NRC3) since activated(NRC3) holds in the state [repair(rc)] 0. where NRC2 is the norm RC2 and NRC3 is the norm RC3. 2 Proposition 1: Let D be a consistent domain description, O be an initial state complete set of observations and DS a set of deontic statements. If (D; O) is consistent then 8N 2 DS and for any state reached by D:
D j=DS;O; activated(N ) or D j=DS;O; :activated(N ) D j=DS;O; disactivated(N ) or D j=DS;O; :disactivated(N )
D j=DS;O; violated(N ) or D j=DS;O; :violated(N )
Planning: In the case of planning we are given a domain description D, a set of observations about the initial state O, a collection of deontic statements DS and a collection of fluent literals G = fg1; :::; ghg which we will refer to as goal. We are required to find a sequence of actions aa; :::; an such that for all 1 i h; D j=O gi after a1; :::; an and for all states passed throughout the execution of the actions, 6 9 such that D j=DS;O; violated(N ).
Given an action domain description D, a set of observations
O and a set of deontic statements DS we construct a program
that partially implements the above. The basic elements and
definitions of types are ( basic). The program putting into
effect (D; O) consists of three parts namely ef ; obs; in
which represent the effect propositions, observations and
inertia rules. In addition, norm and ( lc) partly implement
the norms specification and norm lifeycle. We denote the
union of basic [ ef [ obs [ in [ norm [ lc as .
In addition to the approach of [
f luent(f ) action(a) (1) The predicate f luent. For every fluent f 2 F we add the following rule to the program. (2) The predicate action. For every action a 2 add a rule: A we (3) The predicate time. The predicate is used to represent number of distinct times which in their turn represent the time flow. Initially time(T ) where T is a constant. B. Action rules
(1) Translating effect propositions ( ef ). The effect propositions in D are translated as follows. For every effect proposition of the form (4.1) if f is a fluent in F then the following rules are created: holds(f; T + 1)
terminated(a; T ); time(T ): ab(f; a; T )
terminated(a; T ); time(T ): else if f is the negative fluent literal :g then the following rules are created: : holds(g; T + 1)
terminated(a; T ); time(T ): ab(g; a; T )
terminated(a; T ); time(T ): Intuitively, predicate holds indicates whether a fluent’s value is true or false throughout time. The ab predicate represents changes of a fluent’s value at some specific timestep. (2) Translating observations ( obs). We intentionally omit observations of the type (4.2) and assume that all observations are of the type (4.3). The value propositions in O then are translated as follows. For every value proposition of the form (4.3) if f is a positive fluent literal then the following rule is made: holds(f; 1) : else if f is the negative fluent literal :g then the following rule is created: : holds(g; 1) (3) Inertia rules ( in). Besides the above, we have the following inertia rules. The first one makes sure that if no action is executed during a timestep then a fluent will keep holding a true value at the next timestep if it already holds true at the current timestep. The second one makes sure that if a fluent holds a true value and the action that is performed at some timestep does not make it false, then in the next timestep it will also hold true. The third one says that if no action is executed during a timestep then a fluent will keep holding a flse value at the next timestep if it already holds false at the current timestep. The fourth one makes sure that if a fluent holds a false value and the action that is performed at some timestep does not make it true, then in the next timestep it will also hold false. holds(F; T + 1)
holds(F; T ); not terminated(A; T ): holds(F; T + 1) : holds(F; T + 1) : holds(F; T + 1) holds(F; T ); terminated(A; T ); not ab(F; A; T ):
not holds(F; T ); not terminated(A; T ):
not holds(F; T ); terminated(A; T ); not ab(F; A; T ): The following proposition demonstrates how the holds predicate of will hold a true value at some time step if f holds true at some state reached by the function D. Proposition 2: Let D be a consistent domain description and O be an initial complete set of observations such that (D; O) is consistent. Let ( 0; D) be the unique model of (D; O) and M a stable model of . If f is a fluent in F then f 2 D( n; :::; D( 1; some T 2 N.
0)) iff holds(f; T ) 2 M for (4) Executability rules. It is assumed that every action might be executed whenever the conditions are fulfiled. We use the predicate executable to model the state where the preconditions of action are fulfiled and the action might be executed.
Thus, for every effect proposition of the form (4.1) the following is created: executable(a; T ) holds(p1; T ); :::; holds(pn; T ); not holds(q1; T ); :::; not holds(qn; T ); time(T ): holds(k1; T ); :::; holds(kn; T ); not holds(l1; T ); :::; not holds(ln; T ); time(T ): holds(u1; T ); :::; holds(un; T ); not holds(v1; T ); :::; not holds(vn; T ); time(T ): holds(w1; T ); :::; holds(wn; T ); not holds(z1; T ); :::; not holds(zn; T ); action(Action); time(T ): disact_condition(id; a; T ) maintain_cond(id; a; T ) Keeping in mind the normative semantics described in IV-B we define the rules that implement a norm’s lifecycle ( lc). obligation_activated(Id; Action; T ) activating_condition(Id; Action; T ); not active(Id; Action; T 1); action(Action); time(T ); obligation_id(Id): obligation_disactivated(Id; Action; T ) disact_condition(Id; Action; T ); active(Id; Action; T 1); action(Action); time(T ); obligation_id(Id): The two rules below define when an obligation is active. active(Id; Action; T ) obligation_activated(Id; Action; T ); action(Action); time(T ); obligation_id(Id): active(Id; Action; T ) active(Id; Action; T 1); not obligation_disactivated(Action; T ); action(Action); time(T ); obligation_id(Id):
estimated_time(a; t) ensures that an action starts whenever it is executable and an obligation to execute it becomes active. terminated(Action; T 2) started(Action; T 1); estimated_time(Action; EstimatedT ime); T 2 = T 1 + EstimatedT ime; time(T 2); time(T 1):
violation(Id; Action; T ) active(Id; Action; T ); not maintain_cond(Id; Action; T ); action(Action); time(T ); obligation_id(Id): detects a violation whenever a clause is active and the maintenance condition is not true.
The following propositions ensure the correctness of the program implementing the norm’s lifecycle properties. Proposition 3: Let D be a consistent domain description, O be an initial state complete set of observations such that (D; O) is consistent, DS a set of norms and M a stable model of . If there is a state reached by D such that D j=DS;O; activated(N ) then there is a T 2 N such that activating_condition(id; a; T ) 2 M where id is the unique identifier of the norm N and a is the DeonticStatement of the norm N .
Proposition 4: Let D be a consistent domain description, O be an initial state complete set of observations such that (D; O) is consistent, DS a set of norms and M a stable model of . If there is a state reached by D such that D j=DS;O; disactivated(N ) then there is a T 2 N such that disact_condition(id; a; T ) 2 M where id is the unique identifier of the norm N and a is the DeonticStatement of the norm N .
Proposition 5: Let D be a consistent domain description, O be an initial state complete set of observations such that (D; O) is consistent, DS a set of norms and M a stable model of . If there is a state reached by D such that D j=DS;O; violated(N ) then there is a T 2 N such that maintain_cond(id; a; T ) and active(id; a; T ) 2 M where id is the unique identifier of the norm N and a is the DeonticStatement of the norm N .
Example 4: Let D; O; DS be the domain description, observations and deontic statements of the examples 1 and 2, the program modeling D; O and DS and M one of its stable models. As seen in the example 3, in the state = [repair(rc)] 0 activated(NRC2) will hold. Thus, there for some T 2 N activating_condition(idRC2; repair(rc); T ) 2 M where idRC2 is the unique identifier of the norm RC2.
holds(at_shop; 0): time(0::30): The model will include the following: obligation_activated(rc1; repair(rc); 0) obligation_disactivated(rc1; repair(rc); 10) obligation_activated(rc2; pay(cl); 10) obligation_disactivated(rc2; pay(cl); 11) action_started(repair(rc); 0) action_f inished(repair(rc); 10) action_started(pay(cl); 10) action_f inished(pay(cl); 11) For further information and the ASP code, the reader is referred to the web page where the code is hosted: http://www.lsi.upc.edu/ panagiotidi/aspcode
IX. CONCLUSIONS, DISCUSSION AND FUTURE WORK
Assuming the environment that an agent operates can be
modelled by an action languange, norms impose restrictions
on the behaviour of the agent. This paper presents ongoing
work on the formal specification and development of a
framework that enables to model an action language with
respect to a normative environment. Semantics of the action
language are based on [
This piece of work can be extended in various directions. Formal aspects of planning need to be carefully considered and taken into consideration while advancing with the use of the framework in order to reach conclusions on the future states. A formal notion of goal needs to be introduced in order to reach a desired state. Another interesting aspect to be examined is the use of weighted rules when reasoning with respect to norms against the possible effects of one or more violations. This will ensure that each agent can make decisions on execution time based not only on a set of norms indicating a desired behaviour but also on criteria such as desires, preferences and time constraints.
This research has been funded by the FP7-215890 ALIVE project, funded by the European Commission. Javier VázquezSalceda’s work has been also partially funded by the "Ramón y Cajal" program of the Spanish Ministry of Education and Science.