Modern society relies heavily on communication networks that in turn rely on both wired and wireless infrastructure. This work pertains to scenarios where a group of people or robots need to communicate in an environment where there is no preexisting communications infrastructure. These include sites of emergencies and disasters (e.g., inside burning buildings, search and rescue operations) and unexplored areas on Earth and other planets. Wireless ad hoc or mesh networks offer the ability to keep such entities connected, but they falter when any single entity wishes to leave the developed coverage area. Utilizing mobile repeater nodes can help, but is costly and complicated. By eliminating the need for repeater nodes to traverse the environment, their size and cost can be vastly reduced. This work explores the use of static "breadcrumb" repeater nodes to increase the reach of such a network. Determining when and where to place a static repeater node can be difficult in an environment where radio propagation characteristics are unknown. In this work, several algorithms for node placement are compared under the constraint that placement of a static repeater node should not dictate the entity's movement. The algorithms investigated range from calculating rolling averages to modeling channel parameters on-the-fly. The placement algorithms were configured to run in real-time on TP-Link MR-3040 portable WiFi routers and the approach is demonstrated in an outdoor uncharacterized environment.

Deploying robots in unknown and complex areas for inspection tasks is becoming a real need for various application scenarios. Recently, there has been an increasing interest to develop and use autonomous aerial robots in environments such as urban voids and subterranean mine tunnels, aiming to decrease the human presence in dangerous or inaccessible areas. These areas are characterized by complete darkness and narrow tunnels, where the ground can often be rough and not traversible for mobile vehicles, thus the developments focus on Micro Aerial Vehicles (MAVs). MAVs are mechanically simple and agile platforms that can navigate through cluttered areas and have the potential to perform complex exploration tasks when equipped with proper onboard sensors. One of the key milestones in the development of autonomous robots is self-exploration. The definition of self-exploration according to [7] is "the act of moving through an unknown environment while building a map that can be used for subsequent navigation". By reaching this milestone, robots would be freed from the limitation of requiring already existing maps for navigation. In this thesis, a frontier-based exploration algorithm is established and evaluated to understand how such method could be used to reach the self-exploration milestone. By marking the border between what is known and unknown the method is able to determine the next desired position for the robot to expand the map. The resulting algorithm, together with a path planning method and 3-dimensional mapping framework, the method was tested and examined in simulated environments with different levels of complexity.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-07-25T17:21:34Z No. of bitstreams: 1 RaphaelSantos.pdf: 3718930 bytes, checksum: df335fd5562e8156000972c282fe9724 (MD5) / Made available in DSpace on 2017-07-25T17:21:34Z (GMT). No. of bitstreams: 1 RaphaelSantos.pdf: 3718930 bytes, checksum: df335fd5562e8156000972c282fe9724 (MD5) Previous issue date: 2016-08-17 / Autonomous exploration, in robotics, can be defined as the act of moving into an unknown environment, at priori, while building up a map of the environment. A great deal of literature describes several problems that are relate to the strategy exploration: perception, location, trajectory control and mapping. This work aims to present an autonomous exploration algorithm based on metaheuristics. Therefore, the problem of autonomous exploration of mobile robots is formulated as an optimization problem, providing data for metaheuristics that are able to search points in the space of solutions that represent positions on the map under construction that best meet the objectives of the exploration. Metaheuristics are approximate methods that guarantee sufficiently good solutions to optimization problems. The proposal was implemented and incorporated as an optimization module in a simultaneous location and mapping system that was run on the Robot Operating System environment and proved to be able to guide a simulated robot without human intervention. Two optimization metaheuristics were implemented to guide target to simulated robot: Genetic Algorithm and Firefly Algorithm. Both algorithms have achieved good results, however the second one was able to guide robot by best trajectories. / Exploração autônoma, em robótica, pode ser definida como o ato de mover-se em um ambiente, a princípio desconhecido, enquanto constrói-se um mapa deste ambiente. Uma grande parte da literatura relata vários problemas que se relacionam com a estratégia de exploração: percepção, localização, trajetória, controle e mapeamento. Este trabalho visa apresentar um algoritmo de exploração autonoma baseado em metaheurísticas. Para tanto, o problema de exploração autônoma de robôs móveis é formulado como um problema de otimização, fornecendo dados para que metaheurísticas sejam capazes de buscar pontos no espaço de soluções que representam posições no mapa em construção que melhor satisfaçam os objetivos da exploração. Metaheuristicas são metodos aproximados que garantem soluções suficientemente boas para problemas de otimização. A proposta foi implementada e incorporada como um módulo de otimização em um sistema de localização e mapeamento simultâneos que foi executado em ambiente Robot Operating System e mostrou-se capaz de guiar um robô simulado sem intervenção humana. As metaheurísticas usadas foram o Algoritmo Genético e o Algoritmo de Vagalumes. Ambos os algoritmos obtiveram bons resultados, no entanto o Algoritmo de Vagalumes guiou o robô por trajetórias melhores.

