Asp Tutorial

ANSWER SET PROGRAMMING
Tran Cao Son

Department of Computer Science
New Mexico State University
Las Cruces, NM 88011, USA
tson@cs.nmsu.edu
http://www.cs.nmsu.edu/~tson
October 2005
Answer Set Programming.
Acknowledgement
This tutorial contains some materials from tutorials on answer set programming and on
knowledge representation and logic programming from those provided by
• Chitta Baral, available at www.public.asu.edu/~cbaral.
• Michael Gelfond, available at www.cs.ttu.ued/~mgelfond.
Tran Cao Son 1

Introduction — Answer Set Programming
Answer set programming is a new programming paradigm. It is introduced in the late

90’s and manages to attracts the intention of different groups of researchers thanks to its:
• declarativeness: programs do not specify how answers are computed;
• modularity: programs can be developed incrementally;
• expressiveness: answer set programming can be used to solve problems in high
complexity classes (e.g. Σ2P , Π2 P , etc.)
Answer set programming has been applied in several areas: reasoning about actions and
changes, planning, configuration, wire routing, phylogenetic inference, semantic web,
information integration, etc.
Tran Cao Son 2

Purpose
• Introduce answer set programming

• Provide you with some initial references, just in case
• . . . you get excited about answer set programming
Tran Cao Son 3

Outline
• Foundation of answer set programming: logic programming with answer set semantics
(syntax, semantics, early application).
• Answer set programming: general ideas and examples
• Application of answer set programming in
– Knowledge representation
– Constraint satisfaction problem
– Combinatoric problems
– Reasoning about action and change
– Planning and diagnostic reasoning
• Current issues
Tran Cao Son 4

LOGIC PROGRAMMING AND ANSWER SET SEMANTICS
Answer Set Programming. Logic Programming and Answer Set Semantics
Terminologies – many brorrowed from classical logic
• variables: X, Y, Z, etc.
• object constants (or simply constants): a, b, c, etc.
• function symbols: f, g, h, etc.
• predicate symbols: p, q, etc.
• terms: variables, constants, and f (t1, . . . , tn) such that tis are terms.
• atoms: p(t1, . . . , tn) such that tis are terms.
• literals: atoms or an atom preceded by ¬.
• naf-literals: atoms or an atom preceded by not.
• gen-literals: literals or a literal preceded by not.
• ground terms (atoms, literals) : terms (atoms, literals resp.) without variables.
Tran Cao Son 6

First Order Language, Herbrand Universe, and Herbrand Base
• L – a first order language with its usual components (e.g., variables, constants,
function symbols, predicate symbols, arity of functions and predicates, etc.)
• UL – Herbrand Universe of a language L: the set of all ground terms which can be
formed with the functions and constants in L.
• BL – Herbrand Base of a language L: the set of all ground atoms which can be
formed with the functions, constants and predicates in L.
• Example:
– Consider a language L1 with variables X, Y ; constants a, b; function symbol f of
arity 1; and predicate symbol p of arity 1.
– UL1 = {a, b, f (a), f (b), f (f (a)), f (f (b)), f (f (f (a))), f (f (f (b))), . . .}.
– BL1 = {p(a), p(b), p(f (a)), p(f (b)), p(f (f (a))), p(f (f (b))),
p(f (f (f (a)))), p(f (f (f (b)))), . . .}.
Tran Cao Son 7

Logic Programs – Syntax

A logic program rule is of the form
a0 ← a1, . . . , an, not an+1, . . . , not an+k (1)
where a’s are atoms (of a first order language L); not a is called a naf-atom.
• a0 – head (the left hand side)
• a1, . . . , an – body (the right hand side)
Definition 1 A logic program is a set of logic programming rules.
The language L of a program Π is often given implicitly.
Remark 1 From now on, we will say a rule (resp. a program) instead of a logic
programming rule (resp. a logic program), for short;
Special cases:
• a0 ← – (n = 0) is called a fact ;
• ← a1 , . . . , an – (a0 is missing) is called a constraint or a goal ;
•k=0 – the rule is called a positive rule.
Tran Cao Son 8

Main Definitions
• ground(r, L): the set of all rules obtained from r by all possible substitution of
elements of UL for the variables in r.
• Example 1 Consider the rule “p(f (X)) ← p(X).” and the language L1. Then
ground(r, L1) will consist of the following rules:
p(f (a)) ← p(a).
p(f (b)) ← p(b).
p(f (f (a))) ← p(f (a)).
p(f (f (b))) ← p(f (b)).
...
• For a program Π:
– ground(Π, L) = r∈Π ground(r, L)
S
– LΠ: The language of a program Π is the language consists of the constants,

variables, function and predicate symbols (with their corresponding arities)
occurring in Π. In addition, it contains a constant a if no constant occurs in Π.
– ground(Π) = r∈Π ground(r, LΠ ).
S
Tran Cao Son 9

Example 2 – Π:
p(a).
p(b).
p(c).
p(f (X)) ← p(X).
– ground(Π):
p(a) ←.
p(b) ← .
p(c) ← .
p(f (a)) ← p(a).
p(f (b)) ← p(b).
p(f (c)) ← p(c).
p(f (f (a))) ← p(f (a)).
p(f (f (b))) ← p(f (b)).
p(f (f (c))) ← p(f (c)).
...
Tran Cao Son 10

Intuition and Examples of Using LP (Positive Programs)
• Meaning of a rule
– A positive rule “a0 ← a1, . . . , an” can be viewed as the disjunction
a0 ∨ ¬a1 ∨ . . . ∨ ¬an which says that if a1, . . . , an are true then a0 is true.
– A rule “a0 ← a1, . . . , an , not an+1, . . . , not an+k ” states that if a1, . . . , an are
true and none of the an+1, . . . , an+k can be proven to be true then a0 is true.
– A constraint “← a1, . . . , an, not an+1, . . . , not an+k ” holds if some ai (1 ≤ i ≤ n)
is false or some aj (n + 1 ≤ j ≤ n + k) is true.
• Knowledge representation using LP-rules
f lies(X) ← bird(X). “if X is a bird, then X flies”
wet grass ← sprinkler on. “The grass is wet if the sprinkler is on”
rain ← humid, hot. “hot and humid causes rain”
love(X, Y ) ← love(Y, X). “Love is a symmetric relationship”
Tran Cao Son 11

Herbrand Interpretation
Definition 2 The Herbrand universe (resp. Herbrand base) of Π, denoted by UΠ

(resp. BΠ), is the Herbrand universe (resp. Herbrand base) of LΠ .
Example 3 For
Π = {p(X) ← q(f (X), g(X)). r(Y ) ←}
the language of Π consists of
• two function symbols: f (arity 1) and g (arity 2);
• p, q, and r are predicate symbols;
• variables X, Y ; and
• a (added) constant a.
UΠ = ULΠ = {a, f (a), g(a), f (f (a)), g(f (a)), g(f (a)), g(g(a)), f (f (f (a))), . . .}
BΠ = BLΠ = {p(a), q(a, a), r(a), p(f (a)), q(a, f (a)), r(f (a)), . . .}
Definition 3 (Herbrand Interpretation) A Herbrand interpretation of a program
Π is a set of atoms from its Herbrand base.
Tran Cao Son 12

Semantics – Positive Programs without Constraints

Let Π be a positive proram and I be a Herbrand interpretation of Π. I is called a
Herbrand model of Π if for every rule “a0 ← a1, . . . , an ,” if a1, . . . , an are true with
respect to I (or a1, . . . , an ⊆ I) then a0 is also true with respect to I.
Definition 4 The least Herbrand model for a program Π is called the minimal model
of Π and is denoted by MΠ.
Computing MP . Let Π be a program. We define a fixpoint operator TΠ that maps a
set of atoms (of program Π) to another set of atoms as follows.
TΠ (X) = {a | a ∈ BΠ,
there exists a rule (2)
a ← a1, . . . , anin Π s. t. ai ∈ X}
Note: By a ← a1, . . . , an in Π we mean there exists a rule b ← b1, . . . , bn in Π (that
might contain variables) and a ground substitution σ such that a = bσ and ai = biσ.
Remark 2 The operator TΠ is often called the van Emden and Kowalski’s iteration
operator.
Tran Cao Son 13

Some Examples
For Π = {p(f (X)) ← p(X). q(a) ← p(X).}

we have
UΠ = {a, f (a), f (f (a)), f (f (f (a))), . . .}
and
BΠ = {q(a), p(a), p(f (a)), p(f (f (a))), . . .}
Computing TΠ(X):
• For X = BΠ, TΠ (X) = {q(a)} ∪ {p(f (t)) | t ∈ UΠ }.
• For X = ∅, TΠ (X) = ∅.
• For X = {p(a)}, TΠ(X) = {q(a), p(f (a))}.
• We have that MΠ = ∅ (Why?).
Tran Cao Son 14

Properties of TΠ
• TΠ is monotonic: TΠ(X) ⊆ TΠ (Y ) if X ⊆ Y .
• TΠ has a least fixpoint that can be computed as follows.
1. Let X1 = TΠ(∅) and k = 1
2. Compute Xk+1 = TΠ(Xk ). If Xk+1 = Xk then stops and return Xk .
3. Otherwise, increase k and repeat the second step.
Note: The above algorithm will terminate for positive program Π with finite BΠ.
We denote the least fix point of TΠ with TΠ∞ (∅) or lf p(TΠ ).
Theorem 1 MΠ = lf p(TΠ ).
Theorem 2 For every positive program Π without constraint, MΠ is unique.
Tran Cao Son 15

More Examples
• For Π1 = {p(X) ← q(f (X), g(X)). r(Y ) ←}

we have that
UΠ1 = {a, f (a), g(a), f (f (a)), g(f (a)), g(f (a)), g(g(a)), f (f (f (a))), . . .}
BΠ1 = {p(a), q(a, a), r(a), p(f (a)), q(a, f (a)), r(f (a)), . . .}
Computing MΠ:
X0 = TΠ1 (∅) = {r(a), r(f (a)), r(g(a)), r(f (f (a))), ...}
X1 = TΠ1 (X0) = X0
So, lf p(Π1 ) = {r(a), r(f (a)), r(g(a)), r(f (f (a))), ...}.
• For Π2 = {p(f (X)) ← p(X). q(a) ← p(X).}
UΠ2 = {a, f (a), f (f (a)), f (f (f (a))), . . .}
BΠ2 = {q(a), p(a), p(f (a)), p(f (f (a))), . . .}
Computing MΠ2 :
X0 = TΠ2 (∅) = ∅
X1 = TΠ2 (X0) = X0
So, lf p(Π2 ) = ∅.
Tran Cao Son 16
• For Π3 = {p(f (X)) ← p(X). q(a) ← p(X). p(b).}

