A Data-Driven Approach to Locating and Routing Unmanned Aerial Vehicles for Disaster Area Reconnaissance

Cette thèse présente un cadre général visant l’exploitation des données météorologiques pour aider à planifier l’utilisation d’un véhicule aérien sans pilote (UAV) muni de capteurs pour aider les équipes de recherche et de sauvetage à analyser une zone impactée par une tornade. Cette thèse utilise les bases des problèmes de planification des tournées, d’assignation et de détermination dynamique des routes de véhicules. Nous nous appuyons sur ces principes en incorporant des données historiques sur les tornades afin de rechercher plus efficacement une zone impactée par une tornade. En effet, la localisation et le trajet des tornades ne sont pas totalement aléatoires. Dans cette thèse, nous cherchons à exploiter les données historiques pour développer des stratégies de recherche afin d’évaluer les zones touchées par les tornades de manière plus efficace. Nous démontrons tout d’abord comment les données météorologiques et les données spatiales relatives aux tornades peuvent être incorporées dans les procédures de recherche et de sauvetage afin d’acheminer les UAV adéquatement. Nous développons une méthode d’acheminement des UAV à l’aide de l’ensemble des données historiques disponibles. Nous analysons également les compromis entre le temps nécessaire pour créer des points de passage et la valeur de la fonction objectif. On observe qu’il est possible d’utiliser des «méthodes exactes» pour générer des points de passage. Ainsi, l’heuristique que nous proposons permet de déployer UAV plus rapidement. Ensuite, nous présentons une méthode et une solution pour le localisation d’UAV dans l’état d’Oklahoma à l’aide de données historiques sur les tornades, basées sur des modèles de couverture et d’acheminement des véhicules à stations multiples. Lors de l’affectation des UAV, nous découvrons qu’il faut jusqu’à 70% de UAV en plus pour obtenir une couverture suffisante, alors qu’il n’y a que 5% de chances qu’un UAV donné ne puisse pas voler. Enfin, nous exploitons les données historiques pour identifier plus efficacement l’étendue de la zone impactée par une tornade. Nous constatons que l’utilisation des tendances historiques des tornades permet de réduire de 2% le temps nécessaire à l’identification de l’étendue de la zone touchée (30% des tournées de UAV ne sont pas du tout déterminés de manière dynamique). Cette thèse constitue une première étape pour appuyer les chercheurs et les sauveteurs avec l’utilisation des données météorologiques et d’autres données d’experts. Cette thèse fournit également un contexte et des opportunités supplémentaires pour l’utilisation des détecteurs de signaux sans fil. Cette thèse contient également d’autres propositions, comme la quantification du compromis entre l’utilisation de méthodes exactes et d’heuristiques et leur impact sur la mise en oeuvre d’une solution, ainsi que l’utilisation de la durée totale de réalisation du VRP comme fonction objectif.

Abstract

This dissertation presents a framework for using meteorological data to help plan the use of a unmanned aerial vehicle equipped with sensors to assist searchers and to assess an area that is damaged in the aftermath of a tornado. Using the vehicle routing problem’s framework, location-routing problem’s framework, and dynamic routing principals, we develop several methods using the historical data set of tornadoes to more effectively search an area impacted by a tornado. It is widely believed that the location of tornadoes are completely random. However, in this dissertation we can leverage the historical data to develop search strategies using unmanned aerial vehicles equipped with sensors to assess areas impacted by tornadoes in a more efficient manner. We initially demonstrate how tornado weather data and spatial data can be incorporated into search and rescue procedures to route the unmanned aerial vehicles. We develop a method for routing UAVs using the historical data set and also analyze the trade-offs between time to create waypoints and the yielding objective function value. It is observed that while there is an opportunity to use exact methods to generate waypoints, our proposed heuristic is sufficient for the rapid response needed in post-disaster relief. Next, we present a method and solution to prepositioning unmanned aerial vehicles in Oklahoma using historical tornado data based on set covering and multi-station vehicle routing models. When attempting to allocate unmanned aerial vehicles, we find that we require up to 70% more unmanned aerial vehicles to have sufficient coverage when there is as small as a 5% chance of any given unmanned aerial vehicle being unable to launch. Finally, we leverage historical data to more efficiently identify the extent of the area damaged by a tornado. We find that using the broad historical trends in tornadoes can reduce the amount of time it takes to identify the extent of by 2% (30% off not dynamically routing at all). This dissertation can provide an initial stepping stone for the use of meteorological and other expert data into the search and rescuers’ toolkit. This dissertation also provides further context and opportunities to use wireless sniffers. There are also other takeaways such as quantifying the trade-off between using exact methods and heuristics and their impact on implementation of a solution and the use of the VRP’s make-span as the objective function goal.