Multi-Agent Distributed Optimization and Estimation over Lossy Networks

Nowadays, optimization is a pervasive tool, employed in a lot different fields. Due to its flexibility, it can be used to solve many diverse problems, some of which do not seem to require an optimization framework. As so, the research on this topic is always active and copious. Another very interesting and current investigation field involves multi-agent systems, that is, systems composed by a lot of (possibly different) agents. The research on cyber-physical systems, believed to be one of the challenges of the 21st century, is very extensive, and comprises very complex systems like smart cities and smart power-grids, but also much more simple ones, like wireless sensor networks or camera networks. In a multi-agent context, the optimization framework is extensively used. As a consequence, optimization in multi-agent systems is an attractive topic to investigate. The contents of this thesis focus on distributed optimization within a multi-agent scenario, i.e., optimization performed by a set of peers, among which there is no leader. Accordingly, when these agents have to perform a task, formulated as an optimization problem, they have to collaborate to solve it, all using the same kind of update rule. Collaboration clearly implies the need of messages exchange among the agents, and the focus of the thesis is on the criticalities related to the communication step. In particular, no reliability of this step is assumed, meaning that the packets exchanged between two agents can sometime be lost. Also, the sought-for solution does not have to employ an acknowledge protocol, that is, when an agent has to send a packet, it just sends it and goes on with its computation, without waiting for a confirmation that the receiver has actually received the packet. Almost all works in the existing literature deal with packet losses employing an acknowledge (ACK) system; the effort in this thesis is to avoid the use of an ACK system, since it can slow down the communication step. However, this choice of averting the use of ACKs makes the development of optimization algorithms, and especially their convergence proof, more involved. Apart from robustness to packet losses, the algorithms developed in this dissertation are also asynchronous, that is, the agents do not need to be synchronized to perform the update and communication steps. Three types of optimization problems are analyzed in the thesis. The first one is the patrolling problem for camera networks. The algorithm developed to solve this problem has a restricted applicability, since it is very task-dependent. The other two problems are more general, because both concern the minimization of the sum of cost functions, one for each agent in the system. In the first case, the form of the local cost functions is particular: these, in fact, are locally coupled, in the sense that the cost function of an agent depends on the variables of the agent itself and on those of its direct neighbors. The sought-for algorithm has to satisfy two properties (apart from asynchronicity and robustness to packet losses): the requirement of asking a single communication exchange per iteration (which also reduces the need of synchronicity) and the requirement that the communication among agents is only between direct neighbors. In the second case, the local functions depend all on the same variables. The analysis first focuses on the special case of local quadratic cost functions and their strong relationship with the consensus problem. Besides the development of a robust and asynchronous algorithm for the average consensus problem, a comparison among algorithms to solve the minimization of the sum of quadratic cost functions is carried out. Finally, the distributed minimization of the sum of more general local cost functions is tackled, leading to the development of a robust version of the Newton-Raphson consensus. The theoretical tools employed in the thesis to prove convergence of the algorithms mainly rely on Lyapunov theory and the separation of scales theory.Oggigiorno l’ottimizzazione è uno strumento pervasivo, utilizzato in molti ambiti differenti. Grazie alla sua flessibilità, può essere utilizzato per risolvere numerosi problemi, alcuni dei quali non sembrano a prima vista poter essere formulati come problemi di ottimizzazione. Proprio grazie a questa versatilità, la ricerca sulle tecniche di ottimizzazione è sempre attiva e copiosa. Un altro tema di ricerca molto interessante e attuale riguarda i sistemi multi-agente, cioè sistemi composti da molti agenti (anche diversi fra di loro). La ricerca sui sistemi ciberfisici, ritenuta una delle sfide del ventunesimo secolo, è molto vasta, e comprende sistemi molto complessi come le città intelligenti e le reti di potenza intelligenti, ma anche quelli molto più semplici, come le reti di sensori senza filo o le reti di telecamere. In un contesto multi-agente, lo strumento dell’ottimizzazione è molto usato. Di conseguenza, l’ottimizzazione in sistemi multi-agente è un argomento attraente da investigare. Questa tesi si concentra sull’ottimizzazione distribuita in uno scenario multi agente, cioè in uno scenario in cui l’ottimizzazione è svolta da un insieme di entità con pari capacità, tra le quali non c’è un leader. Di conseguenza, quando questi agenti devono portare a termine una attività, formulata come un problema di ottimizzazione, devono collaborare per svolgerla usando tutti lo stesso tipo di azioni. La collaborazione chiaramente richiede lo scambio di messaggi tra gli agenti, e in questa tesi l’attenzione è focalizzata sulle criticità relative alla fase di comunicazione. In particolare,non si assume che la comunicazione sia affidabile, e di conseguenza i pacchetti (cioè i messaggi) scambiati tra due agenti possono essere talvolta persi. Inoltre, la soluzione ricercata non deve richiedere un protocollo di conferma, cioè, quando un agente deve inviare un pacchetto semplicemente lo invia e continua con le sue computazioni, senza aspettare la conferma che l’agente a cui ha inviato il pacchetto lo abbia effettivamente ricevuto. Quasi tutti i lavori esistenti in letteratura gestiscono le perdite di pacchetto utilizzando un sistema di conferma; lo sforzo in questa tesi è proprio quello di evitare l’uso di messaggi di conferma, dal momento che questi possono rallentare la fase di comunicazione. Questa scelta rende però lo sviluppo di algoritmi di ottimizzazione, e specialmente la dimostrazione della loro convergenza, più complicati. Oltre alla robustezza alla perdita di pacchetti, gli algoritmi sviluppati in questa tesi sono anche asincroni, cioè gli agenti non devono necessariamente essere sincronizzati per svolgere le fasi di aggiornamento e comunicazione. In questa tesi vengono analizzati tre tipi di problemi di ottimizzazione. Il primo è il problema della perlustrazione effettuata da reti di telecamere. L’algoritmo sviluppato per questo problema ha una applicabilità limitata, essendo molto legato al problema stesso. I rimanenti due problemi sono più generali, e riguardano la minimizzazione della somma di funzioni costo, una per ogni agente nel sistema. Nel primo problema, la forma delle funzioni costo locali è particolare. Le funzioni costo sono infatti localmente accoppiate, nel senso che la funzione costo di un agente dipende dalla variabile dell’agente stesso e da quelle dei suoi vicini diretti. L’algoritmo ricercato deve soddisfare due richieste (oltre alla asincronia e alla robustezza alla perdita di pacchetti): deve richiedere un solo scambio di messaggi per iterazione (per ridurre la necessità di sincronizzazione) e deve richiedere lo scambio di informazioni solo tra vicini diretti. Nel secondo problema, le funzioni locali dipendono tutte dalle stesse variabili. L’analisi in questo caso prima si focalizza sul caso speciale di minimizzazione di funzioni costo quadratiche e la loro forte relazione con il problema di consenso. Oltre allo sviluppo di un algoritmo robusto e asincrono per il problema del consenso alla media, viene anche svolta una comparazione tra diversi algoritmi che risolvono la minimizzazione della somma di funzioni costo quadratiche. Infine viene affrontata la minimizzazione distribuita della somma di funzioni costo locali più generali, portando allo sviluppo di una versione robusta del Newton-Rapshon consensus. Gli strumenti teorici impiegati in questa tesi per provare la convergenza degli algoritmi sono soprattutto la teoria di Lyapunov e la teoria della separazione delle scale temporali