Study, design, and evaluation of exploration strategies for autonomous mobile robots

In recent years, autonomous mobile robotics is increasingly becoming an effective way to carry out tasks that are difficult, dangerous, or simply boring for humans. Relevant examples include planetary exploration and search and rescue. While developing a system of autonomous robots, a designer should take care of fundamental issues that relate to locomotion, sensing, localization, and navigation. One of the most important and challenging aspects that could significantly impact on the system performance is the autonomous decision making to carry out the assigned task. This comprises the set of techniques that allow autonomous mobile robots to decide the next location to reach and to possibly coordinate among themselves, according to their current knowledge of the world they operate in. Consider for example the *exploration problem*, where mobile robots are employed for incrementally discovering and mapping the features of initially unknown environments, which could serve for more general missions, such as map building and search and rescue. The robots have to select the next locations where to perform sensing actions within the currently explored portion of the environment and who goes where. Clearly, the decisions made could have a significant impact on the performance of the exploration and, if made effectively, could really boost the robots' autonomy. However, despite the importance of the development of techniques to make mobile robots more autonomous, general techniques are not mature yet. In this dissertation, we focus on some key activities for the multirobot exploration problem, namely the selection of interesting locations (*exploration strategy*) and their assignment to robots (*coordination method*). We aim at contributing to the achievement of three main research goals: to bridge the gap between theory and practice for exploration strategies; to improve exploration strategies and coordination methods employed for exploring an initially unknown environment by one or more robots; and to improve the experimental assessment of multirobot exploration systems. The first goal is motivated by the fact that the exploration problem has been addressed in literature with two rather different approaches. On the one hand, this problem is theoretically studied, by providing worst-case bounds and competitive ratios for proposed methods, although, sometimes, assumptions are far from being realistic. On the other hand, methods are defined and tested in practical contexts of real robots. Against this background, we define the problem of calculating the optimal (offline) exploration paths in grid environments for a robot under realistic assumptions of limited and time-discrete visibility. Simulation results show the viability of our proposed approach for realistic environments. Further, we theoretically analyze some exploration strategies that evaluate candidate destination locations by combining their distance and their expected information gain and operate on graph-based environments. Specifically, we provide bounds on the number of edge traversals required to explore a generic graph by a single robot. Results show that, in the worst case, considering also information gain does not provide any advantage over considering only distance, while it does in the average case on graphs modeling realistic indoor environments. Second, we define exploration strategies and coordination methods that base their decisions not only on metric information that derives from sensor readings, but also on *semantic information* which associates some high-level concepts to areas of the environment. This enables robots to privilege exploration of areas that are relevant (e.g., corridors), as our results obtained with a realistic simulator show. Third, recognizing that the evaluation of autonomous multirobot systems has not reached a maturity level comparable to that of other disciplines, we provide some tools for improving the evaluation of exploration strategies and we contribute to experimentally evaluate what factors impact the performance of exploration. Specifically, we discuss how to compute the competitive ratio of practically-used exploration strategies given a specific setting. Also, we quantitatively assess in simulation to obtain a significant number of repeated experiments the impact of different perception/decision timings on the performance of exploring multirobot systems and the relative influence of exploration strategies and coordination methods. We finally show some possible uses of some of the contributions provided in this dissertation for exploring abstract state spaces in the domain of pursuit-evasion. The long-term goal is to pave the way towards the theoretical and practical development and the experimental assessment of effective exploration strategies and coordination methods to increase mobile robots autonomy. In an even broader perspective, the future objective is to develop a framework for a more general exploration problem where robots can “explore” other features of the environment, including its physical quantities.

