Constraint Optimisation Techniques for Real-World Applications

L'ottimizzazione a vincoli rappresenta una tecnica fondamentale che e stata applicata con successo nell'ambito dei Sistemi Multi-Agente (MAS), con lo scopo di risolvere numerosi problemi di coordinamento tra gli agenti.In questa tesi affrontiamo il problema della Formazione di Coalizioni (CF), uno degli approcci chiave per affrontare problemi di coordinamento nei MAS. In particolare, CF ha l'obiettivo di formare gruppi che massimizzano una funzione obiettivo (e.g., formare macchine condivise da piu agenti in modo da minimizzare i costi di trasporto).Ci concentriamo su un caso particolare di CF denominato CF su Grafi (GCCF), dove una rete tra gli agenti vincola la formazione delle coalizioni. Questo problema si riscontra in molte applicazioni realistiche, ad esempio nel caso di reti di comunicazione o di relazioni sociali. Nello specifico, i contributi principali della tesi sono i seguenti. Proponiamo un nuovo modo di formalizzare il problema GCCF, e un algoritmo efficiente (denominato CFSS) per risolverlo. CFSS e stato testato in contesti realistici quali il collective energy purchasing e il social ridesharing, utilizzando dati reali (i.e., profili di consumo energetico domestico del Regno Unito, GeoLife per le coordinate di spostamento nell'ambito del ridesharing, e Twitter come rete sociale). CFSS e il primo algoritmo in grado di risolvere GCCF su larga scala fornendo buone garanzie di qualita.In aggiunta, affrontiamo il problema di dividere il valore associato ad ogni coalizione tra i suoi membri, in modo da garantire che siano ricompensati adeguatamente per il contributo apportato al gruppo. Questo aspetto di CF, chiamato calcolo dei pagamenti, e cruciale in ambiti caratterizzati da agenti con un comportamento razionale, quali il collective energy purchasing e il social ridesharing. Questo problema e risolto tramite il nostro algoritmo denominato PRF, il primo metodo in grado di risolvere questo problema su larga scala. In aggiunta, i pagamenti calcolati soddisfano la proprieta derivante dalla teoria dei giochi chiamata stabilita, che garantisce che tali pagamenti siano considerati imparziali dagli agenti.Infine, proponiamo un metodo alternativo per la soluzione del problema GCCF, sfruttando la relazione tra GCCF e i problemi di ottimizzazione a vincoli (COP). In particolare, consideriamo Bucket Elimination (BE), uno dei framework piu importanti per la risoluzione dei COP, e proponiamo CUBE, un implementazione parallela di BE su GPU. CUBE adotta uno schema della gestione della memoria innovativo, che porta notevoli benefici dal punto di vista delle performance e permette a CUBE di non essere limitato dal quantitativo di memoria della GPU, cosi da poter risolvere problemi di carattere reale. CUBE e stato testato su SPOT5, un dataset realistico che contiene problemi di coordinamento tra satelliti modellati tramite COP. Inoltre, CUBE e stato usato per risolvere COP-GCCF, la nostra formalizzazione tramite COP del problema GCCF. COP-GCCF e il primo modello che comprende un numero lineare di vincoli rispetto al numero di agenti, caratteristica fondamentale per garantire la scalabilita della nostra tecnica risolutiva. I nostri esperimenti, che utilizzano Twitter come dataset reale, dimostrano che COP-GCCF apporta numerosi vantaggi rispetto allo stato dell'arte, sia in termini di memoria e di runtime.In generale, questa tesi propone una nuova prospettiva su importanti tecniche nell'ambito dei MAS, quali CF e l'ottimizzazione a vincoli, permettendo di risolvere per la prima volta problemi di carattere reale su larga scala.

Constraint optimisation represents a fundamental technique that has been successfully employed in Multi-Agent Systems (MAS) in order to face a number of multi-agent coordination challenges. In this thesis we focus on Coalition Formation (CF), one of the key approaches for coordination in MAS. CF aims at the formation of groups that maximise a particular objective functions (e.g., arrange shared rides among multiple agents in order to minimise travel costs). Specifically, we discuss a special case of CF known as Graph-Constrained CF (GCCF) where a network connecting the agents constrains the formation of coalitions. We focus on this type of problem given that in many real-world applications, agents may be connected by a communication network or only trust certain peers in their social network. In particular, the contributions of this thesis are the following.We propose a novel representation of this problem and we design an efficient solution algorithm, i.e., CFSS. We evaluate CFSS on GCCF scenarios like collective energy purchasing and social ridesharing using realistic data (i.e., energy consumption profiles from households in the UK, GeoLife for spatial data, and Twitter as social network).Results show that CFSS outperforms state of the art GCCF approaches both in terms of runtime and scalability. CFSS is the first algorithm that provides solutions with good quality guarantees for large-scale GCCF instances with thousands of agents (i.e., more that 2700).In addition, we address the problem of computing the transfer or payment to each agent to ensure it is fairly rewarded for its contribution to its coalition. This aspect of CF, denoted as payment computation, is of utmost importance in scenario characterised by agents with rational behaviours, such as collective energy purchasing and social ridesharing. In this perspective, we propose PRF, the first method to compute payments in large-scale GCCF scenarios that are also stable in a game-theoretic sense.Finally, we provide an alternative method for the solution of GCCF, by exploiting the close relation between such problem and Constraint Optimisation Problems (COPs).We consider Bucket Elimination (BE), one of the most important algorithmic frameworks to solve COPs, and we propose CUBE, a highly-parallel GPU implementation of the most computationally intensive operations of BE. CUBE adopts an efficient memory layout that results in a high computational throughput. In addition, CUBE is not limited by the amount of memory of the GPU and, hence, it can cope with problems of realistic nature. CUBE has been tested on the SPOT5 dataset, which contains several satellite management problems modelled as COPs.Moreover, we use CUBE to solve COP-GCCF, the first COP formalisation of GCCF that results in a linear number of constraints with respect to the number of agents. This property is crucial to ensure the scalability of our approach.Results show that COP-GCCF produces significant improvements with respect to state of the art algorithms when applied to a realistic graph topology (i.e., Twitter), both in terms of runtime and memory.Overall, this thesis provides a novel perspective on important techniques in the context of MAS (such as CF and constraint optimisation), allowing to solve realistic problems involving thousands of agents for the first time.