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

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

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.

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.

Ao observar a situação atual, na qual atos de vandalismo e terrorismo tornaram-se frequentes e cada vez mais presentes ao redor do mundo, principalmente em grandes cidades, torna-se clara a necessidade de equipar as forças policiais com tecnologias de observação e monitoramento inteligentes, capazes de identificar e monitorar indivíduos potencialmente perigosos que possam estar infiltrados nas multidões. Ao mesmo tempo, com sua recente popularização, veículos aéreos não tripulados, também chamados VANTs e conhecidos popularmente como "drones", acabaram por tornar-se ferramentas baratas e eficientes para diversas aplicações, incluindo observação, fornecendo a seus utilizadores a capacidade de monitorar alvos, áreas, ou prédios de forma segura e quase imperceptível. Unindo estas duas tendências, este trabalho apresenta o desenvolvimento de um sistema multi-VANT para observção de alvos móveis em multidões, demonstrando a possibilidade de utilização de pequenos VANTs comerciais comuns para o monitoramento de grupos de pedestres. O principal objetivo de tal sistema é monitorar continuamente indivíduos de interesse em um grupo de pessoas, visitando cada um destes indivíduos alternadamente, de forma a manter um registro geral do estado de cada um deles Um sistema deste tipo poderia, por exemplo, ser utilizado por autoridades no controle de manifestações e outras atividades em que grandes grupos de pessoas estejam envolvidos, ajudando a polícia e outros órgãos a identificar indivíduos com comportamento suspeito ou agressivo mais rapidamente, evitando ou minimizando os efeitos de atitudes de vandalismo e de ataques terroristas. Com o intuíto de abordar tal problema da forma mais completa e adequada possível, esta tese apresenta a concepção e o desenvolvimento de um sistema híbrido composto de três diferentes algoritmos: um algoritmo de distribuição de alvos; um de roteamento; e um de repasse de alvos. Primeiramente, neste sistema, um algoritmo de distribuição de alvos baseado em um paradigma de mercado que simula um leilão distribui os alvos entre os VANTs da melhor forma possível. Os VANTs, por sua vez, utilizam um algoritmo genético de roteamento para resolver uma instância do Problema do Caixeiro Viajante e decidir a melhor rota para visitar cada alvo sob sua responsabilidade. Ao mesmo tempo, o sistema analisa a necessidade de redistribuição dos alvos, ativando um algoritmo capaz de realizar esta ação ao perceber sua necessidade quando na iminência de perder algum alvo de vista. Ao fim de seu desenvolvimento, o sistema proposto foi testado em uma série de experimentos especialmente desenvolvidos para avaliar seu desempenho em situações controladas e comprovar sua eficiência para realizar a missão pretendida. / Observing the current scenario, where terrorism and vandalism acts have become commonplace, particularly in big cities, it becomes clear the need to equip law enforcement forces with an efficient observation method, capable of identifying and observing potentially threatening individuals on crowds, to avoid or minimize damage in case of attacks. Moreover, with the popularization of small lightweight Unmanned Aerial Vehicles (UAVs), these have become an affordable and efficient tool, which can be used to track and follow targets or survey areas or buildings quietly, safely and almost undetectably. This work presents the development of a multi-UAV based crowd monitoring system, demonstrating a system that uses small Commercial Of The Shelf (COTS) UAVs to periodically monitor a group of moving walking individuals. The goal of this work is to develop a coordination system for a swarm of UAVS capable of continuously monitoring a large group of individuals (targets) in a crowd, alternately observing each of them at a time while trying to not lose sight of any of these targets. A system equipped with a group of UAVs running this proposal can be used for law-enforcement applications, assisting authorities to monitor crowds in order to identify and to follow suspicious individuals that can have attitudes that could be classified as vandalism or linked to terrorist attack attempts To address this problem a system composed of three parts is proposed and was developed in this thesis. First, an auction algorithm was put in place to distribute interest targets among the multiple UAVs. The UAVs, in turn, make use of a genetic algorithm to calculate the order in which they would visit each of the targets on their observation queue. Moreover, a target handover algorithm was also implemented to redistribute targets among the UAVs in case the system judged that a target was about to be lost by its current observer UAV. The proposed system was evaluated through a set of experiments set-up to verify and to demonstrate the system capabilities to perform such monitoring task, proving its efficiency. During these experiments, it is made clear that the system as a whole has a great potential to solve this kind of moving target monitoring problem that can be mapped to a Time Dependent Travel Salesman Problem (TDTSP), observing targets, and redistributing them among UAVs as necessary during the mission.

