ANSWER SET PROGRAMMING

Chitta Baral

Department of Computer Science and Engg.

Arizona State University Tempe, AZ 85287 chitta@asu.edu

http://www.public.asu.edu/∼cbaral

November 22, 2002

INTRODUCTION

Answer set Programming  Introduction

Declarative Programming

• Answer set programming is a kind of declarative programming.

• Declarative programming: Specify what you want, not How. Leave the How part to the system to figure out.

• Prolog (programming in logic) was one of the first declarative programming language.

Declarative Programming: an example

• Linear programming max f(X_{1}, …, X_{n}) such that g_{1}(X_{1}, …, X_{n}) ≤ k_{1} ⋮ g_{m}(X_{1}, …, X_{n}) ≤ k_{m}

Prolog vs Answer set programming

• Prolog – Problem solving is done by asking a query with a variable.

– The instantiations of that variables encode the solution of the problem.

– Prolog has many non-declarative features.

• Answer set programming (AnsProlog)

– Problem solving is done by computing the “models” (answer sets) of the program.

– Each answer set encodes a solution of the problem.

– AnsProlog (also called A-Prolog) is full declarative.

Answer set Programming  Introduction to AnsProlog by examples

INTRODUCTION TO ANSPROLOG BY EXAMPLES Horn program 1

p ← a.
q ← b.
a ←.

• {a, p} is an answer set of the above program.

• {a, p, b, q} is not an answer set of the above program.

• {a} is not an answer set of the above program.

• {a, p} is the only answer set of the above program.

Horn program 2

p ← p.
q ←.

• {q} is an answer set of the above program.

• {p, q} is not an answer set of the above program.

• {p} is not an answer set of the above program.

• {} is not an answer set of the above program.

• {q} is the only answer set of the above program.

Horn program 3: Ancestors and parents

anc(X, Y) ← par(X, Y).
anc(X, Y) ← anc(Z, Y), par(X, Z).
par(a, b) ←.
par(b, c) ←.
par(d, e) ←.

• Computing the answer set: – Iteration 0: {}

– Iteration 1: Add {par(a, b), par(b, c), par(d, e)}

– Iteration 2: Add {anc(a, b), anc(b, c), anc(d, e)}

– Iteration 3: Add {anc(a, c)}

– Iteration 4: Add {}. STOP.

– Answer set = {par(a, b), par(b, c), par(d, e), anc(a, b), anc(b, c),

anc(d, e), anc(a, c)}.

Chitta Baral  8

• For efficiency purposes: Domains of variables are required in most AnsProlog systems (such as Smodels or Dlv). anc(X, Y) ← domain(X), domain(Y), par(X, Y). anc(X, Y) ← domain(X), domain(Y), domain(Z),

anc(Z, Y), par(X, Z).

par(a, b) ←. par(b, c) ←. par(d, e) ←. domain(a) ←. domain(b) ←. domain(c) ←. domain(d) ←. domain(e) ←.

• Ordering of rules(top-to-bottom) in the file and ordering of predicates in the body of rule (left-to-right) is important in Prolog. NOT so in AnsProlog.

AnsProlog program 1

a ← not b.
q ←.

• {q, b} is not an answer set of the above program.

• {q, a, b} is not an answer set of the above program.

• {q, a} is the only answer set of the above program.

AnsProlog program 2

a ← not b. b ← not a.

• {a} and {b} are answer sets of the above program.

a ← not b. b ← not a.

p ← a.

• {p, a} and {b} are answer sets of the above program.

Semantics of AnsProlog

• Intuition: A is an answer set of a program Π if using the assumption of A the ‘simplification’ of the program Π, a Horn program denoted by Π^{A}, has the only answer set A.

• Similar to solving x = f(x).

– We need to know what is false to be able to simplify the program to a Horn program where we can reason.

– But to know what is false we need the answer set.

– Prolog gives up on this.

– This will turn out to be very important.

• The Simplification (Gelfond-Lifschitz transformation) of Π with respect to a set of atoms A – denoted by Π^{A}.

Chitta Baral  12

– Remove a rule from Π if its body contains not b, where b ∈ A.

– From the remaining rules remove from the body of a rule in Π a component ‘not c’ if c is in A.

• Consider Π = {a ← not b.; b ← not a.}.

• Let A_{1} = {a}, A_{2} = {b}, A_{3} = {}, and A_{4} = {a, b}.

• Π^{A_{1}} = {a ← .} has the only answer set {a} = A_{1}. Hence, A_{1} is an answer set of Π.

• Π^{A_{2}} = {b ← .} has the only answer set {b} = A_{2}. Hence, A_{2} is an answer set of Π.

