Answer set programming: differenze tra le versioni

Versione delle 11:01, 21 nov 2020

Versione delle 12:35, 17 gen 2021

Riga 1:

L{{'}}'''answer set programming''' ('''ASP''') è una forma di [[programmazione logica]] di tipo [[Programmazione dichiarativa|dichiarativo]] utilizzato per [[Algoritmo di ricerca|problemi di ricerca]] complessi (in primis [[NP-difficile|NP-difficili]]), basata sulla [[semantica del modello stabile]] (o ''answer set'').<ref name="pitoni">{{cita pubblicazione|autore=Valentina Pitoni|titolo=Answer Set Programming|url=http://costantini.di.univaq.it/CorsoAI/Answer%20Set%20Programming.pdf|formato=pdf|editore=[[Università degli Studi dell'Aquila]]|accesso=4 aprile 2016|urlarchivio=https://web.archive.org/web/20161104023636/http://costantini.di.univaq.it/CorsoAI/Answer%20Set%20Programming.pdf|dataarchivio=4 novembre 2016|urlmorto=sì}}</ref> In ASP i problemi di ricerca sono ridotti al calcolo di modelli stabili,; per generare tali modelli vengono utilizzati programmi appositi noti come ''answer set solvers''. Il linguaggio tipico di questo modello di programmazione è l{{'}}''Answer Set Programming in Logic'' ([[#AnsProlog|AnsProlog]]), sottoinsieme del [[Prolog]], ed è impiegato in particolare per risolvere problemi di pianificazione (''planning'') e [[rappresentazione della conoscenza]].<ref name="pitoni"/>

== Storia ==

Il metodo di planning proposto nel 1993 da Dimopoulos, Nebel e Köhler<ref>{{cita libro|lingua=en|nome1=Y. |cognome1=Dimopoulos |wkautore2=Bernhard Nebel |nome2=B. |cognome2=Nebel |nome3=J. |cognome3=Köhler |capitolo=Encoding planning problems in non-monotonic logic programs |pp=273–285 |curatore-nome1=Sam |curatore1=Steel |curatore-nome2=Rachid |curatore2=Alami |titolo=Recent Advances in AI Planning: 4th European Conference on Planning, ECP'97, Toulouse, France, September 24–26, 1997, Proceedings |url=http://books.google.com/books?id=QSBoQgAACAAJ |anno=1997 |editore=Springer |isbn=978-3-540-63912-1 |volume=1348 |trasmissione=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>, basato sulla stretta relazione tra le pianificazioni e i modelli stabili,<ref>{{cita libro|lingua=en|nome1=V.S. |cognome1=Subrahmanian |nome2=C. |cognome2=Zaniolo |capitolo=Relating stable models and AI planning domains |curatore=Leon Sterling |titolo=Logic Programming: Proceedings of the Twelfth International Conference on Logic Programming |url_capitolo=http://books.google.com/books?id=vpGEyZWP1dYC&pg=PA233 |anno=1995 |editore=MIT Press |isbn=978-0-262-69177-2 |pp=233–247}} [http://www.cs.ucla.edu/%7Ezaniolo/papers/iclp95.ps as Postscript]</ref> costituì uno dei primi esempi di ''answer set'' programming. L'utilizzo di ''[[answer set]]'' per risolvere problemi di ricerca fu proposto come nuovo paradigma da Marek e Truszczyński, la cui teoria apparve inizialmente nel 1999 su due differenti pubblicazioni.<ref>{{cita libro|lingua=en|nome1=V. |cognome1=Marek |nome2=M. |cognome2=Truszczyński |capitolo=Stable models and an alternative logic programming paradigm |curatore=Krzysztof R. Apt |titolo=The Logic programming paradigm: a 25-year perspective |url=http://books.google.com/books?id=GIhQAAAAMAAJ |anno=1999 |editore=Springer |isbn=978-3-540-65463-6 |url_capitolo=http://xxx.lanl.gov/pdf/cs/9809032 |formato=PDF |pp=169–181 |cid={{harvid|Apt|1999}}}}</ref><ref>{{cita pubblicazione|lingua=en|nome=I. |cognome=Niemelä |titolo=Logic programs with stable model semantics as a constraint programming paradigm |rivista=Annals of Mathematics and Artificial Intelligence |volume=25 |pp=241–273 |anno=1999 |doi=10.1023/A:1018930122475 |url=http://users.ics.aalto.fi/ini/papers/lp-csp-long.ps.gz}} ([[PostScript]])</ref>

L'espressione "''answer set''" come sinonimo di "''stable model''" fu proposta da Lifschitz.<ref>{{Cita pubblicazione|lingua=en|nome=V. |cognome=Lifschitz |titolo=Action Languages, Answer Sets, and Planning |anno=1999}} In {{harvnb|Apt|1999|pp=357–374}}</ref>

== AnsProlog ==

[http://www.tcs.hut.fi/Software/smodels/lparse.ps Lparse] è il nome del programma che è stato creato in origine per l{{'}}''answer set solver'' [http://www.tcs.hut.fi/Software/smodels/ smodels]. Il linguaggio che Lparse accetta è AnsProlog. Un programma in AnsProlog consiste di regole scritte nella forma:

<syntaxhighlight lang="prolog">

<head> :- <body> .

Riga 34:

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

Le variabili (con iniziale maiuscola, come in Prolog) sono utilizzate per abbreviare collezioni di regole che seguono lo stesso schema, oppure per abbreviare collezioni di atomi all'interno della stessa regola. Ad esempio, il programma:

<syntaxhighlight lang="prolog">

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