Network Topology Optimization for Bearing Rigid Multi-Agent Systems via Deep Reinforcement Learning and Graph Neural Networks

Multi-agent systems play important roles in various fields, and with the advancements in bearing-only sensors (e.g. cameras), formation control and localization relying on bearing measurements have attracted considerable attention in recent years. Bearing rigidity theory provides the mathematical tools for analysis and development of methods for such systems and networks, and the main tool it provides is infinitesimal bearing rigidity, which allows the recoverability of the formation shape from only the inter-agent bearing measurements. In a non-ideal scenario, which is the case in real-life applications such as robotic swarms or sensor networks, these bearings are subject to measurement noise, and recovering the formation shape (which is useful for various purposes, such as control or localization) requires more bearing measurements to be made for better estimates, though usually these measurements are associated with a sensing cost. This thesis studies topology optimization of the underlying network of heterogeneous bearing-based multi-agent systems, for achieving rigid formations with consideration to the sensing costs and estimation quality of the formation shape, using graph neural networks trained with deep reinforcement learning. It includes a theoretical analysis based on bearing rigidity theory and combinatorial optimization for heterogeneous bearing-based multi-agent systems, development of the environment, policy architectures, training approach, and a comprehensive set of experiments to analyze the resultant policies and the produced formations, comparing them with classical combinatorial optimization algorithms. Contributions of this work are as follows: establishment of a node-indexed construction of the extended bearing rigidity matrix for heterogeneous frameworks, an analysis of rigidity objectives from a combinatorial optimization perspective, and development of the methodology for topology optimization with graph neural networks and deep reinforcement learning.

I Sistemi Multi-Agente (Multi-Agent Systems) svolgono un ruolo importante in numerosi ambiti e, con i progressi compiuti nei sensori basati esclusivamente sulla misura della direzione (bearing-only), come ad esempio le telecamere, negli ultimi anni hanno ricevuto crescente attenzione il controllo di formazione e la localizzazione basati su misure di bearing. La teoria della bearing rigidity fornisce gli strumenti matematici per l’analisi e lo sviluppo di metodi per tali sistemi e reti, e il principale strumento che mette a disposizione è la Rigidità Infinitesimale di Bearing (Infinitesimal Bearing Rigidity), che consente di determinare la recuperabilità della forma della formazione utilizzando esclusivamente le misure di bearing tra gli agenti. In uno scenario non ideale, come avviene nelle applicazioni reali quali sciami robotici o reti di sensori, tali misure sono soggette a rumore. Il recupero della forma della formazione, utile per diversi scopi quali il controllo o la localizzazione, richiede quindi un numero maggiore di misure di bearing per ottenere stime più accurate, sebbene tali misure siano generalmente associate a un costo di sensing. Questa tesi studia l’ottimizzazione della topologia della rete sottostante a sistemi multi-agente eterogenei basati su misure di bearing, con l’obiettivo di ottenere formazioni rigide tenendo conto sia dei costi di sensing sia della qualità della stima della forma della formazione, mediante Reti Neurali su Grafi (Graph Neural Networks) addestrate tramite Deep Reinforcement Learning. Il lavoro comprende un’analisi teorica basata sulla teoria della bearing rigidity e sull’ottimizzazione combinatoria per sistemi multi-agente eterogenei basati su bearing, lo sviluppo dell’ambiente, delle architetture delle policy e dell’approccio di addestramento, nonché un insieme completo di esperimenti volti ad analizzare le policy ottenute e le formazioni prodotte, confrontandole con algoritmi classici di ottimizzazione combinatoria. I contributi di questo lavoro sono i seguenti: l’introduzione di una costruzione indicizzata per nodo della matrice estesa di bearing rigidity per framework eterogenei; un’analisi degli obiettivi di rigidità dal punto di vista dell’ottimizzazione combinatoria; e lo sviluppo della metodologia per l’ottimizzazione della topologia mediante reti neurali su grafi e deep reinforcement learning.