Analisi ed Implementazione di Algoritmi per il Ragionamento Temporale Qualitativo

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