Ao observar a situação atual, na qual atos de vandalismo e terrorismo tornaram-se frequentes e cada vez mais presentes ao redor do mundo, principalmente em grandes cidades, torna-se clara a necessidade de equipar as forças policiais com tecnologias de observação e monitoramento inteligentes, capazes de identificar e monitorar indivíduos potencialmente perigosos que possam estar infiltrados nas multidões. Ao mesmo tempo, com sua recente popularização, veículos aéreos não tripulados, também chamados VANTs e conhecidos popularmente como "drones", acabaram por tornar-se ferramentas baratas e eficientes para diversas aplicações, incluindo observação, fornecendo a seus utilizadores a capacidade de monitorar alvos, áreas, ou prédios de forma segura e quase imperceptível. Unindo estas duas tendências, este trabalho apresenta o desenvolvimento de um sistema multi-VANT para observção de alvos móveis em multidões, demonstrando a possibilidade de utilização de pequenos VANTs comerciais comuns para o monitoramento de grupos de pedestres. O principal objetivo de tal sistema é monitorar continuamente indivíduos de interesse em um grupo de pessoas, visitando cada um destes indivíduos alternadamente, de forma a manter um registro geral do estado de cada um deles Um sistema deste tipo poderia, por exemplo, ser utilizado por autoridades no controle de manifestações e outras atividades em que grandes grupos de pessoas estejam envolvidos, ajudando a polícia e outros órgãos a identificar indivíduos com comportamento suspeito ou agressivo mais rapidamente, evitando ou minimizando os efeitos de atitudes de vandalismo e de ataques terroristas. Com o intuíto de abordar tal problema da forma mais completa e adequada possível, esta tese apresenta a concepção e o desenvolvimento de um sistema híbrido composto de três diferentes algoritmos: um algoritmo de distribuição de alvos; um de roteamento; e um de repasse de alvos. Primeiramente, neste sistema, um algoritmo de distribuição de alvos baseado em um paradigma de mercado que simula um leilão distribui os alvos entre os VANTs da melhor forma possível. Os VANTs, por sua vez, utilizam um algoritmo genético de roteamento para resolver uma instância do Problema do Caixeiro Viajante e decidir a melhor rota para visitar cada alvo sob sua responsabilidade. Ao mesmo tempo, o sistema analisa a necessidade de redistribuição dos alvos, ativando um algoritmo capaz de realizar esta ação ao perceber sua necessidade quando na iminência de perder algum alvo de vista. Ao fim de seu desenvolvimento, o sistema proposto foi testado em uma série de experimentos especialmente desenvolvidos para avaliar seu desempenho em situações controladas e comprovar sua eficiência para realizar a missão pretendida. / Observing the current scenario, where terrorism and vandalism acts have become commonplace, particularly in big cities, it becomes clear the need to equip law enforcement forces with an efficient observation method, capable of identifying and observing potentially threatening individuals on crowds, to avoid or minimize damage in case of attacks. Moreover, with the popularization of small lightweight Unmanned Aerial Vehicles (UAVs), these have become an affordable and efficient tool, which can be used to track and follow targets or survey areas or buildings quietly, safely and almost undetectably. This work presents the development of a multi-UAV based crowd monitoring system, demonstrating a system that uses small Commercial Of The Shelf (COTS) UAVs to periodically monitor a group of moving walking individuals. The goal of this work is to develop a coordination system for a swarm of UAVS capable of continuously monitoring a large group of individuals (targets) in a crowd, alternately observing each of them at a time while trying to not lose sight of any of these targets. A system equipped with a group of UAVs running this proposal can be used for law-enforcement applications, assisting authorities to monitor crowds in order to identify and to follow suspicious individuals that can have attitudes that could be classified as vandalism or linked to terrorist attack attempts To address this problem a system composed of three parts is proposed and was developed in this thesis. First, an auction algorithm was put in place to distribute interest targets among the multiple UAVs. The UAVs, in turn, make use of a genetic algorithm to calculate the order in which they would visit each of the targets on their observation queue. Moreover, a target handover algorithm was also implemented to redistribute targets among the UAVs in case the system judged that a target was about to be lost by its current observer UAV. The proposed system was evaluated through a set of experiments set-up to verify and to demonstrate the system capabilities to perform such monitoring task, proving its efficiency. During these experiments, it is made clear that the system as a whole has a great potential to solve this kind of moving target monitoring problem that can be mapped to a Time Dependent Travel Salesman Problem (TDTSP), observing targets, and redistributing them among UAVs as necessary during the mission.