Considered in this research is a framework for effective formation control of multirobot systems in dynamic environments. The basic formation control involves two important considerations: (1) Real-time trajectory generation algorithms for distributed control based on nominal agent models, and (2) robust tracking of reference trajectories under model uncertainties. Proposed is a two-layer hierarchical architecture for collectivemotion control ofmultirobot nonholonomic systems. It endows robotic systems with the ability to simultaneously deal with multiple tasks and achieve typical complex formation missions, such as collisionfree maneuvers in dynamic environments, tracking certain desired trajectories, forming suitable patterns or geometrical shapes, and/or varying the pattern when necessary. The study also addresses real-time formation tracking of reference trajectories under the presence of model uncertainties and proposes robust control laws such that over each time interval any tracking errors due to system uncertainties are driven down to zero prior to the commencement of the subsequent computation segment. By considering a class of nonlinear systems with favorable finite-time convergence characteristics, sufficient conditions for exponential finite-time stability are established and then applied to distributed formation tracking controls. This manifests in the settling time of the controlled system being finite and no longer than the predefined reference trajectory segment computing time interval, thus making tracking errors go to zero by the end of the time horizon over which a segment of the reference trajectory is generated. This way the next segment of the reference trajectory is properly initialized to go into the trajectory computation algorithm. Consequently this could lead to a guarantee of desired multi-robot motion evolution in spite of system uncertainties. To facilitate practical implementation, communication among multi-agent systems is considered to enable the construction of distributed formation control. Instead of requiring global communication among all robots, a distributed communication algorithm is employed to eliminate redundant data propagation, thus reducing energy consumption and improving network efficiency while maintaining connectivity to ensure the convergence of formation control.

Like computer architects, robot designers must address multiple, possibly competing, requirements by balancing trade-offs in terms of processing, memory, communication, and energy to satisfy design objectives. However, robot architects currently lack the design guidelines, organizing principles, rules of thumb, and tools that computer architects rely upon. This thesis takes a step in this direction, by analyzing the roles of heterogeneity and distribution in robot systems architecture. This thesis takes a systems architecture approach to the design of robot systems, and in particular, investigates the use of distributed, heterogeneous platforms to exploit locality in robot systems design. We show how multiple, distributed heterogeneous platforms can serve as general purpose robot systems for three distinct domains with different design objectives: increasing availability in a search and rescue mission, increasing flexibility and ease-of-use for a personal educational robot, and decreasing the computation and sensing resources necessary for navigation and foraging tasks.

Multi-robot systems are an established research area with a growing number of applications. Efficient coordination in such systems usually requires knowledge of robot positions and the global map. This work presents a novel map-merging algorithm for merging 3D point cloud maps in multi-robot systems, which produces the global map and estimates robot positions. The algorithm is based on feature- matching transformation estimation with a novel descriptor matching scheme and works solely on point cloud maps without any additional auxiliary information. The algorithm can work with different SLAM approaches and sensor types and it is applicable in heterogeneous multi-robot systems. The map-merging algorithm has been evaluated on real-world datasets captured by both aerial and ground-based robots with a variety of stereo rig cameras and active RGB-D cameras. It has been evaluated in both indoor and outdoor environments. The proposed algorithm was implemented as a ROS package and it is currently distributed in the ROS distribution. To the best of my knowledge, it is the first ROS package for map-merging of 3D maps.

abstract: Robotic technology is advancing to the point where it will soon be feasible to deploy massive populations, or swarms, of low-cost autonomous robots to collectively perform tasks over large domains and time scales. Many of these tasks will require the robots to allocate themselves around the boundaries of regions or features of interest and achieve target objectives that derive from their resulting spatial configurations, such as forming a connected communication network or acquiring sensor data around the entire boundary. We refer to this spatial allocation problem as boundary coverage. Possible swarm tasks that will involve boundary coverage include cooperative load manipulation for applications in construction, manufacturing, and disaster response. In this work, I address the challenges of controlling a swarm of resource-constrained robots to achieve boundary coverage, which I refer to as the problem of stochastic boundary coverage. I first examined an instance of this behavior in the biological phenomenon of group food retrieval by desert ants, and developed a hybrid dynamical system model of this process from experimental data. Subsequently, with the aid of collaborators, I used a continuum abstraction of swarm population dynamics, adapted from a modeling framework used in chemical kinetics, to derive stochastic robot control policies that drive a swarm to target steady-state allocations around multiple boundaries in a way that is robust to environmental variations. Next, I determined the statistical properties of the random graph that is formed by a group of robots, each with the same capabilities, that have attached to a boundary at random locations. I also computed the probability density functions (pdfs) of the robot positions and inter-robot distances for this case. I then extended this analysis to cases in which the robots have heterogeneous communication/sensing radii and attach to a boundary according to non-uniform, non-identical pdfs. I proved that these more general coverage strategies generate random graphs whose probability of connectivity is Sharp-P Hard to compute. Finally, I investigated possible approaches to validating our boundary coverage strategies in multi-robot simulations with realistic Wi-fi communication. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2016

