Proactivity in coordination mechanisms for multi-robot exploration of indoor environments : a graph-based approach

This thesis deals with the problem of exploring unknown environments by means of a team of robots. Specifically, attention is given to the coordination among them to complete the exploration as fast as possible. Starting from two already existing coordination mechanisms, we propose some variants, based on a different approach to the proactive use of the idle robots before they are actually needed in the exploration. The aim of the proposed variants is to exploit what is known about the environment during the exploration in order to improve the base coordination mechanisms. The idea is to determine a convenient waiting location for idle robots, from which they can move when they are needed. To do this, a representation of the environments using graphs has been introduced. They are built on the partial representation of the map and updated as the exploration goes on. The robots not currently needed are moved to a location computed through the values of centrality measures for these graphs. We analyze two different types of graphs, as well as two centrality measures. Their combination produces four variants for each coordination mechanism considered. The proposed variants have been compared to the base coordination mechanisms according to the time required to complete the exploration of a number of environments. Results obtained show that the proposed variants do not enhance performance in general, but they perform better than the corresponding base mechanisms in some specific environments.

Questa tesi riguarda il problema di esplorare ambienti sconosciuti mediante un gruppo di robot, ponendo l'attenzione su come i robot si coordinano per eseguire tale compito nel minor tempo possibile. Partendo da due meccanismi di coordinamento già esistenti, proponiamo delle varianti degli stessi. In particolare, l'aspetto su cui questo lavoro si fonda è un utilizzo proattivo dei robot inizialmente non necessari ai fini dell'esplorazione. L'obiettivo è quello di sfruttare esplicitamente, rispetto ai meccanismi di base, le conoscenze relative all'ambiente che si sta esplorando al fine di far attendere tali robot in una posizione conveniente da cui partire, una volta che saranno necessari. Per far sì che essi siano posizionati in maniera efficace, abbiamo rappresentato l'ambiente con dei grafi, costruiti a partire dalla mappa parziale dell'ambiente ed aggiornati con il proseguire dell'esplorazione. Il miglior punto in cui posizionare i robot non necessari è poi individuato mediante il calcolo di metriche di centralità sui grafi ottenuti. Abbiamo analizzato due differenti tipi di grafi, così come due metriche di centralità. Le loro combinazioni hanno permesso di ottenere quattro varianti per ognuno dei meccanismi di coordinamento considerati. Tali varianti sono state confrontate con i meccanismi di coordinamento di partenza sulla base del tempo richiesto per completare l'esplorazione di diversi ambienti. I dati ottenuti dal loro confronto mostrano che le varianti proposte non migliorano l'esplorazione in generale, ma almeno una tra le varianti proposte fornisce risultati migliori rispetto al corrispondente meccanismo di coordinamento di partenza in specifici ambienti.