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 [1]. Without clear operational semantics an agent cannot clearly reason about the influence of these norms in its practical reasoning mechanism. Some attempts have been made to reduce deontic formalisations of norms into operational formalisations based on, e.g. dynamic Logic [2] or Linear Temporal Logic [3], but often such formalisations cannot really be used at execution time.
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. [4] presents an action description language capable of expressing causal laws which describe effects of actions as well as statements about values of fluents in possible states of the world. Work of the same authors covers some aspects of reasoning over dynamic domains [5] and representation and reasoning over properties of actions [6]. In [7] the authors intent to provide a logic based language in order to represent authorizations and obligation policies within dynamic environments as well as methods for checking compliance of performed actions with the defined policies. Still, the work lacks support for time. Insight into intelligent decision and possible prediction of desired or nondesired behaviours in advance seems to be absent too.
We are aware of the work in [8] in which the authors present a language for implementing multi-agent systems consisting of individual agents that interact with a computational organization specified in terms of roles, norms and sanctions. Still, this piece of work adopts an organisation-centered view more on the flexible role enactment within a BDI cycle while ours assumes a static role enactment and focuses on a decision making mechanism inferring possible future action taking and violated states.
In the last two decades, one of the most successful logic programming approach has been Answer Set Programming (ASP) [9]. ASP is the realization of much theoretical work on Non-monotonic Reasoning and Artificial Intelligence applications. It represents a new paradigm for logic programming that allows, using the concept of negation as failure, to handle problems with default knowledge and produce non-monotonic reasoning. Since its inception, ASP has been regarded as the computational embodiment of Nonmonotonic Reasoning and a primary candidate for an effective knowledge representation tool. This view has been boosted by the emergence of highly efficient solvers for ASP [10], [11], [12]. The efficiency of the answer set solvers has allowed to increase the list of ASP's practical applications, e.g., planning [13], Bioinformatics [14], [15], argumentation theory [16], etc. Answer Set Programming does not represent a conventional logic programming approach as PROLOG. Usually an answer set program P can be regarded as a specification of a given problem where each answer set (a model) of P represents a possible solutions of the given problem.
In this paper (Figure 1) we propose, based on a previous normative formalisation [17], a methodology to represent such normative frameworks in Answer Set Programming. This representation can be used as a basis for decision making procedures as well as planning methodologies. We use as example the obligations between two actors (a Insurance Company and a Repair Company) defined in a electronic contract. This contract is composed by deontic clauses which will become norms of the expected behaviour of the contractual parties. Therefore each instantiated contract becomes a normative context at execution time. The work is at a preliminary state. Still, integrated within an agent's operating cycle, such a framework can operate as the brain of the agent [18], providing the necessary information over the current state of the world such as pending norms and currently violated obligations. Additional layers of planning rules and preferred choices might lead to the desired intelligence and flexibility an agent needs to perform in a normative environment. We define several layers of abstraction (Figure 1). An agent (possibly interacting with an ontology) can interpret the environment it operates in through an action language. The deontic restrictions (which in this paper come from a contract, but in other scenario could come from a Institutional specification) provide guidelines over the agent's behaviour and are formalised through a deontic framework.
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:
• An action language representation • Contract (viewed as a set of norms) representation • Generic rules over the norm lifecycle • Generic planning and choice rules 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.
In this section, we present some basic definitions w.r.t. normal programs and the stable model semantics.
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 {a 1 , ..., a n }, we write not {a 1 , ... 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 L P , to denote the set of atoms that appear in the clauses of P . We denote by HEAD(P ) the set {a|a ← B + , not B − ∈ P }.
The stable model semantics was defined in terms of the so called Gelfond-Lifschitz reduction [19] and it is usually studied in the context of syntax dependent transformations on programs. The following definition of a stable model for normal programs was presented in [19]:
Let P be any normal program. For any set S ⊆ L P , 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 ∈ 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 = {b} and P be the following logic program:
c ← a. We can see that P S is: b ← . c ← a. Notice that P S has three models: {b}, {b, c} and {a, b, c}. Since the minimal model amongst these models is {b}, we can say that S is a stable model of P .
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 [6] but adapt several rules to fit our requirements.
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 ∈ σ. We say a fluent literal ¬f holds in σ if f ∈ σ.
An action domain description D within the action language A consists of effect propositions of the following form:
where a is an action in A, f is a fluent literal in F (also called postcondition of the action a) and p 1 , ..., p n , q 1 , ..., q r 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:
where f is a fluent literal and a 1 , ..., a m are actions.
Intuitively that means that f will hold after the execution of a 1 , ..., a m . When a 1 , ..., a m is an empty sequence then we write:
We also condense a set of value propositions of the form {initially f 1 , ..., initially f n } by
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 σ:
Norms (clauses) express agreements between parties in the form of deontic statements. In order to express the clauses we have adopted a variation [20] [17] of the norm representation defined in [3].
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 [17]: <N ormT ype, DeonticStatement, ActivatingCondition, M aintenanceCondition, DisactCondition, Actor> (4.5) such that:
• N ormT ype ∈ {obligation, permission} 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 [21] the authors discuss the different types of permissions and their role in deontic logic. We assume that permissions are an explicit indication on what an actor can perform. As in standard deontic logic we assume further that whenever there is an obligation it is always implied that the same is a permission too (O a → P a , axiom D of deontic logic).
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 k 1 , ..., k n , ¬l 1 , ..., ¬l n hold in σ. We denote this as D |= DS, O,σ activated(N ). In the contrary case, N is not activated. We denote this as D |= DS, O,σ ¬activated(N ). • N is disactivated in σ iff u 1 , ..., u n , ¬v 1 , ..., ¬v n hold in σ. We denote this as D |= DS, O,σ disactivated(N ). In the contrary case, N is not disactivated. We denote this as D |= DS, O,σ ¬disactivated(N ). • N is violated in σ iff at least one of w 1 , ..., w n , ¬z 1 , ..., ¬z n does not hold in σ. We denote this as D |= DS, O,σ violated(N ). In the contrary case, N is not violated. We denote this as D |= DS, O,σ ¬violated(N ). .., g h } which we will refer to as goal. We are required to find a sequence of actions a a , ..., a n such that for all 1 ≤ i ≤ h, D |= O g i after a 1 , ..., a n and for all states σ passed throughout the execution of the actions, ∃σ such that D |= 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 [6], we assume that actions are durative. That is, they have a starting and ending time and a duration which is the interval between the two. For this, we use predicates like started and teminated to indicate the time that an action starts being executed and the time it terminates.
We introduce here some predicates (π basic ) which avoid the program to have weakly restricted rules.
(1) The predicate f luent. For every fluent f ∈ F we add the following rule to the program.
(2) The predicate action. For every action a ∈ A we add a rule: action(a) ← .
(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.
(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:
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 ), terminated(A, T ), not ab(F, A, T ).
¬ holds(F, T + 1) ← not holds(F, T ), not terminated(A, T ).
¬ holds(F, T + 1) ← 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 . (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(p 1 , T ), ..., holds(p n , T ), not holds(q 1 , T ), ..., not holds(q n , T ), time(T ).
We assume that for every norm N of the form (4.5) a unique id id is assigned to it. In order to represent a norm, a rule of the respective type below is made (π norm ). activating_condition(id, a, T ) ← holds(k 1 , T ), ..., holds(k n , T ), not holds(l 1 , T ), ..., not holds(l n , T ), time(T ).
disact_condition(id, a, T ) ← holds(u 1 , T ), ..., holds(u n , T ), not holds(v 1 , T ), ..., not holds(v n , T ), time(T ).
maintain_cond(id, a, T ) ← holds(w 1 , T ), ..., holds(w n , T ), not holds(z 1 , T ), ..., not holds(z n , T ), action(Action), time(T ).
Keeping in mind the normative semantics described in IV-B we define the rules that implement a norm's lifecycle (π lc ). 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).
We assume that for every action we have an estimated duration on its execution time: estimated_time(a, t) ← .
where t is a constant.
The generic rule started(Action, T ) ← obligation_activated(Id, Action, T ), executable(Action, T ), time(T ), action(Action), obligation_id(Id).
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).
The generic rule 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. and DS and M one of its stable models. As seen in the example 3, in the state σ = [repair(rc)]σ 0 activated(N RC2 ) will hold. Thus, there for some T ∈ N activating_condition(id RC2 , repair(rc), T ) ∈ M where id RC2 is the unique identifier of the norm RC2.
In our example, the initial observation can be: holds(at_shop, 0). 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 [6] and the language is partially implemented and further enriched with temporal projection. The deontic statements such as obligations and permissions as well as properties related to the norm's lifecycle (activation, disactivation, violation) are formalised and implemented according to [20]. An attempt to define and apply planning techniques within the formal model and the implementation is made. 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ázquez-Salceda's work has been also partially funded by the "Ramón y Cajal" program of the Spanish Ministry of Education and Science.