• Π^{A_{3}} = {a ← .; b ← .} has the only answer set {a, b} = A_{4}. Hence, A_{3} is not an answer set of Π.

• Π^{A_{4}} = {} has the only answer set {} = A_{3}. Hence, A_{3} is not an answer set of Π.

AnsProlog programs 3 and 4

a ← not b.
b ← not c.
d ←.

• Answer set of the above program is {d, b}.

p ← not q, r.
q ← not p.

• Answer set of the above program is {q}.

AnsProlog programs 5, 6 and 7

p ← not p, d. r ←. d ←.

• The above program does not have an answer set.

p ← not p, d. r ← not d. d ← not r.

• The only answer set of the above program is {r}.

p ← not p. p ← not d. r ← not d. d ← not r.

• The only answer set of the above program is {r, p}.

SIMPLE ANSPROLOG MODULES

Answer set Programming  Simple AnsProlog Modules

Integrity constraints

• To incorporate the integrity constraint ← l_{1}, …, l_{m}, not l_{m+1}, …, not l_{n}. to a program Π either of the following approach is fine.

• Using a new atom p which is not in Π add the following rule: p ← not p, l_{1}, …, l_{m}, not l_{m+1}, …, not l_{n}.

• Using new atoms p and q which is not in Π add the following rules: p ← l_{1}, …, l_{m}, not l_{m+1}, …, not l_{n}. q ← not p. q ← not q.

Finite enumeration

• Specification: We have atoms p_{1}, …, p_{n}. We would like to construct a program where for each interpretation of the propositions we have an answer set.

• Program: p_{1} ← not n p_{1}. n p_{1} ← not p_{1}. ⋮ p_{n} ← not n p_{n}. n p_{n} ← not p_{n}.

General enumeration but at least one

• Specification: We have a predicate possible(X) that denotes what is possible. Our goal is to enumerate what is possible, with the added stipulation that in each answer set at least one term should be chosen.

• Program: chosen(X) ← possible(X), not not chosen(X). not chosen(X) ← possible(X), not chosen(X). some ← chosen(X). inconsistent ← not inconsistent, not some.

Choice: General enumeration with exactly one

• Specification: We have a predicate possible(X) that denotes what is possible. Our goal is to enumerate what is possible, with the stipulation that in each answer set exactly one term should be chosen and we have one answer set for each term.

• Program possible(a) ←. possible(b) ←. possible(c) ←. diff chosen than(X) ← chosen(Y), X ≠ Y. chosen(X) ← possible(X), not diff chosen than(X).

• The answer sets: {p(a), p(b), p(c), c(a), d(b), d(c)}, {p(a), p(b), p(c), d(a), c(b), d(c)}, {p(a), p(b), p(c), d(a), d(b), c(c)}.

Constrained enumeration

• Specification: Place objects in a rectangular board so that no two objects are in the same row or in the same column.

• Program 1: not chosen(X, Y) ← row(X), column(Y), row(X′),

chosen(X′, Y), X′ ≠ X.

not chosen(X, Y) ← row(X), column(Y), column(Y′),

chosen(X, Y′), Y′ ≠ Y.

chosen(X, Y) ← row(X), column(Y), not not chosen(X, Y).

• Each answer set will have a particular placement.

Chitta Baral  21

• Program 2: chosen(X, Y) ← row(X), column(Y), not not chosen(X, Y). not chosen(X, Y) ← row(X), column(Y), not chosen(X, Y). filled row(X) ← chosen(X, Y). filled column(Y) ← chosen(X, Y). missing row ← row(X), not filled row(X). missing column ← column(X), not filled column(X). inconsistent ← not inconsistent, missing row. inconsistent ← not inconsistent, missing column. inconsistent ← not inconsistent, chosen(X, Y),

chosen(X, Z), Y ≠ Z.

inconsistent ← not inconsistent, chosen(X, Y), chosen(Z, Y), X ≠ Z.

Propositional Satisfiability

• S = {p_{1} ∨ p_{2} ∨ p_{3}, p_{1} ∨ ¬p_{3}, ¬p_{2} ∨ ¬p_{4}}

• The AnsProlog program Π(S) consists of the following: p_{1} ← not n p_{1}. c_{1} ← p_{1}. n p_{1} ← not p_{1}. c_{1} ← p_{2}. p_{2} ← not n p_{2}. c_{1} ← p_{3}. n p_{2} ← not p_{2}. ← not c_{1}. p_{3} ← not n p_{3}. n p_{3} ← not p_{3}. c_{2} ← p_{1}. p_{4} ← not n p_{4}. c_{2} ← n p_{3}. n p_{4} ← not p_{4}. ← not c_{2}.

