One of the applications where the use of robots can be beneficial is Wilderness Search and Rescue (WiSAR), which involves the search for a possibly mobile but non-trackable lost person (i.e., the target) in wilderness environments. A mobile target implies that the search area grows continuously and potentially without bound. This fact, combined with the presence of typically rugged, varying terrain and the possibility of inclement weather, poses a considerable challenge to human Search and Rescue (SAR) personnel with respect to the time and effort required to perform the search and the danger entailed to the searchers. Mobile robots can be advantageous in WiSAR due to their ability to provide consistent performance without getting tired and their lower susceptibility to harsh weather conditions compared to humans. Thus, a coordinated team of robots that can assist human SAR personnel by autonomously performing searches in WiSAR scenarios would be of great value. However, to date, a suitable multi-robot coordination methodology for autonomous search that can satisfactorily address the issues relevant to WiSAR is lacking. The objective of this Dissertation is, thus, to develop a methodology that can autonomously coordinate the search strategy of a multi-robot team in wilderness environments to locate a moving target that is neither continuously nor intermittently observed during the search process. Three issues in particular are addressed: (i) target-location prediction, (ii) robot deployment, and (iii) robot-path planning. The corresponding solution approaches devised to address these issues incorporate the influence of varying terrain that may contain a priori known and unknown obstacles, and deal with unique target physiology and psychology as well as found clues left behind by the target. The solution methods for these three tasks work seamlessly together resulting in a tractable MRC methodology for autonomous robotic WiSAR. Comprehensive simulations have been performed that validate the overall proposed methodology. Moreover, the tangible benefits provided by this methodology were further revealed through its comparison with an alternative search method.

One of the applications where the use of robots can be beneficial is Wilderness Search and Rescue (WiSAR), which involves the search for a possibly mobile but non-trackable lost person (i.e., the target) in wilderness environments. A mobile target implies that the search area grows continuously and potentially without bound. This fact, combined with the presence of typically rugged, varying terrain and the possibility of inclement weather, poses a considerable challenge to human Search and Rescue (SAR) personnel with respect to the time and effort required to perform the search and the danger entailed to the searchers. Mobile robots can be advantageous in WiSAR due to their ability to provide consistent performance without getting tired and their lower susceptibility to harsh weather conditions compared to humans. Thus, a coordinated team of robots that can assist human SAR personnel by autonomously performing searches in WiSAR scenarios would be of great value. However, to date, a suitable multi-robot coordination methodology for autonomous search that can satisfactorily address the issues relevant to WiSAR is lacking. The objective of this Dissertation is, thus, to develop a methodology that can autonomously coordinate the search strategy of a multi-robot team in wilderness environments to locate a moving target that is neither continuously nor intermittently observed during the search process. Three issues in particular are addressed: (i) target-location prediction, (ii) robot deployment, and (iii) robot-path planning. The corresponding solution approaches devised to address these issues incorporate the influence of varying terrain that may contain a priori known and unknown obstacles, and deal with unique target physiology and psychology as well as found clues left behind by the target. The solution methods for these three tasks work seamlessly together resulting in a tractable MRC methodology for autonomous robotic WiSAR. Comprehensive simulations have been performed that validate the overall proposed methodology. Moreover, the tangible benefits provided by this methodology were further revealed through its comparison with an alternative search method.

Game theory can work as a coordination mechanism in multi-agent robotic systems by representing each robot as a player in a game. In ideal scenarios, game theory algorithms guarantee convergence to optimal configurations and have been widely studied for many applications. However, most of the studies focus on theoretical analysis and lack the details of complete demonstrations. In this regard, we implemented a real-time multi-robot system in order to investigate how game-theoretic methods perform in non-idealized settings. An aerial coverage problem was modeled as a potential game, where each aerial vehicle is an independent decision-making player. These players take actions under limited communication, and each is equipped with onboard vision capabilities. Three game-theoretic methods have been modified and implemented to solve this problem. All computations are performed using onboard devices, independent of any ground entity. The performance of the system is analyzed and compared with different tests and configurations

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.

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 / 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 static 2D or 3D environment such as a bridge. Target points are key locations that we are interested to monitor using cameras on the robots. The goal is to compute a tour for all the robots such that every target location is visible from at least one robot’s tour. We want to minimize the sum of lengths of all the robot’s tours combined. We find the best possible solution for this problem. For dynamic scenes, we study the multi-robot trajectory assignment problem for multi-target tracking. Here, the target points may be moving, e.g., expanding plumes in an oil spill. The goal in this is to maximize the total number of targets covered at each time step. We provide the best possible solution in this case. In addition to theoretical contribution, we also present our hardware system design and findings from field experiments.

