Answer set programming: Difference between revisions

Revision as of 14:44, 28 November 2021

Latest revision as of 21:26, 8 May 2024

(16 intermediate revisions by 13 users not shown)

Line 1:

{{Short description|Programming paradigm focused on difficult search problems}}

{{distinguish|Active Server Pages}}

{{Programming paradigms}}

'''Answer set programming''' ('''ASP''') is a form of [[declarative programming]] oriented towards difficult (primarily [[NP-hard]]) [[search algorithm|search problems]]. It is based on the [[stable model semantics|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 and reasoning]]<ref>{{cite book |first=Chitta |last=Baral |title=Knowledge Representation, Reasoning and Declarative Problem Solving |url=https://archive.org/details/knowledgereprese00bara |url-access=registration |year=2003 |publisher=Cambridge University Press |isbn=978-0-521-81802-5}}</ref><ref>{{cite book |first=Michael |last=Gelfond |chapter=Answer sets |editor1-first=Frank |editor1-last=van Harmelen |editor2-first=Vladimir |editor2-last=Lifschitz |editor3-first=Bruce |editor3-last=Porter |title=Handbook of Knowledge Representation |chapter-url=https://books.google.com/books?id=xwBDylHhJhYC&pg=PA285 |year=2008 |publisher=Elsevier |isbn=978-0-08-055702-1 |pages=285–316 }} [http://www.depts.ttu.edu/cs/research/krlab/pdfs/papers/gel07b.pdf as PDF] {{Webarchive|url=https://web.archive.org/web/20160303231241/http://www.depts.ttu.edu/cs/research/krlab/pdfs/papers/gel07b.pdf |date=2016-03-03 }}</ref> and the use of Prolog-style query evaluation for solving problems arising in these applications.

==History==

TheAn early example of answer set programming was the [[Automated planning and scheduling|planning]] method proposed in 19931997 by Dimopoulos, Nebel and Köhler.<ref>

{{cite book |first1=Y. |last1=Dimopoulos |author2-link=Bernhard Nebel |first2=B. |last2=Nebel |first3=J. |last3=Köhler |chapter=Encoding planning problems in non-monotonic logic programs |pages=273–285 |editor1-first=Sam |editor1-last=Steel |editor2-first=Rachid |editor2-last=Alami |title=Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings |url=https://books.google.com/books?id=QSBoQgAACAAJ |year=1997 |publisher=Springer |isbn=978-3-540-63912-1 |volume=1348 |series=Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence}} [https://web.archive.org/web/20170705062155/ftp://ftp.informatik.uni-freiburg.de/documents/papers/ki/dimopoulos-etal-ecp97.ps.gz as Postscript]</ref><ref name="WhatIs">{{cite journal |last1=Lifschitz |first1=Vladimir |title=What is answer set programming? |journal=Proceedings of the 23rd National Conference on Artificial Intelligence |date=13 July 2008 |volume=3 |pages=1594–1597 |url=https://www.cs.utexas.edu/users/vl/papers/wiasp.pdf |publisher=AAAI Press}}</ref> Their approach is based on the relationship between plans and stable models.<ref>

{{cite book |first1=V.S. |last1=Subrahmanian |first2=C. |last2=Zaniolo |chapter=Relating stable models and AI planning domains |editor-first=Leon |editor-last=Sterling |title=Logic Programming: Proceedings of the Twelfth International Conference on Logic Programming |chapter-url=https://books.google.com/books?id=vpGEyZWP1dYC&pg=PA233 |year=1995 |publisher=MIT Press |isbn=978-0-262-69177-2 |pages=233–247}} [http://www.cs.ucla.edu/%7Ezaniolo/papers/iclp95.ps as Postscript]</ref>

is an early example of answer set programming. Their approach is based on the relationship between plans and stable models.<ref>

In 1998 Soininen and Niemelä<ref>{{cite bookcitation |first1=V.ST. |last1=SubrahmanianSoininen |first2=CI. |last2=ZanioloNiemelä |chaptertitle=RelatingFormalizing stableconfiguration modelsknowledge andusing AIrules planningwith domainschoices |editor-firstnumber=Leon |editorTKO-last=SterlingB142 |titleinstitution=Logic Programming: ProceedingsLaboratory of theInformation TwelfthProcessing InternationalScience, ConferenceHelsinki onUniversity Logicof Programming |chapter-url=https://books.google.com/books?id=vpGEyZWP1dYC&pg=PA233Technology |year=19951998 |publisherurl=MIT Press |isbn=978-0-262-69177-2 |pages=233–247}} [http://www.cstcs.uclahut.edufi/%7Ezaniolo~ini/papers/iclp95sn-faanmr98.ps.gz as |format=Postscript]}}</ref>

applied what is now known as answer set programming to the problem of [[product configuration]].<ref name="WhatIs"/> 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.<ref name="WhatIs"/> The first of these papers identified the use of answer set solvers for search as a new [[programming paradigm]].<ref>

Soininen and Niemelä<ref>{{citation |first1=T. |last1=Soininen |first2=I. |last2=Niemelä |title=Formalizing configuration knowledge using rules with choices |number=TKO-B142 |institution=Laboratory of Information Processing Science, Helsinki University of Technology |year=1998 |url=http://www.tcs.hut.fi/~ini/papers/sn-faanmr98.ps.gz |format=Postscript}}</ref>

{{cite book |first1=V. |last1=Marek |first2=M. |last2=Truszczyński |chapter=Stable models and an alternative logic programming paradigm |editor-first=Krzysztof R. |editor-last=Apt |title=The Logic programming paradigm: a 25-year perspective |url=https://books.google.com/books?id=GIhQAAAAMAAJ |year=1999 |publisher=Springer |isbn=978-3-540-65463-6 |format=PDF |pages=169–181 |ref={{harvid|Apt|1999}}|arxiv=cs/9809032 }}</ref>

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 by [[Victor W. Marek|Marek]] and Truszczyński in a paper that appeared in a 25-year perspective on the logic programming paradigm published in 1999 <ref>

|editor-link=Krzysztof R. Apt

{{cite book |first1=V. |last1=Marek |first2=M. |last2=Truszczyński |chapter=Stable models and an alternative logic programming paradigm |editor-first=Krzysztof R. |editor-last=Apt |title=The Logic programming paradigm: a 25-year perspective |url=https://books.google.com/books?id=GIhQAAAAMAAJ |year=1999 |publisher=Springer |isbn=978-3-540-65463-6 |format=PDF |pages=169–181 |ref={{harvid|Apt|1999}}|arxiv=cs/9809032 }}</ref>

and|title=The inLogic [Niemeläprogramming paradigm: a 25-year perspective |url=https://books.google.com/books?id=GIhQAAAAMAAJ |date=20 May 1999] |publisher=Springer |isbn=978-3-540-65463-6 |format=PDF |pages=169–181 |ref={{harvid|Apt|1999}}|arxiv=cs/9809032 }}</ref> That same year Niemelä also proposed "logic programs with stable model semantics" as a new paradigm.<ref>{{cite journal |first=I. |last=Niemelä |title=Logic programs with stable model semantics as a constraint programming paradigm |journal=Annals of Mathematics and Artificial Intelligence |volume=25 |issue=3/4 |pages=241–273 |yeardate=November 1999 |doi=10.1023/A:1018930122475 |s2cid=14465318 |url=http://users.ics.aalto.fi/ini/papers/lp-csp-long.ps.gz |format=Postscript,gzipped}}</ref>

Indeed, the new terminology of "answer set" instead of "stable model" was first proposed by Lifschitz<ref>{{cite journal |first=V. |last=Lifschitz |title=Action Languages, Answer Sets, and Planning |year=1999}} In {{harvnb|Apt|1999|pp=357–374}}</ref> in a paper appearing in the same retrospective volume as the Marek-Truszczynski paper.

==Answer set programming language AnsProlog==

[http://www.tcs.hut.fi/Software/smodels/lparse.ps Lparse] is the name of the program that was originally created as a [[Symbol grounding|grounding]] tool (front-end) for the answer set solver [http://www.tcs.hut.fi/Software/smodels/ smodels]. The language that Lparse accepts is now commonly called AnsProlog,<ref>{{Cite thesis |type=Ph.D. |title=Superoptimisation: Provably Optimal Code Generation using Answer Set Programming |url=http://opus.bath.ac.uk/20352/1/UnivBath_PhD_2009_T_Crick.pdf |last=Crick |first=Tom |year=2009 |publisher=University of Bath |docket=20352 |access-date=2011-05-27 |archive-url=https://web.archive.org/web/20160304035502/http://opus.bath.ac.uk/20352/1/UnivBath_PhD_2009_T_Crick.pdf |archive-date=2016-03-04 |url-status=dead }}</ref> short for ''Answer Set Programming in Logic''.<ref>{{cite web |author=Rogelio Davila |title=AnsProlog, an overview |url=http://www.rogeliodavila.com.mx/Programacion%20Logica/PL%20Notas/AnsProlog%20Overview.ppt |format=PowerPoint}}</ref> It is now used in the same way in many other answer set solvers, including [https://web.archive.org/web/20110717180541/http://assat.cs.ust.hk/ assat], [httphttps://wwwpotassco.cs.uni-potsdam.deorg/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 AnsProlog program consists of rules of the form

Line 34 ⟶ 33:

</syntaxhighlight>

says: choose arbitrarily which of the atoms <math>p,q,r</math> 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 <math>\{p,q,r\}</math>. The definition of a stable model was generalized to programs with choice rules.<ref>{{cite book |first1=I. |last1=Niemelä |first2=P. |last2=Simons |first3=T. |last3=Soinenen |chapter=Stable model semantics of weight constraint rules |editor1-first=Michael |editor1-last=Gelfond |editor2-first=Nicole |editor2-last=Leone |editor3-first=Gerald |editor3-last=Pfeifer |title=Logic Programming and Nonmonotonic Reasoning: 5th International Conference, LPNMR '99, El Paso, Texas, USA, December 2–4, 1999 Proceedings |chapter-url=https://books.google.com/books?id=Abj-OpFeDjQC&pg=PA317 |year=2000 |publisher=Springer |isbn=978-3-540-66749-0 |pages=317–331 |series=Lecture Notes in Computer Science: Lecture Notes in Artificial Intelligence |volume=1730}} [http://www.tcs.hut.fi/~ini/papers/nss-lpnmr99-www.ps.gz as Postscript]</ref> Choice rules can be treated also as abbreviations for [[Stable model semantics#Stable models of a set of propositional formulas|propositional formulas under the stable model semantics]].<ref>{{cite journal |first1=P. |last1=Ferraris |first2=V. |last2=Lifschitz |title=Weight constraints as nested expressions |journal=Theory and Practice of Logic Programming |volume=5 |issue=1–2 |pages=45–74 |date=January 2005 |doi=10.1017/S1471068403001923 |arxiv=cs/0312045 |s2cid=5051610 }} [http://www.cs.utexas.edu/users/vl/papers/weight.ps as Postscript]</ref> For instance, the choice rule above can be viewed as shorthand for the conjunction of three "[[excluded middle]]" formulas:

:<math>(p\lor\neg p)\land(q\lor\neg q)\land(r\lor\neg r).</math>

Line 85 ⟶ 84:

<syntaxhighlight lang="prolog">

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

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

</syntaxhighlight>

Line 92 ⟶ 91:

(start..end)

</syntaxhighlight>

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 compatible way. For example, the fact

<syntaxhighlight lang="prolog">

Line 113 ⟶ 111:

</syntaxhighlight>

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

<syntaxhighlight lang="prolog">

Line 184 ⟶ 182:

and run smodels on it, with the numeric value of <math>n</math> specified on the command line, then the atoms of the form <math>\mathrm{color}(\dots,\dots)</math> in the output of smodels will represent an <math>n</math>-coloring of <math>G</math>.

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—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 (graph theory)|clique]] in a graph is a set of pairwise adjacent vertices. The following Lparse program finds a clique of size <math>\geq n</math> in a given directed graph, or determines that it does not exist:

<syntaxhighlight lang="prolog" line="1">

n {in(X) : v(X)}.

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

</syntaxhighlight>

Line 257 ⟶ 255:

==Comparison of implementations==

Early systems, such as Smodelssmodels, used [[backtracking]] to find solutions. As the theory and practice of [[Boolean SAT solver]]s 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 fullfully converting into a Boolean-logic form. These approaches allow for significant improvements of performance, often by an order of magnitude, over earlier backtracking algorithms.

The [https://potassco.org/ 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[[Message Passing Interface]] 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.<ref>{{Cite journal|lastlast1=Lefèvre|firstfirst1=Claire|last2=Béatrix|first2=Christopher|last3=Stéphan|first3=Igor|last4=Garcia|first4=Laurent|date=May 2017-05|title=ASPeRiX, a first-order forward chaining approach for answer set computing*|url=https://www.cambridge.org/core/journals/theory-and-practice-of-logic-programming/article/abs/asperix-a-firstorder-forward-chaining-approach-for-answer-set-computing/2318F5D6647DF24A8F9A452F4C7B4D49|journal=Theory and Practice of Logic Programming|language=en|volume=17|issue=3|pages=266–310|doi=10.1017/S1471068416000569|arxiv=1503.07717 |s2cid=2371655 |issn=1471-0684}}</ref>

Query-driven implementations of answer set programming, such as the Galliwasp system,<ref>

{{cite book |first1=Kyle. |last1=Marple |first2=Gopal. |last2=Gupta |chapter=Galliwasp: A Goal-Directed Answer Set Solver |editor-first=Elvira|editor-last=Albert |title=Logic-Based Program Synthesis and Transformation, 22nd International Symposium, LOPSTR 2012, Leuven, Belgium, September 18-20, 2012, Revised Selected Papers |year=2012 |publisher=Springer |pages=122-136122–136}}</ref> and s(CASP)<ref>{{cite journal |first1=J. |last1=Arias |first2=M. |last2=Carro |first3=E. |last3=Salazar |first4=K. |last4=Marple |first5=G. |last5=Gupta |title=Constraint Answer Set Programming without Grounding |journal=Theory and Practice of Logic Programming |volume=18 |issue=3–4 |pages=337–354 |date=2018|doi=10.1017/S1471068418000285 |s2cid=13754645 |doi-access=free |arxiv=1804.11162 }}</ref> avoid grounding altogether by using a combination of [[resolution (logic)|resolution]] and [[coinduction]].

s(ASP)<ref>{{cite journal |first1=K.|last1=Marple |first2=E. |last2=Salazar |first3=G. |last3=Gupta |title=Computing Stable Models of Normal Logic Programs Without Grounding |journal=CoRR|volume=abs/1709.00501 |date=2017}} [http://arxiv.org/abs/1709.00501]</ref> and s(CASP)<ref>{{cite journal |first1=J. |last1=Arias |first2=M. |last2=Carro |first3=E. |last3=Salazar |first4=K. |last4=Marple |first5=G. |last5=Gupta |title=Constraint Answer Set Programming without Grounding |journal=Theory and Practice of Logic Programming |volume=18 |issue=3-4 |pages=337-354 |date=2018}} </ref> avoid grounding altogether by using a combination of [[resolution (logic)|resolution]] and [[coinduction]].

{| class="wikitable"

Line 283 ⟶ 280:

!

|-

|{{rh}}|[http://www.info.univ-angers.fr/pub/claire/asperix/ ASPeRiX] {{Webarchive|url=https://web.archive.org/web/20161108121331/http://www.info.univ-angers.fr/pub/claire/asperix/ |date=2016-11-08 }}

|[[Linux]]

|[[GPL]]

Line 324 ⟶ 321:

|-

|{{rh}}|[https://github.com/MatthiasNickles/diff-SAT/ diff-SAT]

|[[Linux]], [[macOS]], [[Microsoft Windows|Windows]] ([[Java Virtualvirtual Machinemachine]])

|[[MIT License]]

|{{okay|Requires grounding}}

Line 403 ⟶ 400:

|

|-

|{{rh}}|[http://www.nku.edu/~wardj1/Research/smodels_cc.html Smodels-cc] {{Webarchive|url=https://web.archive.org/web/20151115171208/http://www.nku.edu/~wardj1/Research/smodels_cc.html |date=2015-11-15 }}

|[[Linux]]

|?

Line 443 ⟶ 440:

*[http://www.kr.tuwien.ac.at/staff/tkren/deb.html A variety of answer set solvers packaged for Debian / Ubuntu]

*[http://www.cs.uni-potsdam.de/clasp/ Clasp Answer Set Solver]

{{Programming paradigms navbox}}

{{DEFAULTSORT:Answer Set Programming}}