An analysis of coordination mechanisms for multi-robot exploration of indoor environments

In this thesis, we consider the problem of coordinating a team of multiple robots to explore an initially unknown environment. The goal of the robots is to explore the environment in order to build its map in the shortest possible time, managing the interferences between them. To coordinate the agents, we propose four new coordination mechanisms, which are variant that improve existing mechanisms. The mechanisms belong to two different families: \textit{online} and \textit{offline}. Online mechanisms allocate the robots by dinamically taking into account the current decisions made by all team members to assign a goal location to an agent, while offline mechanisms define static roles before the exploration starts and, thanks to them, drive the actions of the single agents. To properly compare the mechanisms a formal framework is proposed. The framework involves three main concepts: the \textit{states} through which the exploration evolves, the \textit{coordination mechanism} that allocates target locations to the agents, and the evaluation criteria related to the measures of \textit{interference} and \textit{availability}. The interference measure is here formally defined as the average distance agents have to each other, while the availability measures the average distance agents have to their assigned locations. The four coordination mechanisms that we propose are tested against some benchmark ones. The experiments are performed in 2D simulated environments and the mechanisms are tested over different types of environments. Results show how offline coordination mechanisms outperform the online ones in the initial stages of the exploration, while the situation is reverse as the exploration proceeds. Moreover, offline mechanisms work better in open environments, compared to online mechanisms. As a conclusion, results suggest that a combination of the online and offline mechanisms could provide better performance over a wide range of environments.

In questa tesi, consideriamo il problema di coordinare un team composto da più robot al fine di explorare un ambiente inizialmente sconosciuto. L'obiettivo dei robot è di costruire una mappa dell'ambiettente, minimizzando il tempo di esplorazione e gestendo le loro possibili interferenze. Per coordinare gli agenti, proponiamo quattro nuovi meccanismi di coordinazione, i quali sono varianti migliorative di meccanismi già esistenti. I meccanismi appartengono a due famiglie: online e offline. I meccanismi online allocano i robot considerando dinamente le azioni in cui tutti i membri del team sono correntemente coinvolti, mente i meccanismi offline basano la coordinazione sulla definizione di ruoli, assignati agli agenti prima dell'inizio dell'esplorazione. Per confrontare adeguatamente i meccanismi. proponiamo un framework definitio formalmente per descrivere il problema della coordinazione multi-robot. Il framework si basa su tre concetti fondamentali: gli \textit{stati} attraverso cui evolve l'esplorazione, i meccanismi di coordinazione che allocato i robot ai loro obiettivi, e le misure di interferenze e disponibilità. L'interferenza è formalmente definita come la distanza media tra gli agenti, mentre la disponibilità corrisponde alla distanza media tra gli agenti e gli obiettivi a loro assegnati. I quattro meccanismi di coordinazione proposti sono stati testati in opposizione ad altri già esistenti, presi come riferimento. Gli esperimenti sono stati condotti su ambienti bidimensionali e i meccanismi sono stati testati su diversi tipi di ambienti. I risultati mostrano come i meccanismi offline si comporitno megli di quelli offline negli stadi iniziali dell'esplorazione, mentre la situazione si capovolge mano a mano che l'esplorazione procede. Inoltre, i meccanismi offline lavorano meglio, rispetto a quelli online, su ambienti aperti. Concludendo, i risultati suggeriscono che una combinazione dei meccanismi online ed offline potrebbe portare alle migliori performance su una vasta gamma di ambienti.