User:Michael Gelfond/Draft ASProlog

From Wikipedia, the free encyclopedia

1 Answer Set Prolog

[edit] Answer Set Prolog

[edit] Introduction

Answer Set Prolog (also known as A-Prolog or ASP-Prolog) is a language for knowledge representation and reasoning based on the answer set semantics of logic programs. The language has its roots in declarative programming, the syntax and semantics of standard Prolog, disjunctive databases and non-monotonic logic. Answer Set Prolog allows the expression of disjunction and "classical" or "strong" negation, and has the ability to represent and reason about many important kinds of statements including defaults (statements of the form Elements of class C normally satisfy property P) and exceptions to defaults, causal effects of actions (statement F becomes true as a result of performing an action a), statements expressing lack of information (it is not known if statement P is true or false), various completeness assumptions (statements not entailed by the knowledgebase are false), recursive definitions, etc.

[edit] Syntax and Informal Semantics

A logic program of Answer Set Prolog is a collection of rules of the form:

$l_0 \ or \ ... \ or \ l_k \ \gets \ l_{k+1}, ..., l_{m},\ not \ l_{m+1}, ..., not \ l_n$

where $l_{i}\,$ 's are literals (an atom $p(t)\,$ or its negation $\lnot p(t)$ ). Connectives $not\,$ and $or\,$ are called negation as failure or default negation, and epistemic disjunction respectively. The connective $or\,$ is used instead of the classical ' $\lor$ ' to stress the difference between the two connectives. A rule $r\,$ with variables (written in uppercase) is viewed as a set of its ground instantiations - rules obtained from $r\,$ by replacing $r\,$ 's variables by constants.

Rules of a logic program $\Pi\,$ can be viewed as a collection of constraints that must be satisfied by the beliefs of a rational reasoner associated with $\Pi\,$ . A set of beliefs $S\,$ satisfies a rule if whenever $l_{k+1}\,$ to $l_m\,$ belong to $S\,$ and none of $l_{m+1}\,$ to $l_n\,$ belong to $S\,$ , then at least one of $l_0\,$ to $l_k\,$ belong to $S\,$ .

The answer set semantics assigns to a logic program $\Pi\,$ a collection of answer sets: Sets of literals from $\Pi\,$ corresponding to possible sets of beliefs built by a rational reasoner on the basis of the rules of $\Pi\,$ . In the construction of such a set of beliefs $S\,$ , the reasoner is assumed to be guided by the following informal principles:

$S\,$ must satisfy the rules of $\Pi\,$
The reasoner should adhere to the rationality principle, which says: one shall not believe anything one is not forced to believe.

Programs of Answer Set Prolog can have one, many, or zero answer sets.

[edit] Examples

[edit] Example : Defaults

Normally, computers come preloaded with software. Brand x computers are an exception to this rule, they may or may not come loaded with software. Computers assembled from parts do not come preloaded with software.
The following logic program represents the above knowledge
$\begin{align} comp(a). \\ comp(b). \\ comp(c). \\ brandx(b). \\ assembled(c). \\ preloaded(X) & \gets comp(X), \ not \ ab(X), \ not \ \lnot preloaded(X).\\ ab(X) & \gets brandx(X).\\ \lnot loaded(X) & \gets assembled(X).\\ \end{align}$
This program has one answer set which includes: $\{preloaded(a), \lnot preloaded(c)\}\,$ . Notice that neither $preloaded(b) \,$ nor $\lnot preloaded(b) \,$ is concluded.
This example underscores the difference between $\lnot p$ and $not \ p\,$ with respect to an answer set $S\,$ . The former corresponds to a belief that $p\,$ is false ( $\lnot p \in S$ ), while the later only asserts the absence of belief in $p\,$ ( $p \notin S$ ).

[edit] Example : Actions and their effects

In a room are two bulbs each connected to a swich. Switching a bulb's switch turns the bulb on. At timestep 0 both bulbs are off, and bulb #2 is switched.
The following program represents this knowledge
$\begin{align} timestep(0). \\ timestep(1). \\ \lnot on(b1,0). \\ \lnot on(b2,0). \\ switch(b2,0). \\ on(B,T+1) & \gets switch(B,T).\\ \lnot on(B,T+1) & \gets \lnot on(B,T), \ not \ on(B,T+1). \end{align}$
This program has one answer set which includes $\{on(b2,1), \ \lnot on(b1,1)\}\,$ . The last rule of the program effectively represents the law of inertia: bulbs remain off unless they are explicitly turned on.

[edit] Example : Multimple answer sets

Cars have manual or automatic transmissions.
The corresponding program:
$\begin{align} car(c1). \\ manual(X) \ or \ automatic(X) & \gets car(X). \\ \end{align}$
has two answer sets, $\{ car(c1), \ manual(c1)\}$ and $\{ car(c1), \ automatic(c1)\}$

[edit] Example : Incomplete information

Objects whose location is unknown are missing.
As in the following example program:
$\begin{align} object(tv).\\ object(remote).\\ location(tv,table).\\ missing(X) & \gets \ not \ location(X,Y). \\ \lnot missing(X) & \gets location(X,Y). \end{align}$
The program has one answer set that includes, $\{\lnot missing(tv), \ missing(remote)\}\,$ .

[edit] Inference Engines

There exists a comparatively large number of inference engines (program that compute answer sets) associated with Answer Set Prolog. Systems based on goal-oriented SLDNF-resolution of "classical" Prolog and its variants are sound with respect to the answer set semantics. The same is true for fix-point computations of deductive databases. These systems can be used for answering queries to a subset of Answer Set Prolog which does not contains disjunction, "strong" negation, and rules with empty heads. Recently, inference engines with specialized algorithms aimed at computing the answer sets of arbitrary Answer Set Prolog programs have come of age. These engines are often referred as answer set solvers. Another recently developed approach reduces the computation of answer sets to (possible multiple) calls to satisfiability solvers.

List of Inference Engines:

[edit] Extensions

There is substantial and mathematically elegant extensions of the original Answer Set Prolog. Expanding answer set programming by aggregates - functions on sets - is approaching its final solution. Weak constraints and consistency restoring rules have been introduced to deal with possible inconsistencies. Also, the rules of the language have been generalized to allow nested logical connectives and various means to express preferences between answer sets. The logical reasoning of Answer Set Prolog has also been combined with probabilistic reasoning and with qualitative optimization. All these languages have at least experimental implementations and an emerging theory and methodology of use.