• geometric-semantic matching
• graph attention network (GAT)
• graph matching
• graph neural network (GNN)
• Hungarian
• partial graph matching
• scene graph
• simultaneous localization and mapping (SLAM)
• Sinkhorn

This thesis explores the application of Graph Neural Networks (GNNs) to the problem of scene graph matching in the context of robot localization in indoor environments, a key component of SLAM (Simultaneous Localization and Mapping). Traditional approaches such as iS-Graphs and diS-Graphs rely on matching graphs generated in real time by a robot’s sensors with architectural plans, using algorithms like CLIPPER that are limited to geometric information. These methods, while effective, often struggle in environments with incomplete or imprecise data, and they assume a perfect match between the planned and built environments. Moreover, the algorithm used in these solutions, although capable of achieving accurate results, is a hierarchical combinatorial method whose worst-case complexity is exponential in the number of observed rooms and factorial in the average number of walls per room, due to the combinatorial generation and verification of local and global candidates. This makes the algorithm impractical for real-world scenarios involving many rooms.
To address these limitations, this work proposes the integration of GNNs to enhance graph matching by learning both geometric and semantic patterns. The contributions of this thesis are threefold: (1) the creation of a novel dataset of scene graphs representing apartment environments, structured on two levels with nodes for rooms and walls; (2) the design of a GNN model tailored for full graph matching; and (3) the implementation of a partial matching framework, also based on a GNN, that enables more flexible localization even in the presence of incomplete observations. Both proposed models are based on Graph Attention Networks (GATs) and incorporate a Sinkhorn layer to solve the graph matching problem by estimating a soft assignment matrix between nodes. The proposed approach aims to make robot localization more robust and adaptable to real-world variability.
---
Questa tesi esplora l'applicazione delle Graph Neural Networks (GNN) al problema del scene graph matching nel contesto della localizzazione robotica in ambienti indoor, un elemento chiave dello SLAM (Simultaneous Localization and Mapping). Gli approcci tradizionali, come gli iS-Graphs e i diS-Graphs, si basano sull'allineamento tra grafi generati in tempo reale dai sensori del robot e le planimetrie architettoniche, utilizzando algoritmi come CLIPPER che si limitano alle informazioni geometriche. Questi metodi, sebbene efficaci, presentano difficoltà in ambienti con dati incompleti o imprecisi e assumono una corrispondenza perfetta tra l’ambiente progettato e quello reale. Inoltre, l’algoritmo utilizzato in queste soluzioni, pur ottenendo risultati accurati, è un metodo combinatorio gerarchico la cui complessità, nel caso peggiore, è esponenziale rispetto al numero di stanze osservate e fattoriale rispetto al numero medio di muri per stanza, a causa della generazione e verifica combinatoria di candidati locali e globali. Questo lo rende poco praticabile in scenari reali con molte stanze.
Per superare queste limitazioni, questa tesi propone l’integrazione delle GNN per migliorare il graph matching tramite l’apprendimento di pattern geometrici e semantici. I contributi principali sono tre: (1) la creazione di un nuovo dataset di scene graph rappresentanti ambienti domestici, strutturato su due livelli con nodi stanza e nodi muro; (2) la progettazione di un modello GNN per il graph matching completo; e (3) l’implementazione di un framework per il partial matching, anch’esso basato su una GNN, che consente una localizzazione più flessibile anche in presenza di osservazioni parziali. Entrambi i modelli proposti si basano su Graph Attention Networks (GAT) e includono un layer di Sinkhorn per risolvere il problema del graph matching tramite la stima di una matrice di assegnazione soft tra i nodi. L’approccio proposto mira a rendere la localizzazione robotica più robusta e adattabile alla variabilità degli ambienti reali.