UΠ3 = {a, b, f (a), f (b), f (f (a)), f (f (b)), f (f (f (a))), . . .}
BΠ3 = {q(a), q(b), p(a), p(b), p(f (a)), p(f (b)), p(f (f (a))), . . .}
Computing MΠ3 :
X0 = TΠ3 (∅) = {p(b)}
X1 = TΠ3 (X0) = {p(b), q(a), p(f (b))}
X2 = TΠ3 (X1) = {p(b), q(a), p(f (b)), p(f (f (b)))}
...
So, lf p(TΠ3 ) = {q(a)} ∪ {p(f i(b)) | i = 0, 1, . . .}.
• For Π4 = {p ← a. q ← b. a ← .}, MΠ4 = {a, p}.
• For Π5 = {p ← p.}, MΠ5 = ∅
• For Π6 = {p ← p. q ← .}, MΠ6 = {q}.
• For Π7 = {p(b). p(c). p(f (X)) ← p(X).},MΠ7 = {p(f n(b)) | n =
0, . . . , } ∪ {p(f n(c)) | n = 0, 1. . . . , }
Tran Cao Son 17

Entailment
For a program Π and an atom a, Π entails a (with respect to the minimal model
semantics), denoted by Π |= a, iff a ∈ MΠ.
We say that Π entails ¬a (with respect to the minimal model semantics), denoted by
Π |= ¬a, iff a ∈ MΠ .
Example 4 Let 






p(f (X)) ← p(X).
Π=

q(a) ← p(X).
 p(b).



We have that MΠ = lf p(TΠ) = {q(a)} ∪ {p(f i(b)) | i = 0, 1, . . .}

where f i (b) = f (f (. . . (f (b)))) (f repeated i times)
So, we say:
Π |= q(a),
Π |= ¬q(b), and
Π |= p(f i (b)) for i = 0, 1, . . .
Tran Cao Son 18

Entailment – Another Example
Example 5 • Consider the parent-child database with facts of the form p(X, Y )
(X is a parent of Y ). We can define the ancestor relationship, a(X, Y ) (X is an
ancestor of Y ), using the following rules


 a(X, Y ) ← p(X, Y ).
Πa = 
 a(X, Y ) ← p(X, Z), a(Z, Y ).
Given the set of facts I = {p(a, b), p(b, c), p(c, d)}, let Π = Πa ∪ I. We can easily
compute
MΠ = I ∪ {a(X, Y ) | p(X, Y ) ∈ I} ∪ {a(a, c), a(a, d), a(b, d)}
So, Π |= a(a, c) and Π |= a(a, d), i.e., a is an ancestor of c and d; on the other
hand, Π |= ¬a(d, a), i.e., d is not an ancestor of a.
Tran Cao Son 19
• Consider a directed graph G described by a set of atoms of the form edge(X, Y ).

The following program can be used to determine whether there is a path
connecting two nodes of G.






reachable(X, Y ) ← edge(X, Y )
reachable(X, Y ) ← edge(X, Z), reachable(Z, Y )















ΠG = 

edge(a, b) ←
edge(b, c) ←







←

edge(c, a)







 ...


It can be shown that for every pair of nodes p and q of the graph G,
reachable(p, q) belongs to MΠG iff there exists a path from p to q in the graph G.
Remark 3 Reasoning using positive programs assumes the closed world assumption
(CWA): anything, that cannot be proven to be true, is false.
Tran Cao Son 20

Semantics – General Logic Programs without Constraints

Recall that a program is a collection of rules of the form
a ← a1, . . . , an, not an+1, not an+k .
Let Π be a program and X be a set of atoms, by ΠX we denote the program obtained
from ground(Π) by
1. Deleting from ground(Π) any rule a ← a1, . . . , an, not an+1, not an+k for that
{an+1, . . . , an+k } ∩ X 6= ∅, i.e., the body of the rule contains a naf-atom not al and
al belongs to X; and
2. Removing all of the naf-atoms from the remaining rules.
Remark 4 The above transformation is often referred to as the Gelfond-Lifschitz
transformation.
Remark 5 ΠX is a positive program.
Definition 5 A set of atoms X is called an answer set of a program Π if X is the
minimal model of the program ΠX .
Theorem 3 For every positive program Π, the minimal model of Π, MΠ, is also the
unique answer set of Π.
Tran Cao Son 21

Detailed Computation
• Consider Π2 = {a ← not b. b ← not a.}. We will show that its has two answer
sets {a} and {b}
S1 = ∅ S2 = {a} S3 = {b} S4 = {a, b}
ΠS2 1 : ΠS2 2 : ΠS2 3 : ΠS2 4 :
a← a←
b← b←
MΠS1 = {a, b} MΠS2 = {a} MΠS3 = {b} MP S4 = ∅
2 2 2
MΠS1 6= S1 MΠS2 = S2 MΠS3 = S3 MΠS4 6= S4
2 2 2 2
NO Y ES Y ES NO
• Assume that our language contains two object constants a and b and consider
Π = {p(X) ← not q(X). q(a) ←}. We show that S = {q(a), p(b)} is an answer set
of Π. We have that ΠS = {p(b) ← q(a) ←} whose minimal model is exactly S. So,
S is an answer set of Π.
Tran Cao Son 22
• Π4 = {p ← not p.} We will show that P does not have an answer set.
S1 = ∅, then ΠS4 1 = {p ←} whose minimal model is {p}. {p} =
6 ∅ implies that S1 is
not an answer set of Π4 .
S2 = {p}, then ΠS4 2 = ∅ whose minimal model is ∅. {p} =
6 ∅ implies that S2 is not an
answer set of Π4.
This shows that P does not have an answer set.
In computing answer sets, the following theorem is useful:
Theorem 4 Let Π be a program.
1. Let r be a rule in ground(P ) whose body contains an atom a that does not occur
in the head of any rule in ground(P ). Then, S is an answer set of Π iff S is an
answer set of ground(P ) \ {r}.
2. Let r be a rule in ground(P ) whose body contains a naf-atom not a that does not
occur in the head of any rule in ground(P ). Let r′ be the rule obtained from r by
removing not a. Then, S is an answer set of P iff S is an answer set of
ground(P ) \ {r} ∪ {r′ }.
Tran Cao Son 23

Examples about Answer Sets
Remark 6 A program may have zero, one, or more than one answer sets.
• Π1 = {a ← not b.}.
Π1 has a unique answer set {a}.
• Π2 = {a ← not b. b ← not a.}.
The program has two answer sets: {a} and {b}.
• Π3 = {p ← a. a ← not b. b ← not a.}
The program has two answer sets: {a, p} and {b}.
• Π4 = {a ← not b. b ← not c. d ← .}
Answer sets: {d, b}.
• Π5 = {p ← not p.}
No answer set.
• Π6 = {p ← not p, d. r ← not d. d ← not r.}
Answer set {r}.
Tran Cao Son 24

Entailment w.r.t. Answer Set Semantics
• For a program Π and an atom a, Π entails a, denoted by Π |= a, if a ∈ S for every

answer set S of Π.
• For a program Π and an atom a, Π entails ¬a, denoted by Π |= ¬a, if a 6∈ S for
every answer set S of Π.
• If neither Π |= a nor Π |= ¬a, then we say that a is unknown with respect to Π.
Remark 7 Π does not entail a DOES NOT IMPLY that Π entails ¬a, i.e., reasoning
using answer set semantics does not employ the closed world assumption.
Example 6 • Π1 = {a ← not b.}.
Π1 has a unique answer set {a}. Π1 |= a, Π1 |= ¬b.
• Π2 = {a ← not b. b ← not a.}.
The program has two answer sets: {a} and {b}. Both a and b are unknown
w.r.t. Π2.
• Π3 = {p ← a. a ← not b. b ← not a.}
The program has two answer sets: {a, p} and {b}. Everything is unknown.
Tran Cao Son 25
• Π3 = {a ← not b. b ← not c. d ← .}
Answer sets: {d, b}. Π3 |= b; Π3 |= ¬a; etc.
• Π4 = {p ← not p.}
No answer set. p is unknown.
• Π5 = {p ← not p, d. r ← not d. d ← not r.}
Answer set {r}. Π5 |= r; Π5 |= ¬p; etc.
• Π6 = {p ← not a. p ← not b. a ← not b. b ← not a.}
Two answer sets: {p, a} and {p, b}. So, Π6 |= p but Π6 6|= a and Π6 6|= ¬a?
(likewise b).
• Π7 = {q ← not r. r ← not q. p ← not p. p ← not r.}
One stable model: {p, q}. So, Π7 |= p and Π7 |= q.
Tran Cao Son 26

Further intuitions behind the semantics
• A set of atoms S is closed under a program Π if for all rules of the form
a0 ← a1, . . . , am , not am+1, . . . , not an.
in Π, {a1, . . . , am} ⊆ S and {am+1, . . . , an} ∩ S = ∅ implies that a0 ∈ S.
• A set of atoms S is said to be supported by Π if for all p ∈ S there is a rule of the
form p ← a1, . . . , am , not am+1, . . . , not an.
in Π, such that {a1, . . . , am} ⊆ S and {am+1, . . . , an} ∩ S = ∅.
• A set of atoms S is an answer set of a program Π iff (i) S is closed under Π and (ii)
there exists a level mapping function λ (that maps atoms in S to a number) such that
for each p ∈ S there is a rule in Π of the form p ← a1, . . . , am, not am+1, . . . , not an.
such that {a1, . . . , am} ⊆ S, {am+1, . . . , an} ∩ S = ∅ and λ(p) > λ(ai), for
1 ≤ i ≤ m.
• Note that (ii) above implies that S is supported by Π.
Tran Cao Son 27

LOGIC PROGRAMMING AND KNOWLEDGE
REPRESENTATION
Answer Set Programming. Logic Programming and Knowledge Representation
Commonsense Reasoning
Our knowledge
• is often incomplete (it does not contain complete information about the world), and
• contains defaults (rules which have exceptions, also called normative sentences).
• contains preferences between defaults (prefer a conclusion/default).
For this reasons, we often jump to conclusions (ignore what we do not now), and know
to deal with exceptions and preferences.
Example 7 We know
Normally, birds fly.
Normally, computer science students can program.
Normally, students work hard.
Normally, things do not change.
Normally, students do not watch TV.
Normally, the speed limit on highways is 70 mph.
Normally, it is cold in December.
From this, we make conclusions such as Tweety flies if we know that Tweey is a bird;
Monica can program if she is a computer science student; etc.
Tran Cao Son 29

Representing Defaults
Normally, a’s are b’s. b(X) ← a(X), not ab(r, X)1

Normally, birds fly. f lies(X) ← bird(X), not ab(bird f ly, X)
Normally, animals have four legs.
numberof legs(X, 4) ← animal(X), not ab(animal, X)
Normally, fishs swim. swim(X) ← f ish(X), not ab(f ish, X)
Normally, computer science students can program.
can program(X) ← student(X), is in(X, cs), not abp(X)
Normally, students work hard.
hard working(X) ← student(X), not ab(X)
Typically, classes start at 8am.
start time(X, 8am) ← class(X), not ab(X)
1
r is the ’name’ of the statement; ab(X) or abr (X) can also be used.
Tran Cao Son 30

