This dissertation contributes to the ongoing national project concerning the \emph{Next Generation Air Transportation System} (NextGen) that endeavors, in particular, to reshape the management of air traffic in the continental United States. Our work is part of this effort and mainly concerns modeling and algorithmic enhancements to the Airspace Planning and Collaborative Decision-Making Model (APCDM). First, we augment the APCDM to study an \emph{Airspace Flow Program} (AFP) in the context of weather-related disruptions. The proposed model selects among alternative flight plans for the affected flights while simultaneously (a) integrating slot-exchange mechanisms induced by multiple Ground Delay Programs (GDPs) to permit airlines to improve flight efficiencies through a mediated bartering of assigned slots, and (b) considering issues related to sector workloads, airspace conflicts, as well as overall equity concerns among the involved airlines in regard to accepted slot trades and flight plans. More specifically, the APCDM is enhanced to include the following: a. The revised model accommodates continuing flights, where some flight cannot depart until a prerequisite flight has arrived. Such a situation arises, for example, when the same aircraft will be used for the departing flight. b. We model a slot-exchange mechanism to accommodate flights being involved in multiple trade offers, and to permit slot trades at multiple GDP airports (whence the flight connection constraints become especially relevant). We also model flight cancelations whereby, if a flight assigned to a particular slot is canceled, the corresponding vacated slot would be made available for use in the slot-exchange process. c. Alternative equity concepts are presented, which more accurately reflect the measures used by the airlines. d. A reduced variant of the APCDM, referred to as \textbf{APCDM-Light}, is also developed. This model serves as a fast-running version of APCDM to be used for quick-turn analyses, where the level of modeling detail, as well as data requirements, are reduced to focus only on certain key elements of the problem. e. As an alternative for handling large-scale instances of APCDM more effectively, we present a \emph{sequential variable fixing heuristic} (SFH). The list of flights is first partitioned into suitable subsets. For the first subset, the corresponding decision variables are constrained to be binary-valued (which is the default for these decision variables), while the other variables are allowed to vary continuously between 0 and 1. If the resulting solution to this relaxed model is integral, the algorithm terminates. Otherwise, the binary variables are fixed to their currently prescribed values and another subset of variables is designated to be binary constrained. The process repeats until an integer solution is found or the heuristic encounters infeasibility. f. We experiment with using the APCDM model in a \emph{dynamic, rolling-horizon framework}, where we apply the model on some periodic basis (e.g., hourly), and where each sequential run of the model has certain flight plan selections that are fixed (such as flights that are already airborne), while we consider the selection among alternative flight plans for other imminent flights in a look-ahead horizon (e.g., two hours). These enhancements allow us to significantly expand the functionality of the original APCDM model. We test the revised model and its variants using realistic data derived from the \emph{Enhanced Traffic Management System} (ETMS) provided by the \emph{Federal Aviation Administration} (FAA). One of the new equity methods, which is based on average delay per passenger (or weighted average delay per flight), turns out to be a particularly robust way to model equity considerations in conjunction with sector workloads, conflict resolution, and slot-exchanges. With this equity method, we were able to solve large problem instances (1,000 flights) within 30 seconds on average using a 1\% optimality tolerance. The model also produced comparable solutions within about 20 seconds on average using the Sequential Fixing Heuristic (SFH). The actual solutions obtained for these largest problem instances were well within 1\% of the best known solution. Furthermore, our computations revealed that APCDM-Light can be readily optimized to a 0.01\% tolerance within about 5 seconds on average for the 1,000 flight problems. Thus, the augmented APCDM model offers a viable tool that can be used for tactical air traffic management purposes as an airspace flow program (particularly, APCDM-Light), as well as for strategic applications to study the impact of different types of trade restrictions, collaboration policies, equity concepts, and airspace sectorizations. The modeling of slot ownership in the APCDM motivates another problem: that of generating detoured flight plans that must arrive at a particular slot time under severe convective weather conditions. This leads to a particular class of network flow problems that seeks a shortest path, if it exists, between a source node and a destination node in a connected digraph $G(N,A)$, such that we arrive at the destination at a specified time while leaving the source no earlier than a lower bounding time, and where the availability of each network link is time-dependent in the sense that it can be traversed only during specified intervals of time. We refer to this problem as the \emph{reverse time-restricted shortest path problem} (RTSP). We show that RTSP is NP-hard in general and propose a dynamic programming algorithm for finding an optimal solution in pseudo-polynomial time. Moreover, under a special regularity condition, we prove that the problem is polynomially solvable with a complexity of order $O(|N / A|)$. Computational results using real flight generation test cases as well as random simulated problems are presented to demonstrate the efficiency of the proposed solution procedures. The current airspace configuration consists of sectors that have evolved over time based on historical traffic flow patterns. \citet{kopardekar_dyn_resect_2007} note that, given the current airspace configuration, some air traffic controller resources are likely under-utilized, and they also point out that the current configuration limits flexibility. Moreover, under the free-flight concept, which advocates a relaxation of waypoint traversals in favor of wind-optimized trajectories, the current airspace configuration will not likely be compatible with future air traffic flow patterns. Accordingly, one of the goals for the \emph{NextGen Air Transportation System} includes redesigning the airspace to increase its capacity and flexibility. With this motivation, we present several methods for defining sectors within the \emph{National Airspace System} (NAS) based on a measure of sector workload. Specifically, given a convex polygon in two-dimensions and a set of weighted grid points within the region encompassed by the polygon, we present several mixed-integer-programming-based algorithms to generate a plane (or line) bisecting the region such that the total weight distribution on either side of the plane is relatively balanced. This process generates two new polygons, which are in turn bisected until some target number of regions is reached. The motivation for these algorithms is to dynamically reconfigure airspace sectors to balance predicted air-traffic controller workload. We frame the problem in the context of airspace design, and then present and compare four algorithmic variants for solving these problems. We also discuss how to accommodate monitoring, conflict resolution, and inter-sector coordination workloads to appropriately define grid point weights and to conduct the partitioning process in this context. The proposed methodology is illustrated using a basic example to assess the overall effect of each algorithm and to provide insights into their relative computational efficiency and the quality of solutions produced. A particular competitive algorithmic variant is then used to configure a region of airspace over the U.S. using realistic flight data. The development of the APCDM is part of an ongoing \emph{NextGen} research project, which envisages the sequential use of a variety of models pertaining to three tiers. The \emph{Tier 1} models are conceived to be more strategic in scope and attempt to identify potential problematic areas, e.g., areas of congestion resulting from a severe convective weather system over a given time-frame, and provide aggregate measures of sector workloads and delays. The affected flow constrained areas (FCAs) highlighted by the results from these \emph{Tier 1} models would then be analyzed by more detailed \emph{Tier 2} models, such as APCDM, which consider more specific alternative flight plan trajectories through the different sectors along with related sector workload, aircraft conflict, and airline equity issues. Finally, \emph{Tier 3} models are being developed to dynamically examine smaller-scaled, localized fast-response readjustments in air traffic flows within the time-frame of about an hour prior to departure (e.g., to take advantage of a break in the convective weather system). The APCDM is flexible, and perhaps unique, in that it can be used effectively in all three tiers. Moreover, as a strategic tool, analysts could use the APCDM to evaluate the suitability of potential airspace sectorization strategies, for example, as well as identify potential capacity shortfalls under any given sector configuration. / Ph. D.

