Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Analisi ed Implementazione di Algoritmi per il Ragionamento Temporale Qualitativo

Gestire in modo incrementale l'informazione temporale è un'attività importante in molte aree dell'intelligenza articiale. In questo lavoro di tesi abbiamo indirizzato il ragionamento temporale incrementale nel contesto ben conosciuto della Point Algebra e della subalgebra di ORD-Horn, sottoinsieme dell'Interval Algebra, analizzando ed estendendo una collezione di recenti algoritmi e strutture dati per risolvere i problemi fondamentali del ragionamento temporale.
Gli algoritmi studiati migliorano la complessità computazionale, che si avrebbe utilizzando le tecniche statiche, di un fattore di O(n) o di O(n2), dove n è il numero delle variabili temporali. I risultati sperimentali di questa tesi confermano il vantaggio teorico dei metodi incrementali. Abbiamo inoltre analizzato sperimentalmente nuovi algoritmi per il ragionamento statico nell'ambito della subalgebra di ORD-Horn che, sotto certe condizioni, sono risultati più efficienti delle tecniche precedentemente poposte.

Mostra/Nascondi contenuto.
Introduzione I problemi della rappresentazione della conoscenza temporale [5, 41, 51, 53, 63] e del ragionamento temporale, ad essa strettamente collegato, nascono in molte discipline come l’informatica, la filosofia, la psicologia e la linguistica. In infor- matica sono aspetti centrali dei sistemi informativi, dell’intelligenza artificiale e di altre aree che trattano la modellizzazione dei processi [1]. I sistemi infor- mativi, per esempio, si occupano della gestione di dati, in particolare del loro aggiornamento. Un primo approccio a questo problema consiste nel cancellare tutti i dati obsoleti. Questo, però, permette di accedere solamente alle infor- mazioni più recenti. Per soddisfare domande del tipo “Quali impiegati hanno lavorato per noi l’anno scorso con uno stipendio lordo di 15.000 e?” abbiamo la necessità di rappresentare l’informazione temporale. In alcune applicazioni, come la gestione dei referti medici, il corso temporale degli eventi è un aspetto critico dei dati. In molti settori dell’informatica applicata, come la pianifica- zione [2, 31, 32, 54, 59, 66, 67] e lo scheduling [50], la conoscenza temporale si concretizza nella collezione di relazioni qualitative tra istanti o intervalli di tempo. In intelligenza artificiale i modelli utilizzati per la soluzione di problemi richiedono modelli sofisticati del mondo che possano catturare il cambiamento. Per esempio, nella pianificazione delle attività di un robot si devono modellizza- re gli effetti delle azioni del robot stesso sul mondo per assicurarsi che il piano sia efficace. Nel processo del linguaggio naturale [3, 41, 52] i ricercatori sono interessati ad estrarre il tempo verbale della frase e qualsiasi altra informazione concernente il tempo. Tale conoscenza è necessaria per rispondere alle domande inerenti il futuro o il passato. Gli approcci più promettenti nella rappresentazione di vincoli temporali qua- litativi e nella loro elaborazione sono l’Algebra degli Intervalli (IA acronimo del termine inglese Interval Algebra) [1, 29, 45, 62] di Allen e l’Algebra dei Punti (PA acronimo del termine inglese Point Algebra) [35, 56, 64] di Vilain e Kautz. Dato un insieme di vincoli temporali (o CSP acronimo del termine inglese Con- straint Satisfaction Problem) i problemi fondamentali da risolvere sono deci- derne la soddisfacibilità, trovarne una soluzione e ricavarne la rappresentazione 1

Tesi di Laurea

Facoltà: Ingegneria

Autore: Stefano Paoli Contatta »

Composta da 174 pagine.

 

Questa tesi ha raggiunto 629 click dal 16/05/2006.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.