c_{3} ← n p_{2}.  c_{3} ← n p_{4}.  ← not c_{3}.

• Models of S and answer sets of Π(S) have a 1-1 correspondence.

Universal quantification: an example

• Consider an admission process in a college where admission is refused to an applicant if he has not taken any honors classes.

• An incorrect encoding refuse admission(X) ← applicant(X),

not taken honors class(X, Y).

• A correct encoding has taken a honors class(X) ← taken honors class(X, Y). refuse admission(X) ← applicant(X),

not has taken a honors class(X).

SOME LARGER PROGRAMS – N-QUEENS

Answer set Programming  Some larger programs – N-Queens

The N-queens problem: Solution 1

1. Problem: Put n queens in a board of size n × n so that they do not attack each other, vertically, horizontally, or at 45 degrees.

2. Approach of solution 1: Place queens one by one with possibility space based on the squares. at(I, X, Y) means queen I is in location (X, Y).

3. Declaration:

queen(1) ← …. queen(n) ← . row(1) ← …. row(n) ←. col(1) ← …. col(n) ←.

4. Enumeration

Chitta Baral  26

4.1. For each locations (X, Y) and each queen I, either I is in location (X, Y) or not. at(I, X, Y) ← queen(I), row(X), col(Y), not not at(I, X, Y). not at(I, X, Y) ← queen(I), row(X), col(Y), not at(I, X, Y).

4.2. For each queen I it is placed in at most one location.

← queen(I), row(X), col(Y), row(U), col(Z),

at(I, X, Y), at(I, U, Z), Y ≠ Z. ← queen(I), row(X), col(Y), row(Z), col(V),

at(I, X, Y), at(I, Z, V), X ≠ Z.

4.3. For each queen I it is placed in at least one location.

placed(I) ← queen(I), row(X), col(Y), at(I, X, Y). ← queen(I), not placed(I).

4.4. No two queens are placed in the same location.

← queen(I), row(X), col(Y), queen(J), at(I, X, Y), at(J, X, Y), I ≠ J.

5. Elimination:

5.1. No two distinct queens in the same row.

← queen(I), row(X), col(Y), col(V), queen(J),

at(I, X, Y), at(J, X, V), I ≠ J.

5.2. No two distinct queens in the same column.

← queen(I), row(X), col(Y), row(U), queen(J),

at(I, X, Y), at(J, U, Y), I ≠ J.

5.3. No two distinct queens attack each other diagonally.

← row(X), col(Y), row(U), col(V),

queen(I), queen(J), at(I, X, Y), at(J, U, V),
I ≠ J, abs(X − U) = abs(Y − V).

6. Note: Rule 4.4 is subsumed by both 5.1 and 5.2. In other words, in presence of 5.1 or 5.2 we do not need 4.4. It is needed in 4 if our only goal is enumeration.

The N-queens problem: Solution 2

1. Approach of solution 2: Place queens one by one in unique locations.

2. Declaration: As in Solution 1.

3. Enumeration:

other at(I, X, Y) ← queen(I), row(X), col(Y), row(U), col(Z),

at(I, U, Z), Y ≠ Z.

other at(I, X, Y) ← queen(I), row(X), col(Y), row(Z), col(V),

at(I, Z, V), X ≠ Z.

at(I, X, Y) ← queen(I), row(X), col(Y), not other at(I, X, Y). ← queen(I), row(X), col(Y), queen(J),

at(I, X, Y), at(J, X, Y), I ≠ J.

4. Elimination: As in Solution 1.

The N-queens problem: Solution 3

1. Approach of solution 3: Push two of the elimination constraints into the enumeration phase.

2. Declaration: As in Solution 1.

3. Enumeration:

other at(I, X, Y) ← queen(I), row(X), col(Y), row(U), col(Z),

at(I, U, Z), Y ≠ Z.

other at(I, X, Y) ← queen(I), row(X), col(Y), row(Z), col(V),

at(I, Z, V), X ≠ Z.

at(I, X, Y) ← queen(I), row(X), col(Y), not other at(I, X, Y). other at(I, X, Y) ← queen(I), row(X), col(Y),

col(V), queen(J), at(J, X, V), I ≠ J.

other at(I, X, Y) ← queen(I), row(X), col(Y), row(U),

queen(J), at(J, U, Y), I ≠ J.

Chitta Baral  30

Answer set Programming  Some larger programs – N-Queens

4. Elimination:

← row(X), col(Y), row(U), col(V), queen(I), queen(J), at(I, X, Y), at(J, U, V), I ≠ J, abs(X − U) = abs(Y − V).

The N-queens problem: Solution 4

