In this thesis, the viability of decentralized, noncooperative multi-robot path planning algorithms is tested. Three algorithms based on the Batch Informed Trees (BIT*) algorithm are presented. The first of these algorithms combines Optimal Reciprocal Collision Avoidance (ORCA) with BIT*. The second of these algorithms uses BIT* to create a path which the robots then follow using an artificial potential field (APF) method. The final algorithm is a version of BIT* that supports replanning. While none of these algorithms take advantage of sharing information between the robots, the algorithms are able to guide the robots to their desired goals, with the algorithm that combines ORCA and BIT* having the robots successfully navigate to their goals over 93% for multiple environments with teams of two to eight robots.

Multi-robot systems leverage the numbers and characteristics of different robots to accomplish an overall mission. Efficient task allocation and motion planning of multi-robot teams are essential to ensure each robot's actions contribute to the overall mission while avoiding conflict with each other. The original contribution of this thesis is an optimized, efficient, and multi-factor task allocation algorithm to comprise the main component of a task coordination framework (TCF), with motion planning as a secondary component. This algorithm determines which robot performs which tasks and in what order. It presents a novel solution to the multiple robot task allocation problem (MRTA) as an extension of the multiple travelling salesmen (MTSP) problem. This extension to the MTSP considers operational factors representing physical limitations, the suitability of each robot, and inter-task dependencies. The task allocation algorithm calculates an optimized distribution of tasks such that a global objective function is minimized to simultaneously reduce total cost and ensure an even distribution of tasks among the agents. Once an optimized distribution of tasks is calculated, the motion planning component calculates collision-free velocities to drive the robots to their goal poses to facilitate task execution in a shared environment. The proposed TCF was implemented on teams of unmanned air vehicles (UAVs) and unmanned ground vehicles (UGVs). Test cases considered scenarios where the UAVs executed aerial observation tasks while UGVs executed simulated patrol and delivery tasks. The solutions were tested using real-life robots as a proof of concept and to validate simulations. The robots' kinematic and computer vision models were combined with the task coordination framework to facilitate the implementation. Large-scale simulations involving greater numbers of robots operating in a larger area were also conducted to demonstrate the task coordination framework's versatility and efficacy.

Multi-robot systems have recently witnessed a swell in interest in the past few years because of their various applications such as agricultural autonomy, medical robotics, industrial and commercial automation and, search and rescue. In this thesis, we particularly investigate the behavior of multi-robot systems with respect to stable topology control in asymmetric interaction settings. From theoretical perspective, we first classify stable topologies, and identify the conditions under which we can determine whether a topology is stable or not. Then, we design a limited fields-of-view (FOV) controller for robots that use sensors like cameras for coordination which induce asymmetric robot to robot interactions. Finally, we conduct a rigorous theoretical analysis to qualitatively determine which interactions are suitable for stable directed topology control of multi-robot systems with asymmetric interactions. In this regard, we solve an optimal topology selection problem to determine the topology with the best interactions based on a suitable metric that represents the quality of interaction. Further, we solve this optimal problem distributively and validate the distributed optimization formulation with extensive simulations.  For experimental purposes, we developed a portable multi-robot testbed which enables us to conduct multi-robot topology control experiments in both indoor and outdoor settings and validate our theoretical findings. Therefore, the contribution of this thesis is two fold: i) We provide rigorous theoretical analysis of  stable coordination of multi-robot systems with directed graphs, demonstrating the graph structures that induce stability for a broad class of coordination objectives; ii) We develop a testbed that enables validating multi-robot topology control in both indoor and outdoor settings. / Doctor of Philosophy / In this thesis, we address the problem of collaborative tasks in a multi-robot system where we investigate how interactions within members of the multi-robot system can induce instability. We conduct rigorous theoretical analysis and identify when the system will be unstable and hence classify interactions that will lead to stable multi-robot coordination. Our theoretical analysis tries to emulate realistic interactions in a multi-robot system such as limited interactions (blind spots) that exist when on-board cameras are used to detect and track other robots in the vicinity. So we study how these limited interactions induce instability in the multi-robot system. To verify our theoretical analysis experimentally,  we developed a portable multi-robot testbed that enables us to test our theory on stable coordination of multi-robot system with a team of Unmanned Aerial Vehicles (UAVs) in both indoor and outdoor settings. With this feature of the testbed we are able to investigate the difference in the multi-robot system behavior when tested in controlled indoor environments versus an uncontrolled outdoor environment. Ultimately, the motivation behind this thesis is to emulate realistic conditions for multi-robot cooperation and investigate suitable conditions for them to work in a stable and safe manner. Therefore, our contribution is twofold ; i) We provide rigorous theoretical analysis that enables stable coordination of multi-robot systems with limited interactions induced by sensor capabilities such as cameras; ii) We developed a testbed that enables testing of our theoretical contribution with a team of real robots in realistic environmental conditions.

