RICERCA ITALIANA     

Programma di ricerca

Vincoli e preferenze come formalismo unificante per l'analisi di sistemi informatici e la soluzione di problemi reali

Università di riferimento

Università degli Studi di PADOVA - MATEMATICA PURA ED APPLICATA - PADOVA(PD)

Responsabile dell'Unità di ricerca

Francesca ROSSI

Descrizione

L'attivita' di ricerca dell'unita' di Padova si sviluppa su tre filoni diversi ma altamente correlati tra loro:

1. preferenze e incertezza

2. vincoli e scheduling

3. ottimizzazione multi-obbiettivo.

Il primo filone si occupa dei formalismi per modellare problemi con preferenze e/o incertezza e delle tecniche per risolvere tali problemi, con lo scopo principale di estendere il potere espressivo sia per le preferenze che per l'incertezza, e di poter gestire anche situazioni dove sia le preferenze che l'incertezza originano da piu' agenti, studiando le proprieta' di funzioni di aggregazione di preferenze.

Il secondo filone considera i problemi di scheduling, che sono l'area applicativa di maggior successo per la programmazione con vincoli. Il primo scopo e' quello di considerare preferenze sulle attivita' di un problema di scheduling, il secondo quello di ottenere degli schedule robusti alle modifiche. In entrambi i casi si tratta di gestire preferenze o incertezza all'interno di problemi di scheduling, quindi questo filone e' strettamente collegato al primo perche' si prevede un uso dei formalismi e delle tecniche sviluppate nel primo filone, adattati ai problemi di scheduling.

Nel terzo filone, lo scopo e' di capire come risolvere problemi in cui ci sono diversi criteri di ottimizzazione, possibilmente in contrasto tra loro. Questo e' molto correlato alla situazione in cui vari agenti esprimono le loro preferenze, e anche alla situazione in cui vari vincoli con preferenze devono essere soddisfatti, entrambe affrontate nel primo filone. Qui pero' si vuole studiare soprattutto lo sviluppo di algoritmi ibridi che usano tecniche di Intelligenza Artificiale e Ricerca Operativa per produrre la frontiera Pareto ottima. Tali tecniche saranno anche considerate nella prima attivita' per gestire scenari multi-agente.

In tutte le tre linee di ricerca, prima studieremo lo stato dell'arte, poi svilupperemo nuovi formalismi e tecniche, in seguito studieremo le loro proprieta', e infine valideremo alcune linee di lavoro anche sperimentalmente sia su problemi generati casualmente che su piccoli problemi reali.

Di seguito descriviamo in dettaglio il programma di lavoro in ognuno dei tre filoni.

1. Preferenze e incertezza:

Le preferenze che si trovano in situazioni reali possono essere di vario tipo: qualitative (come in "Preferisco l'estate all'inverno"), quantitative (come in "Do' voto 8 all'estate e voto 5 all'inverno"), o anche condizionate (come in "Se vivessi in montagna, preferirei l'inverno all'estate"). Inoltre, le preferenze possono essere positive (come in "Preferisco il sole alla pioggia") o anche negative (come in "Non vorrei fare tardi"). Nei problemi reali esistono anche cose non solo preferite, ma obbligatorie, che si esprimono naturalmente tramite vincoli, come in "E' necessario che sia a casa prima delle 8pm".

Esistono vari formalismi che sono in grado di descrivere e gestire questi tipi diversi di preferenze e di vincoli. Ad esempio, i vincoli descrivono le cose necessarie, i vincoli soft le preferenze quantitative, le CP-net le preferenze qualitative e condizionate.
Inoltre, i formalismi sono anche stati paragonati dal punto di vista del loro potere espressivo, ed e' stato visto come approssimare una CP-net con dei vincoli soft. Infine, e' stato studiata la coesistenza di preferenze a la CP-net e di vincoli. Ma non esiste nessun formalismo che riesca a gestire tutte queste tipologie di conoscenza allo stesso tempo. Noi vogliamo capire come utilizzare i formalismi esistenti per svilupparne uno che riesca a fare cio'.

Questi vari formalismi hanno anche complessita' computazionali molto diverse. In particolare, per le CP-net e' difficile (NP-hard)
controllare se una soluzione e' migliore dell'altra, mentre questo e' un problema semplice per i vincoli soft. Vogliamo studiare e sfruttare queste differenze per sviluppare algoritmi efficienti per trovare soluzioni ottime e fare test di dominanza.

Per quanto riguarda le preferenze bipolari, cioe' positive e negative, esistono alcuni modi per modellarle, ma noi intendiamo renderli piu' generali e studiare casi in cui il problema di trovare soluzioni ottime secondo entrambi i tipi di preferenze diventa trattabile. Vogliamo anche evitare di dare priorita' ad un tipo di preferenze rispetto all'altro.

