Multi-Agent Distributed Optimization and Estimation over Lossy Networks

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.