1. Approach: Use predicate in(X, Y) to mean that a queen is placed in position (X, Y).

2. Declarations:

row(1) ← …. row(n) ←. col(1) ← …. col(n) ←.

3. Enumeration:

3.1. A queen should not be placed in (X, Y) if there is a queen placed in the same row. not in(X, Y) ← row(X), col(Y), col(Y Y),

Y ≠ Y Y, in(X, Y Y).
Chitta Baral  32

3.2. A queen should not be placed in (X, Y) if there is a queen placed in the same column. not in(X, Y) ← row(X), col(Y), row(XX),

X ≠ XX, in(XX, Y).

3.3. A queen must be placed in (X, Y) if it is not otherwise prevented. in(X, Y) ← row(X), col(Y), not not in(X, Y).

4. Elimination: We now need only one elimination constraint, the same one as before which prevents placements where queens can attack each other diagonally. ← row(X), col(Y), row(XX), col(Y Y),

X ≠ XX, Y ≠ Y Y, in(X, Y), in(XX, Y Y),

abs(X − XX) = abs(Y − Y Y).

N-queens: a non-solution

• Pushing the last elimination rules to the enumeration phase: not in(X, Y) ← row(X), col(Y), row(XX), col(Y Y),

X ≠ XX, Y ≠ Y Y, in(X, Y), in(XX, Y Y),

abs(X − XX) = abs(Y − Y Y).

• Resulting overall formulation: row(1) ← …. row(n) ←. col(1) ← …. col(n) ←. not in(X, Y) ← row(X), col(Y), col(Y Y), Y ≠ Y Y, in(X, Y Y). not in(X, Y) ← row(X), col(Y), row(XX), X ≠ XX, in(XX, Y). not in(X, Y) ← row(X), col(Y), row(XX), col(Y Y),

X ≠ XX, Y ≠ Y Y, in(X, Y), in(XX, Y Y),

abs(X − XX) = abs(Y − Y Y).

in(X, Y) ← dim(X), dim(Y), not not in(X, Y).

Chitta Baral  34

• The last formulation is not correct in the sense that it has answer sets where not all the n queens are placed.

• If n = 4, then one of the answer sets encode the following placement: {in(1, 1), in(3, 2), in(2, 4)}, where only three queens are placed, instead of four.

• Why?

– The above encoding places queens into a valid configuration, where a valid configuration is a configuration of queens that do not attack each other and to which additional queens can not be added without that queen attacking one or more of the already placed queens.

– The configuration {in(1, 1), in(3, 2), in(2, 4)} is valid in that sense, as we can not add a new queen to it in such a way that it does not attack the already placed ones.

WHO LET THE ZEBRA OUT?

Answer set Programming  Who let the zebra out?

Problem statement

• There are five houses each of a different color (red, green, ivory, blue, and yellow) and inhabited by a person of a different nationality (Japanese, Englishman, Norwegian, Ukrainian, and Spaniard), with a different pet (horse, snails, zebra, fox, and dog), drink (water, coffee, tea, milk, and orange juice) and brand of cigarettes (Lucky strike, Winston, Chesterfields, Kools, and Parliaments).

• Constraints

1. The Englishman lives in the red house.

2. The Spaniard owns the dog.

3. The Norwegian lives in the first house on the left.

4. Kools are smoked in the yellow house.

5. The man who smokes Chesterfields lives in the house next to the

man with the fox.

Chitta Baral  37

Answer set Programming  Who let the zebra out?

6. The Norwegian lives next to the blue house.

7. The Winston smoker owns snails.

8. The Lucky Strike smoker drinks orange juice.

9. The Ukrainian drinks tea. 10.The Japanese smokes Parliaments. 11.Kools are smoked in the house next to the house where the horse is

kept. 12.Coffee is drunk in the green house. 13.The green house is immediately to the right (your right) of the

ivory house. 14.Milk is drunk in the middle house.

• The query: Who owns the zebra?

Solution 1 to the Zebra problem

• together(U, V, W, X, Y, Z) meaning that the house number U is together with the cigarette brand V, country W, color X, pet Y, and drink Z. – NOT A GOOD WAY.

• Better representation 1: Use house number as the anchor, and have binary predicates has color, has drink, has animal, has country, and has smoke where the first parameter is the house number and the second parameters are color, drink, pet, country, and smoke respectively.

Chitta Baral  39

Answer set Programming  Who let the zebra out?

