ANSWER SET PROGRAMMING

KNOWLEDGE REPRESENTATION, REASONING AND DECLARATIVE PROBLEM SOLVING USING

ANSPROLOG*: WWW.BARAL.US/BOOKONE

Chitta Baral

Department of Computer Science and Engg.

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

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

June 2004

Answer Set Programming.

Nomenclature

• AnsProlog*: Programming in logic with answer sets

• Also referred to as A-Prolog

• A collection of rules of the form L_{0} or … or L_{k} ← L_{k+1}, …, L_{m}, not L_{m+1}, …, not L_{n}. where L_{i}’s are literals in the sense of first order logic.

• The language

– with syntax encompassing ∗ general logic programs (normal logic programs): k = 0, L_{i}s are atoms.

∗ extended logic programs: k = 0.

∗ disjunctive logic programs: L_{i}s are atoms, m = n.

∗ disjunctive normal logic programs: L_{i}s are atoms.

∗ extended disjunctive normal logic programs: no restrictions.

– and semantics characterized with answer sets

MOTIVATION: “INTELLIGENCE” TO “AI” TO “KR” TO “ANSPROLOG”

Answer Set Programming.  Motivation: “Intelligence” to “AI” to “KR” to “AnsProlog”

A dictionary meaning of the word: “intelligence”

(1)

(a) The capacity to acquire and apply knowledge.

(b) The faculty of thought and reason.

(c) Superior powers of mind. See Synonyms at mind.

(2) An intelligent, incorporeal being, especially an angel.

(3) Information; news. See Synonyms at news. (4)

(a) Secret information, especially about an actual or potential enemy.

(b) An agency, staff, or office employed in gathering such information.

(c) Espionage agents, organizations, and activities considered as a group Source: The American Heritage Dictionary of the English Language, Fourth Edition

Copyright 2000 by Houghton Mifflin Company. Published by Houghton Mifflin Company. All rights reserved.

Chitta Baral  3

Wordnet meaning of ‘intelligence”

n 1: the ability to comprehend; to understand and profit from experience

[ant: stupidity] 2: a unit responsible for gathering and interpreting intelligence 3: secret information about an enemy (or potential enemy); “we sent out planes to gather

intelligence on their radar coverage” 4: new information about specific and timely events; “they awaited news of the outcome”

[syn: news, tidings, word] 5: the operation of gathering information about an enemy [syn: intelligence activity,

intelligence operation] Source: WordNet 1.6, 1997 Princeton University

Artificial Inteligence and ‘Knowledge representation and reasoning’

• AI is the science and engineering necessary to create artifacts that can

– acquire knowledge, i.e., can learn; and

– reason with knowledge (leading to doing tasks such as planning, explaining, diagnosing, acting rationally, etc.),

• Thus to build intelligent artifacts one of two important aspects that is needed is to be able to ‘Reasoning with knowledge’

• To build an artificial entity (or artifact) that can ‘reason with knowledge’ one must ‘represent the knowledge’.

• Central to Knowledge Representation and Reasoning is a knowledge representation framework consisting of

– a knowledge representation language, [KR]

– a language to reason (i.e., ask various questions), [R]

– and connection between theories of the above two. [KR & R] • An analogy: In summary, developing a KR & R framework is as fundamental

to build AI artifacts as Calculus is to Engineering.

Knowledge Representation has come of age.

• Project Halo. (Digital Aristotle.)

• Semantic Web.

• Advance Question Answering

• Cellular event modeling.

• Knowledge based planning. (HTN, TLPLAN, TALPLAN)

What properties should a good KR & R language have?

1. Should be non-monotonic. (So that the system can revise its earlier conclusion in light of new information.)

2. Should have the ability to represent normative statements, exceptions, and default statements, and should be able to reason with them.

3. Should be expressive enough to express and answer problem solving queries such as planning queries, counterfactual queries, explanation queries and diagnostic queries.

4. Should have a simple and intuitive syntax so that domain experts (who may be non-computer scientists) can express knowledge using it.

5. Should have enough existing research (or building block results) about this language so that one does not have to start from scratch.

6. Should have interpreters or implementation of the language so that one can indeed represent and reason in this language. (I.e., it should not be just a theoretical language.)

7. Should have existing applications that have been built on this language so as to demonstrate the feasibility that applications can be indeed built using this language.

Knowledge Representation Languages: a short (biased) history

• First-order logic and propositional logics – both monotonic in nature.

• Description logic – a fragment of FOL;

– is monotonic;

– mostly focussed on representing and reasoning about ontologies or inheritance

hierarchies

• Semantic Nets – basically a graphical sub-class of FOL

• Non-monotonic logics – Circumscription

– Default logic

Chitta Baral  9

– Non-monotonic modal logics (including auto-epistemic logic)

** complex syntax, no expressiveness advantages, limited building block results.

• AnsProlog* vs Pure Prolog

– Differences:

∗ Prolog is sensitive to ordering of rules and ordering of literals in the body of rules.

∗ Inappropriate ordering leads to infinite loops. (Thus Prolog is not declarative; hence not a knowledge representation language)

∗ Prolog stumbles with recursion through negation

∗ No disjunction in the head (less expressive power in the propositional case)

– Similarities: For certain subclasses of AnsProlog*, Prolog can be thought of as a top-down engine.

Why AnsProlog* ?

1. Is non-monotonic.

2. Has the ability to represent normative statements, exceptions, and default statements, and should be able to reason with them.

3. Is expressive enough to express and answer problem solving queries such as planning queries, counterfactual queries, explanation queries and diagnostic queries.

4. Has a simple and intuitive syntax so that domain experts (who may be non-computer scientists) can express knowledge using it.

5. Has enough existing research (or building block results) about this language so that one does not have to start from scratch.

6. Has interpreters or implementation of the language so that one can indeed represent and reason in this language. (I.e., it should not be just a theoretical language.)

7. Has existing applications that have been built on this language so as to demonstrate the feasibility that applications can be indeed built using this language.

SYNTAX AND SEMANTICS OF ANSPROLOG*

Answer Set Programming.  Syntax and Semantics of AnsProlog*

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(t_{1}, …, t_{n}) such that t_{i}s are terms.

• atoms: p(t_{1}, …, t_{n}) such that t_{i}s 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.

Herbrand Universe and Herbrand Base

• Some components of a language: variables, constants, functions, predicates

• HU_{L} – Herbrand Universe of a language L: the set of all ground terms which can be formed with the functions and constants in L.

• HB_{L} – 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 L_{1} with variables X, Y; constants a, b; function symbol f of arity 1; and predicate symbol p of arity 1.

– HU_{L_{1}} = {a, b, f(a), f(b), f(f(a)), f(f(b)), f(f(f(a))), f(f(f(b))), …}.

– HB_{L_{1}} = {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)))), …}.

AnsProlog* programs and their grounding

• A rule is of the form: L_{0} or … or L_{k} ← L_{k+1}, …, L_{m}, not L_{m+1}, …, not L_{n}.

• ground(r, L): the set of all rules obtained from r by all possible substitution of elements of HU_{L} for the variables in r.

• Example:

Consider the rule p(f(X)) ← p(X). and the language L_{1}. Then ground(r, L_{1}) 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 an AnsProlog* program Π:

– ground(Π, L) = ⋃_{r∈Π} ground(r, L)

– L(Π): The langauge that is defined by the predicates, functions and constants occurring in Π.

Chitta Baral  15

Answer Set Programming.  Syntax and Semantics of AnsProlog*

– ground(Π) = ⋃_{r∈Π} ground(r, L(Π)).

• Example:

– Π:

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)). ⋮

Chitta Baral  16

AnsProlog: Syntax and semantics

• Syntax: A collection of rules of the form L_{0} ← L_{1}, …, L_{m}, not L_{m+1}, …, not L_{n}. where L_{i}’s are atoms.

• Semantics of a program Π: Given in terms of answer sets of the program ground(Π).

– Answer sets of AnsProlog^{−not} programs (where m = n for all rules): ∗ The least Herbrand model of the program.

∗ The minimal set of atoms (from Herbrand base of the program) that is closed under the program.

∗ The least fixpoint of van Emden and Kowalski’s iteration operator.

– Gelfond-Lifschitz transformation: Given an AnsProlog program Π and a set S of atoms from HB_{Π}, the Gelfond-Lifschitz transformation Π^{S} is obtained by deleting (i) each rule that has a naf-literal not L in its body with L ∈ S, and (ii) naf-literals of the form not L in the bodies of the remaining rules.

– Answer sets: S is an answer set of an AnsProlog program Π if S is the answer set of the AnsProlog^{−not} program Π^{S}.