The use of micro aerial vehicles (MAV) for civilian use such as exploration and inspection of varying structures, equipment and areas have garnered some interest as of late. MAVs have the mobility and agility to traverse three dimensional space quickly and access hard to reach areas where other alternatives would struggle, but a flying platform such as a MAV comes with it’s own set of distinct problems. Almost any collision with the environment results in a complete failure of the platform. Any exploratory framework would need to perform obstacle avoidance and online path planning in a fully unknown environment with low computation times to ensure that the limited battery resources on the MAV is used in the most efficient way. In this thesis the exploratory rapidly-exploring random tree (ERRT) framework will be further optimized and an efficient strategy for finding valid exploration paths which are not in the immediate vicinity of the MAV will be developed and integrated. The method is demonstrated and proven through results from simulations and real life experiments.

Two crucial functionalities of a fully autonomous robotic agent are localization and navigation. The problem of enabling an agent to localize itself in an unknown environment is an extensive and widely studied topic. One of the main areas of this topic focuses on Simultaneous Localization and Mapping (SLAM). Many advancements in this field have been made over the years resulting in robust and accurate localization systems. Navigation progress has also improved substantially throughout the years resulting in efficient path planning algorithms and effective exploration strategies. Although an abundance of research exists on these two topics, less so exists about the combination of the two and their effect on each other. Therefore, the aim of this thesis was to integrate two state-of-the-art components from each respective area of research into a functioning system. This was done with the aim of studying the interconnectivity between these components while also documenting the integration process and identifying important considerations for similar future endeavours. Evaluations of the system showed that it performed with surprisingly good accuracy although it was severely lacking in robustness. Integration efforts showed good promise; however, it is clear that the two fields are heavily linked and need to be considered in a mutual context when it comes to a complete integrated system. / Förmågor som lokalisering och navigering är inom robotik förutsättande för att kunna möjliggöra en fullt autonom agent. Att för en agent kunna lokalisera sig i en okänd miljö är ett omfattande och brett studerat ämne, och ett huvudfokus inom ämnet är Simultaneous Localization and Mapping (SLAM) som avser lokalisering som sker parallellt med en aktiv kartläggning av omgivningen. Stora framsteg har gjorts inom detta område genom åren, vilket har resulterat i robusta och exakta system för robotlokalisering. Motsvarande framsteg inom robotnavigering har dessutom möjliggjort effektiva algoritmer och strategier för path planning och autonom utforskning. Trots den stora mängd forskning som existerar inom ämnena lokalisering och navigation var för sig, är samspelet mellan de två områdena samt möjligheten att sammankoppla de två aspekterna mindre studerat. I syfte att undersöka detta var målet med detta examensarbete således att integrera två toppmoderna system från de respektive områdena till ett sammankopplat system. Utöver att förmågorna och prestandan hos det integrerade systemet kunde studeras, genomfördes studien med avsikten att möjliggöra dokumentering av integrationsprocessen samt att viktiga insikter kring integrationen kunde identifieras i syfte att främja framtida studier inom samspelet mellan områdena lokalisering och navigation. Utvärderingar av det integrerade systemet påvisade en högre nivå av noggrannhet än förväntat, men fann en markant avsaknad av robusthet. Resultaten från integrationsarbetet anses lovande, och belyser framförallt att finns ett starkt samband mellan de två områdena samt att de bör beaktas i ett gemensamt kontext när de avses användas i ett komplett integrerat system.

