This paper is a characterisation in terms of Weak Constraints both for Minimal Generalised Answer Sets and Optimal Answer Sets, of an updates semantics that provides a solid foundation for the implementation of a system to debug knowledge bases. The proposed system can be employed both to identify conflicts with upcoming information from a dynamic changing environment, and to locate the source of conflict from a given inherent inconsistent knowledge base that is static. In addition, this work introduces some formal specifications towards the implementation of a debugging solver with no need to use a total-order semantics. Accordingly, the two-fold contribution of this work is to show a simpler theoretical framework of preferences characterised in DLV, as well as general foundation to debug both static and dynamic logic programs.
As one of the major and traditional topics in Artificial Intelligence over the last years, Knowledge Representation and Reasoning has proved to be a discipline that provides strong theoretical methods to manage knowledge bases. In particular, this topic has become more widely applied in administration of knowledge in Ambient Intelligence and of intelligent (rational) agents, and it is especially useful in situations of incomplete knowledge from a changing environment. This paper is a proposal to debug knowledge bases that change over time, which is an important topic both in static and dynamic knowledge, and has to be solved before other more-general problems of multiple agents. The proposed framework shall be useful both to find conflicts when new contradictory information arises, and to locate conflicting information from a given static knowledge base, with contradictory information.
There are several earlier related works that have addressed the problem of
debugging knowledge bases. For instance, Balduccini and Gelfond [
As a result, the present work introduces a general alternative to those
proposals, and it addresses both kinds of problems into a single framework, and
without need of an expanded language. This paper introduces a prototype for
updates of knowledge bases, into a more concise and precise method of updates.
In addition to that, it introduces some formal specifications for its
implementation on top of an ASP solver called DLV [
To begin with, one of the latest proposals aiming to meet most well-known
principles for changing knowledge bases comes from [
In need of a solver for the semantics of Acosta G. [
In general, this paper is organised as follows. It starts with preliminary notation and foundation in Section 2, ending with the main definitions of the implemented semantics (Section 2.4). The core of the paper is Section 3, divided into preferred models and debugging knowledge bases. The paper ends with a section of some concluding remarks on the proposal. 2
In this section we expect the reader to be familiar with basic notions of logic programming in ASP and non-monotonic reasoning from the literature. Before going straight to the system description, though, a short background is still necessary. 2.1
The following gives the description of ASP, which is identified with other names
like Stable Logic Programming or Stable Model Semantics [
LASP is a language of propositional logic with propositional symbols: a0, a1, . . . ; connectives: “,” (conjunction) and meta-connective “;”; disjunction, denoted as “|”; ← (derivation, also denoted as →); propositional constants ⊥ (falsum); (verum); “¬” (default negation or weak negation, also denoted with the not word); “∼” (strong negation, equally denoted as “−”); auxiliary symbols: “(”, “)” (parentheses). The propositional symbols are also called atoms or atomic propositions. A literal is an atom or a strong-negated atom. A rule ρ is an ordered pair Head(ρ) ← Body(ρ).
With the notation introduced in Definition 1, one may construct clauses of the following general form that are well known in the literature. Definition 2 (EDLP). An extended disjunctive logic program is a set of rules of form 1 ∨ 2 ∨ . . . ∨ l ← l+1, . . . , m, ¬ m+1, . . . , ¬ n (1) where i is a literal and 0 ≤ l ≤ m ≤ n.
Although ASP is our main basis, a more flexible means is necessary to set up preferences amongst models, so that one may choose the most appropriate, according to general principles and postulates. One of such intermediate mechanisms is Abductive Logic Programming, due to Kakas and Mancarella, briefly presented in the following. 2.2
Balduccini and Gelfond [
a pair Ψ, A∗ where Ψ is an arbitrary program and A∗ a set of literals, called abducibles.
On the other hand, there already exists a semantics to interpret abductive programs, called generalised answer sets (GAS) due to Kakas and Mancarella.
a generalised answer set of the abductive program Ψ, A∗ if and only if ∆ ⊆ A∗ and M(∆ ) is an answer set of Ψ ∪ {α ← | α ∈ ∆ }.
In case there are more than one generalised answer sets, an inclusion order may be established:
eralised answer sets of Ψ, A∗ . The relation M(∆ 1) ≤A∗ M(∆ 2) holds if and only if ∆ 1 ⊆ ∆ 2.
Last, one can easily establish the minimal generalised answer sets from an abductive inclusion order with the following definition.
imal generalised answer set (MGAS) of Ψ, A∗ if and only if M(∆ ) is a generalised answer set of Ψ, A∗ and it is minimal with respect to its abductive inclusion order. 2.3
Leone et al. [
an expression of the form (:∼ 1, . . . , k, ¬ k+1, . . . , ¬ m[w : p]), where for 0 ≤ k ≤ m, 1, . . . , m are literals, while w (the weight) and p (the level, or layer) are positive integer constants or variables.
In addition, Ω (Ψ ) shall denote the finite set of weak constraints occurring in a given program Ψ . Likewise, a ω-program is an EDLP with weak constraints.
In order to provide a more syntactic sugar and a more ASP flavour, another way to define a weak-consitraint expression from Definition 7 is as follows.
pression of the form [w : p] ← 1, . . . , k, ¬ k+1, . . . , ¬ m (2) where for 0 ≤ k ≤ m, 1, . . . , m are literals, while w (the weight) and p (the level, or layer) are positive integer constants or variables.
From now on, the weak-constraints form in Definition 7 shall be employed in the context of DLV-code, while Definition 8 in other more-general contexts.
Similarly to integrity constraints in Section 2.1, one may say that a weakconstraint rule ρ = ([w : p] ← 1, . . . , k, ¬ k+1, . . . , ¬ m) is violated by an answer set S of a program Ψ \ {ρ} if the following three conditions hold: 1. ρ ∈ Ψ 2. { 1, . . . , k} ⊆ S 3. { k+1, . . . , m}
Additionally, Leone et al. simplify the combination of weights in levels by
introducing a function HΨ (S) that grows in direct proportion to the weight and
level of the weak constraint as follows:
Definition 9 (Objective Function, HΨ (S), [
(fΨ (i) · i=1 ρ∈NiΨ (S) weight (ρ)) where wmΨax and lmΨax denote the maximum weight and maximum level over the weak constraints in Ψ , respectively; NiΨ (S) denotes the weak constraints at level i violated by S, and weight (ρ) the weight of weak constraint ρ.
Finally, the best models of such a logic program are those that minimise the number of violated weak constraints.
constraints, a set S is a weak-constraint model of Ψ if and only if 1. S is an answer set of Ψ \ Ω (Ψ ) 2. HΨ (S) is minimal over all the answer sets of Ψ . where Ω (Ψ ) is the finite set of weak constraints in Ψ .
When the underlying semantics is ASP in Definition 10, a weak-constraint model (or also ω-model) is also known as Optimal Answer Set. Moreover, the language of EDLP’s with weak constraints shall be called DATALOG∨,ω, which is very similar to the notation from the literature. 2.4
Now let us briefly introduce the semantics to propose a preference
characterisation and implementation, by the following definitions, taken from [
Formally, an α-relaxed rule is a rule ρ that is weakened by a default-negated
atom α in its body: Head(ρ) ← Body(ρ)∪{¬α}. In addition, an α-relaxed program
is a set of α-relaxed rules. A generalised program of A∗ is a set of rules of form
{ ← | ∈ A∗}, where A∗ is a given set of literals.
Definition 11 (•-update Program, [
Last, the associated models S of the new knowledge base correspond to the answer sets of a •-update program as follows.
Definition 12 (•-update Answer Set, [
Having introduced all necessary background and notation to better understand the results of this proposal, let us present the main results in the following sections. 3
There are two well-known major efficient solvers to compute ASP with a vast
background of implementation and research. They are DLV [
To begin with, an approach to implement an update semantics in MGAS
was first suggested in [
Indeed, a justification from [? ] to use ODLP is that there is a solver available
named PSmodels3 that is an extension to SMODELS [
This section is an introduction to the use of DLV’s Weak Constraints for
their characteristics of preferences [
This approach consists in transforming updates of ELP’s into a ω-program. The answer sets of such a program shall prove to coincide with the GAS’s of the abductive program from the update. So, let us start by introducing some more notation.
A Simple Weak Constraint (ω ) is an expression of the form
[w : p] ← where is a literal; and w and p are optional weight and level parameters as in Definition 7.
Before introducing a result derived from ω , let us introduce some new notation: read LΩ (Ψ) as the signature of the weak constraints occurring in Ψ , which is a finite set of literals; while LN1Ψ (M) stands for the signature of the weak constraints in Ψ at level 1 violated by M—also a finite set of literals. Something worth recalling is that NiΨ (M) denotes the weak constraints at level i violated by M in Ψ .
Proposition 1. Suppose an EDLP, Ψ , with weak constraints Ω (Ψ ) of the form of a simple weak constraint, with w = p = 1; suppose an answer set M of Ψ \ Ω (Ψ ); and a set of literals ∆ ⊆ M ∩ LΩ (Ψ). Then, LN1Ψ (M) = ∆ .
By a slight abuse of notation, let us say that the model(s) of an EDLP with weak constraints are also called answer sets.
Before introducing the translation function, let us extend the well-known standard definition of signature by L Ψ,A∗ , which means the finite set of literals occurring both in Ψ and in A∗.
Definition 13 (Abductive-W Translation). Let Ψ, A∗ be an abductive logic program and α a unique literal, such that α ∈/ L Ψ,A∗ . A translation into a weak-constraint program W(Ψ, A∗) corresponds to Ψ ∪ {α ∨ α ← , [1 : 1] ← α | α ∈ A } ∗ .
(3)
Both this translation and Proposition 1 yield the following useful results for the implementation of GAS-semantics in weak constraints.
Lemma 1. M ∩ L Ψ,A∗ is a generalised answer set of an abductive program Ψ, A∗ if and only if M is an answer set of W(Ψ, A∗).
Proof (sketch). Only-if part. Suppose M is an answer set of W(Ψ, A∗). M is an answer set of Ψ ∪ {α ∨ α ← , [1 : 1] ← α} with α ∈ M and M ∩ L Ψ,A∗ corresponds to the answer set of Ψ ∪{α ← } and therefore to the GAS of Ψ, A∗ . On the other hand, with α ∈/ M, M ∩ L Ψ,A∗ is just an answer sets of Ψ ∪ {} and thus the GAS of Ψ, A∗ . In both cases, M ∩ L Ψ,A∗ is a GAS of Ψ, A∗ , as required.
The if-part is similarly straightforward.
The equivalence between a GAS of an abductive program and an answer set of a ω-program ought to be easier to read after a simple example: Example 1. Suppose an update of Ψ1 with Ψ2 where Ψ1 = {b ← }; Ψ2 = {a ← }. Its corresponding abductive program is Ψ ∪ Ψ2, A∗ where Ψ = {b ← ¬α} and A∗ = {α}. As a result, W(Ψ ∪ Ψ2, A∗) = Ψ ∪ Ψ2 ∪ {α ∨ α ← , [1 : 1] ← α} whose answer set M = {α , a, b}. On the other hand, the GAS of the abductive program is just {a, b} = M ∩ L Ψ ∪Ψ2,A∗ .
Up to now, one can compute GAS’s by means of ω-programs. However, this proposal of updates at the object level requires that the generalised answer sets are minimal with respect to set inclusion. Thus, another result of this section is the following formalism that shows the equivalence between MGAS’s and inclusion-preferred answer sets.
a ω-program, W(Ψ, A∗). Then, M1 is inclusion-preferred to M2, denoted as M1 ≤I M2, if and only if LN1Ψ (M1) ⊆ LN1Ψ (M2).
Corollary 1. M is a minimal generalised answer set of Ψ, A∗ if and only if M is an answer set of the corresponding ω-program W(Ψ, A∗), and is minimal with respect to its inclusion preference.
With this equivalence, it is easy to deliver further results, linked to weakconstraints models, as follows.
M1 ≤C M2, if and only if |LN1Ψ (M1)| ≤ |LN1Ψ (M2)|.
a ω-program, W(Ψ, A∗). Then, M1 is cardinality-preferred to M2, denoted as Corollary 2. M is a minimal cardinality-preferred answer set of Ψ, A∗ if and only if M is weak-constraint model of the corresponding ω-program W(Ψ, A∗).
This section is one of the main contribution of this paper and extends previous claims to implement the declarative semantics. First, it introduces a translation of an abductive logic program. Next, the translation has several ways to be interpreted and we propose two kinds of preferred models. Finally, we introduce the theoretical basis for its implementation.
The following section presents a general view of the implementation, which confirms our claims and provides a testbed with an online prototype5 for further research, toy examples and a component of more complex applications. 5 http://fi.uaemex.mx/juan.acosta/kr-lab/od.html. 3.2
Another main contribution of this work is a general proposal to debug EDLP’s
through updates. This idea is similar to the one proposed by [
By following the semantics introduced in Section 2.4, the rules in the •update program give enough information so as to find the source of conflict, by means of its α-rules, when one of them is satisfied. So, let us begin with some definitions.
A rule ρ ∈ Ψ is said to contradict a consistent EDLP, Ψ , if {ρ} ∪ Ψ has no answer sets.
Proposition 2. Suppose two consistent EDLP’s Ψ1, Ψ2 and the update Ψ1 • Ψ2 with its corresponding α-relaxed program, Ψ1, its abductive program ΨA∗ with a minimal generalised answer set M; where Ψ1 ∪ Ψ2 has no model. The rule ρ ∈ Ψ1 contradicts Ψ2 if and only if its corresponding α-relaxed rule ρ ∈ Ψ1, where α ∈ M and ¬α ∈ Body(ρ ).
Proof (sketch). The proof comes from the fact that Ψ2 is consistent and an αrelaxed rule ρ ∈ Ψ1 is inhibited when its corresponding abducible α is true.
As a result, one may find contradictory rules as in the following example. Example 2. Suppose the ASP programs Ψ1 = {(a ← Ψ2 = {∼b ← ¬x}. Rule (b ← ¬c) contradicts Ψ2. ), (b ← ¬c), (d ← } and
As opposed to Example 2, where Ψ2 might be considered an update to Ψ1, one may also debug a single (static) logic program, as in the following example. Example 3. Suppose the inconsistent program {(a ← ), (b ← ¬c), (d ← ), (∼b ← ), (∼a ← ¬x)} The following combinations of rules contradict: (a ← or (b ← ¬c), (∼a ← ¬x) or (∼b ← ), (∼a ← ¬x). ), (b ← ¬c) or (a ← ), (∼b ← )
Finally, the following result holds.
Proposition 3. Suppose an inconsistent EDLP, Ψ1, and the update Ψ1•∅ with its corresponding α-relaxed program, Ψ1, its abductive program ΨA∗ with a minimal generalised answer set M. The rule ρ ∈ Ψ1 contradicts Ψ1 if and only if its corresponding α-relaxed rule ρ ∈ Ψ1, where α ∈ M and ¬α ∈ Body(ρ ).
This section is an introduction of the main results of this paper, which consist of a general characterisation of preferences in weak constraints and a method to debug logic programs in ASP. They provide a solid theoretical framework towards the implementation of a system in DLV to debug ASP knowledge bases.
In need of a general simpler accessible integral framework to debug knowledge bases, this paper is a characterisation in terms of weak constraints both for MGAS’s and Optimal Answer Sets, of an updates semantics that provide a solid foundation for its implementation. The proposed prototype can be employed both to identify conflicts with upcoming information from a dynamic changing environment, and to locate the source of conflict from a given inherent inconsistent knowledge base that is static. In addition, this work introduces some formal specifications towards the implementation of a debugging solver with no need to use a total-order semantics.