Examples

• Π_{1}: p ← a. q ← b. a ← .

• Π_{2}: p ← p.

• Π_{3}: p ← p. q ← .

• Π_{4}: a ← not b.

• Π_{5}: a ← not b. b ← not a.

• Π_{6}: p ← a. a ← not b. b ← not a.

• Π_{7}: a ← not b. b ← not c. d ← .

• Π_{8}: p ← not p.

• Π_{9}: p ← not p, d. r ←. d ← .

• Π_{10}: p ← not p, d. r ← not d. d ← not r.

• Π_{11}: p ← not p. p ← not d. r ← not d. d ← not r.

SOME BUILDING BLOCK RESULTS

Answer Set Programming.  Some Building Block results

Further intuitions behind the semantics

• A set of atoms S is \underline{closed under} an AnsProlog program Π if for all rules of the form L_{0} ← L_{1}, …, L_{m}, not L_{m+1}, …, not L_{n}. in Π, {L_{1}, …, L_{m}} ⊆ S and {L_{m+1}, …, L_{n}} ∩ S = ∅ implies that L_{0} ∈ S.

• A set of atoms S is said to be \underline{supported by} Π if for all p ∈ S there is a rule of the form p ← L_{1}, …, L_{m}, not L_{m+1}, …, not L_{n}. in Π, such that {L_{1}, …, L_{m}} ⊆ S and {L_{m+1}, …, L_{n}} ∩ S = ∅.

• Clark defined a notion of completion of a program called Clark’s completion. Models of the Clark’s completion of an AnsProlog program Π are closed under and supported by Π and vice-versa.

• Answer sets of Π are models of Clark’s Completion of Π. But not vice-versa. (example: p ← p.)

Chitta Baral  22

• A set of atoms S is an answer set of an AnsProlog 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 ← L_{1}, …, L_{m}, not L_{m+1}, …, not L_{n}. such that {L_{1}, …, L_{m}} ⊆ S, {L_{m+1}, …, L_{n}} ∩ S = ∅ and λ(p) > λ(L_{i}), for 1 ≤ i ≤ m.

• Note that (ii) above implies that S is supported by Π.

• A logical characterization of (ii) above needs to be added to Clark’s completion so as to have a 1-1 correspondence between models and answer sets.

Clark’s Completion and some examples

• Given a propositional AnsProlog program Π consisting of rules of the form: Q ← P_{1}, …, P_{n}, not R_{1}, …, not R_{m}. its completion Comp(Π) is obtained in two steps:

– Step 1: Replace each rule of the above mentioned form with the formula: Q ⇐ P_{1} ∧ … ∧ P_{n} ∧ ¬R_{1} ∧ … ¬R_{m}

– Step 2: For each symbol Q, let Support(Q) denote the set of all clauses with Q in the head. Suppose Support(Q) is the set: Q ⇐ Body_{1} ⋮ Q ⇐ Body_{k} Replace this set with the single formula, Q ⇔ Body_{1} ∨ … ∨ Body_{k}. If Support(Q) = ∅ then replace it by ¬Q. □

Chitta Baral  24

• Π_{4}:

a ← not b.

• Π_{5}:

a ← not b. b ← not a.

• Π_{2}:

p ← p.

• Π_{8}:

p ← not p.

• Initially: Characterizing not was thought to be the main problem, especially when dealing with non-stratified programs.

• New Insight: Clark’s completion is a good and intuitive semantics for not ; but has problems with positive loops.

Analyzing AnsProlog programs using ‘splitting’

• Purpose: Break down an AnsProlog program to smaller components in such a way that the analysis of the components can be carried over to the whole program.

• ‘Splitting’ is more general than the notions of ‘stratification’ and ‘local stratification’. Those programs have a unique answer set.

• The program p ← a. p ← b. a ← not b. b ← not a. can be split to two layers.

Chitta Baral  26

• A splitting set for an AnsProlog program Π is any set U of atoms such that, for every rule r ∈ Π of the form L_{0} ← L_{1}, …, L_{m}, not L_{m+1}, …, not L_{n}. if L_{o} ∈ U then lit(r) = {L_{1}, …, L_{n}} ⊆ U. If U is a splitting set for Π, we also say that U splits Π. The set of rules r ∈ Π such that lit(r) ⊆ U is called the bottom of Π relative to the splitting set U and denoted by bot_{U}(Π). The subprogram Π \ bot_{U}(Π) is called the top of Π relative to U and denoted top_{U}(Π).

• Consider the following program Π_{1}:

a ← b, not c. b ← c, not a. c ←. The set U = {c} splits Π_{1} such that the last rule constitutes bot_{U}(Π_{1}) and the first two rules form top_{U}(Π_{1}).

• Once a program is split into top and bottom with respect to a splitting set, we can compute the answer sets of the bottom part and for each of these answer sets, we can further simplify the top part by partial evaluation before analyzing it further.

• Consider the following program: p ← not q. p ← not p. q ← not r. r ← not q. {q, r} is a splitting set and the only answer set of the above program is {r, p}.

SOME KNOWLEDGE REPRESENTATION EXAMPLES

Answer Set Programming.  Some knowledge representation examples

Normative statements and exceptions

• Normative statements are statements of the form “normally elements belonging to a class c have the property p.” A good representation of normative statements should at least allow us to easily ‘incorporate’ information about exceptional elements of c with respect to the property c.

• “Normally birds Fly. Tweety and Sam are birds.”

flies(X) ← bird(X), not ab(X). bird(tweety) ←. bird(sam) ←.

• Adding “Sam is a penguin, and penguins are exceptional birds that do not fly,” in an elaboration tolerant manner: bird(X) ← penguin(X). ab(X) ← penguin(X). penguin(sam) ←.

Chitta Baral  30

Answer Set Programming.  Some knowledge representation examples

• Adding “Ostriches are exceptional birds that do not fly,” in an elaboration tolerant manner: bird(X) ← ostrich(X). ab(X) ← ostrich(X).

• Weak defaults: For wounded birds we can not conclude whether they fly or not.

• AnsProlog is not quite appropriate for this. We need to be able to eliminate the embedded CWA and allow specification of CWA in a case by case basis.

• Expand AnsProlog to allow classical negation ¬.

• An example:

cross ← not train vs cross ← ¬train

AnsProlog^{¬} programs

• Syntax: A collection of rules of the form L_{0} ← L_{1}, …, L_{m}, not L_{m+1}, …, not L_{n}. where L_{i}’s are literals.

• Semantics of a program Π: Given in terms of answer sets of the program ground(Π).

– Answer sets of AnsProlog^{¬,−not} programs (where m = n for all rules):

∗ The minimal set of literals S (made up of atoms in the Herbrand base of the program) such that: · for any rule L_{0} ← L_{1}, …, L_{m}. in the program , if {L_{1}, …, L_{m}} ⊆ S then L_{0} ∈ S, and · if S contains a pair of complementary literals then S consists of all literals. (called Lit)

– Gelfond-Lifschitz transformation: as before

– Answer sets: S is an answer set of an AnsProlog program Π if S is the answer set of the AnsProlog^{¬,−not} program Π^{S}.

AnsProlog^{¬} examples

AnsProlog^{¬} programs  Their answer sets
{p ← q.  ¬p ← r.  q ← .}  {q, p}
{p ← q.  ¬p ← r.  r ← .}  {r, ¬p}
{p ← q.  ¬p ← r.}  {}
{p ← q.  ¬p ← r.  q ← .  r ← .}  Lit
{¬p ← . p ← ¬q. }
{¬p ← . q ← ¬p. }
{¬q ← not p. }

{a ← not b. b ← not a. q ← a. ¬q ← a.}

Explicit CWA and wounded birds

• Birds and penguins flies(X) ← bird(X), not ab(X). bird(X) ← penguin(X). ab(X) ← penguin(X). bird(tweety) ←. penguin(sam) ←. ¬bird(X) ← not bird(X). ¬penguin(X) ← not penguin(X). ¬ab(X) ← not ab(X). ¬flies(X) ← penguin(X). ¬flies(X) ← ¬bird(X).

• Advantage of the above representation: To remove CWA about a predicate, just remove the explicit CWA rule for that predicate.

Chitta Baral  34

• Incorporating the new knowledge: “John is an wounded bird and wounded birds are weak exceptions” by adding the following rules. wounded bird(john) ←. ¬wounded bird(X) ← not wounded bird(X). bird(X) ← wounded bird(X). ab(X) ← wounded bird(X).

OWA: i.e., no CWA

• Earlier: CWA about birds, penguins, ab and wounded birds, OWA about flies.

• Now: Assume that our information about birds, penguins, ab and wounded birds is incomplete.