• Domain specification: house(1) ←. … house(5) ←. right(X, X + 1) ← house(X), house(X + 1). left(X + 1, X) ← house(X), house(X + 1). next(X, Y) ← right(X, Y). next(X, Y) ← left(X, Y). color(red) ←. color(green) ←. color(blue) ←. color(ivory) ←. color(yellow) ←. country(norway) ←. country(japan) ←. country(uk) ←. country(spain) ←. country(ukraine) ←. smoke(parliaments) ←. smoke(lucky strike) ←. smoke(kools) ←. smoke(chesterfield) ←. smoke(winston) ←. drink(coffee) ←. drink(tea) ←. drink(oj) ←. drink(milk) ←. drink(water) ←.

animal(dog) ←.  animal(snails) ←.  animal(horse) ←.

animal(fox) ←. animal(zebra) ←.

• Enumeration of the predicates has color, has drink, has animal, has country, and has smoke. For the predicate has color, we make sure that every house has a unique color assigned to it, and every color corresponds to a unique house. other color(H, C) ← house(H), color(C), color(CC),

has color(H, CC), C ≠ CC.

other color(H, C) ← house(H), color(C), house(HH),

has color(HH, C), H ≠ HH.

has color(H, C) ← house(H), color(C), not other color(H, C). The enumeration rules for the predicates has drink, has animal, has country, and has smoke are similar to that of the enumeration rules for has color and is given below: other drink(H, C) ← house(H), drink(C), drink(CC),

has drink(H, CC), C ≠ CC. other drink(H, C) ← house(H), drink(C), house(HH),

has drink(HH, C), H ≠ HH.

has drink(H, C) ← house(H), drink(C), not other drink(H, C). other animal(H, C) ← house(H), animal(C), animal(CC),

has animal(H, CC), C ≠ CC.

other animal(H, C) ← house(H), animal(C), house(HH),

has animal(HH, C), H ≠ HH.

has animal(H, C) ← house(H), animal(C),

not other animal(H, C).

other country(H, C) ← house(H), country(C), country(CC),

has country(H, CC), C ≠ CC.

other country(H, C) ← house(H), country(C), house(HH),

has country(HH, C), H ≠ HH.

has country(H, C) ← house(H), country(C),

not other country(H, C).

other smoke(H, C) ← house(H), smoke(C), smoke(CC), has smoke(H, CC), C ≠ CC.

Chitta Baral  42

other smoke(H, C) ← house(H), smoke(C), house(HH),

has smoke(HH, C), H ≠ HH.

has smoke(H, C) ← house(H), smoke(C), not other smoke(H, C).

• The elimination constraints: s_{1} ← house(H), has country(H, uk), has color(H, red). s_{2} ← house(H), has animal(H, dog), has country(H, spain). s_{3} ← has country(1, norway). s_{4} ← house(H), has smoke(H, kools), has color(H, yellow). s_{5} ← house(H), house(HH), has smoke(H, chesterfield),

has animal(HH, fox), next(H, HH). s_{6} ← house(H), house(HH), has color(H, blue),

has country(HH, norway), next(H, HH). s_{7} ← house(H), has smoke(H, winston), has animal(H, snails). s_{8} ← house(H), has smoke(H, lucky strike), has drink(H, oj). s_{9} ← house(H), has country(H, ukraine), has drink(H, tea). s_{10} ← house(H), has smoke(H, parliaments),

has country(H, japan).

Chitta Baral  43

Answer set Programming  Who let the zebra out?

s_{11} ← house(H), house(HH), has smoke(H, kools),

has animal(HH, horse), next(H, HH). s_{12} ← house(H), has color(H, green), has drink(H, coffee). s_{13} ← house(H), house(HH), has color(HH, ivory),

has color(H, green), right(HH, H). s_{14} ← has drink(3, milk). The following rule encodes that satisfied is true iff all the 14 constraints are individually satisfied. satisfied ← s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6}, s_{7}, s_{8}, s_{9}, s_{10}, s_{11}, s_{12}, s_{13}, s_{14}. The following rule eliminates possibilities were satsified is not true. I.e., when one of the 14 conditions does not hold. ← not satisfied.

Solution 2 to the Zebra problem

• Representation idea: Use a single association predicate, and use two new predicates object and same type to distinguish the association of a house number with objects of different types.

• Main advantage: It makes it easier to express the observations as we do not have to remember the particular association predicate for the object being described.

Chitta Baral  45

• Besides the domain specification in Solution 1 we have the following additional rules. object(X) ← color(X). object(X) ← drink(X). object(X) ← animal(X). object(X) ← country(X). object(X) ← smoke(X). same type(X, Y) ← color(X), color(Y). same type(X, Y) ← drink(X), drink(Y). same type(X, Y) ← animal(X), animal(Y). same type(X, Y) ← country(X), country(Y). same type(X, Y) ← smoke(X), smoke(Y).

