Linee di lavoro

L'attivita' di ricerca sara' strutturata nelle seguenti linee di ricerca:

Ragionamento basato su vincoli e preferenze
Considereremo prima preferenze, cioè vincoli che ammettono diversi gradi di soddisfacibilità. e definiremo formalismi per la modellazione compatta di vari tipi di preferenze: bipolari, quantitative, qualitative e condizionali, oltre che alla coesistenza di tali tipi. Ci proponiamo, quindi, di identificare le proprietà generali su cui si basa il ragionamento preferenziale umano e di realizzare metodi risolutivi efficienti. Questo richiederà l'approfondimento di aspetti come l'elicitazione e l'interazione uomo-macchina. In seguito ci focalizzeremo sulla gestione di dati mancanti o imprecisi. Studieremo la rappresentazione di incertezza attraverso degli intervalli di preferenze, anzichè valori precisi, e con distribuzioni di probabilità o possibilità o costi di elicitazione. Considereremo, inoltre, la presenza di variabili incontrollabili, cioè il cui valore è al di fuori dal controllo dell'agente e adatteremo in modo appropriato le nozioni di ottimalità e di robustezza della solurispetto alle diverse forme di incertezza. Svilupperemo, inoltre, un risolutore per problemi con preferenze, capace di gestire i vari tipi di pereferenze nonchè la presenza di incertezza. Potenzieremo, inoltre, tale risolutore con capacità interattive attraverso meccanismi di elicitazione. Due approcci comuni per aumentare l'efficienza dei risolutori di vincoli sono la progettazione di vincoli globali dedicati e gli algoritmi di ricerca ibridi. Intendiamo applicare queste tecniche per risolvere i problemi applicativi di interesse per questo progetto. Tali problemi presentano vincoli complessi e ricorrenti che si possono esprimere come globali. Il nostro primo obiettivo è dunque identificare nuovi vincoli globali, studiarne la complessità computazionale e progettare propagatori efficienti. Questi problemi potrebbero inoltre avere aspetti di ottimizzazione trattabili da algoritmi dedicati di ricerca locale. Il nostro secondo obiettivo è quindi lo studio e la sperimentazione di integrazioni tra algoritmi di ricerca locale e algoritmi di ricerca su alberi. Per quanto riguarda lo sviluppo di un risolutore ibrido, nel primo anno si desidera estendere ed ottimizzae un compilatore recentemente progettato da linguaggi dichiarativi verso programmi GECODE, definire un linguaggio per le metaeuristiche per segliere tipologia e parametri di ricerca combinata, sperimentare su diversi scenari l'efficacia di diverse tipologie e parametri di combinazione migliorando l'efficacia delle tecniche esistenti, implementare in GECODE una classe per la gestione dei reali che sfrutti, sotto certe condizioni, proprietà analitiche per la ricerca di soluzioni. Particolare attenzione sarà fornita alla rappresentazione di numeri a virgola fissa. Nel secondo anno si desidera avere un unico strumento che automaticamente trasforma programmi Prolog o Minizinc in Gecode e effettua la ricerca delle soluzioni con tecniche miste guidate dalle metaeuristiche, e integrare nella libreria di GECODE tale classe per i reali, studiando la combinazione con l'attuale classe per gli insiemi finiti.
Linguaggi di programmazione basati su vincoli
Considerando il framework CLP, sarà necessario estendere le tecniche sviluppate in ricerca operariva, analisi numerica e intelligenza artificiale. Queste tecniche, insieme con quelle basate su vincoli globali e local search, potrebbero essere utili per applicazioni come i sistemi di configurazione, di planning e di protein folding. La prima parte del nostro studio sarà dedita allo studio dello stato dell'arte nei campi sopra descritti. Quindi, la fase successiva sarà l'implementazione di un risolutore vincoli CLP che integri le tecniche usate negli altri campi. Nel primo anno intendiamo anche estendere l'esistente encoding di Action Description Language (ADL) in CLP, con l'introduzione di piu' agenti, con la nozione di durata nelle azioni e con un controllo della concorrenza. Nel secondo anno vogliamo studiare il problema della ricerca di piani ottimi locali e della composizione di questi in un piano completo. Riferendoci al framework di programmazione concorrente con vincoli (cc), nel primo anno pensiamo di studiare le estensioni esistenti del cc che permettono di modellare aspetti temporali, quantitativi e stocastici. Queato studio sarà sviluppato anche per definire una semantica formale per le estensioni temporali e soft del cc. Sulle basi di questo studio, nel secondo anno, svilupperemo un linguaggio concorrent con vincoli che sarà sufficientemente espressivo per esprimere contratti e aspetti di qualità del servizio nel campo delle computazioni orientate ai servizi (SOC) ma anche che permetta la decidibilità di alcune proprietà importanti. Questo dovrebbe permettere di semplificare il lavoro di verifica dei sistemi che implementano i servizi. Inoltre, tale verifica potrebbe essere effettuata anche usando delle tecniche di trasformazione dei programmi. Infatti, nel secondo anno del progetto, intendiamo sviluppare metodologie e tools basati sulla trasformazione dei programmi per la verifica automatica e la sintesi di sistemi software.
Ragionamento temporale:
Nel primo anno si intende innnanzitutto completare la classificazione dei frammenti di HS rispetto alla loro decidibilità/indecidibilità. In parallelo (e probabilmente in entrambi gli anni) si studierà l'effetto dell'estensione e del linguaggio e della semantica dei frammenti decidibili con espressioni metriche e/o di durata. Nel secondo anno sarà affrontato lo sviluppo di algoritmi di decisioni ottimali. Più implementazioni delle procedure di decisione proposte saranno comparate e, in particolare, una basata su tecniche di constraint solving. Si studieranno poi applicazioni bioinformatiche, quali il problema di specificare pattern temporali significativi di processi biologici e quello di caratterizzare proprietà intervallari di interesse, ai sistemi di configurazione, di processo, e nell'ambito del planning si misurerà la loro capacità di gestire in modo effettivo vincoli di integrità e obiettivi temporalmente estesi, comprendenti condizioni di tipo quantitativo. Proseguiremo studiando la classe dei problemi temporali disgiuntivi (DTPs), dove le durate e le distanze temporali possono ammettere intervalli di tempo disgiunti e li estenderemo in modo da permettere la coesistenza dell'incertezza disgiuntiva con variabili non controllabili e con preferenze condizionate dall'occorrenza di eventi. Definiremo poi nozioni appropriate di robustezza temporale e controllabilità e svilupperemo algoritmi per testare e imporre tali proprietà. Considereremo, inoltre, la possibilità di aggiungere preferenze ad altri formalismi per la rappresentazione di incertezza con vincoli temporali, come le Reti Temporali con Alternative. Infine svilupperemo un risolutore per problemi temporali con variabili non controllabili e preferenze che vengono modificate dinamicamente. Il risolutore verrà corredato dalla capacità di testare varie nozioni di controllabilità (forte, debole, e dinamica) e di trovare soluzioni ottime che soddisfino la nozione di controllabilità desiderata.
Preferenze in ambito multi-agente:
Come prima cosa, studieremo metodi efficienti per trovare le soluzioni migliori quando preferenze e vincoli sono espressi da piu' agenti. Consideremo, poi, altre proprietà fondamentali in un abito multi-agente, come la fairness e la non-manipolabilità. In partcolare, studieremo le caratteristiche computazionali di tali scenari. Ci focalizzeremo poi sulla presenza di incertezza sia nei metodi di aggregazione di preferenze sia nelle preferenze dei singoli agenti e approfondiremo le proprietà computazionali di determinare la soluzione migliore con diversi metodi di aggregazione, come ad esempio l'aggregazione sequenziale di competizioni a maggioranza. Studieremo inoltre l'impatto dell'incertezza in termini di manipolabilità delle regole di aggregazione. La presenza di incertezza puo' infatti far aumentare la complessità della manipolazione e quindi aumentarne la fairness. Il passo successivo sarà quello di studiare la teoria dei giochi e la teoria della social choice, due modi differenti di modellare e affrontare i vari aspetti dell'aggregazione di preferenze multi-agente, per integrarne i risultati in contesti AI. Studieremo, inoltre, l'impatto dell'utilizzo di rappresentazioni compatte di preferenze, cioè, vincoli soft e CP-nets, in problemi di matching, come quello del matrimonio stabile. In particolare, dopo aver valutato l'impatto di tale utilizzo in termini di complessità computazionale, privacy e resistenza alla manipolazione, passeremo allo scenario piu' complesso in cui entra in gioco anche l'incertezza e considereremo l'uso di rappresentazioni compatte di preferenze imprecise o incomplete in problemi di matching. Infine, svilupperemo un risolutore completo per problemi di matching con indifferenza e incompletezza dove le preferenze possono essere modellate in modo compatto. Considereremo quindi un approccio basato su ricerca locale per lo stesso problema e confronteremo i due approcci in termi di efficienza e qualità della soluzione. Verranno inoltre sviluppati tools simili per problemi di matching diversi.
Applicazioni:
Nel primo anno si desidera rendere disponibile una versione di COLA che ammetta valori per le variabili in 3D con grado di discretizzazione parametrico. In particolare saranno adattate le attuali procedure di propagazione e inclusi alcuni vincoli globali recentemente studiati. Nel secondo anno si vuol rendere (semi) automatica l'interazione tra COLA ed il protein data bank al fine di recuperare da questo la forma di frammenti della proteina che si desidera studiare e che saranno considerati come blocchi rigidi nel solver. Inoltre saranno sviluppate alcune strategie per il labeling guidate dalle banche dati di angoli torsionali. Inoltre, pensiamo anche di usare le estensioni (temporali/soft/nonmonotone) del linguaggio cc per una rappresentazione quantitativa e una anlisi dei sistemi biologici. La nostra attenzione sarà inizialmente verso la modellazione di reazioni biochimiche con scopo finale di di studiare problemi di farmacocinetica usati in attività di preclinica. Gli aspetti principali della QoS che intendiamo sviluppare sono quelli di trust e fairness. Inoltre vogliamo studiare gli argomenti riguardanti i contratti e la loro osservanza in Service Oriented Computing. A proposito di trust, intendiamo sviluppare il nuovo concetto di multitrust: esso estende la usuale relazione di trust, che riguarda coppie di individui, con una relazione dove un trustor e più trustee interagiscono in modo correlato. Tale correlazione può essere espressa in termini di tempo (ad esempio, fiducia "allo stesso tempo"), di modalità (con lo stesso comportamento) oppure di collaborazione tra i trustee. Alcuni esempi quotidiani possono essere durante il download di un file da sorgenti multiple in reti peer-to-peer, o, in generale, quando un compito può/deve essere conseguito con l'aiuto di molti individui che agiscono insieme: si deve quindi ottenere un valore di trust per l'intero processo. Il nostro obiettivo finale è costruire un framework formale, basato su vincoli soft, dove gestire e combinare requisiti di Qualità del Servizio (QoS). La composizione di un team rappresenta un'altra applicazione generale. Proponiamo Soft Constraint Logic e concurrent constraint programming per rappresentare e valutare la propagazione di trust all'interno di tale scenario. Per conseguire questo, modelliamo una "Web of Trust" adattandola ad un grafo and-or, dove il peso di un connettore corrisponde ad una valutazione di trust tra i nodi del connettore. Per quanto riguarda la fairness, vogliamo studiare l'accettazione di un servizio dal punto di vista etico, o anche l'equità percepita del servizio. Questa è chiaramente una qualità soggettiva del servizio e non può essere misurata dal provider solo considerando un utilizzatore del servizio per volta, ma tutti gli utenti devono essere considerati contemporaneamente. Per esempio, considerando il tempo di attesa per un servizio, per stimare il livello di fairness questo tempo deve essere comparato con quello degli altri clienti: se un utente aspetta un po' di più, ma allo stesso tempo nota che nessun'altro è servito, allora il servizio è ritenuto fair. La funzione utilizzata per misurare la fairness sarà rappresentata da una funzione di benessere sciale (o di utilità individuale) utilizzata in economia. Per gestire la fairness svilupperemo un'estensione di soft concurrent constraint programming. Il nostro obiettivo è considerare la nozione di fairness non qualitativamente (come solitamente fatto in informatica), ma in modo più quantitativo. Infine, considerando il campo della computazione orientata ai servizi, intendiamo studiare applicazioni pratiche del linguaggio per la modellazione di contratti sviluppato nel progetto. Il nostro scopo è di modellare web services in termini di specifiche estensioni del linguaggio cc. In questo modo le operazioni di risoluzione di vincoli potranno essere usate per controllare importanti proprietà comportamentali dei servizi, come, per esempio, se il servizio ha esaudito la richiesta o se la composizione di alcuni servizi sia consistente. Inoltre i vincoli soft ci permetteranno di modellare aspetti quantitativi come il costo, le performance, etc. Crediamo quindi che le estensioni del linguaggio di programmazione concorrente con vincoli (soft) che svilupperemo forniranno un linguaggio utile per provare consistenza, rispetto delle caratteristiche richieste, e altre proprietà quantitative di sistemi reali. In particolare uno dei nostri goal è di analizzare dei servizi esistenti con il modello proposto. Le attività di ricerca su Pianificazione e Sequenziamento saranno organizzate temporalmente in fasi. Nel primo anno si comporranno delle brevi rassegne sui problemi aperti nelle aree di intervento individuate, e si cercheranno anche connessioni con altre ricerche che potrebbero complementare e/o integrare i nuovi risultati perseguiti. Quindi inizierà una fase di sintesi di risultati. L'obiettivo è di avere i nuovi risultati in forma preliminare alla fine del primo anno ed in forma chiusa al mese 18. A quel punto inizierà una fase di test delle nuove funzionalità in dimostratori software opportunamente predisposti. è opportuno fare un'analisi del rischio sui vari obiettivi previsti. Alcuni degli obiettivi sono resi molto robusti dal fatto che intervengono su un percorso di ricerca estremamente consolidato tra i partecipanti al progetto, in particolare parliamo di integrazione di planning e scheduling, della risoluzione di nuovi problemi di scheduling con la metaeuristica Iterative Flattening, del problema di scheduling con risorse soggette ad incertezza ed in larga misura anche del problema della sintesi di spiegazioni orientate agli utenti generici. Altri obiettivi sono fortemente innervati all'interno di questo progetto, parliamo delle ricerche sui legami tra ragionamento a timeline e verifica formale, della estensione del ragionamento con incertezza alla pianificazione con timeline e del collaborazione su temi di ragionamento con preferenze per pianificazione e sequenziamento.