• After removing explicit CWA about birds, penguins, ab and wounded birds. flies(X) ← bird(X), not ab(X). bird(X) ← penguin(X). ab(X) ← penguin(X). bird(tweety) ←. penguin(sam) ←. ¬flies(X) ← penguin(X). ¬flies(X) ← ¬bird(X). wounded bird(john) ←. bird(X) ← wounded bird(X). ab(X) ← wounded bird(X).

• et is a bird. Does it fly?

– Earlier representation will answer yes!

– But, now that we no longer have CWA about being a penguin, its possible that et might be a penguin. We now need to be more conservative in our reasoning.

flies(X) ← bird(X), not ab(X). bird(X) ← penguin(X). \underline{ab(X) ← not ¬penguin(X).} bird(tweety) ←. penguin(sam) ←. \underline{¬penguin(X) ← ¬bird(X).} ¬flies(X) ← penguin(X). ¬flies(X) ← ¬bird(X). wounded bird(john) ←. \underline{¬wounded bird(X) ← ¬bird(X).} bird(X) ← wounded bird(X). \underline{ab(X) ← not ¬wounded bird(X).} \underline{bird(et).}

Chitta Baral  37

Allowing for explicit negative information

• Suppose we have explicit information about the non-flying ability of certain birds.

• Adding such information such as {¬fly(tweety), ¬penguin(tweety), ¬wounded bird(tweety)} should not lead to inconsistency. But it does!

• Such a breakdown can be avoided by replacing the rule flies(X) ← bird(X), not ab(X). by the rule: flies(X) ← bird(X), not ab(X), not ¬flies(X). In addition, for exceptions we only need to have the rule: ¬flies(X) ← exceptional bird(X). and no longer need a rule of the form: ab(X) ← not ¬exceptional bird(X). For weak exceptions we will need the rule: ab(X) ← not ¬weakly exceptional bird(X).

Systematic removal of CWA : an example

• Transitive Closure:

anc(X, Y) ← parent(X, Y). anc(X, Y) ← parent(X, Z), anc(Z, Y). It assumes complete information about parent and gives a complete definition of ancestor.

• Consider the case that where the objects are fossils of dinosaurs dug at an archaeological site, and for pairs of objects (a, b) we can sometimes determine par(a, b) through tests, sometimes determine ¬par(a, b), and sometimes neither. How do we define when anc is true and when it is false.

Chitta Baral  39

Answer Set Programming.  Some knowledge representation examples

• To define when anc is true we keep the old rules. anc(X, Y) ← parent(X, Y). anc(X, Y) ← parent(X, Z), anc(Z, Y). Next we define a predicate m par(X, Y) which encodes when X may be a parent of Y. m par(X, Y) ← not ¬par(X, Y). Using m par we now define m anc(X, Y) which encodes when X may be an ancestor of Y. m anc(X, Y) ← m par(X, Y). m anc(X, Y) ← m par(X, Z), m anc(Z, Y). Now we use m anc to define when ¬anc(X, Y) is true. ¬anc(X, Y) ← not m anc(X, Y).

Reasoning about what is known and what is not

(1) eligible(X) ← highGP A(X).

(2) eligible(X) ← special(X), fairGP A(X).

(3) ¬eligible(X) ← ¬special(X), ¬highGP A(X).

(4) interview(X) ← not eligible(X), not ¬eligible(X).

(5) fairGP A(john) ←.

(6) ¬highGP A(john) ←.

BASIC DECLARATIVE PROBLEM SOLVING MODULES

Answer Set Programming.  Basic Declarative Problem Solving Modules

Constraints

• Π:

a ← not b. b ← not a.

• Π has two answer sets {a} and {b}.

• Now suppose we would like to incorporate the constraint r : ← a. to prune any answer set where a is true.

• To achieve this we can add the following rule.

p ← not p, a. to Π.

Chitta Baral  43

Answer Set Programming.  Basic Declarative Problem Solving Modules

• In general an integrity constraint r written as ← l_{1}, …, l_{m}, not l_{m+1}, …, not l_{n}, where l_{i}s are literals, forbids answer sets which contain the literals l_{1}, …, l_{m} and do not contain the literals l_{m+1}, …, l_{n}.

• r can be simulated by adding the following rule to the program. p ← not p, l_{1}, …, l_{m}, not l_{m+1}, …, not l_{n}. where p does not appear in the original program.

• r can also be simulated by adding the following rules to the program. p ← l_{1}, …, l_{m}, not l_{m+1}, …, not l_{n}. q ← not p. q ← not q. where p and q do not appear in the original program.

Enumeration

• Finite enumeration:

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:

chosen(X) ← possible(X), not not chosen(X). not chosen(X) ← possible(X), not chosen(X). some ← chosen(X). ← not some.

• Consider {possible(a), possible(b), possible(c)}.

Chitta Baral  45

Answer Set Programming.  Basic Declarative Problem Solving Modules

• Choice: General enumeration with exactly one: Our goal is to have a program which has answer sets with the following as subsets. S_{1} = {chosen(a), ¬chosen(b), ¬chosen(c)} S_{2} = {¬chosen(a), chosen(b), ¬chosen(c)} S_{3} = {¬chosen(a), ¬chosen(b), chosen(c)} ¬chosen(X) ← chosen(Y), X ≠ Y. chosen(X) ← possible(X), not ¬chosen(X).

• Choice using AnsProlog:

diff chosen than(X) ← chosen(Y), X ≠ Y. chosen(X) ← possible(X), not diff chosen than(X).

• Choice in Smodels syntax:

1{chosen(X) : possible(X)}1.

Propositional Satisfiability: an illustration

• 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}. n p_{1} ← not p_{1}. p_{2} ← not n p_{2}. n p_{2} ← not p_{2}. p_{3} ← not n p_{3}. n p_{3} ← not p_{3}. p_{4} ← not n p_{4}. n p_{4} ← not p_{4}.

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

• S is satisfiable iff Π(S) has an answer set.

• Basic idea: enumerate possibilities; add constraints.

Answer Set Programming.  Basic Declarative Problem Solving Modules

N-queens: naming queens and placing them one by one

1. Declarations:

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

2. Enumeration:

2.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).

2.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.

2.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).

Chitta Baral  48

Answer Set Programming.  Basic Declarative Problem Solving Modules

2.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.

3. Elimination:

3.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. 3.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. 3.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).

Answer Set Programming.  Basic Declarative Problem Solving Modules

N-queens: Similar to last one but now using Choice rules

1. Declarations: As in the previous formulation.

2. Enumeration:

2.1. Choice using other at(I, X, Y) which intuitively means that the queen I has been placed in a location other than (X, Y). 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). 2.2. No two queens are placed in the same location. (Same as in 2.4 in the last slide.)

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

3. Elimination: As in the previous formulation.

Chitta Baral  50

Answer Set Programming.  Basic Declarative Problem Solving Modules

N-queens: a solution without naming queens

1. Declarations: The simpler domain specification is as follows:

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

2. Enumeration:

2.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) 2.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) 2.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)

3. Elimination: No two queens 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).

Chitta Baral  51

AnsPrologor : Syntax and Semantics

• Syntax: A collection of rules of the form L_{0} or … or L_{k} ← L_{k+1}, …, L_{m}, not L_{m+1}, …, not L_{n}. where L_{i}’s are atoms.

• Semantics of a program Π: Given in terms of answer sets of the program ground(Π).

– Answer sets of AnsProlog^{−not,or} programs (where m = n for all rules): ∗ The minimal models of the program.

– Gelfond-Lifschitz transformation: as before

– Answer sets: S is an answer set of an AnsPrologor program Π if S is an answer set of the AnsProlog^{−not,or} program Π^{S}.

• Translating AnsPrologor to AnsProlog:

– For head-cycle free programs: Replace L_{0} or … or L_{k} ← Body. by L_{0} ← Body, not L_{1}, …, not L_{k}. ⋮ L_{k} ← Body, not L_{1}, …, not L_{k−1}.

– Consider a or b a ← b b ← a Only answer set is {a, b}.

– The AnsProlog translation a ← not b b ← not a a ← b b ← a has no answer sets.

Satisfiability of Universal-existential QBFs using AnsPrologor

• The QBF ∀p_{1}, … p_{k}. ∃q_{1}, …, q_{l}. (ϕ_{1}(p_{1}, …, p_{k}, q_{1}, …, q_{l}) ∧ … ∧ ϕ_{n}(p_{1}, …, p_{k}, q_{1}, …, q_{l})), where ϕ_{i}’s are disjunction of propositional literals, is satisfiable iff not satisfied is false in all answer sets of the following program:

