Answer set programming: differenze tra le versioni

Versione delle 04:50, 3 ott 2017

Versione attuale delle 23:47, 15 mar 2025

(13 versioni intermedie di 7 utenti non mostrate)

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|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]]), sottinsiemesottoinsieme 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–285273-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_capitolourlcapitolo=http://books.google.com/books?id=vpGEyZWP1dYC&pg=PA233 |anno=1995 |editore=MIT Press |isbn=978-0-262-69177-2 |pp=233–247233-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_capitolourlcapitolo=http://xxx.lanl.gov/pdf/cs/9809032 |formato=PDF |pp=169–181169-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–273241-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:

<sourcesyntaxhighlight lang="prolog">

<head> :- <body> .

</syntaxhighlight>

</source>

Il simbolo <code>:-</code> ("if") è omesso se <code><body></code> è vuoto; tali regole, come in [[Prolog]], vengono chiamati ''fatti''.

Un altro tipo di costrutto è la ''scelta''. Ad esempio, la regola:

<sourcesyntaxhighlight lang="prolog">

{p,q,r}.

</syntaxhighlight>

</source>

afferma: scegli arbitrariamente quali fra gli [[Atomo (logica)|atomi]] <math>p,q,r</math> includere nel modello stabile. Un programma contenente solo questa regola ha 8 modelli stabili, sottinsiemi di <math>\{p,q,r\}</math>. Il significato di questa regola nella semantica del modello stabile è rappresentato dalla formula [[Logica proposizionale|proposizionale]]:

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

È possibile, inoltre, imporre dei vincoli alle regole di scelta, come:

<sourcesyntaxhighlight lang="prolog">

1{p,q,r}2.

</syntaxhighlight>

</source>

Tale regola afferma: scegli almeno uno degli atomi <math>p,q,r</math>, ma non più di due. Il significato in logica proposizionale è dato dalla seguente formula:

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

I vincoli di cardinalità possono essere usati anche nel corpo della regola, ad esempio:

<sourcesyntaxhighlight lang="prolog">

:- 2{p,q,r}.

</syntaxhighlight>

</source>

Questo vincolo impone al programma di eliminare i modelli stabili contenenti almeno due atomi appartenenti all'insieme <math>\{p,q,r\}</math>. Il significato in logica proposizionale è dato dalla seguente formula:

:<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:

<sourcesyntaxhighlight lang="prolog">

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

q(X) :- p(X), X!=a.

</syntaxhighlight>

</source>

ha lo stesso significato di:

<sourcesyntaxhighlight lang="prolog">

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

q(b). q(c).

</syntaxhighlight>

</source>

Il programma:

<sourcesyntaxhighlight lang="prolog">

p(a). p(b). p(c). p(d). p(e).

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

</syntaxhighlight>

</source>

è un'abbreviazione di:

<sourcesyntaxhighlight lang="prolog">

p(a). p(b). p(c). p(d). p(e).

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

</syntaxhighlight>

</source>

Un ''intervallo'' è espresso nella forma:

<sourcesyntaxhighlight lang="prolog">

<Predicate>(start..end)

</syntaxhighlight>

</source>

dove <code>start</code> e <code>end</code> sono espressioni aritmetiche dal valore costante. Un intervallo è un'abbreviazione notazionale per definire domini numerici. Ad esempio, il fatto:

<sourcesyntaxhighlight lang="prolog">

a(1..3).

</syntaxhighlight>

</source>

è un'abbreviazione di:

<sourcesyntaxhighlight lang="prolog">

a(1). a(2). a(3).

</syntaxhighlight>

</source>

== Generazione di modelli stabili ==