Cette thèse, effectuée en partenariat entre la société Survey Copter, le laboratoire Hubert Curien et la Direction Générale de l’Armement (DGA), répond à des besoins tant militaires que civils dans le cadre de l’utilisation de drones à basse altitude. Dans un premier temps nous avons focalisé nos recherches sur la détection d’objets mobiles pour les mini-drones de surveillance destinés aux applications militaires, tels que ceux opérés par Survey Copter. Nous présentons d’abord la méthode que nous avons développé qui consiste en une comparaison entre un flot optique et le flot estimé, l’objectif étant de détecter les objets ayant un mouvement différent de celui correspondant à la scène dans sa globalité, et de maximiser la robustesse de cette détection vis-à-vis des problèmes induits par la parallaxe. Puis, nous décrivons le projet général dans lequel s’inscrit cette détection, en détaillant les choix technologiques et compromis qui ont été effectués, l’objectif étant de développer une carte électronique qui puisse être embarquée sur un drone et permettant d’apporter des fonctionnalités d’assistance aux opérateurs. Une seconde partie, réalisée en collaboration avec le Dr. Mubarak Shah, directeur du laboratoire CRCV en Floride, vise à apporter une solution au problème de sécurité qu’engendre le nombre grandissant de micro-drones de loisir évoluant dans l’espace aérien civil. La solution que nous proposons comporte deux étapes, premièrement elle utilise les informations cadastrales pour pré-calculer avant le décollage un plan de vol qui permet d’éviter les zones dangereuses comme les routes. La seconde étape intervient pendant le vol et permet d’adapter localement le plan de vol de façon à éviter le survol des objets mobiles tels que les voitures et piétons. Les résultats encourageants que nous avons obtenus grâce à notre méthode de détection d’objets mobiles ont conduit à une publication dans la conférence ISPA 2015, et notre contribution pour l’utilisation sécurisée de drones dans l’espace aérien civil va faire l’objet d’une soumission à la conférence ICRA 2017 / This thesis, in partnership between Survey Copter (a French company), theHubert Curien laboratory, and the DGA (a compnent of the FrenchMinistry of Defense), aims at providing solutions for low-altitude UAVs for both military and civil applications. We first focus on moving objects detection for military surveillance using mini-UAVs, such as Survey Copter’s products. Our method consists in comparing a dense optical flow with an estimated flow in order to isolate objects that are independently moving compared to the global scene. This method was developed to be robust to parallax which is an inherent problem of such platforms, parallax. In this thesis we also detail an on-going project that consists in the development of an embedded processing board able to provide all necessary functionalities to assist UAV operators in their mission. Given the recent popularity of consumer drones, we worked, with Dr. Mubarak Shah, Director of the CRCV laboratory in Florida, towards providing a solution to the security threat those vehicles represent for public safety. Our method consists in two steps. The first one is performed prior to takeoff by computing the safest path for the mission in order to avoid dangerous areas such as roads. The second is based on an in-flight adaptation process of the initial flight plan to avoid flying above some particular objects such as cars or pedestrians. The promising results obtained thaks to our moving objects detection method have led to a publication in ISPA 2015, and our contribution towards safe navigation of UAVs will be submitted in September to ICRA 2017