Portfolio Approaches in Constraint Programming

Recent research has shown that the performance of a single, arbitrarily efficient algorithm can be significantly outperformed by using a portfolio of —possibly on-average slower— algorithms. Within the Constraint Programming (CP) context, a portfolio solver can be seen as a particular constraint solver that exploits the synergy between the constituent solvers of its portfolio for predicting which is (or which are) the best solver(s) to run for solving a new, unseen instance. In this thesis we examine the benefits of portfolio solvers in CP. Despite portfolio approaches have been extensively studied for Boolean Satisfiability (SAT) problems, in the more general CP field these techniques have been only marginally studied and used. We conducted this work through the investigation, the analysis and the construction of several portfolio approaches for solving both satisfaction and optimization problems. We focused in particular on sequential approaches, i.e., single-threaded portfolio solvers always running on the same core. We started from a first empirical evaluation on portfolio approaches for solving Constraint Satisfaction Problems (CSPs), and then we improved on it by introducing new data, solvers, features, algorithms, and tools. Afterwards, we addressed the more general Constraint Optimization Problems (COPs) by implementing and testing a number of models for dealing with COP portfolio solvers. Finally, we have come full circle by developing sunny-cp: a sequential CP portfolio solver that turned out to be competitive also in the MiniZinc Challenge, the reference competition for CP solvers.

Teoria del consenso e applicazione al problema del coordinamento del moto di robot.

Il sempre crescente numero di applicazioni di reti di sensori, robot cooperanti e formazioni di veicoli, ha fatto sì che le problematiche legate al coordinamento di sistemi multi-agente (MAS) diventassero tra le più studiate nell’ambito della teoria dei controlli. Esistono numerosi approcci per affrontare il problema, spesso profondamente diversi tra loro. La strategia studiata in questa tesi è basata sulla Teoria del Consenso, che ha una natura distribuita e completamente leader-less; inoltre il contenuto informativo scambiato tra gli agenti è ridotto al minimo. I primi 3 capitoli introducono ed analizzano le leggi di interazione (Protocolli di Consenso) che permettono di coordinare un Network di sistemi dinamici. Nel capitolo 4 si pensa all'applicazione della teoria al problema del "loitering" circolare di più robot volanti attorno ad un obiettivo in movimento. Si sviluppa a tale scopo una simulazione in ambiente Matlab/Simulink, che genera le traiettorie di riferimento di raggio e centro impostabili, a partire da qualunque posizione iniziale degli agenti. Tale simulazione è stata utilizzata presso il “Center for Research on Complex Automated Systems” (CASY-DEI Università di Bologna) per implementare il loitering di una rete di quadrirotori "CrazyFlie". I risultati ed il setup di laboratorio sono riportati nel capitolo 5. Sviluppi futuri si concentreranno su algoritmi locali che permettano agli agenti di evitare collisioni durante i transitori: il controllo di collision-avoidance dovrà essere completamente indipendente da quello di consenso, per non snaturare il protocollo di Consenso stesso.

New integer programming models for balanced multi-country kep

Le persone che soffrono di insufficienza renale terminale hanno due possibili trattamenti da affrontare: la dialisi oppure il trapianto di organo. Nel caso volessero seguire la seconda strada, oltre che essere inseriti nella lista d'attesa dei donatori deceduti, possono trovare una persona, come il coniuge, un parente o un amico, disposta a donare il proprio rene. Tuttavia, non sempre il trapianto è fattibile: donatore e ricevente possono, infatti, presentare delle incompatibilità a livello di gruppo sanguigno o di tessuto organico. Come risposta a questo tipo di problema nasce il KEP (Kidney Exchange Program), un programma, ampiamente avviato in diverse realtà europee e mondiali, che si occupa di raggruppare in un unico insieme le coppie donatore/ricevente in questa stessa situazione al fine di operare e massimizzare scambi incrociati di reni fra coppie compatibili. Questa tesi approffondisce tale questione andando a valutare la possibilità di unire in un unico insieme internazionale coppie donatore/ricevente provenienti da più paesi. Lo scopo, naturalmente, è quello di poter ottenere un numero sempre maggiore di trapianti effettuati. Lo studio affronta dal punto di vista matematico problematiche legate a tale collaborazione: i paesi che eventualmente accettassero di partecipare a un simile programma, infatti, devono avere la garanzia non solo di ricavarne un vantaggio, ma anche che tale vantaggio sia equamente distribuito fra tutti i paesi partecipanti.