Utilizzando il software Lparse<ref>{{cita web|url=http://www.tcs.hut.fi/Software/smodels/lparse.ps|titolo=Lparse|editore=[[Università Aalto|Aalto-yliopisto]] - Laboratory of Theoretical Computer Science|urlarchivio=https://web.archive.org/web/20160320044603/http://www.tcs.hut.fi/Software/smodels/lparse.ps|dataarchivio=20 marzo 2016|urlmorto=no|accesso=4 aprile 2016}} ([[PostScript]])</ref> per generare un modello stabile del programma memorizzato nel file dal titolo <code><filename></code> si utilizza il comando:

<sourcesyntaxhighlight lang="bash">

% lparse <filename> | smodels

</syntaxhighlight>

</source>

L'opzione <code>0</code> indica alla funzione <code>smodels</code> di trovare tutti i modelli stabili del programma.<br />Ad esempio, dato il seguente programma contenuto nel file "test":

<sourcesyntaxhighlight lang="prolog">

1{p,q,r}2.

s :- not p.

</syntaxhighlight>

</source>

utilizzando il comando

<sourcesyntaxhighlight lang="bash">

% lparse test | smodels 0

</syntaxhighlight>

</source>

verrà prodotto l'output

<sourcesyntaxhighlight lang="text">

Answer: 1

Stable Model: q p

Riga 98:

Answer: 6

Stable Model: r q s

</syntaxhighlight>

</source>

== Applicazioni ==

Come già detto, lL'answer set programming, oltre ad avere riscontro nella rappresentazione della conoscenza, può essere anche utilizzato per risolvere problemi [[Teoria della complessità computazionale|computazionalmente]] difficili, come il problema della [[colorazione dei grafi]], del [[cammino hamiltoniano]] o di [[soddisfacibilità booleana]].<ref>{{cita web|url=https://www.cs.sfu.ca/CourseCentral/411/jim/ASP2.Modelling.pdf|titolo=Modelling Problems in ASP|editore=Simon Fraser University|formato=PDF|sito=cs.sfu.ca|lingua=en|urlarchivio=https://web.archive.org/web/20160404175606/https://www.cs.sfu.ca/CourseCentral/411/jim/ASP2.Modelling.pdf|dataarchivio=4 aprile 2016|urlmorto=no|accesso=4 aprile 2016}}</ref>

=== Colorabilità ===

Riga 107:

Per fare ciò, basta un breve programma in AnsProlog:

<sourcesyntaxhighlight lang="prolog">

c(1..n).

1 {color(X,I) : c(I)} 1 :- v(X).

:- color(X,I), color(Y,I), e(X,Y), c(I).

</syntaxhighlight>

</source>

Nella riga 1 vengono definiti <math>n</math> colori differenti. La regola presente in riga 2 si occupa di colorare i vertici, ovvero assegna un colore <math>i</math> ad ogni vertice <math>x</math>. Il vincolo nella riga 3 proibisce di assegnare lo stesso colore a due vertici <math>x</math> e <math>y</math> se sono connessi da un arco del grafo.

Definendo un grafo <math>G</math> nella maniera seguente:

<sourcesyntaxhighlight lang="prolog">

v(1..100). % 1,...,100 sono vertici

e(1,55). % esiste un arco che connette 1 e 55

. . .

</syntaxhighlight>

</source>

ed eseguendo il comando smodels, con il valore numerico di <math>n</math> specificato a linea di comando, allora, se esiste una soluzione, verranno stampati in output degli atomi dalla forma <code>color(. , .)</code>, i quali indicano le assegnazioni colore-vertice da eseguire per ottenere la colorazione di cardinalità indicata.

Riga 126:

In Prolog il problema può essere modellato come segue:

<sourcesyntaxhighlight lang="prolog">

dentro(X,Y) | fuori(X,Y) :- arco(X,Y). % ogni arco può essere dentro o fuori ildal percorso.

:-dentro(X,Y), dentro (X,Y1), Y<>Y1. % partendo da un vertice non si può giungere a due vertici distinti.

:-dentro(X,Y), dentro (X1,Y), X<>X1. % partendo da due vertici distinti non si può giungere allo stesso vertice.

Riga 134:

raggiunto(X) :- partenza(X). % il punto di partenza è raggiunto per definizione.

raggiunto(X) :- raggiunto(Y), dentro(Y,X). % partendo da un vertice Y e arrivando ad un vertice X, quest'ultimo è raggiunto.

</syntaxhighlight>

</source>

== Note ==