Résumé : Au Canada, annuellement il y a près de 10 000 personnes disparues. Pour les retrouver chaque fois une alerte est donnée. La police et les groupes de recherche terrestre spécialisés travaillent pour la retrouver, mais, par où commencer? Dans quelles directions orienter les recherches? Combien du temps pour balayer les différents secteurs? C’est souvent une question d’heures ou même des minutes pour la retrouver vivante. La théorie de recherche a trois concepts essentiels; la probabilité d’aire, la probabilité de détection et la probabilité de succès. Notre travail a cherché à préciser la probabilité d’aire. L’objectif de ce travail de recherche a consisté à développer un algorithme pour élaborer des cartes d’isochrones automatiques de la vitesse de marche probable des disparus. Il tient compte des restrictions dues aux variables environnementales (relief, occupation du sol, météorologie) et anthropiques (âge, sexe, taille, poids et activité physique). Le travail est développé au tour d’un système d’information géographique. Sur ceci nous distinguons deux groupes des données. Le premier correspond aux données attributaires que servent à générer la zone tampon et les facteurs de vitesse de l’individu. Ces données sont attachées à la couche du point initial. Dans le deuxième groupe, nous trouvons les données à référence spatiale intérieures à la zone tampon. Les facteurs de vitesse de l’individu et la carte de pentes génèrent la carte de vitesses par superficie. Les données de couverture de sol, quant à elles, produisent la carte de coût de traversée de la superficie. Finalement, la multiplication des deux dernières cartes produit la carte de coût de voyage, laquelle est le résultat essentiel pour concevoir la carte des courbes isochrones. Un algorithme a été construit et développé en langage de programmation Python. Il a été exécuté avec des données saisies dans l’environnement d’ArcGis 10.2. Nous avons observé une tendance des disparus à rester dans un rayon d’une heure de marche à partir du point initial (Pl). De plus, des variables comme les routes, sentiers et lignes de transport d’énergie influencent la marche. Finalement nous avons trouvé que l’outil aide au confinement de la probabilité d’aire. L’outil se démarque par sa simplicité d’usage. À l’intégration des facteurs de marche qui sont reliés à l’individu. Ainsi qu’à l’inclusion des facteurs météorologiques. Il peut s’exécuter partout au Canada. / Abstract : In Canada, annually there are about 10 000 missing persons. To find them whenever a warning is given. Police and specialized ground search groups work to find her, but where to start? In what directions guide research? How much time to scan the different sectors? It is often a matter of hours or even minutes to find her alive. The search theory has three basic concepts; the probability of area, the probability of detection and probability of success. Our work has sought to precise the probability of area in land search. The aim of this research was to develop an algorithm to make automatic isochrone maps that show the probability walking time of the missing person. It takes account of restrictions due to environmental variables (topography, land use, meteorology) and anthropogenic (age, sex, height, weight and physical activity). The work was developed around a geographic information system. On top of this, we distinguish two groups of data. The first is the attribute data that are used to generate the buffer zone and the individual speed factors. These data are attached to the initial planning point layer. In the second group, we find the internal spatial data in the buffer zone. The individual factors of speed and slope map produced the speed map. Ground cover data generated the cost map of crossing the area. Finally, the multiplication of the last two maps produced the travel cost map, which is the last step to design the isochrone map. An algorithm has been built and developed in the Python programming language. It was performed with the data entered into the ArcGIS 10.2 environment. We observed a trend of lost persons to stay around an hour's walk from the initial planning point (IPP). In addition, variables such as roads, paths and power transmission lines affect the walking speed. We found that the tool aid to precise the containment of probability of area. The tool is distinguished by its ease of use. With the integration of walking factors that are connected to the lost persons. We include meteorological factors. It can run across Canada.

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.

