Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Answer set programming

From Wikipedia, the free encyclopedia
Programming paradigm focused on difficult search problems
Not to be confused withActive Server Pages.

Answer set programming (ASP) is a form ofdeclarative programming oriented towards difficult (primarilyNP-hard)search problems. It is based on thestable model (answer set) semantics oflogic programming. In ASP, search problems are reduced to computing stable models, andanswer 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 theDPLL algorithm and, in principle, it always terminates (unlikeProlog query evaluation, which may lead to aninfinite loop).

In a more general sense, ASP includes all applications of answer sets toknowledge representation and reasoning[1][2] and the use of Prolog-style query evaluation for solving problems arising in these applications.

History

[edit]

An early example of answer set programming was theplanning method proposed in 1997 by Dimopoulos, Nebel and Köhler.[3][4] Their approach is based on the relationship between plans and stable models.[5]In 1998 Soininen and Niemelä[6] applied what is now known as answer set programming to the problem ofproduct configuration.[4] In 1999, the term "answer set programming" appeared for the first time in a bookThe Logic Programming Paradigm as the title of a collection of two papers.[4] The first of these papers identified the use of answer set solvers for search as a newprogramming paradigm.[7] That same year Niemelä also proposed "logic programs with stable model semantics" as a new paradigm.[8]

Answer set programming language AnsProlog

[edit]

Lparse is the name of the program that was originally created as agrounding tool (front-end) for the answer set solversmodels. The language that Lparse accepts is now commonly called AnsProlog,[9] short forAnswer Set Programming in Logic.[10] It is now used in the same way in many other answer set solvers, includingassat,clasp,cmodels,gNt,nomore++ andpbmodels. (dlv is an exception; the syntax of ASP programs written for dlv is somewhat different.)

An AnsProlog program consists of rules of the form

<head>:-<body>.

The symbol:- ("if") is dropped if<body> is empty; such rules are calledfacts. The simplest kind of Lparse rules arerules with constraints.

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

{p,q,r}.

says: choose arbitrarily which of the atomsp,q,r{\displaystyle 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}{\displaystyle \{p,q,r\}}. The definition of a stable model was generalized to programs with choice rules.[11] Choice rules can be treated also as abbreviations forpropositional formulas under the stable model semantics.[12] For instance, the choice rule above can be viewed as shorthand for the conjunction of three "excluded middle" formulas:

(p∨¬p)∧(q∨¬q)∧(r∨¬r).{\displaystyle (p\lor \neg p)\land (q\lor \neg q)\land (r\lor \neg 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 atomsp,q,r{\displaystyle p,q,r}, but not more than 2. The meaning of this rule under the stable model semantics is represented by thepropositional formula

(p∨¬p)∧(q∨¬q)∧(r∨¬r){\displaystyle (p\lor \neg p)\land (q\lor \neg q)\land (r\lor \neg r)}
∧(p∨q∨r)∧¬(p∧q∧r).{\displaystyle \land \,(p\lor q\lor r)\land \neg (p\land q\land 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 atomsp,q,r{\displaystyle p,q,r}. The meaning of this rule can be represented by the propositional formula

¬((p∧q)∨(p∧r)∨(q∧r)).{\displaystyle \neg ((p\land q)\lor (p\land r)\lor (q\land r)).}

Variables (capitalized, as inProlog) 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.

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

Aconditional literal is of the form:

p(X):q(X)

If the extension ofq is{q(a1), q(a2), ..., q(aN)}, the above condition is semantically equivalent to writing{p(a1), p(a2), ..., p(aN)} in the place of the condition. For example,

q(1..2).a:-1{p(X):q(X)}.

is a shorthand for

q(1).q(2).a:-1{p(1),p(2)}.

Generating stable models

[edit]

To find a stable model of the Lparse program stored in file${filename} we use the command

%lparse${filename}|smodels

Option 0 instructs smodels to findall stable models of the program. For instance, if filetest contains the rules

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

then the command produces the output

%lparsetest|smodels0Answer: 1Stable Model: q pAnswer: 2Stable Model: pAnswer: 3Stable Model: r pAnswer: 4Stable Model: q sAnswer: 5Stable Model: r sAnswer: 6Stable Model: r q s

Examples of ASP programs

[edit]

Graph coloring

[edit]

Ann{\displaystyle n}-coloring of agraphG=⟨V,E⟩{\displaystyle G=\left\langle V,E\right\rangle } is a functioncolor:V→{1,…,n}{\displaystyle \mathrm {color} :V\to \{1,\dots ,n\}} such thatcolor(x)≠color(y){\displaystyle \mathrm {color} (x)\neq \mathrm {color} (y)} for every pair of adjacent vertices(x,y)∈E{\displaystyle (x,y)\in E}. We would like to use ASP to find ann{\displaystyle 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 numbers1,…,n{\displaystyle 1,\dots ,n} to be colors. According to the choice rule in Line 2, a unique colori{\displaystyle i} should be assigned to each vertexx{\displaystyle x}. The constraint in Line 3 prohibits assigning the same color to verticesx{\displaystyle x} andy{\displaystyle y} if there is an edge connecting them.

If we combine this file with a definition ofG{\displaystyle 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 ofn{\displaystyle n} specified on the command line, then the atoms of the formcolor(…,…){\displaystyle \mathrm {color} (\dots ,\dots )} in the output of smodels will represent ann{\displaystyle n}-coloring ofG{\displaystyle 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 ontrial and error.

Large clique

[edit]

Aclique in a graph is a set of pairwise adjacent vertices. The following Lparse program finds a clique of size≥n{\displaystyle \geq n} in a given directed graph, or determines that it does not exist:

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

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

Hamiltonian cycle

[edit]

AHamiltonian cycle in adirected graph is acycle 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).:-notr(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 predicater(x){\displaystyle r(x)} ("x{\displaystyle x} 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

[edit]

Innatural language processing,dependency-based parsing can be formulated as an ASP problem.[13]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 thearc 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 **********1{node(X,attr(pulcher,a,fem,nom,sg));node(X,attr(pulcher,a,fem,abl,sg))}1:-word(X,pulchra).node(X,attr(latinus,a,fem,acc,sg)):-word(X,latinam).1{node(X,attr(puella,n,fem,nom,sg));node(X,attr(puella,n,fem,abl,sg))}1:-word(X,puella).1{node(X,attr(villa,n,fem,nom,sg));node(X,attr(villa,n,fem,abl,sg))}1:-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 **********0{arc(X,Y,subj)}1:-node(X,attr(_,v,_,3,sg)),node(Y,attr(_,n,_,nom,sg)).0{arc(X,Y,dobj)}1:-node(X,attr(_,v,_,3,sg)),node(Y,attr(_,n,_,acc,sg)).0{arc(X,Y,attr)}1:-node(X,attr(_,n,Gender,Case,Number)),node(Y,attr(_,a,Gender,Case,Number)).0{arc(X,Y,prep)}1:-node(X,attr(_,p)),node(Y,attr(_,n,_,abl,_)),X<Y.0{arc(X,Y,adv)}1:-node(X,attr(_,v,_,_,_)),node(Y,attr(_,p)),notleaf(Y).% ********** guaranteeing the treeness of the graph **********1{root(X):node(X,_)}1.:-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,notpath(X,Y).leaf(X):-node(X,_),notarc(X,_,_).

Language standardization and ASP Competition

[edit]

The ASP standardization working group produced a standard language specification, called ASP-Core-2,[14] 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

[edit]

Early systems, such as smodels, usedbacktracking to find solutions. As the theory and practice ofBoolean 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 fully converting into a Boolean-logic form. These approaches allow for significant improvements of performance, often by an order of magnitude, over earlier backtracking algorithms.

ThePotassco project acts as an umbrella for many of the systems below, includingclasp, grounding systems (gringo), incremental systems (iclingo), constraint solvers (clingcon),action language to ASP compilers (coala), distributedMessage Passing Interface implementations (claspar), and many others.

Most systems support variables, but only indirectly, by forcing grounding, by using a grounding system such asLparse orgringo 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.[15]

Query-driven implementations of answer set programming, such as the Galliwasp system[16] and s(CASP)[17] avoid grounding altogether by using a combination ofresolution andcoinduction.

PlatformFeaturesMechanics
NameOSLicenceVariablesFunction symbolsExplicit setsExplicit listsDisjunctive (choice rules) support
ASPeRiXArchived 2016-11-08 at theWayback MachineLinuxGPLYesNoon-the-fly grounding
ASSATSolarisFreewareSAT-solver based
Clasp Answer Set SolverLinux,macOS,WindowsMIT LicenseYes, in ClingoYesNoNoYesincremental, SAT-solver inspired (nogood, conflict-driven)
CmodelsLinux,SolarisGPLRequires groundingYesincremental, SAT-solver inspired (nogood, conflict-driven)
diff-SATLinux,macOS,Windows (Java virtual machine)MIT LicenseRequires groundingYesSAT-solver inspired (nogood, conflict-driven). Supports solving probabilistic problems and answer set sampling
DLVLinux,macOS,Windows[18]free for academic and non-commercial educational use, and for non-profit organizations[18]YesYesNoNoYesnot Lparse compatible
DLV-ComplexLinux,macOS,WindowsGPLYesYesYesYesbuilt on top ofDLV — not Lparse compatible
GnTLinuxGPLRequires groundingYesbuilt on top of smodels
nomore++LinuxGPLcombined literal+rule-based
PlatypusLinux,Solaris,WindowsGPLdistributed, multi-threaded nomore++, smodels
PbmodelsLinux?pseudo-boolean solver based
SmodelsLinux,macOS,WindowsGPLRequires groundingNoNoNoNo
Smodels-ccArchived 2015-11-15 at theWayback MachineLinux?Requires groundingSAT-solver based; smodels w/conflict clauses
SupLinux?SAT-solver based

See also

[edit]

References

[edit]
  1. ^Baral, Chitta (2003).Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press.ISBN 978-0-521-81802-5.
  2. ^Gelfond, Michael (2008)."Answer sets". In van Harmelen, Frank; Lifschitz, Vladimir; Porter, Bruce (eds.).Handbook of Knowledge Representation. Elsevier. pp. 285–316.ISBN 978-0-08-055702-1.as PDFArchived 2016-03-03 at theWayback Machine
  3. ^Dimopoulos, Y.;Nebel, B.; Köhler, J. (1997). "Encoding planning problems in non-monotonic logic programs". In Steel, Sam; Alami, Rachid (eds.).Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings. Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence. Vol. 1348. Springer. pp. 273–285.ISBN 978-3-540-63912-1.as Postscript
  4. ^abcLifschitz, Vladimir (13 July 2008)."What is answer set programming?"(PDF).Proceedings of the 23rd National Conference on Artificial Intelligence.3. AAAI Press:1594–1597.
  5. ^Subrahmanian, V.S.; Zaniolo, C. (1995)."Relating stable models and AI planning domains". In Sterling, Leon (ed.).Logic Programming: Proceedings of the Twelfth International Conference on Logic Programming. MIT Press. pp. 233–247.ISBN 978-0-262-69177-2.as Postscript
  6. ^Soininen, T.; Niemelä, I. (1998),Formalizing configuration knowledge using rules with choices(Postscript), Laboratory of Information Processing Science, Helsinki University of Technology
  7. ^Marek, V.; Truszczyński, M. (20 May 1999). "Stable models and an alternative logic programming paradigm". InApt, Krzysztof R. (ed.).The Logic programming paradigm: a 25-year perspective(PDF). Springer. pp. 169–181.arXiv:cs/9809032.ISBN 978-3-540-65463-6.
  8. ^Niemelä, I. (November 1999)."Logic programs with stable model semantics as a constraint programming paradigm"(Postscript,gzipped).Annals of Mathematics and Artificial Intelligence.25 (3/4):241–273.doi:10.1023/A:1018930122475.S2CID 14465318.
  9. ^Crick, Tom (2009).Superoptimisation: Provably Optimal Code Generation using Answer Set Programming(PDF) (Ph.D.). University of Bath. Docket 20352. Archived fromthe original(PDF) on 2016-03-04. Retrieved2011-05-27.
  10. ^Rogelio Davila."AnsProlog, an overview"(PowerPoint).
  11. ^Niemelä, I.; Simons, P.; Soinenen, T. (2000)."Stable model semantics of weight constraint rules". In Gelfond, Michael; Leone, Nicole; Pfeifer, Gerald (eds.).Logic Programming and Nonmonotonic Reasoning: 5th International Conference, LPNMR '99, El Paso, Texas, USA, December 2–4, 1999 Proceedings. Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence. Vol. 1730. Springer. pp. 317–331.ISBN 978-3-540-66749-0.as Postscript
  12. ^Ferraris, P.; Lifschitz, V. (January 2005). "Weight constraints as nested expressions".Theory and Practice of Logic Programming.5 (1–2):45–74.arXiv:cs/0312045.doi:10.1017/S1471068403001923.S2CID 5051610.as Postscript
  13. ^"Dependency parsing". Archived fromthe original on 2015-04-15. Retrieved2015-04-15.
  14. ^"ASP-Core-2 Input Language Specification"(PDF). Retrieved14 May 2018.
  15. ^Lefèvre, Claire; Béatrix, Christopher; Stéphan, Igor; Garcia, Laurent (May 2017)."ASPeRiX, a first-order forward chaining approach for answer set computing*".Theory and Practice of Logic Programming.17 (3):266–310.arXiv:1503.07717.doi:10.1017/S1471068416000569.ISSN 1471-0684.S2CID 2371655.
  16. ^Marple, Kyle.; Gupta, Gopal. (2012). "Galliwasp: A Goal-Directed Answer Set Solver". In Albert, Elvira (ed.).Logic-Based Program Synthesis and Transformation, 22nd International Symposium, LOPSTR 2012, Leuven, Belgium, September 18-20, 2012, Revised Selected Papers. Springer. pp. 122–136.
  17. ^Arias, J.; Carro, M.; Salazar, E.; Marple, K.; Gupta, G. (2018)."Constraint Answer Set Programming without Grounding".Theory and Practice of Logic Programming.18 (3–4):337–354.arXiv:1804.11162.doi:10.1017/S1471068418000285.S2CID 13754645.
  18. ^ab"DLV System company page". DLVSYSTEM s.r.l. Retrieved16 November 2011.

External links

[edit]
Imperative
Structured
Object-oriented
(comparison,list)
Declarative
Functional
(comparison)
Dataflow
Logic
Domain-
specific
language
(DSL)
Concurrent,
distributed,
parallel
Metaprogramming
Separation
of concerns
Retrieved from "https://en.wikipedia.org/w/index.php?title=Answer_set_programming&oldid=1321769843"
Category:
Hidden categories:
[8]ページ先頭
©2009-2025 Movatter.jp