Neste trabalho foi desenvolvido um estudo comparativo entre duas estratégias básicas para a combinação de mapas parciais baseados em marcos para sistemas multirobô: a estratégia por associação de marcos e a estratégia por distância relativa entre os robôs (também conhecida por rendez-vous). O ambiente simulado corresponde a um entorno plano povoado de árvores que são mapeadas por uma equipe de dois robôs móveis equipados com sensores laser para medir a largura e localização de cada _arvore (marco). Os mapas parciais são estimados usando o algoritmo FastSLAM. Além do estudo comparativo propõe-se também um algoritmo alternativo de localização e mapeamento simultâneos para multirrobôs cooperativos, utilizando as observações entre os robôs não só para o cálculo da transformação de coordenadas, mas também no desenvolvimento de um processo seqüencial para atualizar o alinhamento entre os mapas, explorando de forma mais eficiente as observações entre robôs. Os experimentos realizados demonstraram que o algoritmo proposto pode conduzir a resultados significativamente melhores em termos de precisão quando comparado com a abordagem de combinação de mapas tradicional (usando distância relativa entre os robôs). / In this text a comparative survey between the two basic strategies used to combine partial landmark based maps in multi-robot systems, data association and inter-robot observations (known as rendezvous), is presented. The simulated environment is a at place populated by trees, which are going to be mapped by a two-mobile robot team equipped with laser range finders in order to measure every tree (landmark) location and width. Partial maps are estimated using the algorithm FastSLAM. Besides the comparative study it is also proposed an alternative algorithm for Simultaneous Localization and Mapping (SLAM) in multi-robot cooperative systems. It uses observations between robots (detections) not only for calculating the coordinate transformation but also in the development of a sequential process for updating the alignment between maps, exploiting in a more efficient way the inter-robot observations. The experiments showed that the algorithm can lead to significantly better results in terms of accuracy when compared with the traditional approach of combining maps (using the relative distance between robots).

abstract: One potential application of multi-robot systems is collective transport, a task in which multiple mobile robots collaboratively transport a payload that is too large or heavy to be carried by a single robot. Numerous control schemes have been proposed for collective transport in environments where robots can localize themselves (e.g., using GPS) and communicate with one another, have information about the payload's geometric and dynamical properties, and follow predefined robot and/or payload trajectories. However, these approaches cannot be applied in uncertain environments where robots do not have reliable communication and GPS and lack information about the payload. These conditions characterize a variety of applications, including construction, mining, assembly in space and underwater, search-and-rescue, and disaster response. Toward this end, this thesis presents decentralized control strategies for collective transport by robots that regulate their actions using only their local sensor measurements and minimal prior information. These strategies can be implemented on robots that have limited or absent localization capabilities, do not explicitly exchange information, and are not assigned predefined trajectories. The controllers are developed for collective transport over planar surfaces, but can be extended to three-dimensional environments. This thesis addresses the above problem for two control objectives. First, decentralized controllers are proposed for velocity control of collective transport, in which the robots must transport a payload at a constant velocity through an unbounded domain that may contain strictly convex obstacles. The robots are provided only with the target transport velocity, and they do not have global localization or prior information about any obstacles in the environment. Second, decentralized controllers are proposed for position control of collective transport, in which the robots must transport a payload to a target position through a bounded or unbounded domain that may contain convex obstacles. The robots are subject to the same constraints as in the velocity control scenario, except that they are assumed to have global localization. Theoretical guarantees for successful execution of the task are derived using techniques from nonlinear control theory, and it is shown through simulations and physical robot experiments that the transport objectives are achieved with the proposed controllers. / Dissertation/Thesis / Doctoral Dissertation Mechanical Engineering 2020