• Enumeration: has(X, Y) intuitively means that the house number X is associated with object Y. other has(X, Y) ← house(X), object(Y), house(Z),

Z ≠ X, has(Z, Y). other has(X, Y) ← house(X), object(Y), object(Z),

Z ≠ Y, same type(Y, Z), has(X, Z).

has(X, Y) ← house(X), object(Y), not other has(X, Y).

• Elimination Constraints: s_{1} ← house(H), has(H, uk), has(H, red). s_{2} ← house(H), has(H, dog), has(H, spain). s_{3} ← has(1, norway). s_{4} ← house(H), has(H, kools), has(H, yellow). s_{5} ← house(H), house(HH), has(H, chesterfield),

has(HH, fox), next(H, HH). s_{6} ← house(H), house(HH), has(H, blue),

has(HH, norway), next(H, HH). s_{7} ← house(H), has(H, winston), has(H, snails). s_{8} ← house(H), has(H, lucky strike), has(H, oj). s_{9} ← house(H), has(H, ukraine), has(H, tea). s_{10} ← house(H), has(H, parliaments), has(H, japan).

Answer set Programming  Who let the zebra out?

s_{11} ← house(H), house(HH), has(H, kools),

has(HH, horse), next(H, HH). s_{12} ← house(H), has(H, green), has(H, coffee). s_{13} ← house(H), house(HH), has(H, green),

has(HH, ivory), right(HH, H). s_{14} ← has(3, milk). In addition as before we have satisfied ← s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6}, s_{7}, s_{8}, s_{9}, s_{10}, s_{11}, s_{12}, s_{13}, s_{14}. ← not satisfied.

PLANNING AND PLAN VERIFICATION

Answer set Programming  Planning and plan verification

Simple Blocks world: problem description

1. The goal description: {on(a, c), on(c, b)}

2. The domain description

2.1. Sort: block(X). In the rest of the descriptions X and Y range

over the sort block. 2.2. fluents: on(X), ontable(X), clear(X), handempty, holding(X). 2.3. Executability Conditions:

executable pick up(X) if clear(X), ontable(X), handempty. executable put down(X) if holding(X). executable stack(X, Y) if holding(X), clear(Y). executable unstack(X, Y) if on(X, Y), clear(X), handempty.

Chitta Baral  50

2.4. Effect propositions:

pick up(X) causes ¬ontable(X), ¬clear(X),

¬handempty, holding(X).

put down(X) causes ¬holding(X), clear(X), handempty,

ontable(X).

stack(X, Y) causes ¬holding(X), ¬clear(Y),

clear(X), handempty, on(X, Y).

unstack(X, Y) causes holding(X), clear(Y), ¬clear(X),

¬handempty, ¬on(X, Y).

3. The initial state description: initially clear(c) initially clear(a) initially ontable(c) initially ontable(b) initially on(a, b) initially handempty

Simple Blocks World: AnsProlog encoding

1. The Domain dependent part π_{strips1}^{dep}(D_{bw}, O_{bw}, G_{bw}):

1.1. The domain π_{strips1}^{dep.dom}(D_{bw}): block(a). block(b). block(c). block(d). fluent(on(X, Y)) ← block(X), block(Y). fluent(ontable(X)) ← block(X). fluent(clear(X)) ← block(X). fluent(holding(X)) ← block(X). fluent(handempty).

Chitta Baral  52

action(pick up(X)) ← block(X). action(put down(X)) ← block(X). action(stack(X, Y)) ← block(X), block(Y). action(unstack(X, Y)) ← block(X), block(Y).

1.2. The executability conditions π_{strips1}^{dep.exec}(D_{bw}): exec(pick up(X), clear(X))). exec(pick up(X), ontable(X)). exec(pick up(X), handempty). exec(put down(X), holding(X)). exec(stack(X, Y), holding(X)). exec(stack(X, Y), clear(Y)). exec(unstack(X, Y), clear(X)). exec(unstack(X, Y), on(X, Y)). exec(unstack(X, Y), handempty).

1.3. The dynamic causal laws: π_{strips1}^{dep.dyn}(D_{bw}): causes(pick up(X), neg(ontable(X))). causes(pick up(X), neg(clear(X))).

Chitta Baral  53

causes(pick up(X), holding(X)). causes(pick up(X), neg(handempty)). causes(put down(X), ontable(X)). causes(put down(X), clear(X)). causes(put down(X), neg(holding(X))). causes(put down(X), handempty). causes(stack(X, Y), neg(holding(X))). causes(stack(X, Y), neg(clear(Y))). causes(stack(X, Y), clear(X)). causes(stack(X, Y), handempty). causes(stack(X, Y), on(X, Y)). causes(unstack(X, Y), holding(X)). causes(unstack(X, Y), clear(Y)). causes(unstack(X, Y), neg(clear(X))). causes(unstack(X, Y), neg(handempty)). causes(unstack(X, Y), neg(on(X, Y))).