Quando le preferenze si uniscono all'incertezza, e' necessario trovare soluzioni che siano ottime per le preferenze ma anche robuste rispetto alle parti incerte del problema. Anche se preferenze ed incertezza in alcuni casi possono essere gestite in modo omogeneo tramite la teoria delle possibilita', e' opportuno, ai fini di un ordinamento adeguato tra le soluzioni, che tali informazioni vengano tenute separate. Questo permette di riconoscere, per una soluzione, sia il suo livello di preferenza che il suo grado di compatibilita' con l'incertezza del problema, che puo' essere visto come la robustezza della soluzione. Opportuni modi di valutare queste due informazioni possono dare piu' peso all'uno o all'altro aspetto di una soluzione.

E' molto comune che piu' agenti vogliano esprimere le loro preferenze su alcuni oggetti condivisi. In questi casi, e' necessario aggregare le loro preferenze per trovare le soluzioni che possano soddisfare tutti al meglio. Varie funzioni di aggregazione possono essere definite, con proprieta' molto diverse tra loro, sia in termini di complessita' computazionale che in termini di expressivita' e adeguatezza. Ad esempio, properieta' interessanti di aggregazioni di preferenze, che sono gia' state studiate in contesti sociali, sono la fairness e la non-manipolabilita'. Vogliamo studiare queste ad altre proprieta' e capire anche i loro risvolti sulla complessita' della funzione di aggregazione. In altri termini, ci interessa capire quanto dobbiamo pagare in termini di complessita' per poter avere una funzione di aggregazione di preferenze che abbia una di queste proprieta' desiderate. E' anche interessante capire se i classici teoremi di impossibilita' che riguardano queste proprieta' nel campo sociale si trovino anche nelle situazioni da noi considerate.

2. Vincoli e scheduling:

Una soluzione ad un problema di scheduling deve essere eseguita così come prevista per mantenere le qualità della soluzione.
Questo è però reso impossibile dalla necessità di eseguire la soluzione in ambienti dinamici dove eventi imprevisti possono velocemente invalidare la soluzione iniziale. Quindi la vita di uno schedule tende ad essere molto corta, così come le qualità ad essa associata. Per ovviare a questo problema si rende necessario studiare soluzioni cosiddette robuste che sono capaci di assorbire, se non tutti, almeno parte dei possibile eventi che si possono verificare durante l'esecuzione.

Tre aspetti si possono distingure nel concetto di robustezza: (1) la capacita' di assorbire eventi imprevisti, (2) la capacita' di produrre rapidamente una nuova soluzione quando necessario, (3) la capacita' di preservare la qualita' delle soluzioni. I primi due aspetti possono essere soddisfatti adottando soluzioni temporalmente flessibili, mentre il terzo puo' essere raggiunto utilizzando metodi specifici per la generazione di soluzioni flessibile di buona qualita'. Su questa base, si vuole analizzare il concetto di flessibilta' sulle risorse in modo da estendere la struttura a vincoli che sottosta alle soluzioni temporalmente flessibili. In aggiunta, si vuole sviluppare un apparato sperimentale per validare la combinazione tra soluzioni flessibili e i metodi di riparazione.

