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.

A study on set variable representations in constraint programming

Il lavoro presentato in questa tesi si colloca nel contesto della programmazione con vincoli, un paradigma per modellare e risolvere problemi di ricerca combinatoria che richiedono di trovare soluzioni in presenza di vincoli. Una vasta parte di questi problemi trova naturale formulazione attraverso il linguaggio delle variabili insiemistiche. Dal momento che il dominio di tali variabili può essere esponenziale nel numero di elementi, una rappresentazione esplicita è spesso non praticabile. Recenti studi si sono quindi focalizzati nel trovare modi efficienti per rappresentare tali variabili. Pertanto si è soliti rappresentare questi domini mediante l'uso di approssimazioni definite tramite intervalli (d'ora in poi rappresentazioni), specificati da un limite inferiore e un limite superiore secondo un'appropriata relazione d'ordine. La recente evoluzione della ricerca sulla programmazione con vincoli sugli insiemi ha chiaramente indicato che la combinazione di diverse rappresentazioni permette di raggiungere prestazioni di ordini di grandezza superiori rispetto alle tradizionali tecniche di codifica. Numerose proposte sono state fatte volgendosi in questa direzione. Questi lavori si differenziano su come è mantenuta la coerenza tra le diverse rappresentazioni e su come i vincoli vengono propagati al fine di ridurre lo spazio di ricerca. Sfortunatamente non esiste alcun strumento formale per paragonare queste combinazioni. Il principale obiettivo di questo lavoro è quello di fornire tale strumento, nel quale definiamo precisamente la nozione di combinazione di rappresentazioni facendo emergere gli aspetti comuni che hanno caratterizzato i lavori precedenti. In particolare identifichiamo due tipi possibili di combinazioni, una forte ed una debole, definendo le nozioni di coerenza agli estremi sui vincoli e sincronizzazione tra rappresentazioni. Il nostro studio propone alcune interessanti intuizioni sulle combinazioni esistenti, evidenziandone i limiti e svelando alcune sorprese. Inoltre forniamo un'analisi di complessità della sincronizzazione tra minlex, una rappresentazione in grado di propagare in maniera ottimale vincoli lessicografici, e le principali rappresentazioni esistenti.

Longitudinal dynamics modeling and handling qualities of a conventional jet aircraft

Un noto centro di ricerca europea ha recentemente modificato un jet convenzionale di classe CS-25 in una piattaforma scientifica. Durante il processo di certificazione delle modifiche, l’impatto delle stesse sulle prestazioni è stato studiato in modo esaustivo. Per lo studio delle qualità di volo, i piloti collaudatori hanno sviluppato una procedura di certificazione ad hoc che consiste in test qualitativi separati della stabilità longitudinale, laterale e direzionale. L’obiettivo della tesi è analizzare i dati di volo, registrati durante i test di collaudo, con l'obiettivo di estrarre informazioni di carattere quantitativo circa la stabilità longitudinale del velivolo modificato. In primo luogo sono state analizzate tre diverse modifiche apportate all’aeromobile e successivamente i risultati sono stati messi a confronto per capirne l’influenza sulle qualità di volo dell’aeromobile. Le derivate aerodinamiche sono state stimate utilizzando la cosiddetta “identificazione dei parametri”, che mira a replicare le variabili registrate durante i test di volo, variando un dato insieme di coefficienti all’interno del modello linearizzato della dinamica dell’aeromobile. L'identificazione del modo di corto periodo ha consentito l'estrazione dei suoi parametri caratteristici, quali il rapporto di smorzamento e la frequenza naturale. La procedura ha consentito inoltre di calcolare il cosiddetto “Control Anticipation Parameter” (CAP), parametro caratterizzante delle qualità di volo di un aeroplano. I risultati ottenuti sono stati messi a confronto con i requisiti prescritti dalla normativa MIL-STD-1797-A, risultando conformi al livello più alto di qualità di volo.

Riorganizzazione della manutenzione in ottica TPM: il caso Toyota Material Handling Manufacturing Italy