Multi-agent information gathering (MA-IG) enables autonomous robots to cooperatively collect information in an unfamiliar area. In some scenarios, the focus is on gathering the true mapping of a physical quantity such as temperature or magnetic field. This thesis proposes a computationally efficient algorithm known as multi-agent RRT-clustered Stackelberg game (MA-RRTc-SG) to solve MA-IG. During exploration, measurements are taken along robot paths to update the belief of a Gaussian process (GP), which gives a continuous estimation of the physical process. To seek informative paths, agents first resort to self-planning: one individually generates a number of choices using sampling-based algorithms and preserves informative ones. Then, paths from different robots are combined and investigated based on a multi-player Stackelberg game. The Stackelberg game ensures robots select the combination of paths that yield maximum system reward. The reward function plays an important role in the aforementioned two steps. In our work, robots are awarded for selecting informative paths and punished for hazardous movements and large control inputs. In experiments, we first conduct variation studies to investigate the influence of key parameters in the proposed algorithm. Then, the algorithm is tested in a simulation case to map the radiation intensity in a nuclear plant. Results show that using our algorithm, robots are able to collect information in an efficient and cooperative way compared to random exploration. / Multi-agent informationsinsamling gör det möjligt för autonoma robotar att samarbeta samla in information i ett okänt område. I vissa scenarier ligger fokus på att samla in den verkliga kartläggningen av en fysisk storhet som temperatur eller magnetfält. Den här avhandlingen föreslår en beräkningseffektiv algoritm som kallas multi-agent RRT-clustered Stackelberg game (MA-RRTc-SG) för att lösa multi-agent informationsinsamling. Under prospektering görs mätningar längs robotbanor för att uppdatera tron på en Gaussisk process, vilket ger en kontinuerlig uppskattning av den fysiska processen. För att söka informativa vägar tillgriper agenter först självplanering: man genererar individuellt ett antal val med hjälp av samplingsbaserade algoritmer och bevarar informativa. Sedan kombineras och undersöks vägar från olika robotar utifrån en Stackelberg spel för flera spelare. Stackelberg spelet säkerställer att robotar väljer kombinationen av vägar som ger maximal systembelöning. Belöningsfunktionen spelar en viktig roll i de ovan nämnda två stegen. I vårt arbete belönas robotar för att välja informativa vägar och straffas för osäkra rörelser och stora kontrollingångar. I experiment genomför vi först variationsstudier för att undersöka inverkan av nyckelparametrar i den föreslagna algoritmen. Därefter testas algoritmen i ett simuleringsfall för att kartlägga strålningsintensiteten i ett kärnkraftverk. Resultaten visar att med vår algoritm kan robotar samla in information på ett effektivt och samarbetssätt jämfört med slumpmässig utforskning.

Dans la communauté robotique aérienne, un croissant intérêt pour les systèmes multirobot (SMR) est apparu ces dernières années. Cela a été motivé par i) les progrès technologiques, tels que de meilleures capacités de traitement à bord des robots et des performances de communication plus élevées, et ii) les résultats prometteurs du déploiement de SMR tels que l’augmentation de la zone de couverture en un minimum de temps. Le développement d’une flotte de véhicules aériens sans pilote (UAV: Unmanned Aerial Vehicle) et de véhicules aériens de petite taille (MAV: Micro Aerial Vehicle) a ouvert la voie à de nouvelles applications à grande échelle nécessitant les caractéristiques de tel système de systèmes dans des domaines tels que la sécurité, la surveillance des catastrophes et des inondations, la recherche et le sauvetage, l’inspection des infrastructures, et ainsi de suite. De telles applications nécessitent que les robots identifient leur environnement et se localisent. Ces tâches fondamentales peuvent être assurées par la mission d’exploration. Dans ce contexte, cette thèse aborde l’exploration coopérative d’un environnement inconnu en utilisant une équipe de drones avec vision intégrée. Nous avons proposé un système multi-robot où le but est de choisir des régions spécifiques de l’environnement à explorer et à cartographier simultanément par chaque robot de manière optimisée, afin de réduire le temps d’exploration et, par conséquent, la consommation d’énergie. Chaque UAV est capable d’effectuer une localisation et une cartographie simultanées (SLAM: Simultaneous Localization And Mapping) à l’aide d’un capteur visuel comme principale modalité de perception. Pour explorer les régions inconnues, les cibles – choisies parmi les points frontières situés entre les zones libres et les zones inconnues – sont assignées aux robots en considérant un compromis entre l’exploration rapide et l’obtention d’une carte détaillée. À des fins de prise de décision, les UAVs échangent habituellement une copie de leur carte locale, mais la nouveauté dans ce travail est d’échanger les points frontières de cette carte, ce qui permet d’économiser la bande passante de communication. L’un des points les plus difficiles du SMR est la communication inter-robot. Nous étudions cette partie sous les aspects topologiques et typologiques. Nous proposons également des stratégies pour faire face à l’abandon ou à l’échec de la communication. Des validations basées sur des simulations étendues et des bancs d’essai sont présentées. / In the aerial robotic community, a growing interest for Multi-Robot Systems (MRS) appeared in the last years. This is thanks to i) the technological advances, such as better onboard processing capabilities and higher communication performances, and ii) the promising results of MRS deployment, such as increased area coverage in minimum time. The development of highly efficient and affordable fleet of Unmanned Aerial Vehicles (UAVs) and Micro Aerial Vehicles (MAVs) of small size has paved the way to new large-scale applications, that demand such System of Systems (SoS) features in areas like security, disaster surveillance, inundation monitoring, search and rescue, infrastructure inspection, and so on. Such applications require the robots to identify their environment and localize themselves. These fundamental tasks can be ensured by the exploration mission. In this context, this thesis addresses the cooperative exploration of an unknown environment sensed by a team of UAVs with embedded vision. We propose a multi-robot framework where the key problem is to cooperatively choose specific regions of the environment to be simultaneously explored and mapped by each robot in an optimized manner in order to reduce exploration time and, consequently, energy consumption. Each UAV is able to performSimultaneous Localization And Mapping (SLAM) with a visual sensor as the main input sensor. To explore the unknown regions, the targets – selected from the computed frontier points lying between free and unknown areas – are assigned to robots by considering a trade-off between fast exploration and getting detailed grid maps. For the sake of decision making, UAVs usually exchange a copy of their local map; however, the novelty in this work is to exchange map frontier points instead, which allow to save communication bandwidth. One of the most challenging points in MRS is the inter-robot communication. We study this part in both topological and typological aspects. We also propose some strategies to cope with communication drop-out or failure. Validations based on extensive simulations and testbeds are presented.

