Torna alla Home Page del corso    Torna alla pagina degli Elaborati   
 

Introduzione

DLV è un sistema di deduzione basato su database e incorpora front-end per alcuni dei più diffusi formalismi nel campo della rappresentazioni della conoscenza (KR).
DLV utilizza un linguaggio logico disgiuntivo che supporta implicazioni, vincoli, query, e true negation.
Dunque DLV sulla base di un insieme di regole (implicazioni e vincoli) e fatti del dominio permette di dedurre ulteriori fatti.
DLV è stato progettato come un sistema general-purpose, infatti può essere utilizzato in molti settori dell'IA, tra i quali il Planning.
Questo elaborato si propone quindi di utilizzare DLV come uno strumento per la pianificazione, cercando inoltre di interfacciare DLV con un software prodotto dal Prof. Gerevini dell'Università degli Studi di Brescia: DISCOPLAN

Utilizzo di DLV

Il software è stato realizzato, ed è tuttora mantenuto, da un team comprendente professori, ricercatori e studenti dell'Università degli Studi di Calabria e del Vienna University of Technology
È disponibile in forma binaria per varie piattaforme (tra le quali Win32, Linux, Solaris).
DLV si basa su un database di regole e fatti di un dominio per fare deduzioni. Il database deve essere scritto in un linguaggio dichiarativo (Datalog): questo implica che l'utente non deve scrivere un programma per risolvere il suo problemi ma deve solo specificare come deve essere la soluzione del problema (i.e. formalizzare il dominio). Il resto lo fa DLV: cerca la catena di regole da usare per trovare una soluzione.
Dunque per usare DLV è necessario specificare due insiemi di input:

Intensional Database: le regole

Estensional Database: i fatti del dominio.

Un elementare database per DLV

laugh :- joke.
joke.

La prima è un'implicazione: significa "joke implica laugh" (dunque e la parte intensionale del database)
La seconda asserisce un fatto: "joke è vero"

Il risultato dell'esecuzione di DLV è il seguente modello:
{joke, laugh}

Infatti DLV applica l'implicazione tenendo conto dello stato di verità del fatto joke

Il linguaggio Datalog per DLV

DLV accetta un database di input che deve essere espresse con un linguaggio logico apposito: il Datalog. Questo linguaggio mette a disposizione dell'utente i seguenti costrutti:

Operatori logici

Congiunzione (and): si esprime con una virgola ( , ) che separa due atomi
Disgiunzione (or): si esprime con una v minuscola ( v ) che separa due atomi
Negazione (not): si esprime in due modi differenti:
not davanti all'atomo da negare per una negazione debole
- davanti all'atomo da negare per una negazione forte


Termini, suddivisi in:

Costanti (i.e.: a1, 2, aBc, c_) : numeri, stringhe che iniziano con una lettera minuscola
Variabili (i.e.: A, Vx, T2) : iniziano necessariamente con una lettera maiuscola


Atomi (i.e.: a(X,1), figlio(X,paolo), padre(X,_)) : sono predicati come quelli della logica del primo ordine. Sono generalmente accompagnati da una lista di termini (variabili e/o costanti) fra parentesi tonde

Fatti : sono combinazioni di uno o più atomi uniti da operatori logici (and , or, not), che sta su una riga del file di database terminata da un punto.

Implicazioni : (i.e.: laugh :- joke.) in cui l'head sta a destra del simbolo di implicazione (":-") mentre il body è a sinistra (head e body sono espressioni come i fatti). Un'implicazione è terminata da un punto.

Vincoli : (i.e.: :- laugh, cry. ) nelle esempio si impone che vengano esclusi tutti i modelli che ottengono una congiunzione tra i due fatti laugh e cry.

Costrutti matematici in DLV

DLV supporta quattro costrutti standard

somma : (+,X,Y,Z) restitutisce true se Z=X+Y, alternativamente si può scrivere Z=X+Y
prodotto : (*,X,Y,Z) restitutisce true se Z=X*Y, alternativamente si può scrivere Z=X*Y
#int : #int(X) restitutisce true se X è un intero.
#succ : #succ(X,Y) restitutisce true se Y è successore di X (cioè Y=X+1).

Costrutti comparativi DLV

Essendo importanti per effettuare comparazione fra variabili, sono stati implementati gli operatori comparativi indispensabili. Eccone una lista:

<
>
<=
>=
==
!=

Predicati irrivelanti in DLV