Stato dell'arte della progettazione automatica di programmi per robot

La comprensione delle proprietà e delle meccaniche di funzionamento dei sistemi complessi e dinamici che ci circondano è uno degli obiettivi principali delle discipline ingegneristiche e scientifiche. Lo sviluppo nel campo dell'Intelligenza Artificiale ha permesso la creazione di entità robotiche sempre più intelligenti, in grado di manifestare comportamenti notevoli e di raggiungere gli obiettivi prefissati: la progettazione di software di controllo ha velocemente ricevuto una crescente responsabilità. Questo elaborato si propone di inquadrare in generale la situazione della progettazione di software di controllo robotici, focalizzandosi in particolare sulle tecniche di progettazione automatica di programmi per robot: dopo aver inquadrato il background su cui si basa la progettazione automatica ed aver mostrato una panoramica dei principali metodi di progettazione diretta, vengono elencate e spiegate le tecniche più utilizzate ed interessanti della progettazione automatica di programmi per robot.

Applicazione del linguaggio ad agenti Jason per la programmazione di alto livello di robot

I sistemi software rivestono nel campo dell'informatica un ruolo di fondamentale importanza. Negli ultimi anni una caratteristica richiesta ai sistemi è la decentralizzazione del controllo, nell'ottica di un sistema visto come connessioni di parti che possono interagire, e dove ciascuna parte possiede un certo grado di autonomia nella scelta delle attività che devono essere compiute. In tale contesto si introduce il paradigma degli agenti, in quanto include sia aspetti relativi ai modelli computazionali, sia aspetti relativi ai linguaggi. Nella tesi si esplora l'applicazione del linguaggio di programmazione Jason applicato alla programmazione dei controllori di robot. In particolare, si esplora ciò che riguarda il comportamento individuale dell'agente.

Extracting FSA descriptions of robot behaviours from the dynamics of automatically designed controller networks

Automatic design has become a common approach to evolve complex networks, such as artificial neural networks (ANNs) and random boolean networks (RBNs), and many evolutionary setups have been discussed to increase the efficiency of this process. However networks evolved in this way have few limitations that should not be overlooked. One of these limitations is the black-box problem that refers to the impossibility to analyze internal behaviour of complex networks in an efficient and meaningful way. The aim of this study is to develop a methodology that make it possible to extract finite-state automata (FSAs) descriptions of robot behaviours from the dynamics of automatically designed complex controller networks. These FSAs unlike complex networks from which they're extracted are both readable and editable thus making the resulting designs much more valuable.

Tesi sperimentale per valutare l'esperienza chirurgica nell'uso del robot Da Vinci Si

Questa tesi si compone di due parti tra loro correlate. Nella prima viene analizzato l’attuale stato dell’arte in ambito di robot chirurgici e, successivamente, sono illustrate le caratteristiche tecniche e funzionali del robot chirurgico Da Vinci Si e ne viene evidenziata la mancanza di sensori in grado di fornire all’utilizzatore un feedback aptico. La seconda parte propone uno studio che ha lo scopo di dimostrare come l’esperienza del chirurgo riesca a sopperire alla mancanza di un sensore in grado di fornire un riscontro della forza impressa sugli strumenti nel campo operatorio. A questo proposito, vengono illustrati i risultati del test appositamente costruito, cui è stato sottoposto un campione di chirurghi di diversi ambiti specialistici, per dimostrare come l’esperienza e la destrezza consentono all’utilizzatore del robot Da Vinci Si di ricevere un’indicazione della forza impressa sui tessuti del campo operatorio tramite un riscontro visivo.

Applying the reactive programming paradigm: Toward a more declarative application development approach