We study the problem of viewpoint planning in static and dynamic scenes using multi-robot teams. This work is motivated by two applications: bridge inspection and environmental monitoring using Unmanned Aerial Vehicles. For static scenes, we are given a set of target points in a polygonal environment that must be monitored using robots with cameras. The goal is to compute a tour for all the robots such that every target is visible from at least one tour. We solve this problem optimally by reducing it to Generalized Travelling Salesman Problem. For dynamic scenes, we study the multi-robot assignment problem for multi-target tracking. The problem can be viewed as the mixed packing and covering problem. We optimally solve the problem using Mixed Quadratic Integer Linear Program to maximize the total number of targets covered. In addition to theoretical contribution, we also present our hardware system design and findings from field experiments. / Master of Science

The evolution of cloud computing has finally started to affect robotics. Indeed, there have been several real-time cloud applications making their way into robotics as of late. Inherent benefits of cloud robotics include providing virtually infinite computational power and enabling collaboration of a multitude of connected devices. However, its drawbacks include higher latency and overall higher energy consumption. Moreover, local devices in proximity incur higher latency when communicating among themselves via the cloud. At the same time, the cloud is a single point of failure in the network. Fog Computing is an extension of the cloud computing paradigm providing data, compute, storage and application services to end-users on a so-called edge layer. Distinguishing characteristics are its support for mobility and dense geographical distribution. We propose to study the implications of applying fog computing concepts in robotics by developing a middle-ware solution for Robotic Fog Computing Cluster solution for enabling adaptive distributed computation in heterogeneous multi-robot systems interacting with the Internet of Things (IoT). The developed middle-ware has a modular plug-in architecture based on micro-services and facilitates communication of IOT devices with the multi-robot systems. In addition, the developed middle-ware solutions support different load balancing or task allocation algorithms. In particular, we establish that we can enhance the performance of distributed system by decreasing overall system latency by using already established multi-criteria decision-making algorithms like TOPSIS and TODIM with naive Q-learning and with Neural Network based Q-learning. / Master of Science

In this thesis, we propose algorithms designed for monitoring hazardous agents. Because hazardous environmental monitoring is either tedious or dangerous for human operators, we seek a fully automated robotic system that can help humans. However, there are still many challenges from hardware design to algorithm design that restrict robots to be applied to practical applications. Among these challenges, we are particularly interested in dealing with algorithmic challenges primarily caused by sensing and communication limitations of robots. We develop algorithms with provable guarantees that map and track hazards using a team of robots. Our contributions are as follows. First, we address a situation where the number of hazardous agents is unknown and varies over time. We propose a search and tracking framework that can extract individual target tracks as well as estimate the number and the spatial density of targets. Second, we consider a team of robots tracking individual targets under limited bandwidth. We develop distributed algorithms that can find solutions in bounded amount of time. Third, we propose an algorithm for aerial robots that explores a translating hazardous plume of unknown size and shape. We present a recursive depth-first search-based algorithm that yields a constant competitive ratio for exploring a translating plume. Last, we take into account a heterogeneous team of robots to map and sample a translating plume. These contributions can be applied to a team of aerial robots and a robotic boat monitoring and sampling a translating hazardous plume over a lake. In this application, the aerial robots coordinate with each other to explore the plume and to inform the robotic boat while the robotic boat collects water samples for offline analysis. We demonstrate the performance of our algorithms through simulations and proof-of-concept field experiments for real-world environmental monitoring. / Doctor of Philosophy / Quick response to hazards is crucial as the hazards may put humans at risk and thorough removal of hazards may take a substantial amount of time. Our vision is that the introduction of a robotic solution would be beneficial for hazardous environmental monitoring. Not only the fact that humans can be released from dangerous or tedious tasks, but we also can take advantage of the robot's agile maneuverability and its precise sensing. However, the development on both hardware and software is not yet ripe to be able to deploy autonomous robots in real-world scenarios. Moreover, partial and uncertain information of hazards impose further challenges. In this these, we present various research problems addressing these challenges in hazardous environmental monitoring. Particularly, we are interested in overcoming challenges from the perspective of software by designing planning and decision-making algorithms for robots. We validate our proposed algorithms through extensive simulations and real-world experiments.