abstract: The need for incorporating game engines into robotics tools becomes increasingly crucial as their graphics continue to become more photorealistic. This thesis presents a simulation framework, referred to as OpenUAV, that addresses cloud simulation and photorealism challenges in academic and research goals. In this work, OpenUAV is used to create a simulation of an autonomous underwater vehicle (AUV) closely following a moving autonomous surface vehicle (ASV) in an underwater coral reef environment. It incorporates the Unity3D game engine and the robotics software Gazebo to take advantage of Unity3D's perception and Gazebo's physics simulation. The software is developed as a containerized solution that is deployable on cloud and on-premise systems. This method of utilizing Gazebo's physics and Unity3D perception is evaluated for a team of marine vehicles (an AUV and an ASV) in a coral reef environment. A coordinated navigation and localization module is presented that allows the AUV to follow the path of the ASV. A fiducial marker underneath the ASV facilitates pose estimation of the AUV, and the pose estimates are filtered using the known dynamical system model of both vehicles for better localization. This thesis also investigates different fiducial markers and their detection rates in this Unity3D underwater environment. The limitations and capabilities of this Unity3D perception and Gazebo physics approach are examined. / Dissertation/Thesis / Masters Thesis Computer Science 2020

In this dissertation, we study multi-robot coordination in the context of multi-target tracking. Specifically, we are interested in the coordination achieved by means of submodular function optimization. Submodularity encodes the diminishing returns property that arises in multi-robot coordination. For example, the marginal gain of assigning an additional robot to track the same target diminishes as the number of robots assigned increases. The advantage of formulating coordination problems as submodular optimization is that a simple, greedy algorithm is guaranteed to give a good performance. However, often this comes at the expense of unrealistic models and assumptions. For example, the standard formulation does not take into account the fact that robots may fail, either randomly or due to adversarial attacks. When operating in uncertain conditions, we typically seek to optimize the expected performance. However, this does not give any flexibility for a user to seek conservative or aggressive behaviors from the team of robots. Furthermore, most coordination algorithms force robots to communicate at each time step, even though they may not need to. Our goal in this dissertation is to overcome these limitations by devising coordination algorithms that are parsimonious in communication, allow a user to manage the risk of the robot performance, and are resilient to worst-case robot failures and attacks. In the first part of this dissertation, we focus on designing parsimonious communication strategies for target tracking. Specifically, we investigate the problem of determining when to communicate and who to communicate with. When the robots use range sensors, the tracking performance is a function of the relative positions of the robots and the targets. We propose a self-triggered communication strategy in which a robot communicates its own position with its neighbors only when a certain set of conditions are violated. We prove that this strategy converges to the optimal robot positions for tracking a single target and in practice, reduces the number of communication messages by 30%. When tracking multiple targets, we can reduce the communication by forming subsets of robots and assigning one subset to track a target. We investigate a number of measures for tracking quality based on the observability matrix and show which ones are submodular and which ones are not. For non-submodular measures, we show a greedy algorithm gives a 1/(n+1) approximation, if we restrict the subset to n robots. In optimizing submodular functions, a common assumption is that the function value is deterministic, which may not hold in practice. For example, the sensor performance may depend on environmental conditions which are not known exactly. In the second part of the dissertation, we design an algorithm for stochastic submodular optimization. The standard formulation for stochastic optimization optimizes the expected performance. However, the expectation is a risk-neutral measure. Instead, we optimize the Conditional Value-at-Risk (CVaR), which allows the user the flexibility of choosing a risk level. We present an algorithm, based on the greedy algorithm, and prove that its performance has bounded suboptimality and improves with running time. We also present an online version of the algorithm to adapt to real-time scenarios. In the third part of this dissertation, we focus on scenarios where a set of robots may fail naturally or due to adversarial attacks. Our objective is to track as many targets as possible, a submodular measure, assuming worst-case robot failures. We present both centralized and distributed resilient tracking algorithms to cope with centralized and distributed communication settings. We prove these algorithms give a constant-factor approximation of the optimal in polynomial running time. / Doctor of Philosophy / Today, robotics and autonomous systems have been increasingly used in various areas such as manufacturing, military, agriculture, medical sciences, and environmental monitoring. However, most of these systems are fragile and vulnerable to adversarial attacks and uncertain environmental conditions. In most cases, even if a part of the system fails, the entire system performance can be significantly undermined. As robots start to coexist with humans, we need algorithms that can be trusted under real-world, not just ideal conditions. Thus, this dissertation focuses on enabling security, trustworthiness, and long-term autonomy in robotics and autonomous systems. In particular, we devise coordination algorithms that are resilient to attacks, trustworthy in the face of the uncertain conditions, and allow the long-term operation of multi-robot systems. We evaluate our algorithms through extensive simulations and proof-of-concept experiments. Generally speaking, multi-robot systems form the "physical" layer of Cyber-Physical Sytems (CPS), the Internet of Things (IoT), and Smart City. Thus, our research can find applications in the areas of connected and autonomous vehicles, intelligent transportation, communications and sensor networks, and environmental monitoring in smart cities.