1.4. The initial state π_{strips1}^{dep.init}(O_{bw.1}):

Chitta Baral  54

Answer set Programming  Planning and plan verification

initially(handempty). initially(clear(a)). initially(clear(c)). initially(ontable(c)). initially(ontable(b)). initially(on(a, b)).

1.5. The goal conditions π_{strips1}^{dep.goal}(G_{bw.1}): finally(on(a, c)). finally(on(c, b)).

2. The domain independent part π_{strips1}^{indep}:

2.1. Defining time:

time(1)…. time(length). 2.2. Defining goal(T):

not goal(T) ← time(T), finally(X), not holds(X, T). goal(T) ← time(T), not not goal(T).

Chitta Baral  55

2.3. Eliminating possible answer sets which do not have a plan of the given length: ← not goal(length).

2.4. Defining contrary:

contrary(F, neg(F)). contrary(neg(F), F).

2.5. Defining executability:

not executable(A, T) ← exec(A, F), not holds(F, T). executable(A, T) ← T < length, not not executable(A, T).

2.6. Fluent values at time-point 1:

holds(F, 1) ← initially(F). 2.7. Effect axiom:

holds(F, T + 1) ← T < length, executable(A, T), occurs(A, T), causes(A, F).

2.8. Inertia:

holds(F, T + 1) ← contrary(F, G), T < length, holds(F, T),

not holds(G, T + 1).

2.9. Enumerating action occurrences: occurs(A, T) ← action(A), time(T), not other occurs(A, T). other occurs(A, T) ← action(A), action(AA), time(T),

occurs(AA, T), A ≠ AA.

← action(A), time(T), occurs(A, T), not executable(A, T).

Using temporal constraints to guide the search

1. Defining bad tower below

holds(bad tower below(X), T) ← holds(ontable(X), T),

finally(on(X, Y)).

holds(bad tower below(X), T) ← holds(on(X, Y), T),

finally(ontable(X)).

holds(bad tower below(X), T) ← holds(on(X, Y), T),

finally(holding(Y)).

holds(bad tower below(X), T) ← holds(on(X, Y), T),

finally(clear(Y)).

holds(bad tower below(X), T) ← holds(on(X, Y), T),

finally(on(X, Z)), Z ≠ Y.

holds(bad tower below(X), T) ← holds(on(X, Y), T), finally(on(Z, Y)), Z ≠ X.

Chitta Baral  58

Answer set Programming  Planning and plan verification

holds(bad tower below(X), T) ← holds(on(X, Y), T), holds(bad tower below(Y), T).

2. Defining goodtower

holds(goodtower(X), T) ← holds(clear(X), T), not finally(holding(X)),

not holds(bad tower below(X), T).

3. Defining badtower

holds(badtower(X), T) ← holds(clear(X), T),

not holds(goodtower(X), T).

4. The temporal constraints.

← holds(goodtower(X), T), holds(on(Y, X), T + 1),

not holds(goodtower(Y), T + 1). ← holds(badtower(X), T), holds(on(Y, X), T + 1).

← holds(ontable(X, T)), finally(on(X, Y)),
not holds(goodtower(Y), T),
holds(holding(X), T + 1).

The temporal conditions in (4) above can be replaced by the following direct constraints on action occurrences. This further cuts down on the planning time.

← holds(goodtower(X), T), occurs(stack(Y, X), T),

not holds(goodtower(Y), T + 1). ← holds(badtower(X), T), occurs(stack(Y, X), T). ← holds(ontable(X, T)), finally(on(X, Y)),

not holds(goodtower(Y), T), occurs(pick up(X), T).

Blocks world using a richer formalism: the description

1. Sort: block(X)

2. Basic fluents: on(X), ontable(X), holding(X).

3. Defined fluents: clear(X), handempty.

4. Definition of defined fluents.

• clear(X) iff ∄Y : on(Y, X)

• handempty iff ∄Y : holding(Y)

5. Executability Conditions:

executable pick up(X) if clear(X), ontable(X), handempty executable put down(X) if holding(X) executable stack(X, Y) if holding(X), ontable(Y) executable stack(X, Y) if holding(X), on(Y, Z) executable unstack(X, Y) if clear(X), on(X, Y), handempty

Chitta Baral  61

6. Effect propositions:

pick up(X) causes holding(X) put down(X) causes ontable(X) stack(X, Y) causes on(X, Y) unstack(X, Y) causes holding(X)