p_{1} or p′_{1} ←.  …  p_{k} or p′_{k} ←.
q_{1} or q′_{1} ←.  …  q_{l} or q′_{l} ←.
not satisfied ← ϕ̂_{1}.  …  not satisfied ← ϕ̂_{n}.

q_{1} ← not satisfied. q′_{1} ← not satisfied. … q_{l} ← not satisfied. q′_{l} ← not satisfied.

Chitta Baral  54

• Intuition: For a given interpretation I_{p} of the ps if for some interpretation I_{q} of the qs the formula F = ϕ_{1} ∧ … ∧ ϕ_{n} is satisfied then it forces out any answer set due to I_{p} and I_{q′} which does not satisfy F as the later will be forced to have all combination of q_{i}s making it non-minimal.

• Thus AnsPrologor can express Π_{2}P problems while AnsProlog can only express Π_{1}P problems.

Sorting using AnsProlog

• Smallest largest and next:

not smallest(X) ← p(X), p(Y), less than(Y, X). smallest(X) ← p(X), not not smallest(X). not largest(X) ← p(X), p(Y), less than(X, Y). largest(X) ← p(X), not not largest(X). not next(X, Y) ← X = Y. not next(X, Y) ← less than(Y, X). not next(X, Y) ← p(X), p(Y), p(Z), less than(X, Z), less than(Z, Y). next(X, Y) ← p(X), p(Y), not not next(X, Y).

• q(1, X) ← smallest(X).

q(i + 1, X) ← q(i, Y), next(Y, X).

• Grounding of the above leads to O(n^{3}) ground rules. Can we do better?

Aggregation within AnsProlog^{¬}

• Consider the following database, where sold(a, 10, Jan1) means that 10 units of item a was sold on Jan 1. sold(a, 10, Jan1) ←. sold(a, 21, Jan5) ←. sold(a, 15, Jan16) ←. sold(b, 16, Jan4) ←. sold(b, 31, Jan21) ←. sold(b, 15, Jan26) ←. sold(c, 24, Jan8) ←. We would like to answer queries such as: “List all items of which more than 50 units (total) were sold, and the total quantity sold for each.”

• The encoding in AnsProlog^{¬}.

Chitta Baral  57

1. Assigning numbers to each tuple of sold while grouping them based on their item. I.e., we would like the answer sets to contain the following facts (or similar ones with a different numbering). assigned(a, 10, 1) ←. assigned(a, 21, 2) ←. assigned(a, 15, 3) ←. assigned(b, 16, 1) ←. assigned(b, 31, 2) ←. assigned(b, 15, 3) ←. assigned(c, 24, 1) ←. The AnsProlog program with such answer sets has the following three groups of rules: 1.1. Unique assignment of numbers to each pair of item, and units.

assigned(X, Y, J) ← sold(X, Y, D), not ¬assigned(X, Y, J).

¬assigned(X, Y, J) ← assigned(X, Y′, J), Y ≠ Y′. ¬assigned(X, Y, J) ← assigned(X, Y, J′), J ≠ J′

1.2. Among the tuples corresponding to each item there is no gap in the number assignment. numbered(X, J) ← assigned(X, Y, J).

← numbered(X, J + 1), not numbered(X, J), J ≥ 1. 1.3. The following rules ensure that for each item, there is a tuple that is assigned

the number 1. one is assigned(X) ← assigned(X, Y, 1). ← sold(X, Y, D), not one is assigned(X).

2. Initializing and updating the aggregate operations. Depending on the aggregate operators the initialize and update facts describe how to start the aggregation process, when the first tuple in each grouping is encountered, and how the aggregate value is updated when additional tuples are encountered. 2.1. Sum:

initialize(sum, Y, Y) ←. update(sum, W, Y, W + Y) ←.

2.2. initialize(sum, Y, Y) means that for the aggregate sum, during the aggregation process when the tuple ( , Y) that is assigned the initial number (which is 1) is considered, Y is the value from which the aggregation starts.

2.3. The aggregation starts from the tuple assigned 1, and runs though the other

tuples in the linear order of their assignment. 2.4. The fact, update(sum, W, Y, W + Y) is used in that process and intuitively

means that while doing the aggregation sum, if the next tuple (based on the ordering of its assignment) is ( , Y), and the current accumulated value is W, then after considering this tuple the accumulated value is to be updated to W + Y.

2.5. Count:

initialize(count, Y, 1). update(count, W, Y, W + 1) ←.

2.6. Min:

initialize(min, Y, Y) ←. update(min, W, Y, W) ← W ≤ Y. update(min, W, Y, Y) ← Y ≤ W.

3. Using the predicates initialize and update we can define other aggregate operators of our choice. Thus, AnsProlog allows us to express user-defined aggregates.

4. The following three rules describe how the initialize and update predicates are used in computing the aggregation. The first rule uses initialize to account for the tuple that is assigned the number 1, and the second rule encodes the aggregate computation when we already have computed the aggregate up to the Jth tuple, and we encounter the J+1th tuple. aggr(Aggr name, 1, X, Z) ← assigned(X, Y, 1), initialize(Aggr name, Y, Z). aggr(Aggr name, J + 1, X, Z) ← J > 0, aggr(Aggr name, J, X, W),

assigned(X, Y, J + 1),

update(Aggr name, W, Y, Z).

5. Computing new aggregate predicates: Once the aggregation is done, we can define new predicates for the particular aggregation that we need. Following are some examples of the encoding of such predicates. 5.1. Total sold per item:

total sold per item(X, Q) ← aggr(sum, J, X, Q),

not aggr(sum, J + 1, X, Y).

5.2. Number of transactions per item:

number of transactions per item(X, Q) ← aggr(count, J, X, Q),

not aggr(count, J + 1, X, Y).

5.3. Minimum amount (other than zero) sold per item:

min sold per item(X, Q) ← aggr(min, J, X, Q),

not aggr(min, J + 1, X, Y).

• Using the above program the answer sets we will obtain will contain the following: total sold per item(a, 46). total sold per item(b, 62). total sold per item(c, 24).

COMING TOGETHER OF KR, R AND DPS: REASONING ABOUT ACTIONS AND PLANNING

Answer Set Programming.  Coming together of KR, R and DPS: reasoning about actions and planning

A: A simple action language

• Syntax:

– Domain description (D): A collection of effect propositions of the form: a causes f if p_{1}, …, p_{n}, ¬q_{1}, …, ¬q_{r} where a is an action, f is a fluent literal, and p_{1}, …, p_{n}, q_{1}, …, q_{r} are fluents.

– Observations(O):

∗ General observations (Oracles): f after a_{1}, …, a_{m}

∗ Initial observations: initially f

– Queries(Q): f after a_{1}, …, a_{m}

• Semantics: Defining D ⊧_{O} Q

Examples of various kinds of reasoning in A

• Temporal projection:

– D = {load causes loaded; shoot causes ¬alive if loaded} – O = { initially alive}.

– D |̸=_{O} ¬alive after shoot

– D ⊧_{O} ¬alive after load, shoot

– O′ = { initially alive; initially loaded}

– D ⊧_{O′} ¬alive after shoot

• Reasoning about the initial situation

– O_{1} = { initially alive; ¬alive after shoot}

– D ⊧_{O_{1}} initially loaded

Answer Set Programming.  Coming together of KR, R and DPS: reasoning about actions and planning

• Observation assimilation:

– generalizes temporal projection and reasoning about the initial situation

– D = {load causes loaded; shoot causes ¬alive if loaded}

– O_{2} = { initially alive; loaded after shoot}

– D ⊧_{O_{2}} ¬alive after shoot.

• Planning

– O = { initially alive} and O′ = { initially alive; initially loaded} – The goal: G = {¬alive}

– shoot is a plan for G with respect to (D, O′)

– shoot is not a plan for G with respect to (D, O)

– load; shoot is a plan for G with respect to (D, O).

Implementing temporal projection using AnsProlog: π_{1}

• Assumption: Observations are only about the initial state and are complete.

• Translating effect propositions: For every effect proposition of the form a causes f if p_{1}, …, p_{n}, ¬q_{1}, … ¬q_{r}, if f is a fluent then have the following rule holds(f, res(a, S)) ← holds(p_{1}, S), …, holds(p_{n}, S), not holds(q_{1}, S), …, not holds(q_{r}, S). else, if f is the negative fluent literal ¬g then have the following rule: ab(g, a, S) ← holds(p_{1}, S), …, holds(p_{n}, S), not holds(q_{1}, S), …, not holds(q_{r}, S).

• Translating observations: For every value proposition of the form initially f, if f is a fluent then have the following: holds(f, s_{0}) ←.

