Answer set programming (ASP) is a form of
declarative programming
In computer science, declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.
Many languages that a ...
oriented towards difficult (primarily
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
)
search problems. It is based on the
stable model (answer set) semantics of
logic programming
Logic programming is a programming paradigm which is largely based on formal logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of log ...
. 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
Prolog is a logic programming language associated with artificial intelligence and computational linguistics.
Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily a ...
query evaluation, which may lead to an
infinite loop).
In a more general sense, ASP includes all applications of answer sets to
knowledge representation
Knowledge representation and reasoning (KRR, KR&R, KR²) is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks such as diagnosing a medic ...
and the use of Prolog-style query evaluation for solving problems arising in these applications.
History
An early example of answer set programming was the
planning
Planning is the process of thinking regarding the activities required to achieve a desired goal. Planning is based on foresight, the fundamental capacity for mental time travel. The evolution of forethought, the capacity to think ahead, is c ...
method proposed in 1997 by Dimopoulos, Nebel and Köhler.
Their approach is based on the relationship between plans and stable models.
In 1998 Soininen and Niemelä
applied what is now known as answer set programming to the problem of
product configuration.
[ In 1999, the term "answer set programming" appeared for the first time in a book ''The Logic Programming Paradigm'' as the title of a collection of two papers.][ The first of these papers identified the use of answer set solvers for search as a new ]programming paradigm
Programming paradigms are a way to classify programming languages based on their features. Languages can be classified into multiple paradigms.
Some paradigms are concerned mainly with implications for the execution model of the language, s ...
. That same year Niemelä also proposed "logic programs with stable model semantics" as a new paradigm.
Answer set programming language AnsProlog
Lparse
is the name of the program that was originally created as a grounding tool (front-end) for the answer set solve
smodels
The language that Lparse accepts is now commonly called AnsProlog, short for ''Answer Set Programming in Logic''. It is now used in the same way in many other answer set solvers, includin
assat
clasp
cmodels
gNt
nomore++
an
pbmodels
dlv
is an exception; the syntax of ASP programs written for dlv is somewhat different.)
An AnsProlog program consists of rules of the form
:- .
The symbol :-
("if") is dropped if
is empty; such rules are called ''facts''. 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
.
says: choose arbitrarily which of the atoms 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 . The definition of a stable model was generalized to programs with choice rules. 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:
:
The language of Lparse allows us also to write "constrained" choice rules, such as
12.
This rule says: choose at least 1 of the atoms , but not more than 2. The meaning of this rule under the stable model semantics is represented by the propositional formula
:
::
Cardinality bounds can be used in the body of a rule as well, for instance:
:- 2.
Adding this constraint to an Lparse program eliminates the stable models that contain at least 2 of the atoms . The meaning of this rule can be represented by the propositional formula
::
Variables (capitalized, as in Prolog
Prolog is a logic programming language associated with artificial intelligence and computational linguistics.
Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily a ...
) 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).
2.
is shorthand for
p(a). p(b). p(c).
2.
A ''range'' is of the form:
(start..end)
where start and end are constant valued arithmetic expressions. A range is a notational shortcut that is mainly used to define numerical domains in
a compatible way. For example, the fact
a(1..3).
is a shortcut for
a(1). a(2). a(3).
Ranges can also be used in rule bodies with the same semantics.
A ''conditional literal'' is of the form:
p(X):q(X)
If the extension of q is , the above condition is semantically equivalent to writing in the place of the condition. For example,
q(1..2).
a :- 1 .
is a shorthand for
q(1). q(2).
a :- 1 .
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
12.
s :- not p.
then the command produces the output
% lparse test , smodels 0
Answer: 1
Stable Model: q p
Answer: 2
Stable Model: p
Answer: 3
Stable Model: r p
Answer: 4
Stable Model: q s
Answer: 5
Stable Model: r s
Answer: 6
Stable Model: r q s
Examples of ASP programs
Graph coloring
An - coloring of a graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
is a function such that for every pair of adjacent vertices . We would like to use ASP to find an -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 1 :- v(X).
:- color(X,I), color(Y,I), e(X,Y), c(I).
Line 1 defines the numbers to be colors. According to the choice rule in Line 2, a unique color should be assigned to each vertex . The constraint in Line 3 prohibits assigning the same color to vertices and if there is an edge connecting them.
If we combine this file with a definition of , such as
v(1..100). % 1,...,100 are vertices
e(1,55). % there is an edge from 1 to 55
. . .
and run smodels on it, with the numeric value of specified on the command line, then the atoms of the form in the output of smodels will represent an -coloring of .
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
Trial and error is a fundamental method of problem-solving characterized by repeated, varied attempts which are continued until success, or until the practicer stops trying.
According to W.H. Thorpe, the term was devised by C. Lloyd Morgan ( ...
.
Large clique
A clique
A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popula ...
in a graph is a set of pairwise adjacent vertices. The following Lparse program finds a clique of size in a given graph, or determines that it does not exist:
n .
:- 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 vertices. The constraint in Line 2 "weeds out" the sets that are not cliques.
Hamiltonian cycle
A Hamiltonian cycle
In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...
in a directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pai ...
is a cycle
Cycle, cycles, or cyclic may refer to:
Anthropology and social sciences
* Cyclic history, a theory of history
* Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr.
* Social cycle, various cycles in soc ...
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.
:- e(X,Y).
:- 2 , v(X).
:- 2 , 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 (" is reachable from 0") to prohibit the vertices that do not satisfy this condition. This predicate is defined recursively in Lines 6 and 7.
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.
Dependency parsing
In natural language processing
Natural language processing (NLP) is an interdisciplinary subfield of linguistics, computer science, and artificial intelligence concerned with the interactions between computers and human language, in particular how to program computers to proc ...
, dependency-based parsing can be formulated as an ASP problem.
The following code parses the Latin sentence "Puella pulchra in villa linguam latinam discit", "the pretty girl is learning Latin in the villa".
The syntax tree is expressed by the ''arc'' predicates which represent the dependencies between the words of the sentence.
The computed structure is a linearly ordered rooted tree.
% ********** input sentence **********
word(1, puella). word(2, pulchra). word(3, in). word(4, villa). word(5, linguam). word(6, latinam). word(7, discit).
% ********** lexicon **********
11 :- word(X, pulchra).
node(X, attr(latinus, a, fem, acc, sg)) :- word(X, latinam).
11 :- word(X, puella).
11 :- word(X, villa).
node(X, attr(linguam, n, fem, acc, sg)) :- word(X, linguam).
node(X, attr(discere, v, pres, 3, sg)) :- word(X, discit).
node(X, attr(in, p)) :- word(X, in).
% ********** syntactic rules **********
01 :- node(X, attr(_, v, _, 3, sg)), node(Y, attr(_, n, _, nom, sg)).
01 :- node(X, attr(_, v, _, 3, sg)), node(Y, attr(_, n, _, acc, sg)).
01 :- node(X, attr(_, n, Gender, Case, Number)), node(Y, attr(_, a, Gender, Case, Number)).
01 :- node(X, attr(_, p)), node(Y, attr(_, n, _, abl, _)), X < Y.
01 :- node(X, attr(_, v, _, _, _)), node(Y, attr(_, p)), not leaf(Y).
% ********** guaranteeing the treeness of the graph **********
11.
:- arc(X, Z, _), arc(Y, Z, _), X != Y.
:- arc(X, Y, L1), arc(X, Y, L2), L1 != L2.
path(X, Y) :- arc(X, Y, _).
path(X, Z) :- arc(X, Y, _), path(Y, Z).
:- path(X, X).
:- root(X), node(Y, _), X != Y, not path(X, Y).
leaf(X) :- node(X, _), not arc(X, _, _).
Language standardization and ASP Competition
The ASP standardization working group produced a standard language specification, called ASP-Core-2, towards which recent ASP systems are converging. ASP-Core-2 is the reference language for the Answer Set Programming Competition, in which ASP solvers are periodically benchmarked over a number of reference problems.
Comparison of implementations
Early systems, such as Smodels, used backtracking
Backtracking is a class of algorithms for finding solutions to some computational problems, notably constraint satisfaction problems, that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it de ...
to find solutions. As the theory and practice of Boolean SAT solvers evolved, a number of ASP solvers were built on top of SAT solvers, including ASSAT and Cmodels. These converted ASP formula into SAT propositions, applied the SAT solver, and then converted the solutions back to ASP form. More recent systems, such as Clasp, use a hybrid approach, using conflict-driven algorithms inspired by SAT, without full converting into a Boolean-logic form. These approaches allow for significant improvements of performance, often by an order of magnitude, over earlier backtracking algorithms.
Th
Potassco
project acts as an umbrella for many of the systems below, including ''clasp'', grounding systems (''gringo''), incremental systems (''iclingo''), constraint solvers (''clingcon''), action language to ASP compilers (''coala''), distributed MPI implementations (''claspar''), and many others.
Most systems support variables, but only indirectly, by forcing grounding, by using a grounding system such as ''Lparse'' or ''gringo'' as a front end. The need for grounding can cause a combinatorial explosion of clauses; thus, systems that perform on-the-fly grounding might have an advantage.
Query-driven implementations of answer set programming, such as the Galliwasp system and s(CASP) avoid grounding altogether by using a combination of resolution and coinduction.
See also
* Default logic
*Logic programming
Logic programming is a programming paradigm which is largely based on formal logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of log ...
* Non-monotonic logic
*Prolog
Prolog is a logic programming language associated with artificial intelligence and computational linguistics.
Prolog has its roots in first-order logic, a formal logic, and unlike many other programming languages, Prolog is intended primarily a ...
*Stable model semantics The concept of a stable model, or answer set, is used to define a declarative semantics for logic programs with negation as failure. This is one of several standard approaches to the meaning of negation in logic programming, along with program co ...
References
External links
ASP-Core-2 2.03c Input Language Specification
First ASP System Competition
Second ASP Competition
Third ASP Competition
Fourth ASP Competition
Platypus
* ttp://www.cs.uni-potsdam.de/clasp/ Clasp Answer Set Solver
{{DEFAULTSORT:Answer Set Programming
Logic programming