Development of a framework for evaluating performance of exploration strategies of autonomous robots

Despite the fact that engineering fields usually have assessed standards for evaluating system performance, in the exploration problem, i.e., in the problem of mapping an initially unknown environment with autonomous mobile robots, there is not yet any standard evaluation methodology for comparing different exploration strategies. The lack of such a standard evaluation framework is probably due to the youth of the approaches to this problem. One of the elements of a standard evaluation framework should be the comparison of the performance of an exploration strategy with the optimal performance attainable in a given environment. However, the problem of calculating the optimal exploration path in a given environment has not yet been adequately addressed in literature. Although several fields (e.g., robotics, graph theory, computational intelligence) dealt with this issue, results allow to calculate the upper or lower bound of the performance (e.g., number of perceptions, distance traveled) of a given strategy, for generic classes of environments. These results do not answer to the question of what is the best performance in a given, specific, environment. The answer to this question has relevance in practically applying exploration strategies. In this thesis, we contribute to build up a framework that allows to compare strategies performance with the optimal exploration path in a given environment. The innovative aspect of this work is that, given an environment, the comparison of different exploration strategies can be performed with respect to the optimal behavior (which is computed by our framework), instead of considering lower or upper bounds. The approach to compute the optimal exploration is based on the use of off-line seach algorithms, such as A* or branch and bound. The quality of the optimal solution greatly depends on initial parameters and assumptions we make (e.g., objective test, representation of the map, perception and locomotion models of the robot). Experimental results obtained in simulation in some realistic environments have shown the validity of our approach to solve the problem of determining the optimal solution for the exploration problem in a specific environment. From the scientific point of view, the contribution of our work is twofold: on the one hand, it contributes to the definition of a standard evaluation framework for exploration strategies, allowing to compare exploration strategies not only between each other in a relative way (which is the current approach), but also against the optimal exploration in an absolute way. On the other hand, our framework could be useful for developing better exploration strategies.

Nonostante nell'ingegneria ci siano solitamente standard condivisi per valutare le performance di un sistema, per il problema dell'esplorazione, cioè per il problema di mappare un ambiente inizialmente sconosciuto con robot mobili autonomi, non è ancora stata definita una metodologia standard di valutazione per confrontare diverse strategie di esplorazione. La mancanza di una metodologia generale di valutazione è dovuta, molto probabilmente, al fatto che gli approcci per risolvere questo problema sono recenti. Uno degli elementi di un framework di valutazione standard dovrebbe essere il confronto delle performance di una strategia di esplorazione rispetto alla performance ottima ottenibile in un dato ambiente. In letteratura, il problema del calcolo del percorso ottimo per esplorare un dato ambiente non è stato ancora studiato in modo approfondito. Anche se molte discipline scientifiche, come la robotica, la teoria dei grafi, l'intelligenza computazionale, hanno trattato questo problema, i risultati ottenuti consentono di calcolare il limite superiore o inferiore delle performance ottenibili con una data strategia di esplorazione, per classi di ambienti generici. Questi risultati non permettono però di capire quale sia la migliore performance in un dato ambiente. Questa informazione è, d'altra parte, rilevante per le applicazioni pratiche. In questa tesi, contribuiamo a sviluppare un framework che permetta di confrontare le performance delle strategie di esplorazione rispetto al percorso ottimo in un dato ambiente. L'aspetto originale di questa ricerca è che le varie strategie esplorative possono essere confrontate rispetto all'ottimo calcolato dal nostro framework, e non più, quindi, considerando solo il limite superiore o inferiore. L'approccio per determinare l'esplorazione ottima si basa sull'uso di algoritmi di ricerca off-line, come A* e branch and bound. La qualità della soluzione ottima dipende fortemente dai parametri iniziali e dalle ipotesi fatte (ad esempio, il test obiettivo, la rappresentazione della mappa, i modelli di percezione e movimento del robot). I risultati ottenuti in esperimenti simulati condotti su ambienti realistici dimostrano che la validità dell'approccio che sta alla base del nostro framework. Dal punto di vista scientifico, il contributo di questo lavoro è duplice: da un lato, contribuisce alla definizione di un framework standard per la valutazione delle strategie di esplorazione, permettendo di confrontare strategie di esplorazione rispetto all'ottimo e non più soltanto in modo relativo; dall'altro questo lavoro è interessante per studiare l'uso del framework sviluppato in questo lavoro per definire migliori strategie di esplorazione.