Exploration is a fundamental problem in robotics that requires robots to navigate through unknown environments to autonomously gather information about their surroundings while executing collision-free paths. In this project, we propose a method for producing smooth paths during the exploration process in indoor environments using UAVs to improve battery efficiency and enhance the quality of pose estimation. The developed framework is built by merging two approaches that represent the state of the art in the field of autonomous exploration with UAVs. The overall exploration logic is given by GLocal, a paper that introduces a hybrid, i.e. both sampling-based and frontier-based, framework that is able to cope with the issue of odometry drift when exploring indoor environments due to the absence of absolute localization, e.g. through GNSS. The second approach is FUEL, which introduces a frontier-based exploration methodology which computes the ’drones path as an optimized non-uniform B-Spline. The framework described in this thesis borrows the optimized B-Spline trajectory generation from FUEL and implements it in GLocal. To do this, the original cost function defined by GLocal for each exploration viewpoint was modified and the resulting samples were used to select the initial control points of the B-Spline. Furthermore, we extended the underlying state machine governing the entire algorithm and we revisited the original re-planning logic. The presented system is evaluated in various simulated environments, showcasing the advantages and disadvantages of this method. These evaluations demonstrate its improved state estimation performance and absolute observed volume, albeit at the expense of longer traveled trajectories in big and complex environments. / Utforskning är ett grundläggande problem inom robotteknik som kräver att robotar navigerar genom okända miljöer för att autonomt samla in information om sin omgivning samtidigt som de utför kollisionsfria banor. I det här projektet föreslår vi en metod för att producera jämna banor under utforskningsprocessen i inomhusmiljöer med hjälp av UAV:er för att förbättra batterieffektiviteten och förbättra kvaliteten på posestimeringen. Det utvecklade ramverket bygger på en sammanslagning av två metoder som representerar den senaste tekniken inom autonom utforskning med UAV:er. Den övergripande utforskningslogiken ges av GLocal, en artikel som introducerar en hybrid, i.e. både samplingsbaserad och gränsbaserad, ram som kan hantera problemet med odometridrift vid utforskning av inomhusmiljöer på grund av frånvaron av absolut lokalisering, e.g. genom GNSS. Den andra metoden är FUEL, som introducerar en gränsbaserad utforskningsmetod som beräknar drönarens bana som en optimerad icke-uniform B-Spline. Ramverket som beskrivs i denna avhandling lånar den optimerade B-Spline-banegenereringen från FUEL och implementerar den i GLocal. För att göra detta modifierades den ursprungliga kostnadsfunktionen som definierades av GLocal för varje utforskningspunkt och de resulterande samplen användes för att välja de initiala kontrollpunkterna för B-Spline. Dessutom utökade vi den underliggande tillståndsmaskinen som styr hela algoritmen och vi reviderade den ursprungliga logiken för omplanering. Det presenterade systemet utvärderas i olika simulerade miljöer, vilket visar fördelarna och nackdelarna med denna metod. Dessa utvärderingar visar på förbättrad prestanda för tillståndsuppskattning och absolut observerad volym, om än på bekostnad av längre färdvägar i stora och komplexa miljöer.

