Modellazione e predizione di mappe semantiche di edifici tramite graph kernel e tecniche Montecarlo Markov Chain

This thesis proposes a generative and predictive model based on graphs for the semantic mapping of buildings. A graph is a mathematical structure formed by a discrete set of simple objects, called nodes, and edges or arcs connecting the nodes. The semantic mapping is a procedure that allows to construct a semantic map, which contains semantic and topological information about the environment. The nodes of a semantic map are associated to the labels that indicate the meaning and the functions of the parts of the environment that they represent. The generative model is structured into three main steps: segmentation, clustering, and sampling. Given a knowledge base of initial graphs representing buildings, the segmentation step divides each graph into a set of significant subgraphs. The clustering step groups the subgraphs according to their similarity, calculated by means of kernel functions defined on graphs. The last step is concerned with the sampling of new graphs by means of a Monte Carlo-Marcov Chain method. New graphs share the same topological and semantic characteristics of the graphs belonging to the initial knowledge base. As an application of our approach, we consider the exploration of a building performed by a mobile robot and exploit our generative model to try to predict, on the basis of the initial knowledge available to the robot and of the already explored parts of the building, the areas still unexplored.

In questo lavoro di tesi si propone un modello generativo e di predizione basato su grafi per il mapping semantico di edifici. Un grafo è una struttura matematica discreta formata da un insieme di oggetti semplici, chiamati nodi, e da archi o lati che connettono i nodi. Il mapping semantico è un procedimento che consente di ottenere una mappa semantica, che contiene informazioni sull'ambiente sia di tipo semantico che topologico. I nodi di una mappa semantica hanno associate delle etichette che indicano il significato e le funzioni delle porzioni di ambiente che rappresentano. Il modello generativo è strutturato in tre fasi principali: segmentazione, clustering e campionamento. Data una base di conoscenza iniziale di grafi che rappresentano edifici, la fase di segmentazione divide ogni grafo in un insieme di sottografi significativi. La fase di clustering raggruppa i sottografi in base alla loro similarità, calcolata tramite delle kernel function definite su grafi. L'ultima fase si occupa del campionamento di nuovi grafi, tramite un metodo Monte Carlo-Marcov Chain, che condividono le stesse caratteristiche topologiche e semantiche dei grafi appartenenti alla base di conoscenza iniziale. Come applicazione del nostro approccio, consideriamo l'esplorazione di un edificio da parte di un robot mobile e impieghiamo il modello generativo costruito per cercare di predire, sulla base della conoscenza iniziale a disposizione del robot e delle parti già esplorate dell'edificio, le aree ancora inesplorate.