Analysis, design and implementation of cooperative control strategies for multi-robot systems under communication constraints is the topic of this thesis. Motivated by a rapidly growing number of applications with networked robots and other vehicles, fundamental limits on the achievable collaborative behavior are studied for large teams of autonomous agents. In particular, a problem is researched in detail in which the group of agents is supposed to agree on a common state without any centralized coordination. Due to the dynamics of the individual agents and their varying connectivity, this problemis an extension of the classical consensus problemin computer science. It captures a crucial component of many desirable features of multi-robot systems, such as formation, flocking, rendezvous, synchronizing and covering. Analytical bounds on the convergence rate to consensus are derived for several systemconfigurations. It is shown that static communication networks that exhibit particular symmetries yield slow convergence, if the connectivity of each agent does not scale with the total number of agents. On the other hand, some randomly varying networks allow fast convergence even if the connectivity is low. It is furthermore argued that if the data being exchanged between the agents are quantized, it may heavily degrade the performance. The extent to which certain quantization schemes are more suitable than others is quantified through relations between the number of agents and the required total network bit rate. The design of distributed coordination and estimation schemes based on the consensus algorithm is presented. A receding horizon coordination strategy utilizing subgradient optimization is developed. Robustness and implementation aspects are discussed. A new collaborative estimation method is also proposed. The implementation of multi-robot control systems is difficult due to the high systemcomplexity. In the final part of this thesis, a hierarchical control architecture appropriate for a class of coordination tasks is therefore suggested. It allows a formal verification of the correctness of the implemented control algorithms. / QC 20100920

The task assignment problem is one of the fundamental combinatorial optimization problems. It has been extensively studied in operation research, management science, computer science and robotics. Task assignment problems arise in various applications of multi-robot systems (MRS), such as environmental monitoring, disaster response, extraterrestrial exploration, sensing data collection and collaborative autonomous manufacturing. In these MRS applications, there are realistic constraints on robots and tasks that must be taken into account both from the modeling perspective and the algorithmic perspective. From the modeling aspect, such constraints include (a) Task group constraints: where tasks form disjoint groups and each robot can be assigned to at most one task in each group. One example of the group constraints comes from tightly-coupled tasks, where multiple micro tasks form one tightly-coupled macro task and need multiple robots to perform each simultaneously. (b) Task deadline constraints: where tasks must be assigned to meet their deadlines. (c) Dynamically-arising tasks: where tasks arrive dynamically and the payoffs of future tasks are unknown. Such tasks arise in scenarios like searchrescue, where new victims are found dynamically. (d) Robot budget constraints: where the number of tasks each robot can perform is bounded according to the resource it possesses (e.g., energy). From the solution aspect, there is often a need for decentralized solution that are implemented on individual robots, especially when no powerful centralized controller exists or when the system needs to avoid single-point failure or be adaptive to environmental changes. Most existing algorithms either do not consider the above constraints in problem modeling, are centralized or do not provide formal performance guarantees. In this thesis, I propose methods to address these issues for two classes of problems, namely, the constrained linear assignment problem and constrained generalized assignment problem. Constrained linear assignment problem belongs to P, while constrained generalized assignment problem is NP-hard. I develop decomposition-based distributed auction algorithms with performance guarantees for both problem classes. The multi-robot assignment problem is decomposed into an optimization problem for each robot and each robot iteratively solving its own optimization problem leads to a provably good solution to the overall problem. For constrained linear assignment problem, my approaches provides an almost optimal solution. For constrained generalized assignment problem, I present a distributed algorithm that provides a solution within a constant factor of the optimal solution. I also study the online version of the task allocation problem with task group constraints. For the online problem, I prove that a repeated greedy version of my algorithm gives solution with constant factor competitive ratio. I include simulation results to evaluate the average-case performance of the proposed algorithms. I also include results on multi-robot cooperative package transport to illustrate the approach.

Advances in mobile robot technology allow an increasing variety of applications to be imagined, including: search and rescue, exploration of unknown areas and working with hazardous materials. State of the art robots are able to behave autonomously and without direct human control, using on-board devices to perceive, navigate and reason about the world. Unmanned Aerial Vehicles (UAVs) are particularly well suited to performing advanced sensing tasks by moving rapidly through the environment irrespective of the terrain. Deploying groups of mobile robots offers advantages, such as robustness to individual failures and a reduction in task completion time. However, to operate efficiently these teams require specific approaches to enable the individual agents to cooperate. This thesis proposes coordinated approaches to search scenarios for teams of UAVs. The primary application considered is Wilderness Search and Rescue (WiSaR), although the techniques developed are applicable elsewhere. A novel frontier-based search approach is developed for rotor-craft UAVs, taking advantage of available terrain information to minimise altitude changes during flight. This is accompanied by a lightweight coordination mechanism to enable cooperative behaviour with minimal additional overhead. The concept of a team rendezvous is introduced, at which all team members attend to exchange data. This also provides an ideal opportunity to create a comprehensive team solution to relay newly gathered data to a base station. Furthermore, the delay between sensing and the acquired data becoming available to mission commanders is analysed and a technique proposed for adapting the team to meet a latency requirement. These approaches are evaluated and characterised experimentally through simulation. Coordinated frontier search is shown to outperform greedy walk methods, reducing redundant sensing coverage using only a minimal coordination protocol. Combining the search, rendezvous and relay techniques provides a holistic approach to the deployment of UAV teams, meeting mission objectives without extensive pre-configuration.