• Inertia rule:

holds(F, res(A, S)) ← holds(F, S), not ab(F, A, S).

Chitta Baral  66

Answer Set Programming.  Coming together of KR, R and DPS: reasoning about actions and planning

• An Example:

– D = {load causes loaded; shoot causes ¬alive if loaded}

– O_{3} = { initially alive; initially ¬loaded}

– The AnsProlog rules will be:

holds(loaded, res(load, S)) ←.

ab(alive, shoot, S) ← holds(loaded, S).

holds(alive, s_{0}) ← .

holds(F, res(A, S)) ← holds(F, S), not ab(F, A, S).

– Notation: [a_{n}, …, a_{1}] denotes the situation res(a_{n} … res(a_{1}, s_{0}) …).

– From the program we can entail holds(alive, [load]), and holds(loaded, [load]), and ¬holds(alive, [shoot, load]).

• Proposition: Let D be a consistent domain description and O be an initial state complete set of observations such that (D, O) is consistent. Let f be a fluent.

(i) D ⊧_{O} f after a_{1}, …, a_{n} iff π_{1}(D, O) ⊧ holds(f, [a_{n}, …, a_{1}]). (ii) D ⊧_{O} ¬f after a_{1}, …, a_{n} iff π_{1}(D, O) |̸= holds(f, [a_{n}, …, a_{1}])

Implementing temporal projection using AnsProlog^{¬}: π_{2}

• Assumption: Observations are only about the initial state and are complete.

• Translating effect propositions: For every effect proposition of the form a causes f if p_{1}, …, p_{n}, ¬q_{1}, … ¬q_{r}, if f is a fluent then we have: holds(f, res(a, S)) ← holds(p_{1}, S), …, holds(p_{n}, S),

¬holds(q_{1}, S), …, ¬holds(q_{r}, S).

ab(f, a, S) ← holds(p_{1}, S), …, holds(p_{n}, S), ¬holds(q_{1}, S), …, ¬holds(q_{r}, S). else, if f is the negative fluent literal ¬g then we have: ¬holds(g, res(a, S)) ← holds(p_{1}, S), …, holds(p_{n}, S),

¬holds(q_{1}, S), …, ¬holds(q_{r}, S).

ab(g, a, S) ← holds(p_{1}, S), …, holds(p_{n}, S), ¬holds(q_{1}, S), …, ¬holds(q_{r}, S).

Chitta Baral  68

Answer Set Programming.  Coming together of KR, R and DPS: reasoning about actions and planning

• Translating observations: For every value proposition of the form initially f, if f is a fluent then we have: holds(f, s_{0}) ←. else, if f is the negative fluent literal ¬g then we have: ¬holds(g, s_{0}) ←.

• Inertia rules:

holds(F, res(A, S)) ← holds(F, S), not ab(F, A, S). ¬holds(F, res(A, S)) ← ¬holds(F, S), not ab(F, A, S).

• Proposition: Let D be a consistent domain description and O be an initial state complete set of observations such that (D, O) is consistent. Let f be a fluent.

(i) D ⊧_{O} f after a_{1}, …, a_{n} iff π_{2}(D, O) ⊧ holds(f, [a_{n}, …, a_{1}]). (ii) D ⊧_{O} ¬f after a_{1}, …, a_{n} iff π_{2}(D, O) ⊧ ¬holds(f, [a_{n}, …, a_{1}]).

Temporal projection in AnsProlog^{¬} in presence of incompleteness: π_{3}

• An Example where the previous encoding falters:

– D = {load causes loaded; shoot causes ¬alive if loaded}

– O_{4} = { initially alive}.

– The earlier AnsProlog^{¬} implementation will consist of:

holds(loaded, res(load, S)) ←. ab(loaded, load, S) ←. ¬holds(alive, res(shoot, S)) ← holds(loaded, S). ab(alive, shoot, S) ← holds(loaded, S). holds(alive, s_{0}) ← . holds(F, res(A, S)) ← holds(F, S), not ab(F, A, S). ¬holds(F, res(A, S)) ← ¬holds(F, S), not ab(F, A, S).

– The program will incorrectly entail holds(alive, [shoot]), while D |̸=_{O_{4}} alive after shoot.

• A conservative encoding:

– Translating effect propositions: The effect propositions in D are translated as follows and are collectively referred to as π_{3}^{ef}. For every effect proposition of the form a causes f if p_{1}, …, p_{n}, ¬q_{1}, …, q_{r}, if f is a fluent then we have: holds(f, res(a, S)) ← holds(p_{1}, S), …, holds(p_{n}, S),

¬holds(q_{1}, S), …, ¬holds(q_{r}, S).

ab(f, a, S) ← not ¬holds(p_{1}, S), …, not ¬holds(p_{n}, S),

not holds(q_{1}, S), …, not holds(q_{r}, S).

else, if f is the negative fluent literal ¬g then we have: ¬holds(g, res(a, S)) ← holds(p_{1}, S), …, holds(p_{n}, S),

¬holds(q_{1}, S), …, ¬holds(q_{r}, S).

ab(g, a, S) ← not ¬holds(p_{1}, S), …, not ¬holds(p_{n}, S),

not holds(q_{1}, S), …, not holds(q_{r}, S).

– Observations and inertia rules are as before.

Answer Set Programming.  Coming together of KR, R and DPS: reasoning about actions and planning

• Proposition: Let D be a consistent domain description and O be an initial state complete set of observations such that (D, O) is consistent. Let f be a fluent.

(i) D ⊧_{O} f after a_{1}, …, a_{n} iff π_{3}(D, O) ⊧ holds(f, [a_{n}, …, a_{1}]). (ii) D ⊧_{O} ¬f after a_{1}, …, a_{n} iff π_{3}(D, O) ⊧ ¬holds(f, [a_{n}, …, a_{1}]).

• Proposition: Let D be a consistent domain description, and O be a (possibly incomplete) set of observations about the initial state such that (D, O) is consistent. Let f be a fluent.

(i) If π_{3}(D, O) ⊧ holds(f, [a_{n}, …, a_{1}]) then D ⊧_{O} f after a_{1}, …, a_{n}. (ii) If π_{3}(D, O) ⊧ ¬holds(f, [a_{n}, …, a_{1}]) then D ⊧_{O} ¬f after a_{1}, …, a_{n}.

Assimilating observations using enumeration and constraints: π_{4}

• Assumption: Observations are not necessarily about the initial state and do not have to be complete.

• Translating effect propositions: For every effect proposition of the form a causes f if p_{1}, …, p_{n}, ¬q_{1}, … ¬q_{r}, if f is a fluent then we have: holds(f, res(a, S)) ← holds(p_{1}, S), …, holds(p_{n}, S),

¬holds(q_{1}, S), …, ¬holds(q_{r}, S).

ab(f, a, S) ← holds(p_{1}, S), …, holds(p_{n}, S), ¬holds(q_{1}, S), …, ¬holds(q_{r}, S). else, if f is the negative fluent literal ¬g then we have: ¬holds(g, res(a, S)) ← holds(p_{1}, S), …, holds(p_{n}, S),

¬holds(q_{1}, S), …, ¬holds(q_{r}, S).

ab(g, a, S) ← holds(p_{1}, S), …, holds(p_{n}, S), ¬holds(q_{1}, S), …, ¬holds(q_{r}, S).

• Inertia rules:

holds(F, res(A, S)) ← holds(F, S), not ab(F, A, S). ¬holds(F, res(A, S)) ← ¬holds(F, S), not ab(F, A, S).

Chitta Baral  73

Answer Set Programming.  Coming together of KR, R and DPS: reasoning about actions and planning

• Enumeration:

holds(F, s_{0}) ← not ¬holds(F, s_{0}). ¬holds(F, s_{0}) ← not holds(F, s_{0}).

• Translating observations: For an observation of the form f after a_{1}, …, a_{m}, if f is a fluent then we have: ← not holds(f, [a_{m}, …, a_{1}]). else if f is the fluent literal ¬g, then we have: ← not ¬holds(g, [a_{m}, …, a_{1}]).

• Proposition: Let D be a consistent domain description, and O be a set of observations such that (D, O) is consistent. Let f be a fluent.

(i) π_{4}(D, O) ⊧ holds(f, [a_{n}, …, a_{1}]) iff D ⊧_{O} f after a_{1}, …, a_{n}. (ii) π_{4}(D, O) ⊧ ¬holds(f, [a_{n}, …, a_{1}]) iff D ⊧_{O} ¬f after a_{1}, …, a_{n}.

A narrative-based formulation of temporal projection: π_{2.nar}