Connected and Automated Vehicles (CAVs) represent a growing area of study in robotics and automotive research. Their potential benefits of increased traffic flow, reduced on-road accident, and improved fuel economy make them an attractive option. While some autonomous features such as Adaptive Cruise Control and Lane Keep Assist are already integrated into consumer vehicles, they are limited in scope and require innovation to realize fully autonomous vehicles. This work addresses the design problems of perception and planning in CAVs. A decentralized sensor fusion system is designed using Multi-target tracking to identify targets within a vehicle's field of view, enumerate each target with the lane it occupies, and highlight the most important object (MIO) for Adaptive cruise control. Its performance is tested using the Optimal Sub-pattern Assignment (OSPA) metric and correct assignment rate of the MIO. The system has an average accuracy assigning the MIO of 98%. The rest of this work considers the coordination of multiple CAVs from a multi-agent motion planning perspective. A centralized planning algorithm is applied to a space similar to a traffic intersection and is demonstrated empirically to be twice as fast as existing multi-agent planners., making it suitable for real-time planning environments. / Master of Science / Connected and Automated Vehicles are an emerging area of research that involve integrating computational components to enable autonomous driving. This work considers two of the major challenges in this area of research. The first half of this thesis considers how to design a perception system in the vehicle that can correctly track other vehicles and assess their relative importance in the environment. A sensor fusion system is designed which incorporates information from different sensor types to form a list of relevant target objects. The rest of this work considers the high-level problem of coordination between autonomous vehicles. A planning algorithm which plans the paths of multiple autonomous vehicles that is guaranteed to prevent collisions and is empirically faster than existing planning methods is demonstrated.

Many applications for field robots can benefit from large numbers of robots, especially applications where the objective is for the robots to cover or explore a region. A key enabling technology for robust autonomy in these teams of small and cheap robots is the development of collaborative perception to account for the shortcomings of the small and cheap sensors on the robots. In this dissertation, I present DDF-SAM to address the decentralized data fusion (DDF) inference problem with a smoothing and mapping (SAM) approach to single-robot mapping that is online, scalable and consistent while supporting a variety of sensing modalities. The DDF-SAM approach performs fully decentralized simultaneous localization and mapping in which robots choose a relevant subset of variables from their local map to share with neighbors. Each robot summarizes their local map to yield a density on exactly this chosen set of variables, and then distributes this summarized map to neighboring robots, allowing map information to propagate throughout the network. Each robot fuses summarized maps it receives to yield a map solution with an extended sensor horizon. I introduce two primary variations on DDF-SAM, one that uses a batch nonlinear constrained optimization procedure to combine maps, DDF-SAM 1.0, and one that uses an incremental solving approach for substantially faster performance, DDF-SAM 2.0. I validate these systems using a combination of real-world and simulated experiments. In addition, I evaluate design trade-offs for operations within DDF-SAM, with a focus on efficient approximate map summarization to minimize communication costs.