We study the problem of planning a tour for an energy-limited Unmanned Aerial Vehicle (UAV) to visit a set of sites in the least amount of time. We envision scenarios where the UAV can be recharged along the way either by landing on stationary recharging stations or on Unmanned Ground Vehicles (UGVs) acting as mobile recharging stations. This leads to a new variant of the Traveling Salesperson Problem (TSP) with mobile recharging stations. We present an algorithm that finds not only the order in which to visit the sites but also when and where to land on the charging stations to recharge. Our algorithm plans tours for the UGVs as well as determines the best locations to place stationary charging stations. While the problems we study are NP-Hard, we present a practical solution using Generalized TSP that finds the optimal solution. If the UGVs are slower, the algorithm also finds the minimum number of UGVs required to support the UAV mission such that the UAV is not required to wait for the UGV. We present a calibration routine to identify parameters that are needed for our algorithm as well as simulation results that show the running time is acceptable for reasonably sized instances in practice. We evaluate the performance of our algorithm through simulations and proof-of-concept experiments with a fully autonomous system of one UAV and UGV. / Master of Science / Commercially available Unmanned Aerial Vehicles (UAVs), especially multi-rotor aircrafts, have a flight time of less than 30 minutes. However many UAV applications, such as surveillance, package delivery, and infrastructure monitoring, require much longer flight times. To address this problem, we present a system in which an Unmanned Ground Vehicle (UGV) can recharge the UAV during deployments. This thesis studies the problem of finding when, where, and how much to recharge the battery. We also allow for the UGV to recharge while moving from one site to another. We present an algorithm that finds the paths for the UAV and UGV to visit a set of points of interest in the least time possible. We also present algorithms for cases when the UGV is slower than the UAV, and more than one UGV may be required. We evaluate our algorithms through simulations and proof-of-concept experiments.

In various industries, such as manufacturing, logistics, agriculture, defense, search and rescue, and transportation, Multi-robot systems (MRSs) are increasingly gaining popularity. These systems involve multiple robots working together towards a shared objective, either autonomously or under human supervision. However, as MRSs operate in uncertain or even adversarial environments, and the sensors and actuators of each robot may be error-prone, they are susceptible to faults and security threats unique to MRSs. Classical techniques from distributed systems cannot detect or mitigate these threats. In this dissertation, novel techniques are proposed to enhance the security and fault-tolerance of MRSs through inter-robot observations and accusations. A fundamental security property is proposed for MRSs, which ensures that forbidden deviations from a desired multi-robot motion plan by the system supervisor are detected. Relying solely on self-reported motion information from the robots for monitoring deviations can leave the system vulnerable to attacks from a single compromised robot. The concept of co-observations is introduced, which are additional data reported to the supervisor to supplement the self-reported motion information. Co-observation-based detection is formalized as a method of identifying deviations from the expected motion plan based on discrepancies in the sequence of co-observations reported. An optimal deviation-detecting motion planning problem is formulated that achieves all the original application objectives while ensuring that all forbidden plan-deviation attacks trigger co-observation-based detection by the supervisor. A secure motion planner based on constraint solving is proposed as a proof-of-concept to implement the deviation-detecting security property. The security and resilience of MRSs against plan deviation attacks are further improved by limiting the information available to attackers. An efficient algorithm is proposed that verifies the inability of an attacker to stealthily perform forbidden plan deviation attacks with a given motion plan and announcement scheme. Such announcement schemes are referred to as horizon-limiting. An optimal horizon-limiting planning problem is formulated that maximizes planning lookahead while maintaining the announcement scheme as horizon-limiting. Co-observations and horizon-limiting announcements are shown to be efficient and scalable in protecting MRSs, including systems with hundreds of robots, as evidenced by a case study in a warehouse setting. Lastly, the Decentralized Blocklist Protocol (DBP), a method for designing Byzantine-resilient decentralized MRSs, is introduced. DBP is based on inter-robot accusations and allows cooperative robots to identify misbehavior through co-observations and share this information through the network. The method is adaptive to the number of faulty robots and is widely applicable to various decentralized MRS applications. It also permits fast information propagation, requires fewer cooperative observers of application-specific variables, and reduces the worst-case connectivity requirement, making it more scalable than existing methods. Empirical results demonstrate the scalability and effectiveness of DBP in cooperative target tracking, time synchronization, and localization case studies with hundreds of robots. The techniques proposed in this dissertation enhance the security and fault-tolerance of MRSs operating in uncertain and adversarial environments, aiding in the development of secure MRSs for emerging applications.