Os Veículos Aéreos Não Tripulados (VANTs) são ideais para operações de risco e estressante para o ser humano são as chamadas dull, dirty and dangerous missions. Portanto, uma importante aplicação desse tipo de robô aéreo diz respeito a operações de busca envolvendo múltiplos VANTs cooperativos, em que há risco de colisões entre aeronaves e o tempo de um voo é limitado, entre outros fatores, pela capacidade de um piloto trabalhar sem descanso. Entretanto, apesar de atualmente verificar-se um crescente número de pesquisas envolvendo VANTs e do grande potencial existente na utilização de VANTs, operações de busca cooperativas ainda não estão ocorrendo. Esse assunto é uma área de estudo multidisciplinar e nascente, que possui diversas linhas de pesquisa. Diferentes algoritmos de navegação e padrões de busca foram estudados visando selecionar o(s) mais adequado(s). Além disso, apresenta-se, neste trabalho, uma visão geral sobre os mecanismos de coordenação multiagente e avalia a adequação de cada uma delas à coordenação distribuída de agentes (VANTs), visando cooperação. Assim, com o objetivo de melhorar o desempenho de uma operação de busca, esta pesquisa de mestrado propõe um modelo de VANTs cooperativos que combina mecanismos de coordenação multiagente, algoritmos de navegação e padrões de busca estabelecidos pelos principais órgãos responsáveis pelas operações de busca e salvamento. Visando avaliar a sensibilidade do percentual médio de detecção de objetos, bem como o tempo médio de busca, foi desenvolvido um simulador e milhares de simulações foram realizadas. Observou-se que, utilizando o modelo, VANTs cooperativos podem reduzir, em média, 57% do tempo de busca (comparando com uma busca de dois VANTs não cooperativos no mesmo cenário), mantendo a probabilidade média de detecção dos objetos próxima de 100% e sobrevoando apenas 30% do espaço de busca. / There are an increasing number of researches into UAV (Unmanned Aerial Vehicle) in the literature. These robots are quite suitable to dull, dirty and dangerous missions. Thus, an important application of these vehicles is the search operations involving multiple UAVs in which there is risk of collisions among aircrafts and the flight time is limited by the maximum time of pilot working hours. However, despite the huge potential use of the UAVs, cooperative search operations with this kind of flying robots are not yet occurring. This research topic is a new and multidisciplinary area of study in its beginning and there are several issues that can be studied, such as centralized versus decentralized control, path planning for cooperative flights, agent reasoning for UAV tactical planning, safety assessments, reliability in automatic target reconnaissance by cameras, agent coordination mechanisms applied to UAV cooperation and the application itself. Different path planning algorithms were studied aiming to attain the most suitable to these kinds of operations, and the conclusions are presented. In addition, official documents of Search and Rescue operations are also studied in order to know the best practices already established for this kind of operations, and, finally, an overview of the coordination multi-agent theory is presented and evaluated to achieve the UAV coordination. This work proposes a model that combines path planning algorithms, search patterns and multi-agent coordination techniques to obtain a cooperative UAV model. The great goal for cooperative UAV is to achieve such performance that the performance of the group overcomes the sum of the individual performances isolatedly. Then, aiming to analyze the average percentage of objects detection, and the average search time, a simulator was developed and thousands of simulations were run. It was observed that, using the proposed model, two cooperative UAVs can perform a search operation 57% faster than two non cooperative UAVs, keeping the average probability of objects detection approaching at 100% and flying only 30% of the search space.

This paper aims to answer the question of how artificial intelligence could help humans maintain and/or improve situational awareness in search and rescue operations at sea, as well as where in such processes artificial intelligence could be incorporated to most efficiently compensate for human vulnerabilities and support human strengths. In order to answer this, a joint cognitive system perspective has been adopted whilst joining in search and rescue practice operations. These operations have been observed and persons participating in them have been interviewed, in order to gather insights about the process and the persons conducting it. The results from these insights coupled with experience with artificial intelligence and automation, show that artificial intelligence could help improve and/or maintain situational awareness by adopting functions which take up unnecessary time from man. According to the joint cognitive system view, these functions should never be solely performed by artificial intelligence however, but in coagency with man; allocated functions should overlap between man and machine. Suggestions have been given regarding which functions in particular an artificial intelligent agent could perform in terms of search and rescue and where these functions occur in the process. None of these suggestions are without man involvement, as they should not be. To summarise, these suggestions include; a UAV equipped with an infrared camera to search large areas quickly, a decision support system equipped with image recognition to analyse images gathered from the UAV, as well as a communication tool which allows for shared search patterns and hotspots between search and rescue units. / WARA-PS

