Learning for scheduling a portfolio of constraint solvers

Nel lavoro di tesi qui presentato si indaga l'applicazione di tecniche di apprendimento mirate ad una più efficiente esecuzione di un portfolio di risolutore di vincoli (constraint solver). Un constraint solver è un programma che dato in input un problema di vincoli, elabora una soluzione mediante l'utilizzo di svariate tecniche. I problemi di vincoli sono altamente presenti nella vita reale. Esempi come l'organizzazione dei viaggi dei treni oppure la programmazione degli equipaggi di una compagnia aerea, sono tutti problemi di vincoli. Un problema di vincoli è formalizzato da un problema di soddisfacimento di vincoli(CSP). Un CSP è descritto da un insieme di variabili che possono assumere valori appartenenti ad uno specico dominio ed un insieme di vincoli che mettono in relazione variabili e valori assumibili da esse. Una tecnica per ottimizzare la risoluzione di tali problemi è quella suggerita da un approccio a portfolio. Tale tecnica, usata anche in am- biti come quelli economici, prevede la combinazione di più solver i quali assieme possono generare risultati migliori di un approccio a singolo solver. In questo lavoro ci preoccupiamo di creare una nuova tecnica che combina un portfolio di constraint solver con tecniche di machine learning. Il machine learning è un campo di intelligenza articiale che si pone l'obiettivo di immettere nelle macchine una sorta di `intelligenza'. Un esempio applicativo potrebbe essere quello di valutare i casi passati di un problema ed usarli in futuro per fare scelte. Tale processo è riscontrato anche a livello cognitivo umano. Nello specico, vogliamo ragionare in termini di classicazione. Una classicazione corrisponde ad assegnare ad un insieme di caratteristiche in input, un valore discreto in output, come vero o falso se una mail è classicata come spam o meno. La fase di apprendimento sarà svolta utilizzando una parte di CPHydra, un portfolio di constraint solver sviluppato presso la University College of Cork (UCC). Di tale algoritmo a portfolio verranno utilizzate solamente le caratteristiche usate per descrivere determinati aspetti di un CSP rispetto ad un altro; queste caratteristiche vengono altresì dette features. Creeremo quindi una serie di classicatori basati sullo specifico comportamento dei solver. La combinazione di tali classicatori con l'approccio a portfolio sara nalizzata allo scopo di valutare che le feature di CPHydra siano buone e che i classicatori basati su tali feature siano affidabili. Per giusticare il primo risultato, eettueremo un confronto con uno dei migliori portfolio allo stato dell'arte, SATzilla. Una volta stabilita la bontà delle features utilizzate per le classicazioni, andremo a risolvere i problemi simulando uno scheduler. Tali simulazioni testeranno diverse regole costruite con classicatori precedentemente introdotti. Prima agiremo su uno scenario ad un processore e successivamente ci espanderemo ad uno scenario multi processore. In questi esperimenti andremo a vericare che, le prestazioni ottenute tramite l'applicazione delle regole create appositamente sui classicatori, abbiano risultati migliori rispetto ad un'esecuzione limitata all'utilizzo del migliore solver del portfolio. I lavoro di tesi è stato svolto in collaborazione con il centro di ricerca 4C presso University College Cork. Su questo lavoro è stato elaborato e sottomesso un articolo scientico alla International Joint Conference of Articial Intelligence (IJCAI) 2011. Al momento della consegna della tesi non siamo ancora stati informati dell'accettazione di tale articolo. Comunque, le risposte dei revisori hanno indicato che tale metodo presentato risulta interessante.

Agents, nodes & resources: Universal naming system for a coordination middleware

La tesi si propone di sviluppare un modello, l'architettura e la tecnologia per il sistema di denominazione del Middleware Coordinato TuCSoN, compresi gli agenti, i nodi e le risorse. Identità universali che rappresentano queste entità, sia per la mobilità fisica sia per quella virtuale, per un Management System (AMS, NMS, RMS) distribuito; tale modulo si occupa anche di ACC e trasduttori, prevedendo questioni come la tolleranza ai guasti, la persistenza, la coerenza, insieme con il coordinamento disincarnata in rete, come accade con le tecnologie Cloud. All’interno dell’elaborato, per prima cosa si è fatta una introduzione andando a descrivere tutto ciò che è contenuto nell’elaborato in modo da dare una visione iniziale globale del lavoro eseguito. Di seguito (1° capitolo) si è descritta tutta la parte relativa alle conoscenze di base che bisogna avere per la comprensione dell’elaborato; tali conoscenze sono relative a TuCSoN (il middleware coordinato con cui il modulo progettato dovrà interfacciarsi) e Cassandra (sistema server distribuito su cui si appoggia la parte di mantenimento e salvataggio dati del modulo). In seguito (2° capitolo) si è descritto JADE, un middleware da cui si è partiti con lo studio per la progettazione del modello e dell’architettura del modulo. Successivamente (3° capitolo) si è andati a spiegare la struttura e il modello del modulo considerato andando ad esaminare tutti i dettagli relativi alle entità interne e di tutti i legami fra esse. In questa parte si è anche dettagliata tutta la parte relativa alla distribuzione sulla rete del modulo e dei suoi componenti. In seguito (4° capitolo) è stata dettagliata e spiegata tutta la parte relativa al sistema di denominazione del modulo, quindi la sintassi e l’insieme di procedure che l’entità consumatrice esterna deve effettuare per ottenere un “nome universale” e quindi anche tutti i passaggi interni del modulo per fornire l’identificatore all’entità consumatrice. Nel capitolo successivo (5° capitolo) si sono descritti tutti i casi di studio relativi alle interazioni con le entità esterne, alle entità interne in caso in cui il modulo sia o meno distribuito sulla rete, e i casi di studio relativi alle politiche, paradigmi e procedure per la tolleranza ai guasti ed agli errori in modo da dettagliare i metodi di riparazione ad essi. Successivamente (6° capitolo) sono stati descritti i possibili sviluppi futuri relativi a nuove forme di interazione fra le entità che utilizzano questo modulo ed alle possibili migliorie e sviluppi tecnologici di questo modulo. Infine sono state descritte le conclusioni relative al modulo progettato con tutti i dettagli in modo da fornire una visione globale di quanto inserito e descritto nell’elaborato.