7. Causal ramification constraints: on(X, Y) causes ¬holding(X) holding(X) causes ¬on(X, Y) ontable(X) causes ¬holding(X) holding(X) causes ¬ontable(X)

8. Causal qualification constraint: on(X, Y), on(Z, Y), X ≠ Z causes false

AnsProlog encoding of the BWP in the richer formalism

1. The domain dependent part π_{adl1}^{dep}(D_{bw1}, O_{bw1}, G_{bw1}):

1.1. The domain: π_{adl1}^{dep.dom}(D_{bw1}): fluent(on(X, Y)). fluent(ontable(X)). fluent(holding(X)). defined fluent(clear(X)). defined fluent(handempty).

Chitta Baral  63

1.2. The executability conditions π_{adl1}^{dep.exec}(D_{bw1}):

executable(pick up(X), T) ← T < length, holds(clear(X), T), holds(ontable(X), T),

holds(handempty, T).

executable(put down(X), T) ← T < length,

holds(holding(X), T).

executable(stack(X, Y), T) ← T < length,

holds(holding(X), T), holds(ontable(Y), T).

executable(stack(X, Y), T) ← T < length,

holds(holding(X), T), holds(on(Y, Z), T).

executable(unstack(X, Y), T) ← T < length, holds(clear(X), T), holds(on(X, Y), T),

holds(handempty, T).

1.3. The dynamic causal laws π_{adl1}^{dep.dyn}(D_{bw1}): The use of defined fluents and causal ramification constraints drastically cuts down on the number of dynamic causal laws. Instead of 18 of them, we now have only 4 of them.

Chitta Baral  64

causes(pick up(X), holding(X)). causes(put down(X), ontable(X)). causes(stack(X, Y), on(X, Y)). causes(unstack(X, Y), holding(X)).

1.4. Defined fluents π_{adl1}^{dep.def}(D_{bw1}):

holds(neg(clear(X)), T) ← holds(holding(X), T). holds(neg(clear(X)), T) ← holds(on(Y, X), T). holds(clear(X), T) ← holds(ontable(X), T),

not holds(neg(clear(X)), T).

holds(clear(X), T) ← holds(on(X, Y), T),

not holds(neg(clear(X)), T).

holds(neg(handempty), T) ← holds(holding(X), T). holds(handempty, T) ← not holds(neg(handempty), T).

1.5. Qualification constraints π_{adl1}^{dep.qual}(D_{bw1})

← holds(on(X, Y), T), holds(on(Z, Y), T), neq(X, Z). 1.6. Static ramification constraints π_{adl1}^{dep.ram}(D_{bw1})

static causes(on(X, Y), neg(holding(X))).

Chitta Baral  65

Answer set Programming  Planning and plan verification

static causes(holding(X), neg(on(X, Y))). static causes(ontable(X), neg(holding(X))). static causes(holding(X), neg(ontable(X))).

1.7. The initial state π_{adl1}^{dep.init}(O_{bw1}): As before. 1.8. The goal state π_{adl1}^{dep.goal}(G_{bw1}): As before.

2. The domain independent part π_{adl1}^{indep}. 2.1. Defining time: as before. 2.2. Defining goal(T): as before. 2.3. Defining plan existence: as before. 2.4. Defining contrary: as before. 2.5. Fluent values at time point 1: as before. 2.6. Defining literal:

literal(G) ← fluent(G). literal(neg(G)) ← fluent(G).

2.7. Effect axioms: Here the effect axioms only define the effects of actions on literals made up of basic fluents. holds(F, T + 1) ← literal(F), T < length,

executable(A, T), occurs(A, T), causes(A, F).

2.8. Inertia: Here the inertia axioms are also defined only with respect to literals made up of basic fluents. holds(F, T + 1) ← literal(F), contrary(F, G),

T < length, holds(F, T), not holds(G, T + 1).

2.9. Effect axiom for static causal laws:

holds(F, T) ← T < length, holds(G, T), static causes(G, F). 2.10. Occurrences of actions: as before.

CONCLUSION

Answer set Programming  Conclusion

AnsProlog^{∗}

• AnsProlog^{∗}: Adding disjunction, classical negation, empty heads to AnsProlog.

• AnsProlog and AnsProlog^{∗} are non-monotonic.

• AnsProlog and AnsProlog^{∗} are fully declarative.

• AnsProlog^{∗} is as expressive as Default logic but much simpler. (First-order logic can not express transitive closure, or aggregates.)

• Largest collection of building block results about AnsProlog^{∗} that help build large programs from small ones and analyze big programs by partitioning them to modules.

• Several efficient implementations. (Smodels, Dlv, others).

• Has been used in many applications.