Answer set programming: Difference between revisions

Revision as of 21:13, 12 August 2020

Revision as of 19:54, 18 December 2020

Line 8:

==History==

The [[Automated planning and scheduling|planning]] method proposed in 1993 by Dimopoulos, Nebel and Köhler<ref>

{{cite book |first1=Y. |last1=Dimopoulos |author2linkauthor2-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}} [ftp://ftp.informatik.uni-freiburg.de/documents/papers/ki/dimopoulos-etal-ecp97.ps.gz as Postscript]</ref>

is an early example of answer set programming. 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 |chapterurlchapter-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>

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>

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>

Line 18:

==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 |accessdateaccess-date=2011-05-27 |archiveurlarchive-url=https://web.archive.org/web/20160304035502/http://opus.bath.ac.uk/20352/1/UnivBath_PhD_2009_T_Crick.pdf |archivedatearchive-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], [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 AnsProlog program consists of rules of the form

Line 34:

</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 |chapterurlchapter-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 }} [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 254:

== Language standardization and ASP Competition ==

The ASP standardization working group produced a standard language specification, called ASP-Core-2,<ref>{{cite web|url=https://www.mat.unical.it/aspcomp2013/files/ASP-CORE-2.03c.pdf|title=ASP-Core-2 Input Language Specification|accessdateaccess-date=14 May 2018}}</ref> 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==

Line 330:

|-

|{{rh}}|[[DLV]]

|[[Linux]], [[macOS]], [[Microsoft Windows|Windows]]<ref name="dlvsystem.com">{{cite web |url=http://www.dlvsystem.com |title=DLV System company page |publisher=DLVSYSTEM s.r.l. |accessdateaccess-date=16 November 2011}}</ref>

|free for academic and non-commercial educational use, and for non-profit organizations<ref name="dlvsystem.com" />

|{{yes}}