• Translating effect propositions: For every effect proposition of the form a causes f if p_{1}, …, p_{n}, ¬q_{1}, … ¬q_{r}, if f is a fluent then we have: holds(f, T + 1) ← occurs(a, T), holds(p_{1}, T), …, holds(p_{n}, T),

not holds(q_{1}, T), …, not holds(q_{r}, T).

ab(f, a, T) ← occurs(a, T), holds(p_{1}, T), …, holds(p_{n}, T),

not holds(q_{1}, T), …, not holds(q_{r}, T). else, if f is the negative fluent literal ¬g then we have: not holds(g, T + 1) ← occurs(a, T), holds(p_{1}, T), …, holds(p_{n}, T),

not holds(q_{1}, T), …, not holds(q_{r}, T).

ab(g, a, T) ← occurs(a, T), holds(p_{1}, T), …, holds(p_{n}, T),

not holds(q_{1}, T), …, not holds(q_{r}, T).

Chitta Baral  75

Answer Set Programming.  Coming together of KR, R and DPS: reasoning about actions and planning

• Translating observations: For every value proposition of the form initially f, if f is a fluent then we have: holds(f, 1) ←. else, if f is the negative fluent literal ¬g then we have: not holds(g, 1) ←.

• Inertia rules: Besides the above we have the following inertia rules:

holds(F, T + 1) ← occurs(A, T), holds(F, T), not ab(F, A, T). not holds(F, T + 1) ← occurs(A, T), not holds(F, T), not ab(F, A, T).

• Proposition: Let D be a consistent domain description and O be an initial state complete set of observations such that (D, O) is consistent. Let f be a fluent.

(i) D ⊧_{O} f after a_{1}, …, a_{n} iff π_{2.nar}(D, O) ∪ {occurs(a_{1}, 1), …, occurs(a_{n}, n)} ⊧ holds(f, n + 1). (ii) D ⊧_{O} ¬f after a_{1}, …, a_{n} iff π_{2.nar}(D, O) ∪ {occurs(a_{1}, 1), …, occurs(a_{n}, n)} ⊧ not holds(f, n + 1)

From reasoning with narratives to Answer Set Planning: π_{2.planning}

• We have all the rules from the narrative reasoning program π_{2.nar}.

• Choice rules: We have the following choice rules that make sure that one and only one action occurs at each time point up to l. not occurs(A, T) ← occurs(B, T), A ≠ B. occurs(A, T) ← T ≤ l, not not occurs(A, T).

• Goal: Finally we have the following constraint, for our goal h.

← not holds(h, l + 1).

Chitta Baral  77

• Proposition: Let D be a consistent domain description, O be an initial state complete set of observations such that (D, O) is consistent, l be the length of the plan that we are looking for, and h be a fluent which is the goal.

(i) If there is a sequence of actions a_{1}, …, a_{l} such that D ⊧_{O} h after a_{1}, …, a_{l} then there exists a consistent answer of π_{2.planning}(D, O, h, l) containing {occurs(a_{1}, 1), …, occurs(a_{l}, l)} as the only facts about occurs. (ii) If there exists a consistent answer of π_{2.planning}(D, O, h, l) containing {occurs(a_{1}, 1), …, occurs(a_{l}, l)} as the facts about occurs then D ⊧_{O} h after a_{1}, …, a_{l}.

More on reasoning about actions and planning

• Allowing executability conditions: executable drive if has car

• Allowing static constraints:

– move to(Y) causes at(Y).

– A person can only be at one place at one time.

– initially at(A).

– Impact of move to(B)?

– marry(Y) causes married to(Y)

– A person can only be married to one person at one time.

– initially married to(A).

– Impact of marry(B)?

– Classical logic: Both constraint written the same way.

– In AnsProlog*:

¬at(Y) ← at(X), X ≠ Y.

← married to(X), married to(Y), X ≠ Y.

Chitta Baral  79

Answer Set Programming.  Coming together of KR, R and DPS: reasoning about actions and planning

• Concurrent actions: when to inherit and when not to.

{close} causes ¬opened {open} causes opened {paint} causes painted.

• Planning with hierarchical (HTN), temporal (LTL) and procedural constraints (Golog).

– HTN: hierarchical task networks

– LTL: Linear temporal logic.

– Golog.

• Agent architecture based on observation assimilation, projection and planning from the current situation.

– Observe the world and add the observations to the agent’s set of observations (O).

– Construct a plan from the current moment of time to achieve the goal.

– Execute the first action of the plan and add this execution as an observation to the set O.

Answer Set Programming.  Coming together of KR, R and DPS: reasoning about actions and planning

• Action based explanation: Explaining observations by what might have happened.

• Action based diagnosis

– Assume that initially all components were fine.

– Find missing action occurrences that explain the observations.

– Determine what components are bad in the current situation.

COMPUTING ANSWER SETS

Answer Set Programming.  Computing Answer Sets

Direct algorithms

• Branch-n-bound using Well-founded semantics

• SLG approach

• Smodels algorithm

• DLV algorithm

• Algorithms based on graphs and colorings

Well-founded semantics for AnsProlog programs

• For an AnsProlog program Π, let Γ_{Π}(S) denote the answer set of Π^{S}.

• Thus S is an answer set of Π if S = Γ_{Π}(S).

• Well-founded semantics of AnsProlog programs is given by {lfp(Γ_{Π}^{2}), gfp(Γ_{Π}^{2})}

• I.e., for an atom p we have Π ⊧_{wf} p iff p ∈ lfp(Γ_{Π}^{2}) and Π ⊧_{wf} ¬p iff p ∉ gfp(Γ_{Π}^{2}).

• Since fixpoints of Γ_{Π} are also fixpoints of Γ_{Π}^{2}, the well-founded semantics is an approximation of the answer set semantics for AnsProlog programs.

• Proposition: Let Π be an AnsProlog program and A be an atom.

(i) A ∈ lfp(Γ_{Π}^{2}) implies Π ⊧ A.

(ii) A ∉ gfp(Γ_{Π}^{2}) implies Π |̸= A.

• p ← a.

p ← b.

a ← not b.

b ← not a.

wfs-bb: an illustration

• Consider the following program P: r_{1} : a ←. r_{2} : b ← a. r_{3} : d ← not e. r_{4} : e ← not d, c. r_{5} : f ← g, a. r_{6} : g ← f, d. r_{7} : h ← not h, f. r_{8} : i ← not j, b. r_{9} : j ← not i, not c. r_{a} : k ← not l, i. r_{b} : l ← not k, j.

• WFS = ⟨{a, b, d}, {c, e, f, g, h}⟩

Answer set computation using SAT solvers

• Basic Idea: Compile the program to an appropriate propositional theory and compute its models.

• Tight programs: An AnsProlog program Π is said to be tight (or positive order consistent), if there exists a function λ from HB_{Π} to the set of natural numbers such that for every L_{0} ← L_{1}, …, L_{m}, not L_{m+1}, …, not L_{n} in ground(Π), and for every 1 ≤ i ≤ m: λ(L_{0}) > λ(L_{i}).

• Proposition: For any propositional AnsProlog program, if Π is tight then X is an answer set of Π iff X is a model of Comp(Π).

• An AnsProlog^{¬,⊥} program Π is said to be tight on a set X of literals, if there exists a partial mapping λ with domain X from literals to the set of natural numbers such that for every rule L_{0} ← L_{1}, …, L_{m}, not L_{m+1}, …, not L_{n} in ground(Π), if L_{0}, …, L_{m} ∈ X, then for every 1 ≤ i ≤ m: λ(L_{0}) > λ(L_{i}).

• p ← p.

This program is obviously not tight. But it is tight on the set of literals {}.

Chitta Baral  86

• Proposition: For any AnsProlog^{¬,⊥} program Π and any consistent set X of literals such that Π is tight on X, X is an answer set of Π iff X is closed under and supported by Π.

• Proposition: For any propositional AnsProlog program and any set X of atoms such that Π is tight on X, X is an answer set of Π iff X is a model of Comp(Π).

• What if the above two approaches do not work?

– Transform the program to a tight program. (Lin and Reiter.)

– Transform the program by finding strongly connected components and adding rules corresponding to it to make the program inherently tight – a necessary and sufficient condition for the equivalence between answer sets and models of Comp(Π). (Lin and Jicheng Zhao.)

– Add additional propositional formulas to Comp(Π).

∗ Ben-Eliyahu and Dechter find strongly connected components and use it to construct new formulas.

∗ Lin and Y. Zhao find positive loops and add loop formulas.

Loop formulas

• Definition: A set of atoms L is said to be a loop in a program Π, if for every pair p, q in L, there is a positive path from p to q in the dependency graph of Π.