Negli ultimi anni, la robotica mobile autonoma ha acquisito sempre più importanza in attività difficili, pericolose o semplicemente noiose da eseguire da parte degli essere umani, come ad esempio l'esplorazione di pianeti e il soccorso di vittime in ambienti disastrati. Durante la progettazione di un sistema di robot mobili autonomi, il progettista deve risolvere diverse problematiche importanti che includono la locomozione, la percezione, la localizzazione e la navigazione. Uno degli aspetti rilevanti che potrebbe avere impatti significativi sulla performance del sistema riguarda la parte decisionale che permette di compiere l'attività assegnata in modo autonomo. Questo comprende l'insieme di tecniche che permettono ai robot mobili autonomi di decidere la prossima locazione candidata da raggiungere (attraverso una *strategia di navigazione*), e, possibilmente, di coordinarsi tra di loro (attraverso un *metodo di coordinamento*). Tipicamente, queste decisioni vengono prese considerando la conoscenza del mondo esterno che il sistema robotico ha acquisito fino a quel momento. Si prenda in considerazione ad esempio il *problema dell'esplorazione*, in cui robot mobili autonomi vengono impiegati per scoprire e mappare in modo incrementale un ambiente inizialmente sconosciuto. Questa attività è alla base di molte applicazioni, come ad esempio il *search and rescue*. A partire dall'area di ambiente attualmente conosciuta, i robot devono decidere le prossime posizioni da cui effettuare una percezione e l'allocazione di esse ai vari robot. Nonostante l'importanza dello sviluppo di tecniche che permettono ai robot mobili di essere più autonomi, quest'ultime non sono ancora del tutto mature. Questa tesi si focalizza su alcuni aspetti chiave del problema dell'esplorazione multirobot: la scelta di locazioni interessanti da raggiungere (attraverso una strategia di esplorazione) e il loro assegnamento ai robot (attraverso un metodo di coordinamento). Il lavoro presentato in questa tesi vuole contribuire a tre obiettivi di ricerca: costruire un ponte tra teoria e pratica per le strategie di esplorazione; migliorare le strategie di esplorazione e i metodi di coordinamento usati nei sistemi di esplorazione multirobot; e portare la loro valutazione sperimentale a una maturità comparabile a quella di altre discipline. Innanzitutto, studiando i lavori presenti in letteratura, si può notare che il problema dell'esplorazione è trattato con due approcci diversi. Da un lato, questo problema è studiato in modo teorico: solitamente, i metodi sono proposti con delle garanzie teoriche, come *bound* e *competitive ratio* nel caso peggiore. Spesso però in questi tipi di lavori, le assunzioni fatte sul modello non sono realistiche. Dall'altro lato esistono lavori che definiscono e testano in modo empirico le tecniche per risolvere questo problema in alcuni contesti pratici, utilizzando robot reali (o realisticamente simulati). Rispetto a questi approcci radicalmente diversi, in questa tesi viene definito il problema di calcolare un percorso offline di esplorazione ottimo per un robot in ambienti rappresentati a griglia, con delle assunzioni più realistiche, ossia visibilità limitata e discreta. I risultati sperimentali mostrano la fattibilità di questo approccio per ambienti realistici. Un secondo contributo in questa direzione è dato dall'analisi teorica di alcune strategie di esplorazione che sono state usate in alcuni contesti reali. In particolare, vengono considerate strategie di esplorazione che valutano il prossimo punto da raggiungere con distanza e guadagno in termini di informazione. Il modello dell'ambiente considerato è basato su grafi. Attraverso quest'analisi, vengono forniti dei bound sulla distanza percorsa, misurata come numero di attraversamenti di archi, per esplorare un grafo generico. I risultati mostrano che, nel caso peggiore, considerando una strategia di esplorazione che considera anche il guadagno di informazione non si ha nessun vantaggio rispetto all'uso di una strategia di esplorazione che considera solo la distanza percorsa, mentre nel caso medio quest'informazione aiuta a migliorare le performance del sistema. In secondo luogo, in questa tesi, vengono definite delle strategie di esplorazione e metodi di coordinamento che basano le decisioni non solo su informazioni metriche che potrebbero essere ricavate dalle letture dei sensori montati sui robot, ma anche su informazioni semantiche che associano concetti di alto livello ad aree dell'ambiente. Questo risulta utile quando, ad esempio, un comportamento desiderabile da parte dei robot è quello di privilegiare aree da esplorare considerate rilevanti (ad esempio i corridoi). I risultati sperimentali confermano la bontà del sistema proposto. Inoltre, riconoscendo che, nonostante in varie discipline dell'ingegneria ci siano solitamente standard condivisi per valutare le performance di un sistema, in robotica, non è ancora stata definita una metodologia standard di valutazione per confrontare sistemi diversi. In questo senso, un altro contributo di questa tesi sta nel fornire uno strumento per migliorare la valutazione delle strategie di esplorazione, per cui viene mostrato come si può calcolare il competitive ratio dato un ambiente specifico. Inoltre, vengono analizzati sperimentalmente alcuni dei fattori che hanno impatto sulla performance dell'esplorazione. Specificatamente, vengono valutati, in simulazione per ottenere un numero significativo di esperimenti ripetuti, l'influenza relativa delle strategie di esplorazione e dei metodi di coordinamento e l'impatto di cambiare le frequenze di percezione/decisione sulla performance di un sistema robotico per l'esplorazione. Infine, viene mostrato un possibile uso di alcuni contributi dati in questa tesi per esplorare uno spazio più astratto degli stati in un contesto di guardia e ladro. L'obiettivo di lungo termine è costruire una base verso uno sviluppo e una valutazione sperimentale teorica e pratica delle strategie di esplorazione e dei metodi di coordinamento per migliorare l'autonomia dei robot mobili. In una prospettiva più ampia, l'obiettivo futuro è sviluppare un framework per problemi di esplorazione più generali, in cui i robot “esplorano” altre caratteristiche dell'ambiente, come alcune sue grandezze fisiche.