The adoption of small-size Unmanned Aerial Vehicles (UAVs) in the commercial and professional sectors is rapidly growing. The miniaturisation of sensors and processors, the advancements in connected edge intelligence and the exponential interest in Artificial Intelligence (AI) are boosting the affirmation of autonomous nano-size drones in the Internet of Things (IoT) ecosystem. However, achieving safe autonomous navigation and high-level tasks like exploration and surveillance with these tiny platforms is extremely challenging due to their limited resources. Lightweight and reliable solutions to this challenge are subject to ongoing research. This work focuses on enabling the autonomous flight of a pocket-size, 30-gram platform called Crazyflie in a partially known environment. We implement a modular pipeline for the safe navigation of the nano drone between waypoints. In particular, we propose an AI-aided, vision-based reactive planning method for obstacle avoidance. We deal with the constraints of the nano drone by splitting the navigation task into two parts: a deep learning-based object detector runs on external hardware while the planning algorithm is executed onboard. For designing the reactive approach, we take inspiration from existing sensorbased navigation solutions and obtain a novel method for obstacle avoidance that does not rely on distance information. In the study, we also analyse the communication aspect and the latencies involved in edge offloading. Moreover, we share insights into the finetuning of an SSD MobileNet V2 object detector on a custom dataset of low-resolution, grayscale images acquired with the drone. The results show the ability to command the drone at ∼ 8 FPS and a model performance reaching a COCO mAP of 60.8. Field experiments demonstrate the feasibility of the solution with the drone flying at a top speed of 1 m/s while steering away from an obstacle placed in an unknown position and reaching the target destination. Additionally, we study the impact of a parameter determining the strength of the avoidance action and its influence on total path length, traversal time and task completion. The outcome demonstrates the compatibility of the communication delay and the model performance with the requirements of the real-time navigation task and a successful obstacle avoidance rate reaching 100% in the best-case scenario. By exploiting the modularity of the proposed working pipeline, future work could target the improvement of the single parts and aim at a fully onboard implementation of the navigation task, pushing the boundaries of autonomous exploration with nano drones. / Användningen av små obemannade flygfarkoster (UAV) inom den kommersiella och professionella sektorn ökar snabbt. Miniatyriseringen av sensorer och processorer, framstegen inom connected edge intelligence och det exponentiella intresset för artificiell intelligens (AI) ökar användningen av autonoma drönare i nanostorlek i ekosystemet för sakernas internet (IoT). Att uppnå säker autonom navigering och uppgifter på hög nivå, som utforskning och övervakning, med dessa små plattformar är dock extremt utmanande på grund av deras begränsade resurser. Lättviktiga och tillförlitliga lösningar på denna utmaning är föremål för pågående forskning. Detta arbete fokuserar på att möjliggöra autonom flygning av en 30-grams plattform i fickformat som kallas Crazyflie i en delvis känd miljö. Vi implementerar en modulär pipeline för säker navigering av nanodrönaren mellan riktpunkter. I synnerhet föreslår vi en AI-assisterad, visionsbaserad reaktiv planeringsmetod för att undvika hinder. Vi hanterar nanodrönarens begränsningar genom att dela upp navigeringsuppgiften i två delar: en djupinlärningsbaserad objektdetektor körs på extern hårdvara medan planeringsalgoritmen exekveras ombord. För att utforma den reaktiva metoden hämtar vi inspiration från befintliga sensorbaserade navigeringslösningar och tar fram en ny metod för hinderundvikande som inte är beroende av avståndsinformation. I studien analyserar vi även kommunikationsaspekten och de svarstider som är involverade i edge offloading. Dessutom delar vi med oss av insikter om finjusteringen av en SSD MobileNet V2-objektdetektor på en skräddarsydd dataset av lågupplösta gråskalebilder som tagits med drönaren. Resultaten visar förmågan att styra drönaren med ∼ 8 FPS och en modellprestanda som når en COCO mAP på 60.8. Fältexperiment visar att lösningen är genomförbar med drönaren som flyger med en topphastighet på 1 m/s samtidigt som den styr bort från ett hinder som placerats i en okänd position och når måldestinationen. Vi studerar även effekten av en parameter som bestämmer styrkan i undvikandeåtgärden och dess påverkan på den totala väglängden, tidsåtgången och slutförandet av uppgiften. Resultatet visar att kommunikationsfördröjningen och modellens prestanda är kompatibla med kraven för realtidsnavigering och ett lyckat undvikande av hinder som i bästa fall uppgår till 100%. Genom att utnyttja modulariteten i den föreslagna arbetspipelinen kan framtida arbete inriktas på förbättring av de enskilda delarna och syfta till en helt inbyggd implementering av navigeringsuppgiften, vilket flyttar gränserna för autonom utforskning med nano-drönare.