• Definition: Let L be a loop with respect to a program Π, then R^{+}(L, Π), the set of rules in Π with head in L that are involved in L is {r | r ∈ Π, head(r) ∈ L, body(r) ∩ L ≠ ∅}.

• Definition: Let L be a loop with respect to a program Π, then R^{−}(L, Π), the set of rules in Π with head in L that are not involved in L is {r | r ∈ Π, head(r) ∈ L, body(r) ∩ L = ∅}.

• Intuition behind loop formulas: “If none of the atoms in the loop can be proved using other rules, then these atoms must be false.”

Chitta Baral  88

Answer Set Programming.  Computing Answer Sets

• Definition: Let L = {p_{1}, …, p_{n}} be a loop with respect to a program Π, and let R^{−}(L, Π) consist of the following rules: p_{1} ← body_{11}…. p_{1} ← body_{1k_{1}}. ⋮ p_{n} ← body_{1n}…. p_{1} ← body_{1k_{n}}. Then the loop formula corresponding to L is ¬(body_{11} ∨ body_{1k_{1}} ∨ … ∨ body_{n1} ∨ body_{nk_{n}}) ⊃ (¬p_{1} ∧ … ∧ ¬p_{n})

• Proposition: Let Π be an AnsProlog program and LF (Π) be the set of all the loop formulas for all the loops in Π. S is an answer set of Π iff S is a model of Comp(Π) ∪ LF (Π).

• Consider the program p ← p.

Comp(Π) = {p ⇔ p}.

• The number of loop formulas may be exponential in the size of the program.

• ASSAT does not find all the loop a-priori.

So why not use Propositional logic in the first place?

• Propositional logic is good for machines in that it is easier to find models for it.

• But AnsProlog is good for people in terms of ease of knowledge representation; is more elaboration tolerant; is non-monotonic. ...

• It is proven that AnsProlog can not be translated to propositional logic with an exponential blow up in the worst case.

• Best of both worlds: Program in AnsProlog; Compile to propositional logic to obtain answer sets whenever it is necessary and is feasible.

ANSWER SET PROGRAMMING SYSTEMS

Answer Set Programming.  Answer Set Programming Systems

Some existing systems

• Smodels: Core syntax is AnsProlog; has additional features.

• DLV: Core syntax is AnsPrologor ; has additional features.

• ASSAT: Core syntax is AnsProlog.

• Prolog

• Cmodels

• NoMoRe

Programming using Smodels: http://www.tcs.hut.fi/Software/smodels/

• Graph Colorability: The graph is described by the facts with respect to predicates vertex and edge and the given set of colors are expressed using the predicate col. vertex(1..4). edge(1,2). edge(1,3). edge(2,3). edge(1,4). edge(2,4). % edge(3,4). col(a;b;c). 1 { color(X,C) : col(C) } 1 :- vertex(X). :- edge(X,Y), col(C), color(X,C), color(Y,C). :- edge(Y,X), col(C), color(X,C), color(Y,C). hide col(X). hide vertex(Y). hide edge(X,Y).

Chitta Baral  93

Answer Set Programming.  Answer Set Programming Systems

• Knapsack problem: We have five items (1-5) and each item has a cost (or size) and value associated with it. We have a sack with a given capacity (12) and the goal is to select a subset of the items which can fit the sack while maximizing the total value. item(1..5). weight val(1) = 5. weight val(2) = 6. weight val(3) = 3. weight val(4) = 8. weight val(5) = 2. weight cost(1) = 4. weight cost(2) = 5. weight cost(3) = 6. weight cost(4) = 5. weight cost(5) = 3. in sack(X) :- item(X), not not in sack(X). not in sack(X) :- item(X), not in sack(X). val(X) :- item(X), in sack(X). cost(X) :- item(X), in sack(X). cond1 :- [ cost(X) : item(X) ] 12. :- not cond1. maximize { val(X) : item(X) }. hide item(X). hide not in sack(X). hide cost(X). hide val(X).

Answer Set Programming.  Answer Set Programming Systems

• Single Unit Combinatorial Auction: Bidders are allowed to bid on a bundle of items. The auctioneer has to select a subset of the bids so as to maximize the price it gets, and making sure that it does not accept multiple bids that have the same item as each item can be sold only once. The auctioneer has the set of items {1, 2, 3, 4}, and the buyers submit bids {a, b, c, d, e} where a constitutes of ⟨{1, 2, 3}, 24⟩, meaning that the bid a is for the bundle {1, 2, 3} and its price is $24. and so on. bid(a;b;c;d;e). item(1..4). in(1,a). in(2,a). in(3,a). in(2,b). in(3,b). in(3,c). in(4,c). in(2,d). in(3,d). in(4,d). in(1,e). in(4,e). weight sel(a) = 24. weight sel(b) = 9. weight sel(c) = 8. weight sel(d) = 25. weight sel(e) = 15. sel(X) :- bid(X), not not sel(X). not sel(X) :- bid(X), not sel(X). :- bid(X), bid(Y), sel(X), sel(Y), not eq(X,Y), item(I), in(I,X), in(I,Y). maximize [ sel(X) : bid(X) ]. hide bid(X). hide not sel(X). hide item(X). hide in(X,Y).

Programming using DLV: http://www.dbai.tuwien.ac.at/proj/dlv/

• Single Unit Combinatorial auction using weak constraints bid(a). bid(b). bid(c). bid(d). bid(e). in(1,a). in(2,a). in(3,a). in(2,b). in(3,b). in(3,c). in(4,c). in(2,d). in(3,d). in(4,d). in(1,e). in(4,e). sel(X) v not sel(X) :- bid(X). :- sel(X), sel(Y), X != Y, in(I,X), in(I,Y). :∼ not sel(a). [24:1] :∼ not sel(b). [9:1] :∼ not sel(c). [8:1] :∼ not sel(d). [25:1] :∼ not sel(e). [15:1]

Programming Tricks

• Neither Smodels nor DLV allow function symbols or explicit sets and lists.

• Aggregation in Smodels sold(a, 10, jan1). sold(a, 21, jan5). sold(a, 15, jan16). sold(b, 16, jan4). sold(b, 31, jan21). sold(b, 15, jan26). sold(c, 24, jan8). item(a;b;c). number(1..100). date(jan1;jan5;jan16;jan4;jan21;jan26;jan8). weight sold(X,Y,Z) = Y. total sold(I, N) :- item(I), number(N), N [ sold(I, X, D) : number(X) : date(D) ] N. total sell transactions(I, N) :- item(I), number(N),

N { sold(I, X, D) : number(X) : date(D) } N.

Chitta Baral  97

Answer Set Programming.  Answer Set Programming Systems

• Sets causes(a, f, s). set(s). in(p1, s). ... in(pn, s).

