Answer set programming

Answer set programming

Answer set programming (ASP) is a form of declarative programming oriented towards difficult (primarily NP-hard) search problems. It is based on the stable model (answer set) semantics of logic programming. In ASP, search problems are reduced to computing stable models, and "answer set solvers" -- programs for generating stable models -- are used to perform search. The computational process employed in the design of many answer set solvers is an enhancement of the DPLL algorithm and, in principle, it always terminates (unlike Prolog query evaluation, which may lead to an infinite loop).

In a more general sense, ASP includes all applications of answer sets to knowledge representation [Baral 2003; Gelfond 2008] and the use of Prolog-style query evaluation for solving problems arising in these applications.

History

The planning method proposed by Dimopoulos, Nebel and Köhler [1997] is an early example of answer set programming. Their approach is based on the relationship between plans and stable models described in [Subrahmanian and Zaniolo 1995] . Soininen and Niemelä [1998] applied what is now known as answer set programming to the problem of product configuration. The use of answer set solvers for search was identified as a new programming paradigm in [Marek and Truszczyński 1999] (the term "answer set programming" was used for the first time as the title of a part of the collection where that paper appeared) and in [Niemelä 1999] .

Answer set programming language Lparse

[http://www.tcs.hut.fi/Software/smodels/lparse.ps Lparse] is the name of the program that was originally created as a front-end for the answer set solver [http://www.tcs.hut.fi/Software/smodels/ smodels] , and is now used in the same way in many other answer set solvers, including [http://assat.cs.ust.hk/ assat] , [http://www.cs.uni-potsdam.de/clasp/ clasp] , [http://www.cs.utexas.edu/users/tag/cmodels/ cmodels] , [http://www.tcs.hut.fi/Software/gnt/ gNt] , [http://www.cs.uni-potsdam.de/nomore/ nomore++] and [http://www.cs.uky.edu/ai/pbmodels/ pbmodels] . ( [http://www.dbai.tuwien.ac.at/proj/dlv/ dlv] is an exception; the syntax of ASP programs written for dlv is somewhat different.)

An Lparse program consists of rules of the form

:- .

The symbol :- ("if") is dropped if is empty. The simplest kind of Lparse rules are rules with constraints.

One other useful construct included in this language is "choice". For instance, the choice rule

{p,q,r}.

says: choose arbitrarily which of the atoms p,q,r to include in the stable model. The lparse program that contains this choice rule and no other rules has 8 stable models -- arbitrary subsets of {p,q,r}. The definition of a stable model was generalized to programs with choice rules by Ilkka Niemelä, Patrik Simons and Timo Soininen [1999] . According to [Ferraris and Lifschitz, 2005] , choice rules can be treated also as abbreviations for propositional formulas under the stable model semantics. For instance, the choice rule above can be viewed as shorthand for the conjunction of three "excluded middle" formulas:

:(plor eg p)land(qlor eg q)land(rlor eg r).

The language of lparse allows us also to write "constrained" choice rules, such as

1{p,q,r}2.

This rule says: choose at least 1 of the atoms p,q,r, but not more than 2. The meaning of this rule under the stable model semantics is represented by the propositional formula

:(plor eg p)land(qlor eg q)land(rlor eg r)

::land,(plor qlor r)land eg(pland qland r).

Cardinality bounds can be used in the body of a rule as well, for instance:

:- 2{p,q,r}.

Adding this constraint to an Lparse program eliminates the stable models that contain at least 2 of the atoms p,q,r. The meaning of this rule can be represented by the propositional formula

:: eg((pland q)lor(pland r)lor(qland r)).

Variables (capitalized, as in Prolog) are used in Lparse to abbreviate collections of rules that follow the same pattern, and also to abbreviate collections of atoms within the same rule. For instance, the Lparse program

p(a). p(b). p(c).q(X) :- p(X), X!=a.

has the same meaning as

p(a). p(b). p(c).q(b). q(c).

The program

p(a). p(b). p(c).{q(X):p(X)}2.

is shorthand for

p(a). p(b). p(c).{q(a),q(b),q(c)}2.

Generating stable models

To find a stable model of the Lparse program stored in file we use the command

% lparse | smodels

Option 0 instructs smodels to find "all" stable models of the program. For instance, if file test contains the rules

1{p,q,r}2.s :- not p.

then the command

% lparse test | smodels 0

produces the output

Answer: 1Stable Model: q p Answer: 2Stable Model: p Answer: 3Stable Model: r p Answer: 4Stable Model: q s Answer: 5Stable Model: r s Answer: 6Stable Model: r q s

Examples of ASP programs

Graph coloring

An n-coloring of a graph G is a function color from its set of vertices to {1,dots,n} such that color(x) eq color(y) for every pair of adjacent vertices x,y. We would like to use ASP to find an n-coloring of a given graph (or determine that it does not exist).

This can be accomplished using the following Lparse program:

c(1..n). 1 {color(X,I) : c(I)} 1 :- v(X). :- color(X,I), color(Y,I), e(X,Y), c(I).

Line 1 defines the numbers 1,dots,n to be colors. According to the choice rule in Line 2, a unique color i should be assigned to each vertex x. The constraint in Line 3 prohibits assigning the same color to vertices x and y if there is an edge connecting them.

If we combine this file with a definition of G, such as

v(1..100). % 1,...,100 are verticese(1,55). % there is an edge from 1 to 55. . .

and run smodels on it, with the numeric value of n specified on the command line, then the atoms of the form color(dots,dots) in the output of smodels will represent an n-coloring of G.

The program in this example illustrates the "generate-and-test" organization that is often found in simple ASP programs. The choice rule describes a set of "potential solutions" -- a simple superset of the set of solutions to the given search problem. It is followed by a constraint, which eliminates all potential solutions that are not acceptable. However, the search process employed by smodels and other answer set solvers is not based on trial and error.

Large clique

A clique in a graph is a set of pairwise adjacent vertices. The following lparse program finds a clique of size geq n in a given graph, or determines that it does not exist:

n {in(X) : v(X)}.:- in(X), in(Y), v(X), v(Y), X!=Y, not e(X,Y), not e(Y,X).

This is another example of the generate-and-test organization. The choice rule in Line 1 "generates" all sets consisting of geq n vertices. The constraint in Line 2 "weeds out" the sets that are not cliques.

Hamiltonian cycle

A Hamiltonian cycle in a directed graph is a cycle that passes through each vertex of the graph exactly once. The following Lparse program can be used to find a Hamiltonian cycle in a given directed graph if it exists; we assume that 0 is one of the vertices.

{in(X,Y)} :- e(X,Y).

:- 2 {in(X,Y) : e(X,Y)}, v(X).:- 2 {in(X,Y) : e(X,Y)}, v(Y).

r(X) :- in(0,X), v(X).r(Y) :- r(X), in(X,Y), e(X,Y).

:- not r(X), v(X).

The choice rule in Line 1 "generates" all subsets of the set of edges. The three constraints "weed out" the subsets that are not Hamiltonian cycles. The last of them uses the auxiliary predicate r(x) ("x is reachable from 0") to prohibit the vertices that do not satisfy this condition. This predicate is defined recursively in Lines 4 and 5.

This program is an example of the more general "generate, define and test" organization: it includes the definition of an auxiliary predicate that helps us eliminate all "bad" potential solutions.

Comparison of implementations

References

* C. Baral [2003] "Knowledge Representation, Reasoning and Declarative Problem Solving." Cambridge University Press.

* Y. Dimopoulos, B. Nebel and J. Köhler [1997] " [ftp://ftp.informatik.uni-freiburg.de/documents/papers/ki/dimopoulos-etal-ecp97.ps.gz Encoding planning problems in non-monotonic logic programs.] " In: Proceedings of ECP-97, Springer Verlag, pages 273-285.

* P. Ferraris and V. Lifschitz [2005] " [http://www.cs.utexas.edu/users/vl/papers/weight.ps Weight constraints as nested expressions.] " Theory and Practice of Logic Programming, Vol. 5, pages 45-74.

* M. Gelfond [2008] " [http://www.krlab.cs.ttu.edu/Papers/download/gel07b.pdf Answer sets.] " In: Handbook of Knowledge Representation, Elsevier, pages 285-316.

* V. Marek and M. Truszczyński [1999] " [http://xxx.lanl.gov/pdf/cs/9809032 Stable models and an alternative logic programming paradigm.] " In: The Logic Programming Paradigm: a 25-Year Perspective, Springer Verlag, pages 169-181.

* I. Niemelä [1999] " [http://www.tcs.hut.fi/~ini/papers/lp-csp-long.ps Logic programs with stable model semantics as a constraint programming paradigm.] " Annals of Mathematics and Artificial Intelligence, Vol. 25, pages 241-273.

* I. Niemelä, P. Simons and T. Soinenen [1999] " [http://www.tcs.hut.fi/~ini/papers/nss-lpnmr99-www.ps.gz Stable model semantics of weight constraint rules.] " In: Proceedings of LPNMR-99, pages 317-331.

* T. Soininen and I. Niemelä [1998] " [http://www.tcs.hut.fi/~ini/papers/sn-faanmr98.ps.gz Formalizing configuration knowledge using rules with choices.] " Technical Report TKO-B142, Laboratory of Information Processing Science, Helsinki University of Technology.

* V.S.Subrahmanian and C. Zaniolo [1995] " [http://www.cs.ucla.edu/%7Ezaniolo/papers/iclp95.ps Relating stable models and AI planning domains.] " In: Proceedings of ICLP-95, pages 233-247.

ee also

*Default logic
*Logic programming
*Non-monotonic logic
*Prolog
*Stable model semantics

External links

* [http://asparagus.cs.uni-potsdam.de/contest/ First ASP System Competition]
* [http://www.cs.uni-potsdam.de/platypus/ Platypus]


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Programming paradigm — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concu …   Wikipedia

  • Programming in the large and programming in the small — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computin …   Wikipedia

  • Abductive logic programming — is a high level knowledge representation framework that can be used to solve problems declaratively based on abductive reasoning. It extends normal Logic Programming by allowing some predicates to be incompletely defined, declared as abducible… …   Wikipedia

  • Logic programming — is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy s [1958] advice taker proposal, logic is used as a purely declarative… …   Wikipedia

  • Programming language — lists Alphabetical Categorical Chronological Generational A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that… …   Wikipedia

  • Constraint logic programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing …   Wikipedia

  • Object-oriented programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing …   Wikipedia

  • Constraint programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computin …   Wikipedia

  • Declarative programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computing …   Wikipedia

  • Class-based programming — Programming paradigms Agent oriented Automata based Component based Flow based Pipelined Concatenative Concurrent computin …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”