Negli esempi presenti in letteratura i problemi di scheduling considerano vari aspetti globali della soluzione quali il makespan (il tempo di completamento di tutte le attivita'). Un aspetto interessante da considerare sono problemi di scheduling con differenti livelli
di preferenza per ogni attività. Questo tipo di problemi ha grande riscontro nel mondo reale. Ad esempio nella gestione di un satellite di comunicazione, servire una particolare richiesta può essere più redditizia di altre o dovuta in seguito a diversi valori di priorità.

Considerare attivita' con diverse preferenze in problemi di scheduling richiede di introdurre nuovi metodi risolutivi. In particolare, nostro principale obiettivo e' analizzare la complessita' dell'integrazione di tecniche attuali basate su attivita' con diverse preferenze in architetture di scheduling. Ad esempio, un modo per la risoluzione di problemi di scheduling si basa su metodi iterativi in cui soluzioni parziali vengono passo passo raffinate rimuovendo i vari conflitti individuati. L'analisi delle preferenze puo' essere integrata a questo livello con gli attuali metodi (ad esempio, profilo di risorse). Un approccio alternativo invece si basa sull'utilizzo della flessibilta' temporale delle soluzioni. Infatti, e' possibile sfruttare l'insieme di allocazioni per ogni attivita' che soluzioni flessibili assicurano, per considerare, in una fase separata, il soddisfacimento delle preferenze

3. Ottimizzazione multi-obbiettivo:

In questo progetto, si desiderano studiare ed integrare tecniche di Intelligenza Artificiale e di Ricerca Operativa per l'ottimizzazione multi-obiettivo. Lo scopo è quello di sviluppare algoritmi ibridi in grado di generare efficientemente la frontiera Pareto ottima.

Preferenze ed ottimizzazione multi-obiettivo possono essere viste come due aspetti di uno stesso concetto: ad assegnamenti (eventualmente, parziali), vengono associati livelli di soddisfazione o valori di una funzione obiettivo. Mentre nell'ottimizzazione multi-obiettivo il valore di ogni funzione e` tipicamente un numero reale, nelle preferenze puo` essere un valore preso da qualunque insieme ordinato (eventualmente, con ordinamento parziale). Storicamente, le preferenze son state studiate di piu` nell'Intelligenza Artificiale, mentre l'ottimizzazione multi-obiettivo e` tradizionalmente approfondita in Ricerca Operativa.

Spesso gli approcci più efficienti per risolvere problemi di ottimizzazione combinatoria sono approcci ibridi, che nascono dalla integrazione di algoritmi sviluppati nella Ricerca Operativa con quelli tipici dell'Intelligenza Artificiale. Tipicamente, gli algoritmi sviluppati in Programmazione a Vincoli sono particolarmente orientati alla soddisfacibilità del problema, cioè a trovare una soluzione che soddisfa tutti i vincoli. Gli algoritmi sviluppati in Ricerca Operativa sono particolarmente efficienti nell'ottimizzazione: utilizzano all'interno della ricerca branch-and-bound rilassamenti del problema, decomposizioni, cutting planes. I due tipi di approcci sono complementari da questo punto di vista ed algoritmi ibridi che cercano di sfruttare gli aspetti migliori di entrambi i campi sono risultati particolarmente efficienti e sono riusciti ad ottenere soluzioni che nessuna delle due tecniche, prese separatamente, era riuscita a produrre in tempi ragionevoli.

Altri approcci utilizzati in Ricerca Operativa utilizzano algoritmi di ricerca locale, che hanno dimostrato di essere molto veloci nell'ottimizzazione, anche se sono tipicamente incompleti. Anche per questi algoritmi sono state studiate integrazioni con la programmazione a vincoli. Particolarmente interessante, ai fini del progetto, è il metodo chiamato large neighbourhood search, che esplora in maniera esaustiva l'intorno della configurazione corrente utilizzando la programmazione a vincoli. Usando la programmazione a vincoli per esplorare l'intorno è possibile utilizzare intorni di dimensione più grande ed esplorarli all'ottimo, il che permette di arrivare a soluzioni migliori prima di essere bloccati in minimi (o massimi) locali.

La ricerca proposta è divisa in quattro fasi.

In una prima fase, si studieranno gli algoritmi di ottimizzazione multi-obiettivo proposti in letteratura nelle diverse aree dell'intelligenza artificiale e della ricerca operativa. Si porrà particolare attenzione ai problemi di ottimizzazione combinatoria, così come sono sviluppati nelle due aree. Si studieranno in particolare gli algoritmi proposti nella programmazione a vincoli, nella programmazione lineare intera, nella ricerca locale e nei metodi basati su popolazione (in particolare, algoritmi genetici).

Nella seconda fase, si studieranno le tecniche sviluppate fino a questo momento per integrare algoritmi di ricerca operativa (in particolare, ricerca locale e programmazione lineare intera) con programmazione a vincoli al fine di ottenere soluzioni in tempi più brevi o di ottenere soluzioni migliori a parità di tempo di calcolo. In particolare, le tecniche che appaiono più promettenti sono le tecniche di decomposizione di problemi in sottoproblemi (ad esempio, decomposizione di Benders) e ricerca locale con esplorazione di uno spazio ampio delle configurazioni vicine (large neighborhood search).

Nella terza fase, si studierà l'applicabilità delle tecniche di integrazione fra ricerca locale e programmazione lineare intera con programmazione a vincoli studiate nella seconda fase, all'ottimizzazione multi-obiettivo. In particolare, verranno integrati algoritmi di ottimizzazione multi-obiettivo di programmazione a vincoli con algoritmi di ottimizzazione mono e multi-obiettivo delle altre aree. Lo scopo di questa terza fase è quello di ottenere algoritmi in grado di generare l'intera frontiera Pareto-ottima o una sua caratterizzazione accettabile in tempi brevi. Tale caratterizzazione potrebbe essere un sottoinsieme significativo dei punti che costituiscono la frontiera, oppure insiemi di punti che, benché non appartenenti alla frontiera, ne siano sufficientemente vicini.

All'interno di tutte queste fasi, si terrà in particolare considerazione la rappresentazione dei dati in memoria. Specificamente, la frontiera Pareto ottima potrebbe contenere un numero molto elevato di soluzioni. Si dovranno utilizzare strutture dati appropriate che permettano di accedere velocemente ai dati in memoria, utilizzando indicizzazioni hash o con alberi di ricerca.

La quarta fase consiste nella validazione degli algoritmi sviluppati, che verrà fatta attraverso sperimentazione, sia utilizzando i benchmark standard disponibili, sia utilizzando problemi reali, in particolare di scheduling e/o di pianificazione di orario.