Le but de cette thèse est d'étendre l'état de l'art par des contributions sur le comportement collectif d'un groupe de robots volants, à savoir des quadrirotors UAV. Afin de pouvoir sûrement naviguer dans un environnement, ces derniers peuvent se reposer uniquement sur leurs capacités à bord et non sur des systèmes centralisés (e.g., Vicon ou GPS). Nous réalisons cet objectif en offrant une possible solution aux problèmes de contrôle en formation et de localisation à partir de mesures à bord et via une communication locale. Nous abordons ces problèmes exploitant différents concepts provenant de la théorie des graphes algébriques et de la théorie de la rigidité. Cela nous permet de résoudre ces problèmes de façon décentralisée et de proposer des algorithmes décentralisés capables de prendre en compte également des limites sensorielles classiques. Les capacités embarquées que nous avons mentionnées plus tôt sont représentées par une caméra monoculaire et une centrale inertielle (IMU) auxquelles s'ajoute la capacité de chaque robot à communiquer (par RF) avec certains de ses voisins. Cela est dû au fait que l'IMU et la caméra représentent une possible configuration économique et légère pour la navigation et la localisation autonome d'un quadrirotor UAV. / The aim of this Thesis is to give contributions to the state of the art on the collective behavior of a group of flying robots, specifically quadrotor UAVs, which can only rely on their onboard capabilities and not on a centralized system (e.g., Vicon or GPS) in order to safely navigate in the environment. We achieve this goal by giving a possible solution to the problems of formation control and localization from onboard sensing and local communication. We tackle these problems exploiting mainly concepts from algebraic graph theory and the so-called theory of rigidity. This allows us to solve these problems in a decentralized fashion, and propose decentralized algorithms able to also take into account some typical sensory limitations. The onboard capabilities we referred to above are represented by an onboard monocular camera and an inertial measurement unit (IMU) in addition to the capability of each robot to communicate (through RF) with some of its neighbors. This is due to the fact that an IMU and a camera represent a possible minimal, lightweight and inexpensive configuration for the autonomous localization and navigation of a quadrotor UAV.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-03-09T12:13:05Z No. of bitstreams: 1 rafaeljosefonsecadesa.pdf: 2699281 bytes, checksum: ca2455c138265324b1a8fcbb6075da41 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-03-10T12:58:01Z (GMT) No. of bitstreams: 1 rafaeljosefonsecadesa.pdf: 2699281 bytes, checksum: ca2455c138265324b1a8fcbb6075da41 (MD5) / Made available in DSpace on 2017-03-10T12:58:01Z (GMT). No. of bitstreams: 1 rafaeljosefonsecadesa.pdf: 2699281 bytes, checksum: ca2455c138265324b1a8fcbb6075da41 (MD5) Previous issue date: 2016-09-09 / Com a evolução da tecnologia, estão aumentando as aplicabilidades dos robôs em nosso meio. Em alguns casos, a utilização de sistemas com múltiplos robôs autônomos trabalhando em cooperação se torna uma ótima alternativa. Há várias pesquisas em andamento na área de robótica com o intuito de aprimorar estas tarefas. Entre estas pesquisas estão os sistemas de patrulhamento. Neste trabalho, o sistema de patrulhamento utilizando múltiplos robôs é implementado considerando a série de chegada de alertas nas estações de monitoramento e o robô pode andar somente em uma única direção. Devido ao número de estações que podem entrar em alerta e ao número de robôs, o controle desse sistema se torna complexo. Como a finalidade de um sistema de patrulhamento é atender possíveis alertas de invasores, é imprescindível que haja uma resposta rápida do controlador responsável para que um robô logo seja encaminhado com o propósito de atender a esse alerta. No caso de sistemas com múltiplos robôs, é necessário que haja uma coordenação do controlador para que os robôs possam atender o máximo de alertas possíveis em um menor instante de tempo. Para resolver esse problema, foi utilizado um controlador composto por uma técnica inteligente de otimização bioinspirada chamada de “Algoritmo Genético” (AG). Este controlador centraliza todas as decisões de controle dos robôs, sendo responsável por orientá-los em relação aos movimentos e captação de informação. As decisões são tomadas com o intuito de maximizar a recompensa do sistema. Esta recompensa é composta pelo ganho de informação do sistema e por uma penalização gerada pela demora em atender aos alertas ativados. Foram feitas simulações com a intenção de verificar a eficácia desse controlador, comparando-o com um controlador utilizando heurísticas pré-definidas. Essas simulações comprovaram a eficiência do controlador via Algoritmo Genético. Devido ao fato do controlador via AG analisar o sistema como um todo enquanto que o controlador heurístico analisa apenas o estágio atual, foi possível observar que a distribuição dos robôs no mapa permitia um atendimento mais ágil às estações com alerta ativados, assim como uma maior aquisição de informações do local. Outro fato importante foi em relação à complexidade do sistema. Foi notado que quanto maior a complexidade do sistema, ou seja, quanto maior o número de robôs e de estações, melhor era a eficiência do controlador via Algoritmo Genético em relação ao controlador heurístico. / New technologies have been considerable advances, and consequently, thus allows the robot appearance as an integral part of our daily lives. In recent years, the design of cooperative multi-robot systems has become a highly active research area within robotics. Cooperative multi-robot systems (MRS) have received significant attention by the robotics community for the past two decades, because their successful deployment have unquestionable social and economical relevance in many application domain. There are several advantages of using multi-robot systems in different application and task. The development and conception of patrolling methods using multi-robot systems is a scientific area which has a growing interest. This work, the patrol system using multiple robots is implemented considering the series of arrival of alerts in the monitoring stations known and the robot was limited to move in one direction. Due to the large number of stations that can assume alert condition and due to the large number of robots, the system control becomes extremely complex. Patrol systems are usually designed for surveillance. An efficient controller permits a patrol in a way that maximizes their chances of detecting an adversary trying to penetrate through the patrol path. The obvious advantage of multi-robot exploration is its concurrency, which can greatly reduce the time needed for the mission. Coordination among multiple robots is necessary to achieve efficiency in robotic explorations. When working in groups, robots need to coordinate their activities. However, a Genetic Algorithm approach was implemented to carryout an optimized control action provided from the controller. In fact the controller determines the robot's behavior. The decision strategies are implemented in order to maximize the system response. The present work deals with a computational study of controller based on Genetic Algorithm and it comparison with another controller based pre-defined heuristics. The simulation results show the efficiency of the proposed controller based on Genetic Algorithm, when compared with the controller based on heuristics. The right decisions from the controller based on Genetic Algorithm allowed a better distribution of the robots on the map leading to fast service stations with active alert, as well as increased acquisition of location information. Another important fact was regarding the complexity of the system. Also, as a result, it was noticed an excellent efficiency of the controller based on Genetic Algorithm when the existence of the large number of robots and stations.