Il presente lavoro di tesi nasce dall'attività di stage svolto presso la Toyota Material Handling Manufacturing Italy S.p.A. di Bologna, azienda specializzata nella produzione di carrelli elevatori. Lo scopo prefissato di questo elaborato è quello di fornire una visione globale della Total Productive Maintenance, andando successivamente ad illustrare gli strumenti e le metodologie impiegate in un contesto reale e quindi i risultati ottenibili nel medio-lungo termine. La prima parte dell’elaborato va ad illustrare lo scenario moderno nel quale le imprese sono chiamate a confrontarsi e a competere per raggiungere i propri obiettivi. Nella seconda parte viene trattato il tema della “manutenzione dei sistemi produttivi” con particolare attenzione agli approcci risolutivi e alle politiche intraprese nel corso degli ultimi anni per poi analizzare il principale strumento di gestione della manutenzione utilizzato in scala mondiale, ovvero la Total Production Maintenance. L’ultima parte, dopo un capitolo riservato alla presentazione dell’azienda, si concentra sulle attività svolte presso l’azienda, sugli strumenti e tecniche utilizzate, per poi analizzare i risultati ottenuti ed ottenibili grazie al percorso intrapreso.

Sviluppo e validazione di un algoritmo di Vehicle Routing per un caso di logistica distributiva in collaborazione con Toyota Material Handling Italia

L’elaborato descrive le fasi di progettazione, programmazione e validazione di un programma sviluppato in ambiente Java per il Vehicle Routing Problem. L’algoritmo implementato è di tipo euristico costruttivo primal e presenta funzionalità specifiche per la gestione di un elevato numero di vincoli e l’applicazione a casistiche reali. La validazione è stata effettuata su una base dati reale e in confronto a dataset di cui è nota la soluzione ottima. Il programma è stato progettato per risultare flessibile alle richieste dell’utente e utilizzabile per valutazioni economiche in ambito consulenziale.

Il ruolo del controllo posturale per il movimento selettivo degli arti superiori attraverso la facilitazione con trunk constraint nel paziente neurologico: case report

Background Recentemente la letteratura scientifica ha dimostrato come un corretto controllo posturale faciliti i movimenti dell’arto superiore. Ci sono evidenze secondo cui, applicando al paziente dei contenimenti sul tronco, si ha un miglioramento della funzionalità dell’arto superiore. Obiettivi L’obiettivo principale della tesi era quello di verificare come il sostegno del tronco con l’utilizzo di una stabile struttura assiale, attraverso un supporto esterno definito “trunk constraint”, incrementi il controllo posturale, per facilitare i movimenti frazionati degli arti superiori in persone con esiti di patologie neurologiche. Materiali e metodi Il caso clinico riguarda un uomo di 60 anni con esiti di emiparesi sinistra da ictus ischemico destro. E’ stato eseguito un protocollo di dieci sessioni di trattamento, di un’ora ciascuna, in cui veniva applicata la facilitazione attraverso trunk constraint in diversi setting riabilitativi. I dati sono stati raccolti tramite le scale: Trunk Control Test, Trunk Impairment Scale e Fugl-Meyer Assessment. Inoltre, è stata eseguita l’analisi osservazionale, attraverso videoripresa, di un gesto funzionale dell’arto superiore. Risultati I dati rilevati dimostrano degli effetti positivi rispetto alle ipotesi di partenza. Infatti sono stati riscontrati miglioramenti negli item delle scale somministrate e nella valutazione qualitativa dell’arto superiore. In particolare, si è evidenziato un miglioramento nel controllo del tronco nella scala Trunk Control Test e nella Trunk Impairment Scale e della funzione dell’arto superiore alla scala Fugl-Meyer Assessment. L’analisi osservazionale dei video dimostra un miglioramento del timing di attivazione durante la fase di reaching. Conclusioni I risultati ottenuti supportano il fatto che un incremento dell’attività antigravitaria del tronco, anche attraverso supporti esterni come la trunk constraint, possono facilitare un miglioramento funzionale dell’arto superiore.

Machine Learning in Automatic Tabulation for Constraint Model Reformulation