After almost 10 years from “The Free Lunch Is Over” article, where the need to parallelize programs started to be a real and mainstream issue, a lot of stuffs did happened: • Processor manufacturers are reaching the physical limits with most of their approaches to boosting CPU performance, and are instead turning to hyperthreading and multicore architectures; • Applications are increasingly need to support concurrency; • Programming languages and systems are increasingly forced to deal well with concurrency. This thesis is an attempt to propose an overview of a paradigm that aims to properly abstract the problem of propagating data changes: Reactive Programming (RP). This paradigm proposes an asynchronous non-blocking approach to concurrency and computations, abstracting from the low-level concurrency mechanisms.

Un’applicazione di elaborazione del linguaggio naturale per il gioco di "Indovina chi?" su robot umanoide

La tesi è stata incentrata sul gioco «Indovina chi?» per l’identificazione da parte del robot Nao di un personaggio tramite la sua descrizione. In particolare la descrizione avviene tramite domande e risposte L’obiettivo della tesi è la progettazione di un sistema in grado di capire ed elaborare dei dati comunicati usando un sottoinsieme del linguaggio naturale, estrapolarne le informazioni chiave e ottenere un riscontro con informazioni date in precedenza. Si è quindi programmato il robot Nao in modo che sia in grado di giocare una partita di «Indovina chi?» contro un umano comunicando tramite il linguaggio naturale. Sono state implementate regole di estrazione e categorizzazione per la comprensione del testo utilizzando Cogito, una tecnologia brevettata dall'azienda Expert System. In questo modo il robot è in grado di capire le risposte e rispondere alle domande formulate dall'umano mediante il linguaggio naturale. Per il riconoscimento vocale è stata utilizzata l'API di Google e PyAudio per l'utilizzo del microfono. Il programma è stato implementato in Python e i dati dei personaggi sono memorizzati in un database che viene interrogato e modificato dal robot. L'algoritmo del gioco si basa su calcoli probabilistici di vittoria del robot e sulla scelta delle domande da proporre in base alle risposte precedentemente ricevute dall'umano. Le regole semantiche realizzate danno la possibilità al giocatore di formulare frasi utilizzando il linguaggio naturale, inoltre il robot è in grado di distinguere le informazioni che riguardano il personaggio da indovinare senza farsi ingannare. La percentuale di vittoria del robot ottenuta giocando 20 partite è stata del 50%. Il data base è stato sviluppato in modo da poter realizzare un identikit completo di una persona, oltre a quello dei personaggi del gioco. È quindi possibile ampliare il progetto per altri scopi, oltre a quello del gioco, nel campo dell'identificazione.

Aggregate Programming in Scala: a Core Library and Actor-Based Platform for Distributed Computational Fields

La programmazione aggregata è un paradigma che supporta la programmazione di sistemi di dispositivi, adattativi ed eventualmente a larga scala, nel loro insieme -- come aggregati. L'approccio prevalente in questo contesto è basato sul field calculus, un calcolo formale che consente di definire programmi aggregati attraverso la composizione funzionale di campi computazionali, creando i presupposti per la specifica di pattern di auto-organizzazione robusti. La programmazione aggregata è attualmente supportata, in modo più o meno parziale e principalmente per la simulazione, da DSL dedicati (cf., Protelis), ma non esistono framework per linguaggi mainstream finalizzati allo sviluppo di applicazioni. Eppure, un simile supporto sarebbe auspicabile per ridurre tempi e sforzi d'adozione e per semplificare l'accesso al paradigma nella costruzione di sistemi reali, nonché per favorire la ricerca stessa nel campo. Il presente lavoro consiste nello sviluppo, a partire da un prototipo della semantica operazionale del field calculus, di un framework per la programmazione aggregata in Scala. La scelta di Scala come linguaggio host nasce da motivi tecnici e pratici. Scala è un linguaggio moderno, interoperabile con Java, che ben integra i paradigmi ad oggetti e funzionale, ha un sistema di tipi espressivo, e fornisce funzionalità avanzate per lo sviluppo di librerie e DSL. Inoltre, la possibilità di appoggiarsi, su Scala, ad un framework ad attori solido come Akka, costituisce un altro fattore trainante, data la necessità di colmare l'abstraction gap inerente allo sviluppo di un middleware distribuito. Nell'elaborato di tesi si presenta un framework che raggiunge il triplice obiettivo: la costruzione di una libreria Scala che realizza la semantica del field calculus in modo corretto e completo, la realizzazione di una piattaforma distribuita Akka-based su cui sviluppare applicazioni, e l'esposizione di un'API generale e flessibile in grado di supportare diversi scenari.

