Online exploration of graphs with an autonomous robot : a theoretical analysis

Exploration of unknown environments plays a significant role in many mobile robot applications, like map building, coverage, and searching. In literature, exploration strategies are usually defined and evaluated following two rather different approaches. On the one hand, they are defined in practical contexts of real (or realistically simulated) robots and are empirically assessed by testing them in some environments. On the other hand, exploration strategies are defined in theoretical settings (e.g., exploration of graphs) and are assessed using theoretical tools like worst-case bounds. Being inherently an online task, exploration is usually greedily addressed by letting a robot evaluate some candidate destination locations in order to choose where to go next. In this thesis, we provide a theoretical analysis of some exploration strategies. We consider a single robot exploring an initially unknown environment represented by an undirected graph. The goal of the robot is to find an exploration path (not necessarily closed) that perceives a given fraction of vertices of the graph with the minimum number of edge traversals (atomic movements from a vertex to an adjacent vertex). We assume that the robot learns of the vertices, and of the corresponding edges, within a given perception range from its current position. Our results significantly complement some of the worst-case bounds on the number of edge traversals required to explore a generic graph presented in the literature, explicitly embedding in the analysis the sensor range of the robot, and considering exploration strategies based on information gain and on combination of information gain with distance. We also provide an average-case analysis (which, to the best of our knowledge, has never appeared in the literature) of exploration strategies in classes of graphs that model realistic indoor environments. The main contribution of this thesis is a theoretical analysis that integrates and possibly better explains the experimental results obtained with real (and realistically simulated) exploring robots.

L’esplorazione di ambienti sconosciuti è fondamentale in molte applicazioni in cui sono utilizzati robot mobili, come la costruzione della mappa di un edificio, la ricerca e i problemi di covering. In letteratura, le strategie di esplorazione sono solitamente definite e valutate in due modi differenti. Da una parte, sono definite in un contesto pratico, con robot reali (o realisticamente simulati) e valutate empiricamente attraverso test in diversi ambienti. Dall’altra parte, sono definite in un contesto teorico (e.g., esplorazione di grafi) e valutate attraverso strumenti teorici, come limiti nel caso pessimo. Essendo un’attività effettuata online, l’esplorazione è tipicamente affrontata in modo greedy, lasciando al robot la valutazione delle possibili posizioni future in cui muoversi. In questa tesi sono analizzate, da un punto di vista teorico, alcune strategie di esplorazione. Lo scenario considerato è quello in cui un singolo robot mobile esplora un ambiente inizialmente sconosciuto, rappresentato da un grafo non orientato. L’obiettivo del robot è trovare un percorso di esplorazione (non necessariamente chiuso) che percepisca una certa percentuale di vertici del grafo, con il minor numero possibile di archi attraversati (movimenti atomici da un vertice a un vertice adiacente). Il robot percepisce i vertici e i loro archi corrispondenti, all’interno di un certo raggio di percezione dalla sua posizione corrente. I risultati di questa tesi completano in modo significativo alcuni dei limiti relativi al caso peggiore (rispetto al numero di attraversamenti di archi richiesto per esplorare un generico grafo) presenti in letteratura, considerando esplicitamente nell’analisi il raggio del sensore del robot, e considerando strategie di esplorazione basate sull’information gain o sulla combinazione fra information gain e distanza. In questa tesi vengono anche analizzate, dal punto di vista del caso medio, alcune classi di grafi che modellano ambienti indoor realistici. Il principale contributo di questa tesi è un’analisi teorica che ha lo scopo di contribuire a spiegare meglio i risultati sperimentali ottenuti nell’esplorazione con robot reali o realisticamente simulati.