Os Veículos Aéreos Não Tripulados (VANTs) são ideais para operações de risco e estressante para o ser humano são as chamadas dull, dirty and dangerous missions. Portanto, uma importante aplicação desse tipo de robô aéreo diz respeito a operações de busca envolvendo múltiplos VANTs cooperativos, em que há risco de colisões entre aeronaves e o tempo de um voo é limitado, entre outros fatores, pela capacidade de um piloto trabalhar sem descanso. Entretanto, apesar de atualmente verificar-se um crescente número de pesquisas envolvendo VANTs e do grande potencial existente na utilização de VANTs, operações de busca cooperativas ainda não estão ocorrendo. Esse assunto é uma área de estudo multidisciplinar e nascente, que possui diversas linhas de pesquisa. Diferentes algoritmos de navegação e padrões de busca foram estudados visando selecionar o(s) mais adequado(s). Além disso, apresenta-se, neste trabalho, uma visão geral sobre os mecanismos de coordenação multiagente e avalia a adequação de cada uma delas à coordenação distribuída de agentes (VANTs), visando cooperação. Assim, com o objetivo de melhorar o desempenho de uma operação de busca, esta pesquisa de mestrado propõe um modelo de VANTs cooperativos que combina mecanismos de coordenação multiagente, algoritmos de navegação e padrões de busca estabelecidos pelos principais órgãos responsáveis pelas operações de busca e salvamento. Visando avaliar a sensibilidade do percentual médio de detecção de objetos, bem como o tempo médio de busca, foi desenvolvido um simulador e milhares de simulações foram realizadas. Observou-se que, utilizando o modelo, VANTs cooperativos podem reduzir, em média, 57% do tempo de busca (comparando com uma busca de dois VANTs não cooperativos no mesmo cenário), mantendo a probabilidade média de detecção dos objetos próxima de 100% e sobrevoando apenas 30% do espaço de busca. / There are an increasing number of researches into UAV (Unmanned Aerial Vehicle) in the literature. These robots are quite suitable to dull, dirty and dangerous missions. Thus, an important application of these vehicles is the search operations involving multiple UAVs in which there is risk of collisions among aircrafts and the flight time is limited by the maximum time of pilot working hours. However, despite the huge potential use of the UAVs, cooperative search operations with this kind of flying robots are not yet occurring. This research topic is a new and multidisciplinary area of study in its beginning and there are several issues that can be studied, such as centralized versus decentralized control, path planning for cooperative flights, agent reasoning for UAV tactical planning, safety assessments, reliability in automatic target reconnaissance by cameras, agent coordination mechanisms applied to UAV cooperation and the application itself. Different path planning algorithms were studied aiming to attain the most suitable to these kinds of operations, and the conclusions are presented. In addition, official documents of Search and Rescue operations are also studied in order to know the best practices already established for this kind of operations, and, finally, an overview of the coordination multi-agent theory is presented and evaluated to achieve the UAV coordination. This work proposes a model that combines path planning algorithms, search patterns and multi-agent coordination techniques to obtain a cooperative UAV model. The great goal for cooperative UAV is to achieve such performance that the performance of the group overcomes the sum of the individual performances isolatedly. Then, aiming to analyze the average percentage of objects detection, and the average search time, a simulator was developed and thousands of simulations were run. It was observed that, using the proposed model, two cooperative UAVs can perform a search operation 57% faster than two non cooperative UAVs, keeping the average probability of objects detection approaching at 100% and flying only 30% of the search space.

In the field of VLSI circuit optimization, the scaling of semiconductor devices has led to the miniaturization of the feature sizes resulting in a significant increase in the integration density and size of the circuits. At the nanometer level, due to the effects of manufacturing process variations, the design optimization process has transitioned from the deterministic domain to the stochastic domain, and the inter-relationships among the specification parameters like delay, power, reliability, noise and area have become more intricate. New methods are required to examine these metrics in a unified manner, thus necessitating the need for multi-metric optimization. The optimization algorithms need to be accurate and efficient enough to handle large circuits. As the size of an optimization problem increases significantly, the ability to cluster the design metrics or the parameters of the problem for computational efficiency as well as better analysis of possible trade-offs becomes critical. In this dissertation research, several utilitarian methods are investigated for variation aware multi-metric optimization in VLSI circuit design and spatial pattern clustering. A novel algorithm based on the concepts of utility theory and risk minimization is developed for variation aware multi-metric optimization of delay, power and crosstalk noise, through gate sizing. The algorithm can model device and interconnect variations independent of the underlying distributions and works by identifying a deterministic linear equivalent model from a fundamentally stochastic optimization problem. Furthermore, a multi-metric gate sizing optimization framework is developed that is independent of the optimization methodology, and can be implemented using any mathematical programming approach. It is generalized and reconfigurable such that the metrics can be selected, removed, or prioritized for relative importance depending upon the design requirements. In multi-objective optimization, the existence of multiple conflicting objectives makes the clustering problem challenging. Since game theory provides a natural framework for examining conflicting situations, a game theoretic algorithm for multi-objective clustering is introduced in this dissertation research. The problem of multi-metric clustering is formulated as a normal form multi-step game and solved using Nash equilibrium theory. This algorithm has useful applications in several engineering and multi-disciplinary domains which is illustrated by its mapping to the problem of robot team formation in the field in multi-emergency search and rescue. The various algorithms developed in this dissertation achieve significantly better optimization and run times as compared to other methods, ensure high utility levels, are deterministic in nature and hence can be applied to very large designs. The algorithms have been rigorously tested on the appropriate benchmarks and data sets to establish their efficacy as feasible solution methods. Various quantitative sensitivity analysis have been performed to identify the inter-relationships between the various design parameters.