È indicato con un underscore _. Si usano in tutti qu casi in cui un predicato è ininfluente ai fini della regola in cui compare, ad esempio:
persona(X) :- genitore(X,_).
persona(X) :- genitore(_,X).
sta ad indicare che X è una persona se ha un genitore oppure ha un figlio.
In genere non è indispensabile usare un predicato irrilevante: in parecchi casi può essere efficacemente sostituito da una una variabile libera.

Negazione forte e negazione debole

Di default, DLV considera falso un fatto il cui stato di verità non ` ancora stato specificato (dall'utente o da un'implicazione applicabile). La differenza tra le due negazioni sta prorpio nel trattare la negazione di un predicato non ancora specificato:

con la negazione debole, il negato di un predicato non specificato è VERO
con la negazione forte, il negato di un predicato non specificato è FALSO. In pratica,per funzionare, richiede che il predicato abbia acquisito un valore di verità

Un esempio di uso di DLV: il problema delle 8 regine

Ecco un esempio di un database che formalizza il problema di posizionare 8 regine su una scacchiera 8 x 8 in modo che non si attacchino a vicenda:

% una riga che comincia con il simbolo percentuale è un commento

% questa implicazione permette a DLV di posizionare una regina per ogni istante di
% tempo, nella riga corrispondente all'istante di tempo crescente,
%in una qualunque colonna
q(X,1) v q(X,2) v q(X,3) v q(X,4) v q(X,5) v q(X,6) v q(X,7) v q(X,8) :- #int(X), X>0.

% vincolo: è permessa una sola regina per colonna
:- q(X1,Y), q(X2,Y), X1 <> X2.

% vincolo: non ci devono essere atttacchi sulle diagonali "principali"
:- q(X1,Y1), q(X2,Y2), X2 = X1+N, Y2 = Y1+N, N > 0.

% vincolo: non ci devono essere atttacchi sulle diagonali "secondarie"
:- q(X1,Y1), q(X2,Y2), X2 = X1+N, Y1 = Y2+N, N > 0.

Detto queen.dl il file di testo qui sopra, è necessario invocare DLV nel seguente modo:

$ dlv -n=1 -N=8 queen.dl

Il parametro "-N=8" indica che DLV deve sostituire nell'implicazione numeri da 1 a 8

Il parametro "-n=1" serve per far cercare una sola soluzione.

Ulteriori informazioni su DLV

Il sito ufficiale: http://www.dbai.tuwien.ac.at/proj/dlv/
Il manuale ufficiale: Manuale di DLV
Un tutorial con molti esempi: Tutorial

DLV e pianificazione

In questo elaborato è stato principalmente affrontato il problema del planning mediante DLV.
Inoltre sono state analizzate la possibilità e l'utilità di un interfacciamento tra DLV e DISCOPLAN
Sono stati affrontati i seguenti problemi:

Dominio dei blocchi (BlockDomain)-Sussman Anomaly con tre blocchi
Dominio dei blocchi (BlockDomain)-Sussman Anomaly con undici blocchi
Mondo della scimmia

Interfacciamento tra DLV e DISCOPLAN

DISCOPLAN è un software che, data la formalizzazione di un dominio determinato come output di UCPOP, genera in modo automatico vincoli di tipo implicativo, esclusivo, statico, single-valuedness, antisimmetrico, XOR, OR ed altri.
L'obiettivo posto è di verificare l'utilità di questi vincoli in una formalizzazione per DLV.
Purtroppo, l'uso di DISCOPLAN come preprocessor per DLV non ha una grande utilità. Infatti una parte dei vincoli generati da DISCOPLAN sono necessari per formalizzare il dominio nel linguaggio Datalog usato da DLV, l'altra parte dei vincoli di DISCOPLAN risulta essere completamente inutile: nel peggiore dei casi non influenza il comportamento di DLV ma rallenta la ricerca di un modello. Nel migliore dei casi, non rallenta DLV, ma comunque non aggiunge alcun vantaggio.

La poca utilità di un interfacciamento tra DISCOPLAN e DLV è dovuto al fatto che DLV è stato progetttato come sistema general-purpose. Per questo, la formalizzazione del dominio in DLV risulta molto differente da quella dei pianificatori ad hoc, per cui non risente di miglioramenti.

Sicuramente si può affermare che DISCOPLAN è uno strumento di sicura validità nella stesura della formalizzazione di un dominio per DLV: come già detto alcuni dei vincoli generati da DISCOPLAN sono di vitale importanza per DLV, e dunque possono fungere da linee guida da cui partire nella formalizzazione del dominio stesso.

Sezione DOWNLOAD