• Lists of arbitrary depth: p([a, [b, [c, d]) p(l). head(l,a). body(l, l1). head(l1, b). body(l1, l2). head(l2, c). body(l2, l3). head(l3, d). body(l3, nil).

Correct query answering using Prolog

• Pure Prolog: Syntax of AnsProlog and semantics of Prolog.

• Pure Prolog semantics is based on

(i) SLDNF resolution with the leftmost selection rule (i.e., LDNF resolution) where by only the leftmost literal in each query is marked selected;

(ii) but ignoring floundering; (iii) omitting occur check during unification; and (iv) selecting input rules during resolution from the beginning of the program to the

end.

• Theorem: If an AnsProlog program Π is well moded for some input-output specification and there is no rule in Π whose head contains more than one occurrence of the same variable in its output positions then Π is occur check free with respect to any ground query.

• Theorem: If an AnsProlog program Π is well moded for some input-output specification and all predicate symbols occurring under not are moded completely by input then a ground query to Π does not flounder.

Chitta Baral  99

• Proposition: If Π is an acceptable AnsProlog program and Q is a ground query then all SLDNF derivations – with left most selection – of Q (with respect to Π) are finite and therefore the Pure Prolog interpreter terminates on Q.

• Summary: One way to show that the Pure prolog semantics of a program agrees with the AnsProlog semantics is by showing that the conditions in above three results are satisfied.

COMPLEXITY, EXPRESSIVENESS AND RELATIONS WITH OTHER LANGUAGES

Answer Set Programming.  Complexity, Expressiveness and relations with other languages

Complexity vs Expressiveness

• Let L be a sub-class of AnsProlog*, Π be a program in L, D_{in} be a set of ground facts in L, and A be a literal.

– Data complexity of L: Complexity of checking D_{in} ∪ Π ⊧ A, in terms of the length of the input ⟨D_{in}, A⟩, given a fixed Π in L.

– Program complexity of L: Complexity of checking D_{in} ∪ Π ⊧ A, in terms of the length of the input ⟨Π, A⟩, given a fixed D_{in} in L.

– Combined complexity of L: Complexity of checking D_{in} ∪ Π ⊧ A, in terms of the length of the input ⟨Π, D_{in}, A⟩.

• Given an AnsProlog* program Π the recognition problem associated with it is to determine if Π ∪ I ⊧ A, given some facts I and a ground literal A. Alternatively, the recognition problem of Π is to determine membership in the set {⟨I, A⟩ : Π ∪ I ⊧ A}.

• An AnsProlog* program Π is said to be in complexity class C if the recognition problem associated with Π is in C.

Chitta Baral  102

• An AnsProlog* sub-class L is data-complete for complexity class C (or equivalently, the data complexity class of L is C-complete) if

(i) (membership): each program in L is in C, and (ii) (hardness): there exists a program in L for which the associated recognition problem is complete with respect to the class C.

• Expressiveness: An AnsProlog* sub-class L is said to capture the complexity class C if

(i) each program in L is also in C, and (ii) every problem of complexity C can be expressed in L.

• L is data-complete in C does not imply that L captures C.

Even though there may exist queries in L for which the associated recognition problem is complete with respect to the class C, there may be problems in the class C which can not be expressed in L.

• L captures C does not imply that L is data-complete in C.

This is because even though L captures C there may not exist a problem that is C-complete.

Summary of the complexity results of AnsDatalog* sub-classes

AnsDatalog* Class  Complexity Type  Complexity Class
AnsDatalog^{−not}  Data complexity  P-complete
AnsDatalog^{−not}  Program complexity  EXPTIME-complete
Stratified AnsDatalog  Data complexity  P-complete
Stratified AnsDatalog  Program complexity  EXPTIME-complete
AnsDatalog (under WFS)  Data complexity  P-complete
AnsDatalog (under WFS)  Program complexity  EXPTIME-complete
AnsDatalog (answer set existence) complexity of SM(Π) ≠ ∅  NP-complete
AnsDatalog Data complexity coNP-complete
AnsDatalog  Program complexity coNEXPTIME complete
AnsDatalog^{¬}  Existence of answer set  NP-complete
AnsDatalog^{¬}  Data complexity  coNP-complete
AnsDatalog^{or ,−not}  Deciding Π ⊧_{GCW A} A  coNP-complete
AnsDatalog^{or ,−not}  Deciding Π ⊧_{GCW A} ¬A  Π_{2}P-complete
AnsDatalogor  Data complexity  Π_{2}P-complete
AnsDatalogor  Program complexity coNEXPTIME^{NP}-comp.

Summary of expressiveness of AnsDatalog* sub-classes

AnsDatalog* Sub-class  Relation  Complexity Class

(or a non-AnsProlog* class)

Datalog^{+}  ⊂≠  P
Datalog^{+} (on ordered databases)  captures  P
Datalog^{+}  equal  F P L^{+}(∃)
Stratified AnsDatalog  ⊂≠  FPL
Non-recursive range restr AnsDatalog  equal  relational algebra
Non-recursive range restr AnsDatalog  equal  relational calculus
Non-recursive range restr AnsDatalog  equal FOL (without function symbols)
AnsDatalog (under WFS) equal FPL
Stratified AnsDatalog (on ordered databases) captures  P
AnsDatalog under WFS (on ordered databases) captures  P
AnsDatalog under brave semantics  captures  NP
AnsDatalog  captures  coNP
AnsDatalog^{or,−not,≠} (under brave semantics) captures  Σ_{2}P
AnsDatalog^{or,−not,≠}  captures  Π_{2}P
AnsDatalogor (under brave semantics)  captures  Σ_{2}P
AnsDatalogor  captures  Π_{2}P

Complexity and expressiveness of programs with function symbols

AnsProlog* Class  Complexity type Complexity Class

(With Functions)

AnsProlog^{−not} complexity r.e. complete
AnsProlog^{−not} (without recursion)  complexity NEXPTIME-complete
AnsProlog^{−not} (with restrictions^{1}) complexity PSPACE-complete
Stratified AnsProlog (n levels of stratification) complexity  Σ_{n+1}^{0}-complete
Non-recursive AnsProlog  Data complexity  P
AnsProlog (under WFS)  complexity  Π_{1}^{1}-complete
AnsProlog  complexity  Π_{1}^{1} complete
AnsProlog^{or ,−not}  under GCWA  Π_{2}^{0} complete
AnsPrologor  complexity  Π_{1}^{1}-complete
AnsProlog* Class  relation Complexity Class
AnsProlog (under WFS) captures  Π_{1}^{1}
AnsProlog  captures  Π_{1}^{1}
AnsPrologor  captures  Π_{1}^{1}

AnsProlog* vs Classical logic

• Propositional theories can be easily mapped to AnsProlog.

• There is no rule-modular mapping from propositional AnsProlog to propositional logic.

– A mapping T (.) from the language L_{1} to L_{2} is said to be rule-modular if for any theory (or program) Π in L_{1}, for each set (possibly empty) of atomic facts F, the “models” of Π ∪ F and T (Π) ∪ F coincide.

• Classical logic vs AnsProlog*

– Since the semantics of AnsProlog* is based on the Herbrand universe and answer sets of AnsProlog programs are Herbrand Interpretations there is often a mismatch between classical theories and AnsProlog* programs if we do not restrict ourselves to Herbrand models.

Chitta Baral  108

– T_{1} : ontable(a) ∧ ontable(b)

– Π_{1} obtained by translating T_{1} ontable(X) ← not n ontable(X). n ontable(X) ← not ontable(X). good model ← ontable(a), ontable(b). ← not good model. Query Q given by ∀X.ontable(X).

– Π_{1} ⊧ ∀X.ontable(X).

– But T_{1} |̸= ∀X.ontable(X).

– Note: While using resolution with respect to T_{1} and Q, the clauses obtained from T_{1} ∪ {¬Q} is the set {ontable(a), ontable(b), ¬ontable(c)} – where c is a skolem constant, which does not lead to a contradiction.

– Way out: In AnsProlog* judiciously introduce skolem constants derived by transforming the query into a clausal form as done during resolution.

Description logic vs AnsProlog*

• A straightforward translation of {child = ∃ childof, son = male ⊓ child} to AnsProlog would be the following rules. r_{1} : child(X) ← childof(X, Y). r_{2} : son(X) ← male(X), child(X).

• But while {child = ∃ childof, son = male ⊓ child, son(a)} ⊧^{dl} child(a), {r_{1}, r_{2}, son(a)} |̸= child(a).

• Besides r_{1} and r_{2}, a correct AnsProlog translation will consist of the following rules: r_{3} : male(X) ← top(X), not female(X). r_{4} : female(X) ← top(X), not male(X). r_{5} : childof(X, Y) ← top(X), top(Y), X ≠ Y, not not childof(X, Y). r_{6} : not childof(X, Y) ← top(X), top(Y), X ≠ Y, not childof(X, Y). r_{7} : ← childof(X, Y), childof(Y, X). and facts about the predicate top listing all elements belonging to the concept ⊤.

Chitta Baral  110

Answer Set Programming.  Complexity, Expressiveness and relations with other languages

• Now to assimilate son(a) we need to add the following: r_{8} : ← not son(a). whose effect is to eliminate all potential answer sets which do not contain son(a).

CONCLUSION AND SOME FUTURE DIRECTIONS

Answer Set Programming.  Conclusion and some future directions

Conclusion

• Being able to represent and reason with knowledge is one of the two key components of AI systems.

• AnsProlog* is a good candidate as the ‘core’ of a knowledge representation language – satisfies all the ‘desirable’ criteria that we listed.

• The compilation to propositional logic approach of computing answer sets adds a new dimension to their fast computation.

• Still lot more needs to be done.

Emerging and Future directions

• Further development of the language. The ‘core’ is there, need features such as cardinality constraints, sets, aggregates, preference between rules, etc.

• As language is broadened, need to expand the building block results.

• Need better systems: Smodels and dlv work only with function free programs, and Prolog works with a very restricted subset.

• Integration of probability with logic.

• Integration with other knowledge representation languages and/or borrowing their features: description logic, constraints of the kind in CLP, higher level syntax such as in F-logic, function symbols and numbers as in Prolog.

• Discovering efficient encodings for polynomially solvable problem.

• Emerging applications: Semantics Web, data and knowledge integration.

• Inductive AnsProlog* or learning AnsProlog* rules from data; using knowledge encoded in AnsProlog* during learning.

• Using it in more, bigger and eye-catching application domains.

Chitta Baral  114