This thesis presents how unmanned aerial vehicles (UAVs) can successfully assist in search and rescue (SAR) operations using wireless localization. The zone-grid to partition to capture/detect WiFi probe requests follows the concepts found in Search Theory Method. The UAV has attached a sensor, e.g., WiFi sniffer, to capture/detect the WiFi probes from victims or lost people’s smartphones. Applying the Random-Forest based machine learning algorithm, an estimation of the user's location is determined with a 81.8% accuracy. UAV technology has shown limitations in the navigational performance and limited flight time. Procedures to optimize these limitations are presented. Additionally, how the UAV is maneuvered during flight is analyzed, considering different SAR flight patterns and Li-Po battery consumption rates of the UAV. Results show that controlling the UAV by remote-controll detected the most probes, but it is less power efficient compared to control it autonomously.

This dissertation presents a suite of design tools for multi-agent systems that address three main areas: network design, decentralized controller generation, and the synthesis of decentralized control strategies by combining individual decentralized controllers. First, a new metric for quantifying heterogeneity in multi-agent systems is presented based on combining different notions of entropy, and is shown to overcome the drawbacks associated with existing diversity metrics in various scientific fields. Moreover, a new method of controlling multi-agent networks through the single-leader network paradigm is presented where by directly exploiting the homogeneity of agent capabilities, a network which is not completely controllable can be driven closer to a desired target configuration than by using traditional control techniques. An algorithm is presented for generating decentralized control laws that allow for agents to best satisfy a desired global objective, while taking into account network topological constraints and limitations on how agents can compute their control signals. Then, a scripting tool is developed to aid in specifying sequences of decentralized controllers to be executed consecutively, while helping ensure that the required network topological requirements needed for each controller to execute properly are maintained throughout mode switches. Finally, the underlying concepts behind the developed tools are showcased in three example applications: distributed merging and spacing for heterogeneous aircraft during terminal approaches, collaborative multi-UAV convoy protection in dynamic environments, and an educational tool used to teach a graduate-level networked controls course at the Georgia Institute of Technology.

This research investigated the Mission Specialist role in micro unmanned aerial systems (mUAS) and was informed by human-robot interaction (HRI) and technology findings, resulting in the design of an interface that increased the individual performance of 26 untrained CBRN (chemical, biological, radiological, nuclear) responders during two field studies, and yielded formative observations for HRI in mUAS. Findings from the HRI literature suggested a Mission Specialist requires a role-specific interface that shares visual common ground with the Pilot role and allows active control of the unmanned aerial vehicle (UAV) payload camera. Current interaction technology prohibits this as responders view the same interface as the Pilot and give verbal directions for navigation and payload control. A review of interaction principles resulted in a synthesis of five design guidelines and a system architecture that were used to implement a Mission Specialist interface on an Apple iPad. The Shared Roles Model was used to model the mUAS human-robot team using three formal role descriptions synthesized from the literature (Flight Director, Pilot, and Mission Specialist). The Mission Specialist interface was evaluated through two separate field studies involving 26 CBRN experts who did not have mUAS experience. The studies consisted of 52 mission trials to surveil, evaluate, and capture imagery of a chemical train derailment incident staged at Disaster City. Results from the experimental study showed that when a Mission Specialist was able to actively control the UAV payload camera and verbally coordinate with the Pilot, greater role empowerment (confidence, comfort, and perceived best individual and team performance) was reported by a majority of participants for similar tasks; thus, a role-specific interface is preferred and should be used by untrained responders instead of viewing the same interface as the Pilot in mUAS. Formative observations made during this research suggested: i) establishing common ground in mUAS is both verbal and visual, ii) type of coordination (active or passive) preferred by the Mission Specialist is affected by command-level experience and perceived responsibility for the robot, and iii) a separate Pilot role is necessary regardless of preferred coordination type in mUAS. This research is of importance to HRI and CBRN researchers and practitioners, as well as those in the fields of robotics, human-computer interaction, and artificial intelligence, because it found that a human Pilot role is necessary for assistance and understanding, and that there are hidden dependencies in the human-robot team that affect Mission Specialist performance.

published_or_final_version / Architecture / Master / Master of Architecture