Combinatorial decision and optimization problems belong to numerous applications, such as logistics and scheduling, and can be solved with various approaches. Boolean Satisfiability and Constraint Programming solvers are some of the most used ones and their performance is significantly influenced by the model chosen to represent a given problem. This has led to the study of model reformulation methods, one of which is tabulation, that consists in rewriting the expression of a constraint in terms of a table constraint. To apply it, one should identify which constraints can help and which can hinder the solving process. So far this has been performed by hand, for example in MiniZinc, or automatically with manually designed heuristics, in Savile Row. Though, it has been shown that the performances of these heuristics differ across problems and solvers, in some cases helping and in others hindering the solving procedure. However, recent works in the field of combinatorial optimization have shown that Machine Learning (ML) can be increasingly useful in the model reformulation steps. This thesis aims to design a ML approach to identify the instances for which Savile Row’s heuristics should be activated. Additionally, it is possible that the heuristics miss some good tabulation opportunities, so we perform an exploratory analysis for the creation of a ML classifier able to predict whether or not a constraint should be tabulated. The results reached towards the first goal show that a random forest classifier leads to an increase in the performances of 4 different solvers. The experimental results in the second task show that a ML approach could improve the performance of a solver for some problem classes.

Calcolo strutturale tramite simulazione agli elementi finiti ed analisi delle criticità di macchinari della linea di prodotto Handling

Questa tesi si propone di analizzare due macchinari della linea di “Handling” della divisione Active di IMA S.p.A., ovvero la macchina “Cyclops” e la macchina “Hercules”. Per entrambe le macchine si vuole svolgere un’analisi completa dei rischi strutturali: si vogliono individuare, infatti, i componenti strutturalmente critici al fine di proporre migliorie e soluzioni per evitare problematiche o danneggiamenti alle macchine. Per l’individuazione delle criticità strutturali, la prima cosa effettuata è stata un’analisi del funzionamento dei macchinari, attraverso uno studio dei singoli componenti e dei loro montaggi, a cui è seguita un’analisi dei carichi e delle sollecitazioni agenti su entrambe le macchine in condizioni di lavoro standard. A valle di queste analisi è stato possibile, quindi, individuare i componenti maggiormente sollecitati e, con l’ausilio di un software di nome Creo Simulate, ovvero un’estensione del software PTC Creo, molto diffuso nell’ambito della progettazione 3D di componenti industriali, sono state eseguite delle simulazioni virtuali di calcolo agli elementi finiti. Dall’analisi dei risultati delle simulazioni eseguite al calcolatore si sono evidenziate le eventuali criticità di ogni componente proponendo modifiche di progettazione, sia in termini di modifica della geometria del componente, sia riguardo a possibili modifiche nella scelta dei materiali. In aggiunta alle simulazioni virtuali, per completezza d’analisi, sono state svolte anche analisi strutturali di tipo analitico per la verifica di collegamenti bullonati e collegamenti saldati e per la verifica a fatica di alberi in rotazione.

Introduzione di un piano di campionamento indicizzato secondo l'AQL per i materiali in ingresso nel settore del material handling e dell'intralogistica. Il caso System Logistics S.p.A.

L’elaborato si è sviluppato all'interno dell’azienda System Logistics S.p.A. di Fiorano Modenese, leader nel settore del material handling e dell’intralogistica. Il focus dell'elaborato è sulla progettazione di un piano di campionamento indicizzato secondo il livello di qualità accettabile. Successivamente ad una presentazione più approfondita dell’azienda e dei prodotti offerti, si passa all’introduzione teorica dei temi dell’intralogistica e della qualità. Questo permette di comprendere il contesto operativo più generale in cui si inserisce il progetto. Infatti, la parte centrale è dedicata alla presentazione delle origini, degli obiettivi e della metodologia del progetto, in particolare, anticipando le procedure che si sono poste come basi strutturali della progettazione. La parte finale descrive il processo statistico che ha portato all’ottenimento del nuovo piano di campionamento e la sua applicazione empirica ai componenti più critici della navetta del LogiMate, il più recente prodotto dell’azienda. In quest’ultima fase si pone il focus sul processo di raccolta e analisi dei dati presentando, in particolare, un’analisi comparativa rispetto alla situazione iniziale dal punto di vista del rischio e un’analisi effettuata con le Carte di Controllo sul processo produttivo di un fornitore. L’esposizione è realizzata anche mediante grafici, ottenuti principalmente attraverso il supporto di Excel e Minitab, al fine illustrare in modo più agevole ed esplicito i risultati ottenuti.