Installazione del navigation stack su rover terrestre e applicazione del kinect nello human-robot interaction.

Progetto SHERPA. Installazione e configurazione del Navigaton Stack su Rover terrestre. Utilizzo e configurazione di LMS151 Sick. Utilizzo e configurazione di Asus Xtion Pro. Progettazione di software per la localizzazione e l'inseguimento di persone tramite camera di profondita.

Analysis of robot dynamics through complexity measures: an application in automatic design

L'applicazione di misure, derivanti dalla teoria dell'informazione, fornisce un valido strumento per quantificare alcune delle proprietà dei sistemi complessi. Le stesse misure possono essere utilizzate in robotica per favorire l'analisi e la sintesi di sistemi di controllo per robot. In questa tesi si è analizzata la correlazione tra alcune misure di complessità e la capacità dei robot di portare a termine, con successo, tre differenti task. I risultati ottenuti suggeriscono che tali misure di complessità rappresentano uno strumento promettente anche nel campo della robotica, ma che il loro utilizzo può diventare difficoltoso quando applicate a task compositi.

Realizzazione di un controller su piattaforma Android per la movimentazione di manipolatori industriali

Nell'ottica di trovare modalità sempre più intuitive per movimentare manipolatori industriali l’obiettivo della tesi è quello di realizzare una mobile app su piattaforma Android in grado appunto di movimentare un generico manipolatore industriale. L'applicazione sviluppata fornisce all'utente un’interfaccia semplice e intuitiva che permette, dopo un’opportuna configurazione iniziale, di controllare il moto di un manipolatore industriale attraverso l’uso del touch screen e degli elementi grafici dell’interfaccia. Oltre a istruire un manipolatore l’applicazione offre anche delle funzionalità per il salvataggio e la gestione di determinate configurazioni che il manipolatore può assumere nello spazio. Il grande vantaggio dell’applicazione è quello di fornire un’interfaccia universale per la movimentazione di qualsiasi manipolatore. Si può affermare quindi che essa fornisce un livello di astrazione superiore. In questo progetto di tesi è stato effettuato il testing dell'applicazione sviluppata sia con il manipolatore industriale Comau Smart Six, robot antropomorfo a 6 gradi di libertà, sia con un manipolatore simulato in Unity 3D. Sono stati raccolti dei dati, in particolare dei grafici, che mettono in relazione i comandi impartiti al manipolatore e i dati ricevuti da questo, in modo da ricavarne dei parametri che misurano l'efficienza e la correttezza dell'applicazione.

Reactive programming: un caso di studio

L'obiettivo di questa tesi è analizzare e testare la programmazione reattiva, paradigma di programmazione particolarmente adatto per lo sviluppo di applicazioni altamente interattive. La progettazione di sistemi reattivi implica necessariamente l'utilizzo di codice asincrono e la programmazione reattiva (RP) offre al programmatore semplici meccanismi per gestirlo. In questa tesi, la programmazione reattiva è stata utilizzata e valutata mediante la realizzazione di un progetto real-world chiamato AvvocaTimer. Verrà affrontata la progettazione, implementazione e collaudo di una parte del sistema attraverso l'approccio reattivo e, successivamente, confrontata con la prima versione, realizzata con i metodi attualmente usati per gestire codice asincrono, per analizzare vantaggi e/o svantaggi derivanti dall'utilizzo del nuovo paradigma.

Integrazione di piattaforme d'esecuzione e simulazione in una toolchain Scala per aggregate programming

La tesi è calata nell'ambito dell'Aggregate Programming e costituita da una prima parte introduttiva su questo ambito, per poi concentrarsi sulla descrizione degli elaborati prodotti e infine qualche nota conclusiva unitamente a qualche possibile sviluppo futuro. La parte progettuale consiste nell'integrazione del framework Scafi con il simulatore Alchemist e con una piattaforma di creazione e di esecuzione di sistemi in ambito Spatial Computin, con lo scopo di potenziare la toolchain esistente per Aggregate Programming. Inoltre si riporta anche un breve capitolo per l'esecuzione del framework scafi sviluppato in scala sulla piattaforma Android.