Example 8 (Birds) Suppose that we know

• r1: Normally, birds fly.
• r3: Penguins are birds.
• r3: Penguins do not fly.
• r4: Tweety is a penguin.
• r5: Tim is a bird.

r1





: f lies(X) ← bird(X), not ab(r1, X)
: ← penguin(X)

r2 bird(X)







Πb = 

r3 : ab(r1, X) ← penguin(X)
r : penguin(tweety) ←


 4




: ←

 r bird(tim)


5
Answer set of Πb : ?
Tran Cao Son 31


r1





: ← penguin(X)

r2 bird(X)







Πb = 

r3 : ab(r1, X) ← penguin(X)
r4 : penguin(tweety) ←







: ←

 r bird(tim)


5
Answer set of Πb :
{bird(tim), f lies(tim), penguin(tweety), ab(r1, tweety), bird(tweety)
Πb |= f lies(tim) and Πb |= ¬f lies(tweety)
Tran Cao Son 32

Defaults – Example
Example 9 (Animals) Consider the following information:

• Normally lions and tigers are cats.
• Sam and John are lions.
• Sam is not a cat.
• Sam is a sea lion.
This information can be represented by the following program

r1 




: cat(X) ← lion(X), not ab(r1, X)

r2 : cat(X) ← tiger(X), not ab(r2, X)







r3 : lion(X) ← sea lion(X)




Πa = 





r4 : ab(r1, X) ← sea lion(X)
r5 : sea lion(sam) ←







 r : lion(john) ←


6

We can check that Πa entails that sam is a lion but not a cat while john is a cat
which is a lion.
Tran Cao Son 33

Defaults – More Examples
Example 10 • We know that computers are normally fast machines, the

commodore is a slow machine because it is an old one. This can be represented
by the following program:

r1




: f ast machine(X) ← computer(X), not ab(X)
r2 : old(X) ← comodore(X)




Πc = 




r3 : computer(X) ← comodore(X)

 r : ab(X) ← old(X)


4
• The Boeing 747, concord, and FA21314 are airplanes. Airplanes normally fly
unless they are out of order. FA21314 is out of order.






r1 : f lies(X) ← airplane(X), not ab(X)

r2 : ab(X) ← out of order(X)







r3 : airplane(boeing 747) ←




Πairplanes =




r4 : airplane(concord) ←

r5 : airplane(f a21324) ←







 r6 : out of order(f a21324) ←



Tran Cao Son 34

EXTENSIONS OF LOGIC PROGRAMMING
AND COMPUTING ANSWER SETS
Extensions of Logic Programming
Answer Set Programming. and Computing Answer Sets
Additional Features for Knowledge Representation and Reasoning
To add expressiveness and make logic programming a more suitable language for
knowledge representation and reasoning, additional features and constructors are
introduced:
• classical negation: instead of atoms, literals are used in the rule
l0 ← l1, . . . , ln , not ln+1, . . . , not ln+k
where li is a literal (an atom a or its negation ¬a). This will allow us to represent and
reason with negative information.
• epistemic disjunction: rule is allowed to have epistemic disjunction in the head
l0 or . . . or lm ← lm+1, . . . , lm+n , not lm+n+1, . . . , not lm+n+k
where or is a epistemic disjunction. This rule states that if lm+1, . . . , lm+n are true
and there is no reason for believing that the lm+n+1, . . . , lm+n+k are true then at least
one of the l0, . . . , lm is believed to be true.
• nested expression: allowing not not l.
Tran Cao Son 36
• weighted-atom:
l{l0 = w0, . . . , lk = wk , not lk+1 = wk+1 , . . . , not lk+n = wk+n }u
where li’s are a literal, wi are integers, and l and u are two integers. This atom is true
with respect to a set of literals S if
0≤j≤k k+1≤j≤k+n
l≤ wj + wj ≤ u
X X
lj ∈S lj 6∈S
Special case: choice atom – wi = 1 for every i.

Programs with weight constraints are defined by allowing weight atoms to appear in
place of atoms.
• Answer set semantics: defined accordingly. See for example,
– M. Gelfond and V. Lifschitz, “Classical negation in logic programs and disjunctive
databases,” New Generation Computing, 1991, pp. 365-385.
– V. Lifschitz, L. R. Tang and H. Turner, ”Nested expressions in logic programs,”
Annals of Mathematics and Artificial Intelligence, Vol. 25, 1999, pp. 369-389.
– I. Niemelä and P. Simons. Extending the Smodels System with Cardinality and
Weight Constraints.Logic-Based Artificial Intelligence, pp. 491-521. Kluwer
Academic Publishers, 2000.
Tran Cao Son 37

Using Classical Negation

r1





: ← penguin(X)

r2 bird(X)







Πb =  r
 3
: ab(r1, X) ← penguin(X)
r4 : penguin(tweety) ←







: ←

 r bird(tim)


5
• In the bird example, “Penguins do not fly” is more intuitive than “Normally, penguins
do not fly.” So, r3 of Πb should be changed to
r3′ : ¬f lies(X) ← penguin(X).
Doing so will make the program Πb inconsistent! Obviously, r1 does not account for
the class of birds who do not fly. We should change the rule r1 to
r1′ : f lies(X) ← bird(X), not ab(r1, X), not ¬f lies(X)
The new program, Π′b = Πb \ {r1, r3} ∪ {r1′ , r3′ } will correctly answer the same
questions such as “does Tim flies” and “does Tweety fly?”
Tran Cao Son 38
• Suppose that we have a list of professor and their courses:

Professor Course
mike ai
sam db
staff C
where staf f stands for “someone” – an unknown professor – who might be different
than mike and sam.
This list can be expressed by a set of atoms of the form teach(P, C) (P teaches C):
teach(mike, ai), teach(sam, db), and teach(staf f, c).
By default, we know that if a professor P teaches the course C, then (P, C) will be
listed (and hence the atom teach(P, C) will be present.) Thus, by default, professor
P does not teach the course C if teach(P, C) is not present. The exception to this
rule are the courses taught by “staff”. This leads to the following two rules:
¬teach(P, C) ← not teach(P, C), not ab(P, C).

ab(P, C) ← teach(staf f, C)
This will allow us to conclude that mike teaches ai but we do not know whether he
teaches c or not.
Tran Cao Son 39

Answer Sets of Programs with Constraints
For a set of ground atoms S and a constraint c

← a0, . . . , an, not an+1, . . . , not an+k
we say that c is satisfied by S if {a0, . . . , an} \ S 6= ∅ or {an+1, . . . , an+k } ∩ S 6= ∅.
Let Π be a program with constraints. Let
ΠO = {r | r ∈ Π, r has non-empty head}
(ΠO is the set of normal logic program rules in Π) and
ΠC = Π \ ΠO
(ΠC is the set of constraints in Π).
Definition 6 A set of atoms S is an answer sets of a program Π if it is an answer
set of ΠO and satisfies all the constraints in ground(ΠC ).
Example 11 Π2 = {a ← not b. b ← not a.} has two answer sets {a} and {b}.
But, Π′2 = {a ← not b. b ← not a. ← not a} has only one answer set {a}.
Tran Cao Son 40

Computing Answer Sets
• Complexity: The problem of determining the existence of an answer set for finite
propositional programs (programs without function symbols) is NP-complete. For
programs with disjunctions, function symbols, etc. it is much higher.
A consequence of this property is that there exists no polynomial-time algorithm for
computing answer sets.
Special cases: answer sets of positive programs without function symbols can be
computed in polynomial time in the size of the program.
A good survey on the complexity and expresiveness of different classes of logic
programs can be found in
– Chitta Baral. Knowledge representation, reasoning and declarative problem
solving, Cambridge University Press, 2003.
• Answer set solvers: Programs that compute answer sets of (finite and grounded)
logic programs. Two main approaches:
Tran Cao Son 41
– Direct implementation: Due to the complexity of the problem, most solvers

implement a variation of the generate-and-test algorithm. The advantage of this
approach is that we are free to invent! Many systems:
∗ Smodels available at http://www.tcs.hut.fi/Software/smodels/
∗ Dlv available at http://www.dbai.tuwien.ac.at/proj/dlv/
∗ deres available at http://www.cs.engr.uky.edu/ai/deres.html
∗ nomore available at http://www.cs.uni-potsdam.de/~linke/nomore/
– Using SAT solvers: A program Π is translated into a satisfiabilty problem FΠ
and a call to a SAT solver is made to compute solution of FΠ. The main task of
this approach is to write the program for the conversion from Π to FΠ . Recent
discoveries ensure that there is an one-to-one correspondence between solutions of
FΠ and answer sets of Π (e.g., see paper from the ASSAT web site). Two
systems:
∗ Cmodels available at
http://www.cs.utexas.edu/users/tag/cmodels.html
∗ ASSAT available at http://assat.cs.ust.hk/
Remark 8 Most of the above systems make use of lparse, a grounding program for
logic programs with function symbols (typed) and weight constraints. The program is
available at the Smodels web site.
Tran Cao Son 42
Remark 9 A Java implementation of Smodels, called Jsmodels, is available at

http: // www. cs. nmsu. edu/ ~hle/ jsmodel. html .
Usage of lparse and Smodels
• lparse: a preprocessor for programs using as input to Smodels. Some restrictions
apply:
– Finite domains: every variable is typed and has a finite domain;
– Safe rule: variables appear in the head of a rule must occur in the body of the
rule, in a predicate that specifies the domain of the variable;
– Built-in predicates: assign, plus, minus, etc.. (see lparse user’s manual for
more). Do not use them in your programs or you will get errors.
• Command line:
lparse <options> prog1 prog2 ... | smodels number of models
Tran Cao Son 43

ANSWER SET PROGRAMMING
Answer Set Programming. Answer Set Programming
Brief History and References

• Answer set programming was introduced in
– V. W. Marek, M. Truszczynski. Stable models and an alternative logic
programming paradigm. In The Logic Programming Paradigm, K.R. Apt, V.W.
Marek, M. Truszczynski, D.S. Warren (eds.), pp. 375-398. Springer-Verlag, 1999.
– I. Niemelä. Logic programming with stable model semantics as a constraint
programming paradigm. Annals of Mathematics and Artificial Intelligence,
25(3,4):241–273, 1999.
• Take off thanks to the development of several answer set solvers (Smodels and Dlv),
• the application of answer set programming in several applications such as planning,
system configuration, cryptography, NASA’s application, etc.
• 2001: first symposium on answer set programming: “Answer Set Programming:
Towards Efficient and Scalable Knowledge Representation and Reasoning,”
http://www.cs.nmsu.edu/~tson/ASP2001/csp01.html.
• 2002 – now: several symposia on ASP (http://wasp.unime.it/).
• 2001 – now: several papers on answer set programming have been published.
Tran Cao Son 45

Answer Set Programming. Answer Set Programming
Main Idea
Given a problem P , whose solutions are S1, . . . , Sn which can be computed by

• generating a hypothetical solution and
• testing whether it is really a solution.
This process is very similar to the process of computing answer sets of a logic program
Π: given a program Π its answer sets can be computed by
• generating a set of atoms X and
• checking whether X is an answer set of Π
This gives us the idea: Solve P by representing P as a logic program ΠP whose answer
sets correspond one-to-one to S1, . . . , Sn using the follong steps:
• Repesenting P as ΠP ;
• Computing answer sets of ΠP ; and
• Converting answer sets of ΠΠ to solutions of P
Tran Cao Son 46

EXAMPLES
Answer Set Programming. Examples
Graph Coloring
3 3
1 1
Coloring
4 4
2 2
5 5
Figure 1: Graph Coloring Problem
Problem: Given a (bi-directed) graph and three colors red, green, and yellow. Find a
color assignment for the nodes of the graph such that no edge of the graph connects two
nodes of the same color.
Tran Cao Son 48

Graph Coloring
Example 12 (Graph coloring problem) Given a (bi-directed) graph and three

colors red, green, and yellow. Find a color assignment for the nodes of the graph such
that no edge of the graph connects two nodes of the same color.
• Representation: A graph can be specified by
– the set of nodes and
– the set of edges.
• Solution: A mapping from the set of nodes to the set of colors
{red, green, yellow} such that no edge connects two nodes of the same color.
• Solving the problem (manualy):
– Numbering the nodes from 1 to n
– Assigning each node a color
– Checking if the assignment is a solution, i.e., satisfies the constraints no
edge connects two nodes of the same color
Tran Cao Son 49

Graph Coloring – Program

Writing a program to solve the graph coloring problem:
• Graph representation:
– The nodes: node(1), . . . , node(n).
– The edges: edge(i, j).
• Solution repesentation: use the predicate color(X, Y ) - node X is assigned the color
Y.
• Generating the solutions: Each node is assigned one color. The three rules
color(X, red) ← not color(X, green), not color(X, yellow). (3)
color(X, green) ← not color(X, red), not color(X, yellow). (4)
color(X, yellow) ← not color(X, green), not color(X, red). (5)
or the weighted rule
1{color(X, red), color(X, yellow), color(X, green)}1 ← node(X).
can be used. (The weighted rule says that each node should be colored using exactly
one color.)
Tran Cao Son 50
• Checking for a solution: needs to make sure that no edge connects two nodes of the
same color. This can be represented by a constraint:
← edge(X, Y ), color(X, C), color(Y, C). (6)
%% prog1
%% representing the graph
node(1). node(2). node(3). node(4). node(5).
edge(1,2). edge(1,3). edge(2,4). edge(2,5). edge(3,4). edge(3,5).
%% each node is assigned a color

color(X,red):- not color(X,green), not color(X, yellow).
color(X,green):- not color(X,red), not color(X, yellow).
color(X,yellow):- not color(X,green), not color(X, red).
%% constraint checking
:- edge(X,Y), color(X,C), color(Y,C).
Try with lparse prog1 | smodel 1 or lparse prog1 | smodel 0 and see
the result.
Tran Cao Son 51

prog1 can be divided into three group of rules

• Rules for describing the graph;
• Rules for generating the hypothetical solutions; and
• Rules for checking the correctness of the solutions.
It is a good practice to separate the rules into two files: (a) the first file contains rules for
describing the graph (let us called this file prog11, for our example, this program
contains the first two lines of prog1); and (b) the second file contains other rules. (let us
called this file prog12 which contains the other rules of prog1).
Command line: lparse prog11 prog12 | smodels
Tran Cao Son 52

Correctness of prog1
Let us denote the program prog1 developed for a graph G by ΠG .

• What is to prove? (one-to-one mapping between solutions of G and answer sets of
ΠG .) Intuitively, this means
– If ΠG has an answer set then the 3-coloring problem for G has a solution and vice
versa.
– If ΠG does not have an answer set then the coloring problem of G has no solution.
• How can we prove this?
– Take an answer set S of ΠG , construct a solution for the coloring problem of G
from S.
– Take a color mapping M , which is a solution for the problem, construct an answer
set for ΠG.
Tran Cao Son 53
We can prove the following theorems.

Theorem 5 Let S be an answer set of ΠG . Then, the 3-coloring problem of G has
a solution corresponds to S.
Proof. We prove the following:
1. For every node k of the graph G, S contains one and only one atom from the set
C = {color(k, red), color(k, green), color(k, yellow)}, i.e., S ∩ C has only one
element. Assume that it is not the case. Then, there are only three cases: S contains
zero, two, or three elements of the set C. Assume that
Case 1: S does not contain any element from C. Then, ΠSG contains
color(k, red) ← node(k). (because of rule (3))
color(k, green) ← node(k). (because of rule (4))
color(k, yellow) ← node(k). (because of rule (5))
Because k is a node of G, we can easily see that color(k, red), color(k, yellow), and
color(k, green) belong to the minimal model of ΠSG. Thus, S cannot be an answer set of
ΠG because it cannot be equal the minimal model of ΠSG. This contradicts the
assumption that S is an answer set of ΠG . Hence, this case cannot happen.
Case 2: S contains two elements from C. Since the three colors are equivalent and so,
without loss of generality, we assume that S contains color(k, red) and color(k, green);
and it does not contain color(k, yellow). Then, ΠSG will not contain any rule whose
head is an atom belonging to C. (all the rules of the form (3)-(5) for X = k are
Tran Cao Son 54
removed). This implies that the minimal model of ΠSG cannot contain any element of C.
This implies that S cannot be an answer set of ΠG because it cannot be equal the
minimal model of ΠSG . Again, this contradicts the assumption that S is an answer set of
ΠG. Hence, this case cannot happen.
Case 3: S contains all elements of C. This is similar to the second case, i.e., ΠSG does
not contain any rule whose head is a member of C, and hence, S would not be an
answer set of ΠG.
The three cases show that for each node k, S contains 1-and-only-1 member of the set
{color(k, red), color(k, green), color(k, yellow)}.
2. Now we need to show that the color mapping specified by the answer set S is a
solution to the coloring problem.
Let 1, . . . , n be the nodes of the graph and c1, . . . , cn be the color such that
color(i, ci) ∈ S for i = 1, . . . , n. We need to show that if edge(i, j) belongs to G then
ci 6= cj . Again, we prove by contradiction. Let assume that there is an edge (p, q) in G
and cp = cq . This means that the body of the rule (6) for edge(p, q), color(p, cp), and
color(q, cq ) is satisfied. This means that S is not an answer set of ΠG, i.e., our
assumption contradicts the fact that S is an answer set of ΠG. Thus, our asssumption is
incorrect, i.e., we have proved that for every edge (i, j) of G, ci 6= cj . This shows that S
corresponds to a solution of the 3-coloring problem for G.
Tran Cao Son 55

Theorem 6If the 3-coloring problem for G has a solution M then ΠG has an
answer set correcsponds to M .
Proof. Let 1, . . . , n be the nodes of the graph. Consider a solution for the 3-coloring
problem for G. Let c1, . . . , cn be the color of the node i = 1, . . . , n, respectively. We will
show that the set of atoms
S = {node(i) | i = 1, . . . , n} ∪ {edge(i, j) | (i, j) is an edge of G}∪
{color(i, ci) | i = 1, . . . , n}
is an answer set of ΠG.
Let us compute ΠSG . We can see that ΠSG consists of the following rules:
• the rules defining the graph, i.e., the rules node(1) ← .... node(n) ← (nodes of the
graph) and the rules edge(i, j) ← if (i, j) is an edge of G.
• for each node i, one rule of the form color(i, ci ) ← node(i) which comes from one of
the rules (3)-(5).
• for each edge (i, j), three constraints:
← edge(i, j), color(i, red), color(j, red)
← edge(i, j), color(i, yellow), color(j, yellow)
← edge(i, j), color(i, green), color(j, green)
Tran Cao Son 56

We need to show that S is the minimal model of ΠSG that does not violates any of the
constraints.
Let X0 = {node(i) | i = 1, . . . , n} ∪ {edge(i, j) | (i, j) is an edge of G}.
Obviously, TΠS (∅) = X0 and
G
TΠS (X0) = S, and TΠS (S) = S. (*)
G G
Furthermore, because for every edge (i, j), ci 6= cj , we can conclude that there exists no
edge (i, j) in G and a color C ∈ {red, green, yellow} such that S contains color(i, C)
and color(j, C). This is equivalent to say that the constraints in ΠSG are satisfied by S.
Together with (*), we conclude that S is an answer set of ΠG.
Tran Cao Son 57

n-Queens
Q Q
Q Q
Q Q
Q Q
Figure 2: 4-queens Problem
Problem: Place n queens on a n × n chess board so that no queen is attacked (by

another one).
Tran Cao Son 58

n-Queens
• Representation: the chess board can be represented by a set of cells cell(i, j) and
the size n.
• Solution: Each cell is assigned a number 1 or 0. cell(i, j) = 1 means that a queen is
placed at the position (i, j) and cell(i, j) = 0 if no queen is placed at the position (i, j)
• Generating a possible solution:
– cell(i, j) is either true or false
– select n cells, each on a column, assign 1 to these cells.
• Checking for the solution: ensures that no queen is attacked
Tran Cao Son 59

n-Queens – writing a program
Use a constant n to represent the size of the board

col(1..n). // n columns
row(1..n). // n rows
Since two queens can not be on the same column, we know that each column has to have
one and only one queen. Thus, using the weighted-rule
1{cell(I, J) : row(J)}1 ← col(I).
we can make sure that only one queen is placed on one column. To complete the
program, we need to make sure that the queens do not attack each other.
• No two queens on the same row
← cell(I, J1), cell(I, J2), J1 6= J2.
• No two queens on the same column (not really needed)
← cell(I1, J), cell(I2, J), I1 6= I2.
• No two queens on the same diagonal
← cell(I1, J1), cell(I2, J2), |I1 − I2| = |J1 − J2|
Tran Cao Son 60
%% prog2
%% representing the board, using n as a constant
col(1..n). % n column
row(1..n). % n row
%% generating solutions
1 {cell(I,J) : row(J)}:- col(I).
% two queens cannot be on the same row/column

:- col(I), row(J1), row(J2), neq(J1,J2), cell(I,J1), cell(I,J2).
:- row(J), col(I1), col(I2), neq(I1,I2), cell(I1,J), cell(I2,J).
% two queens cannot be on a diagonal

:- row(J1), row(J2), J1 > J2, col(I1), col(I2), I1 > I2,
cell(I1,J1), cell(I2,J2), eq(I1 - I2, J1 - J2).
:- row(J1), row(J2), J1 > J2, col(I1), col(I2), I1 < I2,

cell(I1,J1), cell(I2,J2), eq(I2 - I1, J1 - J2).
Command line: lparse -c n=?? prog2 | smodels
Tran Cao Son 61

Tile covering problem
Covering with 1
by 2 tiles
Figure 3: 4 x 4 Tile Covering Problem
Problem: Given a slightly damaged chess board (n × n). Find a covering of the board
using m 1 × 2-tiles so that all the good squares on the board are covered. If no such
covering exists, report there is no solution.
Tran Cao Son 62

Tile covering problem
• Problem: Given a slightly damaged chess board (n × n). Find a covering of the
board using m 1 × 2-tiles so that all the good squares on the board are covered. If no
such covering exists, report there is no solution.
• Representation:
• the board
− dimension
− damaged/good cells
• the tiles with their coverage
As with N-queens problem, we can use the two predicates row() and col() to
represent the possible board cells
We can use bad(i, j) to indicate that the cell (i, j) is damaged We can use the
predicate cell(i, j, t) to represent the information that the cell (i, j) is covered by the
tile t
Tran Cao Son 63

• Generating a possible solution: We assign each tile a number. Then we can

assign a tile to a location. Since each tile covers two and only two cells, we can used
the weighted-rule:
2cell(I, J, T ) : col(I) : row(J)2 ← tile(T ).
to generate a possible solution.
• Checking for a solution: We need to check for the following constraints:
– bad cell needs not be covered
– no two tiles on the same cell
– The cells covered by a tile must be neightbor
– The cells covered by a tile cannot lie on a diagonal
The result program prog3:
% representation of the board
% col(.) and row(.) as in the queen example
% bad(.) for damaged cell
% ntiles is a constant for the number of tiles
col(1..n). row(1..n). tile(1..ntiles).

Tran Cao Son 64
bad(1,1). bad(3,2).
% generating possible solutions
2 {cell(I,J,T) : col(I) : row(J) } 2 :- tile(T).
% bad cell needs not be covered
:- col(I), row(J), tile(T), bad(I,J), cell(I,J,T).
% one tile over one cell only
:- col(I),row(J),tile(T1),tile(T2),neq(T1,T2),cell(I,J,T1),cell(I,J,T2).
% cell covered by the same tile must be neightbor

% (not far from each other)
:- tile(T), cell(I1,J1,T), cell(I2,J2,T), col(I1), col(I2),

row(J1), row(J2), I1 - I2 > 1.
Tran Cao Son 65


row(J1), row(J2), J1 - J2 > 1.
% they cannot be on a diagonal

row(J1), row(J2), neq(I1,I2), neq(J1,J2).
Tran Cao Son 66

Making it Shorter
col(1..n). row(1..n). tile(1..ntiles). %represenation
#domain tile(T;T1;T2).
#domain col(I;I1;I2).
#domain row(J;J1;J2).
bad(1,1). bad(3,2).
2 {cell(I,J,T) : col(I) : row(J) } 2 :- tile(T). %generating ..
:- bad(I,J), cell(I,J,T). % bad cell needs not ..
:- cell(I,J,T1),cell(I,J,T2),neq(T1,T2). % one cell one tile
:- cell(I1,J1,T), cell(I2,J2,T), I1 - I2 > 1. % neightbor only ..

:- cell(I1,J1,T), cell(I2,J2,T), J1 - J2 > 1.
:- cell(I1,J1,T), cell(I2,J2,T), neq(I1,I2), neq(J1,J2). % no diagonal
Tran Cao Son 67

K-clique
• Problem: Given a number k and a graph G. We say that G has a clique of size k if
there is a set of k different vertices (nodes) in G such that each pair of vertices from
this set is connected through an egde.
• Representation:
• Graph (node() and edge())
• Clique (clique(N )) to say that node N belongs to the clique if clique(N ) is true;
otherwise it does not belong to the clique.
• Generating a solution: Selecting k nodes – this is equivalent to assigning k atoms
of the set
{clique(1), . . . , clique(n)}
the truth value true. This can be achieved by the rule
k{clique(N ) : node(N )}k.
Tran Cao Son 68
• Checking for a solution: if every pair of the selected nodes is connected then this
is a solution; otherwise it is not a solution. This means that there exists no pair (I, J)
such that clique(I) and clique(J) are true but edge(I, J) is not true.
← clique(I), clique(J), I 6= J, not edge(I, J).
% prog4
node(1..5). % nodes
#domain node(N1;N2).
edge(1,2). edge(1,3). edge(2,3). % edges

edge(1,4). edge(1,5).
edge(N1,N2):- edge(N2,N1). % bi-directed
k {clique(N):node(N)} k. % generating solution
:- clique(N1), clique(N2), neq(N1,N2), not edge(N1,N2).
Tran Cao Son 69

Constraint Satisfaction Problem
• Problem: A constraint satisfactory problem (CSP) consists of

– a set of variables v1, . . . , vk ;
– a set of possible values for each variable, called the d omain of the variable;
– a set of constraints where a constraint can be either a allowed combination of
variables or a prohibited combination of variables;
– sometime, an optimal constraint on some objective function.
• Solution: An assignment of variables such that non of the constraints is violated.
• Idea for solving using CSP answer set programming:
– rules for specifying the domains of variables
– rules for generating a possible solution
– rules for checking the constraints
Tran Cao Son 70

Examples of CSP – n-Queens Problem
The n-queens problem could be viewed as a CSP:

• Variables: n-pairs (x1, y1 ), . . . , (xn, yn ), each represents a queen
• Domains of each variable: 1 ≤ xi, yi ≤ n
• Prohibited constraints: for every pair of i 6= j, xi 6= xj , yi 6= yj , and
|xj − xi | =
6 |yj − yi |.
• We do not have constraints for allowed combination.
Tran Cao Son 71

Examples of CSP – Combinatorial Auction
A company sells A a number of products p1, . . . , pn to m customers c1, . . . , cm . Each

customer bids on some of the items. The set of the items for customer ci will be denoted
by si . A customer wins a bid would imply that he gets everything he wants. The
company wants to get maximal profit. How should A decide who wins the auction?
Let bi denote the bid of customer i. Then, the problem is to find the value for bi, i.e., the
variables of the problem are bi’s.
The domain of each variable is {0, 1}.
We do not allow that two customers get the same item. This gives the prohibited
combination: ¬(bi ∧ bk ) for every pair i 6= k if si ∩ sk 6= ∅.
The company wants to get maximal profit means that the sum
Σni=1bipbi
should be maximum where pbi is the value of the item pi offered by customer i.
Tran Cao Son 72
Example 13 There are three items a, b, and c. Customer 1 wants a for $US 2 and b
for $US 4. Customer 2 wants a for $US 1 and c for $US 6. Who should win?
The problem has two variables: b1 and b2; s1 = {a, b} and s2 = {b, c}. s1 ∩ s2 6= ∅.
This means that we have a constraint ¬(b1 ∧ b2), i.e., we cannot sell to both 1 and 2.
Then, the constraint to maximize Σni=1bipbi makes us decide that 2 wins, i.e, we should
sell to 2.
Tran Cao Son 73

Solving CSP by Answer Set Programming
Given a CSP problem P , we define ΠP as a program consists of the following rules

• for each variable vi and each element cij in the domain of vi, ΠP contains a rule
vi(cij )
• for each variable vi, ΠP contains the rule

1{vi(ci1 ), . . . , vi(cinj )}1
• for each allowed combination co which allows vi1 , ldots, vij to take a value c∗i1 , . . . , c∗ij ,
ΠP contains the following three rules:
– constraint(co) ←
– satisf ied(co) ← vi1 (c∗i1 ), . . . , vij (c∗ij )
– ← constraint(co), not satisf ied(co).
which have the final effect of requiring vil to be assigned to the value cij .
Tran Cao Son 74
• for each prohibited combination co that disallows vi1 , ldots, vij to take a value
c∗i1 , . . . , c∗ij , ΠP contains the constraint:
← v1(c∗1 ), . . . , vn (c∗n).
NOTE: We simplify the problem a little bit here. A constraint co might place
conditions on only few variables – not all. Also, a variable might occur in more than
one allowed combination.
Tran Cao Son 75

A Program for n-Queens as CSP
Describing the variables:

x1(1). x1(2). . . . x1(n). . . . x2(1). x2(2). . . . x2(n).
y1(1). y1 (2). . . . y1(n). . . . yn (1). yn (2). . . . yn (n).
For the prohibited combination xi 6= xj we have:
← x1(1), x2(1). ← x1(1), x3(1) . . . ← x1(1), xn(1).
← x1(2), x2(2). ← x1(2), x3(2) . . . ← x1(2), xn(2).
...
← x1(n), x2(n). ← x1(n), x3(n) . . . ← x1(n), xn(n).
Similar rules are written for the prohibited combination yi 6= yj .
Rules for the prohibited combination |xi − xi| =6 |yi − yj |: for each pair i 6= j
← xi(c1), yi (r1), xj (c2), yj (r2),
abs(c1, r1, a1), abs(c2, r2, a2), a1 6= a2.
where abs(p, q, p − q) ← p ≥ q and abs(p, q, q − p) ← p < q are the two additional
rules.
Tran Cao Son 76

REASONING ABOUT ACTIONS AND CHANGES
Answer Set Programming. Reasoning about Actions and Changes
An Example – A Variation of the Yale Shooting Problem
Consider the story: Matt – a turkey – is walking along the road. Jimmy – a hunter – is
coming from the opposite direction. He takes out a loaded gun and shoots at Matt.
There are several questions that arise given the above story:
• Is Matt still alive?
• Is the gun still loaded?
• Is Jimmy walking?
• Does Jimmy have the same number of guns?
• etc.
Problems:
• the frame problem – compact representation of what does not change after the
execution of an action.
• the ramification problem – reasoning about indirect effects of actions.
Tran Cao Son 78

Frame and Ramification Problem

Consider the story: Matt – a turkey – is walking along the road. Jimmy – a hunter – is
coming from the opposite direction. He takes out one of his loaded guns and shoots at
Matt.
From the story, we know that the action “shoot” occurs. Commonsense tells us that the
turkey will be dead and the gun becomes unloaded if it can hold at most one bullet.
However, several other properties of the environment stay unchanged after the action
has completed. For instance,
• the road does not change its direction;
• the number of bullets in the other guns of Jimmy does not change;
• the number of guns belonging to Jimmy does not change
• the amount of water in the lake nearby does not change; etc.
• etc.
We also know that if Matt is hit by the gun, he will be dead and if he is dead he cannot
not continue walking.
Tran Cao Son 79

The Language A
A is a high-level action language for representing and reasoning about actions and
change. It has a simple and independent semantics based on transition system. It is
introduced in
• M. Gelfond and V. Lifschitz: “Representing Actions and Change by Logic Programs”,
Journal of Logic Programming, vol. 17, Num. 2,3,4, pp. 301–323, 1993.
Several extensions of A have been proposed. We will use AL, which is introduced in
• C. Baral, M. Gelfond: “Reasoning agents in Dynamic Domains.” Logic Based
Artificial Intelligence , Edited By J. Minker, Kluwer 2000
Tran Cao Son 80
In AL, an action theory is defined over two disjoint sets, a set of fluents (a fluent is a
property whose value changes over time) and a set of actions, and is a set of
propositional propositions of the form
a causes f if p1, . . . , pn (7)
f if p1, . . . , pn (8)
initially f (9)
where f and pi’s are fluent literals (a fluent literal is either a fluent g or its negation ¬g,
written as neg(g)) and a is an action. (7), referred as dynamic law, represents the
(conditional) effect of action a. (8) is a static law which represents the relationship
between fluents. Propositions of the form (9), also called v-propositions, are used to
describe the initial situation. An action theory is given by a pair (D, I) where D consists
of propositions of the form (7)-(9) and I consists of propositions of the form (9). D and
I will be called the domain description and initial state, respectively. We assume that
for each fluent f , initially f or initially ¬f belongs to I but not both.
Tran Cao Son 81

Example 14 (Story) • To say that initially, the turkey is walking and not dead,
we write
initially ¬dead and initially walking
• Initially, the gun is loaded
initially loaded
• Shooting causes the turkey to be dead if the gun is loaded can be expressed by
shoot causes dead if loaded and shoot causes ¬loaded if loaded

• Un/Loading the gun causes the gun to be un/loaded
load causes leaded and unload causes ¬loaded
• Dead turkeys cannot walk
¬walking if dead
So, the action theory is
Iy = { initially ¬dead, initially walking, initially loaded}
and
 
shoot causes dead if loaded

 shoot causes ¬loaded if loaded 

Dy = 
 load causes leaded ¬walking if dead 

Tran Cao Son 82

Semantics
load shoot
dead, -walking,
-loaded
load
dead, -walking, shoot

loaded shoot
-dead, walking,
-loaded
shoot
shoot
load
-dead, -walking,
loaded
-dead, walking,
shoot loaded
load
-dead, -walking,
-loaded load
shoot
Figure 4: Transition Diagram for (Dy , Iy )
Each node represents a state: a consistent and complete set of fluent literals satisfying
all the static laws in Dy . (Picture)
Tran Cao Son 83

• Each node represents a state: a consistent and complete set of fluent literals satisfying
all the static laws in Dy .
• A fluent literal l holds in a state s if l ∈ s.
• Each directed link between two states s1 and s2 represents a transition from s1 to s2
due to the execution of the action (the label of the link). s2 is called a possible next
state.
• Transition function Φ specifies the set of possible next states:
Φ(a, s) = {s′ | s′ is a possible next state}.
For example,
Φ(shoot, s1) = {s2}
where s1 = {loaded, walking, ¬dead} and s2 = {¬loaded, ¬walking, dead}.
• Φ is extended to define Φ̂ by
– Φ̂([], s) = {s}
– Φ̂([a1, . . . , an], s) = s′∈Φ(a1 ,s) Φ̂([a2, . . . , an], s′ ).
S
The entailment relation of (D, I) is defined by:

D |= f after a1, . . . , an iff f holds in every state in Φ̂([a1, . . . , an], s0). (10)
Tran Cao Son 84

Interested Questions in Reasoning About Actions and Changes
Given an action theory (D, I), we are often interest in the following questions/problems:
• Projection: What will be true/false after the execution of the sequence of action
a1, . . . , am from the initial state? Or, whether
(D, I) |= f after a1, . . . , an (11)
holds for a given fluent literal f .
• Planning: Which sequence of actions will changes the world from the initial state into
a state that satisfies a given fluent literal f ? Or, find a sequence of action a1, . . . , am
such that f will be true after the execution of the sequence of action a1, . . . , am from
the initial state.
Remark 10 We can easily generalize the result to answer questions with respect to a
fluent formula.
Tran Cao Son 85

A Logic Program for Projection (Computing |=)
Given an action theory (D, I) and a sequence of actions α = [a1, . . . , an], we want to
know what is true and what is false after the execution of α from the initial state. In
other words, for every fluent f , we want to know whether
(D, I) |= f after a1, . . . , an
holds or not.
We will compute |= using logic programming. For each action theory (D, I), we define a
program π(D, I) as follows. The language of π(D, I) contains the following predicates:
• holds(F, T ): this states that the fluent literal F holds at time T .
• occ(A, T ): action A occurs at time moment T .
• time(T ): denotes the time moment T .
Tran Cao Son 86
and we make sure that the following property holds:

(D, I) |= f after a1, . . . , an if f π(D, I) |= holds(f, n)
where the first |= symbol represents the entailment relation defined in (10) and the
second |= symbol represents the entailment relation defined by the answer set semantics
of π(D, I).
The program π(D, I) is defined as follows:
• For each dynamic law “a causes f if f1 , . . . , fn ”, π(D, I) contains the following
rule:
holds(f, T + 1) ← time(T ), occ(a, T ), holds(f1, T ), . . . , holds(fn, T ). (12)
• For each static law “f if f1 , . . . , fn ” , π(D, I) contains the rule:
holds(f, T + 1) ← time(T ), holds(f1, T ), . . . , holds(fn, T ). (13)
• For each v-proposition “ initially f ”, π(D, I) contains the rule
holds(f, 0). (14)
• For each fluent f , π(D, I) will also contain the well-known inertial rules:
holds(f, T + 1) ← time(T ), f luent(f ), holds(f, T ), not holds(¬f, T + 1).
holds(¬f, T + 1) ← time(T ), f luent(f ), holds(¬f, T ), not holds(f, T + 1).
(15)
Tran Cao Son 87
Remark 11 π(D, I) also contains some rules that make the encoding more compact.
(See example).
Let π n be the set of rules of π(D, I) in which the time variable takes the value from 0 to
n. Let π = π n ∪ {occ(a1, 0), . . . , occ(an , n − 1)}. The following can be proven:
Theorem 5 For every action theory (D, I), a sequence of actions a1, . . . , an, and a
fluent f ,
(D, I) |= f after a1, . . . , an
iff
π |= holds(f, n),
i.e., holds(f, n) belongs to every answer set of the program π.
Tran Cao Son 88

Example – One Gun

For the Yale-Shooting problem we have the following rules (See proga1):
% Defining time %defining fluents
time(0..length). fluent(loaded). fluent(dead). fluent(walking).
% Defining actions
action(load). action(shoot).
% The initial state

holds(loaded, 0). holds(neg(dead), 0). holds(walking, 0).
% Representing action’s effects

holds(dead, T+1) :- time(T), occ(shoot, T), holds(loaded, T).
holds(neg(loaded), T+1) :- time(T), occ(shoot, T).
holds(loaded, T+1) :- time(T), occ(load, T).
% Static law
holds(neg(walking), T) :- holds(dead, T).
Tran Cao Son 89
% Defining fluent literals/Contrary literals

literal(F):- fluent(F). literal(neg(F)):- fluent(F).
contrary(F, neg(F)):- fluent(F). contrary(neg(F), F):- fluent(F).
% The inertial rule

holds(F,T+1):- literal(F), time(T), holds(F,T),
contrary(G,F), not holds(G,T+1).
To determine whether
(D, I) |= dead after shoot,
we compute the answer sets of the program π = π 1 ∪ occ(shoot, 0) using the command
lparse -c length=1 proga1 a1inst | smodel 0
where the file a1inst contains the two facts: occ(shoot, 0). It is easy to verify that
holds(dead, 1) belongs to every answer set of π and thus (D, I) |= dead after shoot.
Remark 12 The constant length is used to specify the length of the action sequence.
Tran Cao Son 90

Considering Executability Condition
Sometime, an action requires some condition for it to be executable. In AL, this is

called an executability condition and is described by a proposition of the form
a executable if p1 . . . , pn (16)
which says that a can only be executed if the fluent literals p1 . . . , pn hold.
For instance, Jimmy (the hunter) can only execute the action shoot if he is not
wounded. This is expressed by
shoot executable if ¬wounded
Introducing executability condition requires some changes:
• In the transition diagram, the link with the label a between s and s′ exists only if a is
executable in s and s′ is a possible state reached after executing a.
Tran Cao Son 91
• In the program π(D, I), for each proposition (16), we add a rule
possible(A, T ) ← holds(p1, T ), . . . , holds(pn, T ).
Furthermore, we add a constraint
← occ(A, T ), not possible(A, T )
to π(D, I) which forbids A to occur when its executability condition is not satisfied.
π(D, I) can be used in the same way for projection as before.
Tran Cao Son 92

Another Example — The Block World Domain
c
b a
Figure 5: A Block World Domain
In this domain we have 3 blocks a, b, c. Each block is either on the table or on top of
another block. They form tower like b and c (a tower of 2 blocks), and a (a tower of one
block). The top block of a tower can be moved to the table or on top of another tower.
To move a block, that is not on top of a tower, we need to move all the blocks above it.
Furthermore, we are interested in building a new tower or finding out where a block is
located, whether a block is on the table, on top of some other block, etc.
We will write on(X, Y ) to denote that block X is on block Y ; We will also use t as a
constant to denote the table. We write move(X, Y ) to represent the action that moves
X on top of Y .
Tran Cao Son 93
c
b a
Figure 6: A Block World Domain
The set of fluents F is

{on(X, Y ) | X, Y ∈ {a, b, c, t}}\({on(X, X) | X ∈ {a, b, c, t}∪{on(t, X) | X ∈ {a, b, c}).
Furthermore, the set of actions A is
{move(X, Y ) | X, Y ∈ {a, b, c}, X 6= Y } ∪ {move(X, t) | X ∈ {a, b, c}}.
Tran Cao Son 94

We begin with describing the initial state:







initially on(c, b)

Ib = 

initially on(b, t)
initially on(a, t)




In addition, we also have that

initially ¬on(X, Y ) where on(X, Y ) ∈ F \ {on(c, b), on(b, t), on(a, t)}. The domain
Db contains of the following propositions

move(a, b) executable if ¬on(c, a), ¬on(c, b), ¬on(b, a), ¬on(a, b)






move(a, t) executable if ¬on(c, a), ¬on(b, a)







...







move(a, b) causes on(a, b)








Db = 

move(a, t) causes on(a, t)
...







¬on(a, t) if on(a, b)








¬on(a, c) if on(a, b)







 ...



Tran Cao Son 95

A Program for the Block World Domain
% Defining the time constants and objects

time(0..length). block(a). block(b). block(c).
% Defining fluents
fluent(on(X,Y)):- block(X), block(Y), neq(X,Y).
fluent(on(X,t)):- block(X).
% Defining an additional fluent whose value is determined by others

fluent(clear(X)):- block(X).
% Defining actions
action(move(X,Y)):- block(X), block(Y), neq(X,Y).

action(move(X,Y)):- block(X), table(Y).
Tran Cao Son 96

% Static law
holds(neg(on(X,Y)), T):- time(T),
block(X), block(Y), neq(X,Y),
block(Z), neq(X,Z), neq(Y,Z), holds(on(X,Z), T).
holds(neg(on(X,Y)), T):- time(T),

block(X), block(Y), neq(X,Y), holds(on(X,t), T).
holds(neg(on(X,t)), T):- time(T),

block(X), block(Y), neq(X,Y), holds(on(X,Y), T).
holds(neg(clear(X)), T):- time(T),

fluent(on(Y,X)), holds(on(Y,X), T).
holds(clear(X), T):- time(T),

block(X), not holds(neg(clear(X)), T).
% Executability condition
possible(move(X,t),T):- block(X), time(T), holds(clear(X), T).
Tran Cao Son 97
possible(move(X,Y),T):- time(T), block(X), block(Y), neq(X,Y),

holds(clear(X), T), holds(clear(Y), T).
:- action(A), time(T), occ(A,T), not possible(A,T).
% Representing action effects
holds(on(X,Y), T+1):- time(T),

block(X), block(Y), neq(X,Y), occ(move(X,Y), T).
holds(on(X,t), T+1):- time(T), block(X), occ(move(X,t), T).
% The initial state

holds(on(c,b), 0).
holds(on(a,t), 0).
holds(on(b,t), 0).
holds(neg(F), 0):- fluent(F), not holds(F, 0).
% Defining fluent literals/Contrary literals
Tran Cao Son 98


% The inertial rule

holds(on(X,Y), T+1) :-
time(T),
holds(on(X,Y), T),
not holds(neg(on(X,Y)), T+1).
holds(on(X,t), T+1) :-
time(T),
holds(on(X,t), T),
not holds(neg(on(X,t)), T+1).
We then can use Smodels to answer query like
(Db, Ib ) |= on(a, c) ∧ on(c, t) after [move(c, t), move(a, c)]
Tran Cao Son 99

Planning
Answer set planning was introduced in

• V. Lifschitz, “Answer set planning,” in Proceedings of the 1999 International
Conference on Logic Programming, 1999, pp. 23-37.
• V. Subrahmanian and C. Zaniolo, “Relating stable models and ai planning domains,”
In Proceedings of the International Conference on Logic Programming, 1995, pp.
233–247.
A planning problem is specified by a triple hD, I, ϕi where (D, I) is an action theory
and ϕ is a fluent formula (or goal), representing the goal state. A sequence of actions
a1, . . . , am is a plan for ϕ if
(D, I) |= ϕ after a1, . . . , am.
Tran Cao Son 100

Given a planning problem hD, I, ϕi, answer set planning solves it by translating it into a
logic program Π(D, I, ϕ) that has two components:
• The program π(D, I): this program describes the action theory (D, I).
• The set of rules for describing the goal and generating action occurrences:
– for each f ∈ ϕ, Π(D, I, ϕ) contains the rule
← not holds(f, length). (17)
which guarantees that f holds at the time moment length
– a rule of the form
1{occ(A, T ) : action(A)}1 ← time(T ), T < length. (18)
which states that at any moment of time, one and only one action must occur. We
add the condition T < length to not allow actions to occur at the time length.
Remark 13 Correctness of Π(D, I, ϕ) can be found in
• Tran Cao Son, Chitta Baral, Tran Hoai Nam, and Sheila McIlraith,
“Domain-Dependent Knowledge in Answer Set Planning,” ACM TOCL.
Tran Cao Son 101

Answer Set Planning – Examples
• Suppose that we are interested in the planning problem (Dy , Iy , dead), we need to add
the following rules to this program:
:- not holds(dead, length).
1{occ(A,T) : action(A)} 1 :- time(T), T < length.
Generating an answer set for this, we will find a plan shoot.

• For the block world domain, to check whether the goal situation in the next Figure
can be achieved
Tran Cao Son 102

a
c b
b a c
Initial Goal
we add the following rule to the program:
1 {occ(A,T) : action(A) } 1 :- time(T), T < length.
:- not goal(length).
goal(T):- time(T), holds(on(c,t), T),

holds(on(b,c), T), holds(on(a,b), T).
Computing an answer set, we obtain an answer set containing the atoms
occ(move(b,c),1) occ(move(a,b),2) occ(move(c,t),0) which represent the
plan move(c, t), move(b, c), move(a, b).
Tran Cao Son 103

Another Example — Missionaries and Cannibals
% Defining the constants

time(0..length).
number(0..3).
missionary(1..3). cannibal(1..3).
location(l1). location(l2). % two banks
% X missionaries and Y cannibals are at location L

fluent(at(X,Y,L)):- missionary(X),cannibal(Y),location(L).
% the boat is at location L

fluent(boat_at(L)):- location(L).
% X missionaries and Y cannibals move from one bank to another bank

action(cross(I,J,L)):-
number(I), number(J), location(L), I+J <= 2, I+J > 0.
Tran Cao Son 104

% effects of crossing
holds(at(M+P,N+Q,L1),T+1):-
time(T),
number(M), number(N), location(L),
number(P), number(Q), action(cross(M,N,L)),
occ(cross(M,N,L), T), location(L1), neq(L,L1),
holds(at(P,Q,L1), T).
holds(boat_at(L1),T+1):-
time(T),
action(cross(M,N,L)), location(L1), neq(L,L1),
occ(cross(M,N,L), T).
holds(neg(boat_at(L)),T+1):-
time(T),
action(cross(M,N,L)),
occ(cross(M,N,L),T).
Tran Cao Son 105

holds(at(P-M,Q-N,L),T+1):-
time(T),
number(P), number(Q), action(cross(M,N,L)),
occ(cross(M,N,L), T),
holds(at(P,Q,L), T).
% executability condition
possible(cross(I,J,L), T):-
time(T),
number(I), number(J), location(L),
number(P), number(Q), action(cross(I,J,L)),
holds(boat_at(L), T),
holds(at(P, Q, L), T), P>=I, Q>=J.
% initial condition
holds(at(3,3,l1),0).
holds(at(0,0,l2),0).
holds(boat_at(l1),0).
Tran Cao Son 106

% constraint
:- number(I), number(J), location(L), I+J <= 2, I+J>0,
time(T), occ(cross(I,J,L), T), not possible(cross(I,J,L), T).
not_good :- number(I), number(J), location(L),

time(T), holds(at(I,J,L), T), I < J, I > 0.
:- not_good.
% goal
:- not goal(length).
goal(T):- time(T), holds(at(3,3,l2), T).

goal(T+1):- time(T), goal(T).
1 { occ(A, T): action(A) } 1 :- time(T), not goal(T).
Tran Cao Son 107

Diagnosis
Reference
• Chitta Baral, Sheila McIlraith, and Tran Cao Son. Formulating diagnostic problem
solving using an action language with narratives and sensing, Proceedings of the
International Conference on the Principles of Knowledge Representation and
Reasoning (KRR’00), 2000, pages 311-322.
Consider the following narrative
• 9am: John arrived at work and turned the light on. As usual, the light went on and
John started his daily work.
• 12 pm: John turned off the light and went to lunch.
• 1pm: John turned on the light when he got back from lunch. The light did not go on.
• 1:15pm: The company’s electrician arrived. He replaced the bulb and turned on the
light, the light did not go on. He then checked the fuses and replaced one which was
blown. The light is back.
Tran Cao Son 108

Narrative Description – General Idea
'$ '$ '$ '$

turn on turn off turn on
¬light on - light on - ¬light on - ¬light on
&% &% &% &%

s0 s1 s2 s3
The narrative can be described by a triple (SD, COM P S, OBS) where

• SD is an action theory describing actions (e.g. turn on, turn off, replace bulb, etc.)
and their expected outcomes and relationships between fluents. It includes also
actions that are beyond the control of the agents such as break(bulb) causes the bulb
to be broke.
• COM P is a set of objects that can be broken (bulb, fuse, ...); for each object o, an
action of the form break(o) with the outcome ab(o), indicating that o is broken, is
included in SD.
• OBS is a set of observations that describes the history of the world (might be
incomplete) in term of which actions were executed, when they were executed relative
to each other, and what are the outcomes of the actions;
Tran Cao Son 109

The Narrative as a System

We illustrate the concepts using the example. Let Sys = (SD, {bulb}, OBS) be a
ssytem with






(r1) turn on causes light on if ¬ab(bulb)
(r2) turn off causes ¬light on




SD = 
 



(r3) ¬light on if ab(bulb)
(r4) break(bulb) causes ab(bulb)



and 
(o1)





turn on occurs at s0
(o2) turn off occurs at s1







(o3) turn on between s2, s3








(o4) s0 precedes s1







(o5) s1 precedes s2




OBS = 




(o6) s2 precedes s3

(o7) ¬light on at s0







(o8) light on at s1







(o9) ¬light on at s2








 (o10) ¬light on at s3


Tran Cao Son 110

Diagnostic Reasoning Process
Address the questions

• when does a system need a diagnosis?
Answer: When there are inconsistency between observations and expected outcomes;
or when the system does not have a model if we remove all actions break(o) from SD.
• what are the diagnoses?
Answer: Additional action occurrences that help explain the indescrepancies
between observations and expected outcomes.
• how to fix a system that needs a diagnosis?
Answer: Collecting enough information and executing test actions if necessary so
that a diagnosis is singed out. Thereafter, executing the repair actions necessary to fix
the system.
Tran Cao Son 111

Diagnostic Reasoning Process – A Summary
Answer the question: when a system needs a diagnosis and what are the diagnoses.
• generating candidate diagnoses based on an incomplete history of events that have
occurred and observations that have been made.
• in the event of multiple candidate diagnoses, performing actions to enable observations
that will discriminate candidate diagnoses. The selection of a particular action is often
biased towards confirming the most likely diagnosis, or the one that is easiest to test.
• generating (possibly with conditional) plans, comprising both world-altering actions
and sensing actions, to discriminate candidate diagnoses.
• updating the space of diagnoses in the face of changes in the state of the world, and in
the face of new observations.
Tran Cao Son 112

The Narrative as a Logic Program – General Idea
Given a system description (SD, COM P S, OBS) with

• SD: a set of propositions of the form a causes f if p1, . . . , pn or f if p1, . . . , pn;
this set of propositions describes the normal system behavior;
• COM P S: a set of components that can be broken
• OBS: a set of observations representing a narrative of the system.
We will write a logic program Π(SD, COM P S, OBS) (or Π for short) to compute
diagnoses. Π will need to contain the following parts:
• rules for generating a sequence of actions
• rules for checking if the generated sequence of actions is a possible diagnosis; this
includes
– rules that assign situations to time moments – this assignement must respect the
ordering between situations in the observations
– rules that make sure that observations are satisfied.
Tran Cao Son 113

Elements of Π – Part 1
Constants: time, situations, actions, fluents, and literals

time(0..length).
% define situations
sit(s0). sit(s1). sit(s2). sit(s3).
% actions
action(turn_on). action(turn_off). action(break(bulb)).
% fluents
fluent(light_on). fluent(ab(bulb)).
% literal
Tran Cao Son 114

Effects of actions (similar to what has been done in the part on reasoning about
actions/planning).
holds(light_on, T+1):- time(T),
occ(turn_on, T), holds(neg(ab(bulb)), T).
holds(neg(light_on), T+1):- time(T), occ(turn_off, T).
holds(ab(bulb), T+1):- time(T), occ(break(bulb), T).
holds(neg(light_on), T):- time(T), holds(ab(bulb), T).
% inertial axiom
holds(F, T+1):- time(T), literal(F), contrary(F, G),

holds(F, T), not holds(G, T+1).
Tran Cao Son 115

Satisfying all the observations

% specifying the set of observations situation order
prec(s0,s1). prec(s1,s2). prec(s2,s3).
% fluent observations
at(neg(light_on), s0). at(neg(ab(bulb)), s0). at(light_on, s1).

at(neg(light_on), s2). at(neg(light_on), s3).
% action observations
between(s0,s1,turn_on). between(s2,s3,turn_on).
Tran Cao Son 116

% generating situation order each situation happens at a time moment
1 {happens(S, T): time(T) } 1 :- sit(S).
% s0 is always at the time moment 0

:- time(T), happens(s0,T), T > 0.
:- time(T), happens(s3,T), T < length.
:- time(T1), time(T2), sit(S1), sit(S2),

happens(S1,T1), happens(S2,T2), prec(S1,S2), T1>T2.
:- time(T1), time(T2), sit(S1), sit(S2), action(A),

happens(S1,T1), happens(S2,T2), between(S1,S2,A), neq(T2,T1+1).
% generating action occurrences

{occ(A, T): action(A)} 1 :- time(T), T < length.
Tran Cao Son 117

% fluent observations
holds(F, T):- time(T), literal(F), sit(S), at(F, S), happens(S, T).
% constraints, making sure that action occurrences happen

% as they are observed
:- time(T1), time(T2), action(A), action(A1),

between(S1,S2,A), happens(S1,T1), occ(A1,T1), neq(A1, A).
occ(A, T1):- time(T1), action(A), between(S1,S2,A), happens(S1,T1).
:- time(T), action(A1), action(A2), neq(A1,A2), occ(A1, T), occ(A2, T).
% constraints that eliminate inconsistency model

:- time(T), fluent(F), holds(F, T), holds(neg(F), T).
Tran Cao Son 118

lparse -c length=5 bulb | smodels

smodels version 2.26. Reading...done
Answer: 1
Stable Model:
occ(turn_on,0)
occ(turn_off,1)
occ(turn_on,2)
occ(break(bulb),3)
occ(turn_on,4)
happens(s3,5) happens(s2,4) happens(s1,1) happens(s0,0)
prec(s2,s3) prec(s1,s2) prec(s0,s1)
Tran Cao Son 119

Other Applications – References
• E. Erdem, V. Lifschitz and M. Wong, Wire routing and satisfiability planning, in

Proc. CL-2000, 2000.
• E.Erdem, V. Lifschitz and D. Ringe, Temporal phylogenetic networks and logic
programming, Theory and Practice of Logic Programming.
• T. Eiter: Data Integration and Answer Set Programming. LPNMR 2005: 13-25
• E. Erdem, V. Lifschitz, L. Nakhleh and D. Ringe, Reconstructing the evolutionary
history of Indo-European l anguages using answer set programming, PADL-2003.
• M. Balduccini and M. Gelfond: Diagnostic Reasoning with A-Prolog, TPLP,
3(4-5):425-461, 2003.
• M.Balduccini, M.Gelfond, M.Nogueira, R.Watson,M.Barry: An A-Prolog decision
support system. for the space shuttle, AAAI Spring 2001 Symposium, Mar 2001
• K. Heljanko and I. Niemelä. Bounded LTL Model Checking with Stable Models,
TPLP, 3 (4-5): 519-550, 2003.
Tran Cao Son 120

CURRENT ISSUES
Answer Set Programming. Current Issues
Theoretical Issues
• Language development: extensions to allow new language constructors that are

useful for knowledge representation. For example, there is a growing interest in
developing logic programs with
– aggregates,
– ordered disjunction, and
– constraint atoms
This includes the introduction of new constructors and the semantics of the programs
with these constructors. Some references:
– N. Pelov, Semantics of logic programs with aggregates, Ph.D. Thesis, Department
of Computer Science, K.U.Leuven, Leuven, Belgium, April, 2004.
– W. Faber, N. Leone, and G. Pfeifer, Recursive aggregates in disjunctive logic
programs: Semantics and complexity. Proceedings of JELIA 04.
– L. Liu and M. Truszczynski, Properties of Programs with Monotone and Convex
Constraints. Proceedings of AAAI-05.
Tran Cao Son 122
– G. Brewka, I. Niemelä, and T. Syrjänen. Logic Programs with Ordered

Disjunction. To appear in Computational Intelligence, 20(2), 333-357, 2004.
– T. C. Son, E. Pontelli, and I. Elkabani: A Translational Semantics for Aggregates
in Logic Programming, NMSU-CS-2005-005.
• New characterization of answer sets: this includes the study of the semantics
here-and-there, the characterization of answer sets using rule graphs, or the
relationship between graph coloring and answer sets. Some references:
– V. Lifschitz, D. Pearce and A. Valverde, Strongly equivalent logic programs, ACM
Transactions on Computational Logic, Vol. 2, 2001, pp. 526-541.
– P. Ferraris and V. Lifschitz, Weight constraints as nested expressions, Theory and
Practice of Logic Programming, Vol. 5, 2005, pp. 45–74.
– K. Konczak, T. Linke, T. Schaub: Graphs and Colorings for Answer Set
Programming: Abridged Report. LPNMR 2004: 127-140
– S. Costantini, O. M. D’Antona, A. Provetti: On the equivalence and range of
applicability of graph-based representations of logic programs. Inf. Process. Lett.
84(5): 241-249 (2002)
• Study of properties of programs: building block results for normal logic programs as
well as programs within the new language (e.g. with new language constructor) are
Tran Cao Son 123
studied. In particular, theorems

– on the conditions for equivalence between logic programs (strong/weak equivalent)
– that can easy the process of proving properties of a programs (e.g. correctness of
programs),
– that provide new insight in the definition of answer set semantics,
– that open the door for new way to compute answer sets,
are sought.
More references
• F. Lin and X. Zhao, On odd and even cycles in normal logic programs In Proc. of
AAAI-04. pp. 80-85
• F. Lin, Reducing Strong Equivalence of Logic Programs to Entailment in Classical
Propositional Logic In Proc. of KR-02.
• F. Lin, Y. Zhao. ASSAT: Computing answer sets of a logic program by SAT solvers
• J. Lee, A Model-Theoretic Counterpart of Loop Formulas, Proc IJCAI-05.
• M. Gebser and T. Schaub, Loops: Relevant or Redundant, LPNMR-05.
• F. Lin, Y. Chen, Discovering Classes of Strongly Equivalent Logic Programs,
IJCAI-05.
Tran Cao Son 124
Implementation Issues
• Development of answer set solvers: Current answer set solvers have restrictions on
the type of atoms that can be considered (e.g., ground programs, no recursive
aggregates, etc.) Providing new answer set solvers that can deal with more expressive
programs is the goal of developers of new answer set solvers. Some attempts can be
found in
– T. Eiter, M. Fink, H. Tompits, S. Woltran: Strong and Uniform Equivalence in
Answer-Set Programming: Characterizations and Complexity Results for the
Non-Ground Case. AAAI 2005: 695-700.
– T. Eiter, W. Faber, M. Fink, G. Pfeifer, S. Woltran: Complexity of Answer Set
Checking and Bounded Predicate Arities for Non-ground Answer Set
Programming. Answer Set Programming 2003
– T. Dell’Armi, W. Faber, G. Ielpa, N. Leone, S. Perri, G. Pfeifer: System
Description: DLV with Aggregates. LPNMR 2004: 326-330
– I. Elkabani, E. Pontelli, T. C. Son: SmodelsA - A System for Computing Answer
Sets of Logic Programs with Aggregates. LPNMR 2005: 427-431
Tran Cao Son 125
– E. Pontelli, T. C. Son, I. Elkabani: Smodels with CLP? A Treatment of

Aggregates in ASP. LPNMR 2004: 356-360.
• Development of tools and programming environment: References on the integration
of answer set programming into other languages and an interactive environment for
answer set programming can be found in
– O. El-Khatib, E. Pontelli, T. C. Son: ASP-PROLOG: A System for Reasoning
about Answer Set Programs in Prolog. PADL 2004: 148-162
– O. El-Khatib, E. Pontelli, T. C. Son: Justification and debugging of answer set
programs in ASP. AADEBUG 2005: 49-58
Tran Cao Son 126

Asp Tutorial

Uploaded by

Copyright:

Available Formats

Asp Tutorial

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Asp Tutorial

Uploaded by

Copyright:

Available Formats

ANSWER SET PROGRAMMING

Tran Cao Son

New Mexico State University

Las Cruces, NM 88011, USA

Tran Cao Son 1

Introduction — Answer Set Programming

Answer set programming is a new programming paradigm. It is introduced in the late

Tran Cao Son 2

• Introduce answer set programming

Tran Cao Son 3

Tran Cao Son 4

Terminologies – many brorrowed from classical logic

Tran Cao Son 6

First Order Language, Herbrand Universe, and Herbrand Base

Tran Cao Son 7

Logic Programs – Syntax

Tran Cao Son 8

– LΠ: The language of a program Π is the language consists of the constants,

Tran Cao Son 9

Tran Cao Son 10

Intuition and Examples of Using LP (Positive Programs)

Tran Cao Son 11

Definition 2 The Herbrand universe (resp. Herbrand base) of Π, denoted by UΠ

Tran Cao Son 12

Semantics – Positive Programs without Constraints

Tran Cao Son 13

For Π = {p(f (X)) ← p(X). q(a) ← p(X).}

Tran Cao Son 14

Tran Cao Son 15

• For Π1 = {p(X) ← q(f (X), g(X)). r(Y ) ←}

• For Π3 = {p(f (X)) ← p(X). q(a) ← p(X). p(b).}

Tran Cao Son 17

We have that MΠ = lf p(TΠ) = {q(a)} ∪ {p(f i(b)) | i = 0, 1, . . .}

Π |= p(f i (b)) for i = 0, 1, . . .

Tran Cao Son 18

Entailment – Another Example

• Consider a directed graph G described by a set of atoms of the form edge(X, Y ).

Tran Cao Son 20

Semantics – General Logic Programs without Constraints

Tran Cao Son 21

Tran Cao Son 23

Examples about Answer Sets

Tran Cao Son 24

Entailment w.r.t. Answer Set Semantics

• For a program Π and an atom a, Π entails a, denoted by Π |= a, if a ∈ S for every

Tran Cao Son 26

Further intuitions behind the semantics

Tran Cao Son 27

Tran Cao Son 29

Normally, a’s are b’s. b(X) ← a(X), not ab(r, X)1

Tran Cao Son 30

Example 8 (Birds) Suppose that we know

Tran Cao Son 31

{bird(tim), f lies(tim), penguin(tweety), ab(r1, tweety), bird(tweety)

Πb |= f lies(tim) and Πb |= ¬f lies(tweety)

Tran Cao Son 32

Example 9 (Animals) Consider the following information:

Tran Cao Son 33