publications

1. SSRN

   Identification and Prediction of Disruptions in Airline Networks

   Li, Max Z,  Gopalakrishnan, Karthik, Zhu, Xiyitao, Nandi, Aritro, Balakrishnan, Hamsa, and Marla, Lavanya

   Abs PDF

   Disruptions in the air transportation system oftentimes lead to demand-capacity imbalances, resulting in flight delays and cancellations as byproducts of traffic management and system recovery actions. In order to better predict the impact of disruptions, as well as provide more targeted and proactive system recovery actions, it is critical to unambiguously identify key characteristics such as: (1) When did the disruption occur, (2) what was the duration of the disruption and subsequent recovery, and (3) how will an ongoing disruption evolve. In particular, providing performance measures regarding the duration, intensity, and type of disruption is straightforward for individual airports; for a large, geographically disparate, and interconnected network of airports, these characteristics are less clear. To address this, we first formalize the notion of \textitdisruption-recovery trajectories (DRTs) for the air transportation system through representing key network delay and cancellation performance measures as evolving between discrete states. These DRTs capture information regarding both the magnitude and spatial impact of air transportation system disruptions. Using this DRT framework, we report on past disruption and recovery characteristics for four major US airlines, as well as demonstrate the ability to predict short-term evolution of disruptions and recoveries without detailed schedule information, potentially enabling near-real time decision support for prescriptive management actions.

2. arXiv

   Differentially Private Stochastic Convex Optimization for Network Routing Applications

   Tsao, Matthew,  Gopalakrishnan, Karthik, Yang, Kaidi, and Pavone, Marco

   Abs PDF

   Network routing problems are common across many engineering applications. Computing optimal routing policies requires knowledge about network demand, i.e., the origin and destination (OD) of all requests in the network. However, privacy considerations make it challenging to share individual OD data that would be required for computing optimal policies. Privacy can be particularly challenging in standard network routing problems because sources and sinks can be easily identified from flow conservation constraints, making feasibility and privacy mutually exclusive. In this paper, we present a differentially private algorithm for network routing problems. The main ingredient is a reformulation of network routing which moves all user data-dependent parameters out of the constraint set and into the objective function. We then present an algorithm for solving this formulation based on a differentially private variant of stochastic gradient descent. In this algorithm, differential privacy is achieved by injecting noise, and one may wonder if this noise injection compromises solution quality. We prove that our algorithm is both differentially private and asymptotically optimal as the size of the training set goes to infinity. We corroborate the theoretical results with numerical experiments on a road traffic network which show that our algorithm provides differentially private and near-optimal solutions in practice.

2023

1. AISTATS

   Online Learning for Traffic Routing under Unknown Preferences

   Jalota, Devansh,  Gopalakrishnan, Karthik, Azizan, Navid, Johari, Ramesh, and Pavone, Marco

   International Conference on Artificial Intelligence and Statistics (AISTATS) 2023

   Abs PDF

   In transportation networks, users typically choose routes in a decentralized and self-interested manner to minimize their individual travel costs, which, in practice, often results in inefficient overall outcomes for society. As a result, there has been a growing interest in designing road tolling schemes to cope with these efficiency losses and steer users toward a system-efficient traffic pattern. However, the efficacy of road tolling schemes often relies on having access to complete information on users’ trip attributes, such as their origin-destination (O-D) travel information and their values of time, which may not be available in practice. Motivated by this practical consideration, we propose an online learning approach to set tolls in a traffic network to drive heterogeneous users with different values of time toward a system-efficient traffic pattern. In particular, we develop a simple yet effective algorithm that adjusts tolls at each time period solely based on the observed aggregate flows on the roads of the network without relying on any additional trip attributes of users, thereby preserving user privacy. In the setting where the O-D pairs and values of time of users are drawn i.i.d. at each period, we show that our approach obtains an expected regret and road capacity violation of O(\sqrtT), where T is the number of periods over which tolls are updated. Our regret guarantee is relative to an offline oracle that has complete information on users’ trip attributes. We further establish a Ω(\sqrtT) lower bound on the regret of any algorithm, which establishes that our algorithm is optimal up to constants. Finally, we demonstrate the superior performance of our approach relative to several benchmarks on a real-world transportation network, thereby highlighting its practical applicability.

2. Frontiers

   Traffic Management Protocols for Advanced Air Mobility

   Chin, Christopher, Qin, Victor,  Gopalakrishnan, Karthik, and Balakrishnan, Hamsa

   Frontiers in Aerospace Engineering 2023

   Abs

   The demand for advanced air mobility (AAM) operations is expected to be at a much larger scale than conventional aviation. Additionally, AAM flight operators are likely to compete in providing a range of on-demand services in congested airspaces, with varying operational costs. These characteristics motivate the need for the development of new traffic management algorithms for advanced air mobility. In this paper, we explore the use of traffic management protocols (“rules-of-the-road" for airspace access) to enable efficient and fair operations. First, we show that it is possible to avoid gridlock and improve efficiency by leveraging the concepts of cycle detection and backpressure. We then develop a cost-aware traffic management protocol based on the second-price auction. Using simulations of representative advanced air mobility scenarios, we demonstrate that our traffic management protocols can help balance efficiency and fairness, in both the operational and the economic contexts.

3. ICML

   Scalable Multi-Agent Reinforcement Learning through Intelligent Information Aggregation

   Nayak, Siddharth, Choi, Kenneth, Ding, Wenqi, Dolan, Sydney,  Gopalakrishnan, Karthik, and Balakrishnan, Hamsa

   International Conference on Machine Learning 2023

   Abs HTML PDF

   We consider the problem of multi-agent navigation and collision avoidance when observations are limited to the local neighborhood of each agent. We propose InforMARL, a novel architecture for multi-agent reinforcement learning (MARL) which uses local information intelligently to compute paths for all the agents in a decentralized manner. Specifically, InforMARL aggregates information about the local neighborhood of agents for both the actor and the critic using a graph neural network and can be used in conjunction with any standard MARL algorithm. We show that (1) in training, InforMARL has better sample efficiency and performance than baseline approaches, despite using less information, and (2) in testing, it scales well to environments with arbitrary numbers of agents and obstacles.

4. JATM

   An empirical study of the resilience of the US and European air transportation networks

   Baspinar, Baris,  Gopalakrishnan, Karthik, Koyuncu, Emre, and Balakrishnan, Hamsa

   Journal of Air Transport Management 2023

   Abs HTML

   Air travel connects people and goods across vast geographical regions. However, operational inter-dependencies in the air transportation system due to factors such as aircraft, crew, and passenger connectivity also result in the spread of disruptions in the system. Our work uses tools from network science and control theory to characterize the relation between the inter-connectivity (i.e., network structure, both in terms of flights and delays) and the robustness of the air transportation system. These methods are applied to characterize the resilience of the air transportation networks in the United States (US) and Europe by considering the flight and delay network structures and delay dynamics. Our study reveals that stronger inter-connectivity in the US makes the system more susceptible to disruptions that spread rapidly. However, we also find that this higher connectivity enables greater flexibility and controllability while recovering from disruptions.

2022

1. ITSC

   Private and Decentralized Location Sharing for Congestion-Aware Routing

   Tsao, Matthew, Yang, Kaidi,  Gopalakrishnan, Karthik, and Pavone, Marco

   IEEE International Transportation Systems Conference 2022

   Abs HTML PDF

   Data-driven methodologies offer many exciting upsides, but they also introduce new challenges, particularly in the realm of user privacy. Specifically, the way data is collected can pose privacy risks to end users. In many routing services, a single entity (e.g., the routing service provider) collects and manages user trajectory data. When it comes to user privacy, these systems have a central point of failure since users have to trust that this entity will not sell or use their data to infer sensitive private information. Unfortunately, in practice many advertising companies offer to buy such data for the sake of targeted advertisements. With this as motivation, we study the problem of using location data for routing services in a privacy-preserving way. Rather than having users report their location to a central operator, we present a protocol in which users participate in a decentralized and privacy-preserving computation to estimate travel times for the roads in the network in a way that no individuals’ location is ever observed by any other party. The protocol uses the Laplace mechanism in conjunction with secure multi-party computation to ensure that it is cryptogrpahically secure and that its output is differentially private. A natural question is if privacy necessitates degradation in accuracy or system performance. We show that if a road has sufficiently high capacity, then the travel time estimated by our protocol is provably close to the ground truth travel time. We validate the protocol through numerical experiments which show that using the protocol as a routing service provides privacy guarantees with minimal overhead to user travel time.

2. CEAS

   Dynamics of disruption and recovery in air transportation networks

   Li, Max Z,  Gopalakrishnan, Karthik, Balakrishnan, Hamsa, Shin, Sang Hyun, Jalan, Darsh, Nandi, Aritro, and Marla, Lavanya

   CEAS Aeronautical Journal 2022

   Abs HTML PDF

   Flight delays occur in the air transportation system when disruptive events such as weather, equipment outage, or congestion create an imbalance between system capacity and demand. These cycles of disruptions and subsequent recoveries can be viewed from a dynamical systems perspective: exogenous inputs (convective weather, airspace restrictions, etc.) disrupt the system, inducing delays and inefficiencies from which the system eventually recovers. We study these disruption and recovery cycles through a state-space representation that captures the severity and spatial impact of airport delays. In particular, using US airport delay data from 2008 to 2017, we first identify representative disruption and recovery cycles. These representative cycles provide insights into the common operational patterns of disruptions and recoveries in the system. We also relate these representative cycles to specific off-nominal events such as airport outages, and elucidate the differing disruption–recovery pathways for various off-nominal events. Finally, we explore temporal trends in terms of when and how the system tends to be disrupted, and the subsequent recovery.

3. CEAS

   Efficient and fair traffic flow management for on-demand air mobility

   Chin, Christopher,  Gopalakrishnan, Karthik, Balakrishnan, Hamsa, Egorov, Maxim, and Evans, Antony

   CEAS Aeronautical Journal 2022

   Abs HTML PDF

   The increased use of drones and air-taxis is expected to make airspace resources more congested, necessitating the use of unmanned aircraft systems traffic management (UTM) initiatives to ensure safe and efficient operations. Typically, strategic UTM involves solving an optimization problem that ensures that proposed flight schedules do not exceed airspace and vertiport capacities. However, the dynamic nature and low lead-time of applications such as on-demand delivery and urban air mobility traffic may reduce the efficiency and fairness of strategic UTM. We first discuss the adaptation of three fairness metrics into a traffic flow management problem (TFMP). Then, with computational simulations of a drone package delivery scenario in Toulouse, we evaluate trade-offs in the TFMP between efficiency and fairness, as well as between different fairness metrics. We show that system fairness can be improved with little loss in efficiency. We also consider two approaches to the integrated scheduling of both high lead-time flights (i.e., flights with a schedule known in advance) and low lead-time flights in a rolling horizon optimization framework. We compare the performance of both approaches for different horizon lengths and under varying proportions of high and low lead-time flights.

4. ICRAT

   Routing with Privacy for Drone Package Delivery Systems

   Ding, Geoffrey, Berke, Alex,  Gopalakrishnan, Karthik, Degue, Kwassi H, Balakrishnan, Hamsa, and Li, Max Z

   Best Paper in UAS/UAM/AAM track, 10th International Conference on Research in Air Transportation 2022

   Abs HTML PDF

   Unmanned aerial vehicles (UAVs), or drones, are increasingly being used to deliver goods from vendors to customers. To safely conduct these operations at scale, drones are required to broadcast position information as codified in remote identification (remote ID) regulations. However, location broadcast of package delivery drones introduces a privacy risk for customers using these delivery services: Third-party observers may leverage broadcast drone trajectories to link customers with their purchases, potentially resulting in a wide range of privacy risks. We propose a probabilistic definition of privacy risk based on the likelihood of associating a customer to a vendor given a package delivery route. Next, we quantify these risks, enabling drone operators to assess privacy risks when planning delivery routes. We then evaluate the impacts of various factors (e.g., drone capacity) on privacy and consider the trade-offs between privacy and delivery wait times. Finally, we propose heuristics for generating routes with privacy guarantees to avoid exhaustive enumeration of all possible routes and evaluate their performance on several realistic delivery scenarios.

5. ICRAT

   Airline Disruption Management with Delay Ledgers

   Chin, Christopher,  Gopalakrishnan, Karthik, Li, Max Z, and Balakrishnan, Hamsa

   Best Paper in Network Management track, 10th International Conference on Research in Air Transportation 2022

   Abs HTML PDF

   The impact of disruptions may result in reduced capacities at airports, forcing airlines to revise schedules and delay flights. However, due to myriad factors (e.g., passengers who may miss their connections, remaining flights to be performed by an aircraft, high-valued passengers with elite statuses), a delayed flight may be more or less costly to an airline, even when compared to another similarly delayed flight. Currently, identifying optimal slot swaps between airlines requires sharing the airline-specific delay cost of each flight. However, this is not amenable as sharing these private delay costs could reveal sensitive business practices. We propose the use of a procedure called the Delay Ledger (DELED) which enables airlines to identify a set of beneficial slot swaps across a network of airports which guarantees improvements in terms of private delay costs while ensuring that no private flight-specific valuations are shared. DELED is guaranteed to lower airline delay costs, incentivizes truthful airline participation, and supports flexible airline privacy preferences. We evaluate DELED across 30 days with 8 major US airlines, resulting in average reductions in private delay costs of 8-22% per day compared to current approaches.

6. TR-E

   Timescales of Delay Propagation in Airport Networks

   Wang, yanjun, Li, Max,  Gopalakrishnan, Karthik, and Liu, Tongdan

   Transportation Research Part E 2022

   Abs HTML PDF

   Flight delays persist and spread in airport networks due to high interconnectivity in the air transportation infrastructure. How quickly delay propagates between two airports is determined by factors such as the number of flights between airports, the duration of the flight, presence of disruptions, and schedule buffers. Accurate estimation of the time for delay propagation can improve system predictability and reliability. However, noisy airport delay data, along with a lack of visibility into airline scheduling and disruption management strategies, result in a challenging estimation problem for such propagation timescales. We present an algorithm to estimate statistically significant time lags between airport delays from noisy, aggregate operational data. The algorithm uses sliding correlation windows to extract the airport pairs with stable delay lags. We apply our method to identify different timescales of interactions for US airport delays in 2017. Our analysis yields two main results: (1) The most stable lags between airport delays involve the Northeast airports; (2) The stable lags between two airports are negatively correlated to the scheduled flight times between the same two airports. These results regarding delay propagation speeds have potential implications for delay prediction models and airline schedule design.

2021

1. AIAA

   Spatial Delay Distributions in Chinese Airline Networks

   Wang, yanjun,  Gopalakrishnan, Karthik, and Li, Max

   AIAA AVIATION 2020 Forum 2021

   Abs HTML PDF

   Understanding a variety of performance characteristics is a crucial first step in improving efficiency and managing delays in airline networks. Given the diversity of operating conditions and constraints, particularly across different national airspace, there can be important insights to be gained by analyzing different national airspace and airlines. In this work, we apply several data-driven techniques to characterize various airport delay distributions in Chinese airline networks. Specifically, we focus on examining two central characteristics of air transportation delays: its impact on the system and where the impacts are distributed spatially. We show that it is not enough to simply examine the former, as many operational impacts of delays can only be found through also considering spatial factors of airline delays. We focus on the airport delays at major Chinese airports incurred by the four largest domestic airlines in China (Air China, China Southern, China Eastern, and Hainan), and provide insights into aspects such as temporal trends in delay magnitudes versus spatial distribution, as well as outlying days in terms of delay impacts. We note that the focus of this work is on applications and operational impacts, rather than a methodological deep dive.

2. ITS

   Efficiency and fairness in unmanned air traffic flow management

   Chin, Christopher,  Gopalakrishnan, Karthik, Egorov, Maxim, Evans, Antony, and Balakrishnan, Hamsa

   IEEE Transactions on Intelligent Transportation Systems 2021

   Abs HTML PDF

   As the demand for Unmanned Aircraft Systems (UAS) operations increases, UAS Traffic Flow Management (UTFM) initiatives are needed to mitigate congestion, and to ensure safety and efficiency. Congestion mitigation can be achieved by assigning airborne delays (through speed changes or path stretches) or ground delays (holds relative to the desired takeoff times) to aircraft. While the assignment of such delays may increase system efficiency, individual aircraft operators may be unfairly impacted. Dynamic traffic demand, variability in aircraft operator preferences, and differences in the market share of operators complicate the issue of fairness in UTFM. Our work considers the fairness of delay assignment in the context of UTFM. To this end, we formulate the UTFM problem with fairness and show through computational experiments that significant improvements in fairness can be attained at little cost to system efficiency. We demonstrate that when operators are not aligned in how they perceive or value fairness, there is a decrease in the overall fairness of the solution. We find that fairness decreases as the air-ground delay cost ratio increases and that it improves when the operator with dominant market share has a weak preference for the fairness of its allocated delays. Finally, we implemented UTFM in a rolling-horizon setting with dynamic traffic demand, and find that efficiency is adversely impacted. However, the impact on fairness is varied and depends on the metric used.

3. AnnRev

   Control and optimization of air traffic networks

   Gopalakrishnan, Karthik, and Balakrishnan, Hamsa

   Annual Review of Control, Robotics, and Autonomous Systems 2021

   Abs HTML PDF

   The air transportation system connects the world through the transport of goods and people. However, operational inefficiencies such as flight delays and cancellations are prevalent, resulting in economic and environmental impacts. In the first part of this article, we review recent advances in using network analysis techniques to model the interdependencies observed in the air transportation system and to understand the role of airports in connecting populations, serving air traffic demand, and spreading delays. In the second part, we present some of our recent work on using operational data to build dynamical system models of air traffic delay networks. We show that Markov jump linear system models capture many of the salient characteristics of these networked systems. We illustrate how these models can be validated and then used to analyze system properties such as stability and to design optimal control strategies that limit the propagation of disruptions in air traffic networks.

4. MobiSys

   Throughput-fairness tradeoffs in mobility platforms

   Balasingam, Arjun,  Gopalakrishnan, Karthik, Mittal, Radhika, Arun, Venkat, Saeed, Ahmed, Alizadeh, Mohammad, Balakrishnan, Hamsa, and Balakrishnan, Hari

   Proceedings of the 19th Annual International Conference on Mobile Systems, Applications, and Services 2021

   Abs HTML PDF

   This paper studies the problem of allocating tasks from different customers to vehicles in mobility platforms, which are used for applications like food and package delivery, ridesharing, and mobile sensing. A mobility platform should allocate tasks to vehicles and schedule them in order to optimize both throughput and fairness across customers. However, existing approaches to scheduling tasks in mobility platforms ignore fairness. We introduce Mobius, a system that uses guided optimization to achieve both high throughput and fairness across customers. Mobius supports spatiotemporally diverse and dynamic customer demands. It provides a principled method to navigate inherent tradeoffs between fairness and throughput caused by shared mobility. Our evaluation demonstrates these properties, along with the versatility and scalability of Mobius, using traces gathered from ridesharing and aerial sensing applications. Our ridesharing case study shows that Mobius can schedule more than 16,000 tasks across 40 customers and 200 vehicles in an online manner.

5. EAAMO

   When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes

   Jalota, Devansh, Solovey, Kiril,  Gopalakrishnan, Karthik, Zoepf, Stephen, Balakrishnan, Hamsa, and Pavone, Marco

   Equity and Access in Algorithms, Mechanisms, and Optimization 2021

   Abs HTML PDF

   Congestion pricing has long been hailed as a means to mitigate traffic congestion; however, its practical adoption has been limited due to social inequity issues, e.g., low-income users are priced out off certain roads. This issue has spurred interest in the design of equitable mechanisms that refund the collected toll revenues to users. Although revenue refunding has been extensively studied, there has been no characterization of how such schemes can be designed to simultaneously achieve system efficiency and equity objectives. In this work, we bridge this gap through the study of congestion pricing and revenue refunding (CPRR) schemes in non-atomic congestion games. We first develop CPRR schemes, which in comparison to the untolled case, simultaneously (i) increase system efficiency and (ii) decrease wealth inequality, while being (iii) user-favorable: irrespective of their initial wealth or values-of-time (which may differ across users) users would experience a lower travel cost after the implementation of the proposed scheme. We then characterize the set of optimal user-favorable CPRR schemes that simultaneously maximize system efficiency and minimize wealth inequality. These results assume a well-studied behavior model of users minimizing a linear function of their travel times and tolls, without considering refunds. Overall, our work demonstrates that through appropriate refunding policies we can achieve system efficiency while reducing wealth inequality.

6. TrSci

   Graph signal processing techniques for analyzing aviation disruptions

   Li, Max Z,  Gopalakrishnan, Karthik, Pantoja, Kristyn, and Balakrishnan, Hamsa

   Transportation Science 2021

   Abs HTML PDF

   Understanding the characteristics of air-traffic delays and disruptions is critical for developing ways to mitigate their significant economic and environmental impacts. Conventional delay-performance metrics reflect only the magnitude of incurred flight delays at airports; in this work, we show that it is also important to characterize the spatial distribution of delays across a network of airports. We analyze graph-supported signals, leveraging techniques from spectral theory and graph-signal processing to compute analytical and simulation-driven bounds for identifying outliers in spatial distribution. We then apply these methods to the case of airport-delay networks and demonstrate the applicability of our methods by analyzing U.S. airport delays from 2008 through 2017. We also perform an airline-specific analysis, deriving insights into the delay dynamics of individual airline subnetworks. Through our analysis, we highlight key differences in delay dynamics between different types of disruptions, ranging from nor’easters and hurricanes to airport outages. We also examine delay interactions between airline subnetworks and the system-wide network and compile an inventory of outlier days that could guide future aviation operations and research. In doing so, we demonstrate how our approach can provide operational insights in an air-transportation setting. Our analysis provides a complementary metric to conventional aviation-delay benchmarks and aids airlines, traffic-flow managers, and transportation-system planners in quantifying off-nominal system performance.

7. ACC

   Differentially Private Outlier Detection in Multivariate Gaussian Signals

   Degue, Kwassi H,  Gopalakrishnan, Karthik, Li, Max Z, Balakrishnan, Hamsa, and Le Ny, Jerome

   2021 American Control Conference (ACC) 2021

   Abs HTML PDF

   The detection of outliers in data, while preserving the privacy of individual agents who contributed to the data set, is an increasingly important task when monitoring and controlling large-scale systems. In this paper, we use an algorithm based on the sparse vector technique to perform differentially private outlier detection in multivariate Gaussian signals. Specifically, we derive analytical expressions to quantify the trade-off between detection accuracy and privacy. We validate our analytical results through numerical simulations.

8. CDC

   Differentially Private Outlier Detection in Correlated Data

   Degue, Kwassi H,  Gopalakrishnan, Karthik, Li, Max Z, and Balakrishnan, Hamsa

   2021

   Abs HTML PDF

   The detection of outliers has become increasingly important for the control and monitoring of large-scale networked systems such as transportation and smart grids. Data from these systems, such as location traces or power consumption, are collected from individual agents, and are often privacy-sensitive. Furthermore, the networked nature of these systems results in the data of different individuals being correlated with each other. In this paper, we use the concept of differential privacy to design a privacy-preserving algorithm for outlier detection in correlated data. We determine analytic formulas to evaluate the performance of the proposed differentially private algorithm, and we analyze the trade-off between privacy level and detection accuracy. We illustrate our methodology using an example based on outlier detection in household electricity usage data.

9. ATM

   Airport Ground Holding with Hierarchical Control Objectives

   Chin, Christopher, Li, Max Z,  Gopalakrishnan, Karthik, and Balakrishnan, Hamsa

   14th USA/Europe Air Traffic Management Research and Development Seminar 2021

   Abs HTML PDF

   Disruptions in the air transportation system, perhaps due to extreme weather, often result in unexpected, or off- nominal, delays at airports. A resilient air traffic management system seeks to restore airport delays to their nominal values quickly after such disruptions. Two primary factors make the design of efficient recovery algorithms for air transportation networks challenging: the lack of a high-fidelity model for predicting and controlling airport delay dynamics, and poor computational tractability of large-scale flight rescheduling opti- mization problems. We propose a two-stage hierarchical control strategy for rescheduling aircraft (i.e., assigning delays) after network disruptions. Our high-level planner leverages a low- fidelity approximation of airport delay dynamics to propose a reference plan based on user preferences. This reference plan accounts for complex objectives such as ensuring a “smooth” redistribution of delays across airports (quantified by the total variation). The low-level controller then solves the multi-airport ground holding problem (MAGHP), augmented to track the reference plan. The solution to the augmented MAGHP yields a revised flight schedule with lower total variation than the original MAGHP, while still satisfying operational constraints. We illustrate the benefits of our proposed methodology using six disruption case studies of the National Airspace System (NAS).

10. DroNets

    Toward a Marketplace for Aerial Computing

    Balasingam, Arjun,  Gopalakrishnan, Karthik, Mittal, Radhika, Alizadeh, Mohammad, Balakrishnan, Hamsa, and Balakrishnan, Hari

    2021

    Abs PDF

    The rapid proliferation of commodity drones has expanded interest in building applications that acquire imagery, video, and sensor data at scale. In addition, recent work on drone programming frameworks have simplified the development of aerial computing apps that gather this data. These advancements have popularized the drones-as-a-service model, where large drone fleets serve multiple apps simultaneously. This paper proposes a marketplace for aerial computing, where apps can gather aerial data on demand and providers can offer up their drones for aerial computing. We introduce Aerialis, a drones-as-a-service platform that schedules tasks to drones by arbitrating bids submitted by apps. Aerialis allows apps with different semantics and spatiotemporal preferences to express how much they would like to pay for each aerial computing task. It then aggregates requests across apps, and schedules tasks on drones according to a marketplace policy (e.g., maximizing revenue or guaranteeing quality-of-service to apps). We build a prototype of Aerialis, and implement urban sensing apps to monitor air pollution, measure road traffic, and profile cellular throughput. We discuss operational challenges in deploying Aerialis, and show how the measurements collected from our real-world experiments offer valuable insights for engineers and city planners.

11. TR-C

    Network-centric benchmarking of operational performance in aviation

    Gopalakrishnan, Karthik, Li, Max Z, and Balakrishnan, Hamsa

    Transportation Research Part C: Emerging Technologies 2021

    Abs PDF

    Performance analysis of the air traffic operations is challenging because of the need to account for weather impacts and network effects. In this paper, we propose a framework that uses network clustering to identify baselines for benchmarking airline on-time performance. We demonstrate our framework by computing cancellation and departure delay baselines using US flight data for the years 2014-16. Subsequently, we use these baselines to benchmark daily on-time performance at the system-wide, airline-, and airport-specific levels, for both mainline and regional carriers. This framework enables an airline to conduct self- and peer-comparisons, evaluate improvements over time, and diagnose causes of poor on-time performance. Furthermore, our framework can be used by system operators to identify long-term trends in traffic management initiatives.

12. ATM/JAT

    Protocol-Based Congestion Management for Advanced Air Mobility

    Chin, Christopher,  Gopalakrishnan, Karthik, Balakrishnan, Hamsa, Egorov, Maxim, and Evans, Antony

    Kevin Corker Award for Best Paper in Conference, 14th USA/Europe Air Traffic Management Research and Development Seminar. Also in a special issue of the AIAA Journal of Air Transportation. 2021

    Abs HTML PDF

    Advanced air mobility operations (e.g., air taxis and drone deliveries) are expected to significantly increase the demand for limited airspace resources. Two key characteristics of these operations are that flights will be scheduled with short lead times, and operators may be unable or reluctant, for reasons of privacy, to share flight intent information. Consequently, there is a need for congestion management algorithms that are efficient and fair in dynamic, reduced-information settings. In this paper, we address these challenges by designing a protocol that determines the “rules-of-the-road” for airspace access under these settings. The proposed protocol centers on the construction of priority queues to determine access to each congested volume of airspace. We leverage the concepts of backpressure and cycle detection to avoid gridlock and promote efficiency, and present several flight- and operator-level prioritization schemes. We evaluate the impacts of the prioritization schemes on system- wide and operator-level efficiency and fairness through extensive simulations of three scenarios: random flight patterns, cross- flows, and hub-based operations. In all scenarios, we find that backpressure prioritization yields the most efficient solution, and that accrued delay or dominant resource prioritization is the most fair depending on the user’s choice of fairness metric.

2020

1. ICRAT

   Tradeoffs between efficiency and fairness in unmanned aircraft systems traffic management

   Chin, Christopher,  Gopalakrishnan, Karthik, Balakrishnan, Hamsa, Egorov, Maxim, and Evans, Antony

   Best Paper in Network Management track, 9th International Conference on Research in Air Transportation 2020

   Abs HTML PDF

   The growing use of drones and other Unmanned Aircraft Systems (UAS) is expected to make airspace resources more congested, necessitating the use of UAS Traffic Management (UTM) initiatives to ensure safe and efficient operations. The core functions of UTM are to prevent the loss of airborne separation and to mitigate congestion at departure or arrival points. These functions can be achieved through revising the schedule by assigning airborne delays (speed changes or path stretches) or ground delays (delayed takeoff times) to aircraft. Our work evaluates the fairness aspects of delay assignment while attempting to achieve more efficient UTM. Dynamic and high traffic demand, variability in UAS operators’ preferences, and differences in vehicle capabilities can adversely impact the fairness of the revised schedule. We show through computational experiments that, for certain fairness metrics, significant improvements in fairness can be attained with very little decrease in system efficiency. We also quantify the tradeoff between efficiency and fairness under dynamic demand, when trajectories are incorporated in a rolling horizon framework.

2. ICRAT

   Dynamics of Disruption and Recovery in Air Transportation Networks

   Li, Max Z,  Gopalakrishnan, Karthik, Balakrishnan, Hamsa, Shin, Sang Hyun, Jalan, Darsh, Nandi, Aritro, and Marla, Lavanya

   Best Paper in System Performance track, 9th International Conference on Research in Air Transportation 2020

   Abs HTML PDF

   Flight delays occur in the air transportation system when disruptive events such as weather, equipment outage, or congestion create an imbalance between system capacity and demand. These cycles of disruptions and subsequent recoveries can be viewed from a dynamical systems perspective: exogenous inputs (convective weather, airspace restrictions, etc.) disrupt the system, inducing delays and inefficiencies from which the system eventually recovers.We study these disruption and recovery cycles through a state-space representation that captures the severity and spatial impact of airport delays. In particular, using US airport delay data from 2008-2017, we first identify representative disruption and recovery cycles. These representative cycles provide insights into the common operational patterns of disruptions and recoveries in the system. We also relate these representative cycles to specific off-nominal events such as airport outages, and elucidate the differing disruption-recovery pathways for various off-nominal events. Finally, we explore temporal trends in terms of when and how the system tends to be disrupted, and the subsequent recovery.

3. SIGMOD

   Miris: Fast object track queries in video

   Bastani, Favyen, He, Songtao, Balasingam, Arjun,  Gopalakrishnan, Karthik, Alizadeh, Mohammad, Balakrishnan, Hari, Cafarella, Michael, Kraska, Tim, and Madden, Sam

   Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data 2020

   Abs HTML PDF

   Video databases that enable queries with object-track predicates are useful in many applications. Such queries include selecting objects that move from one region of the camera frame to another (e.g., finding cars that turn right through a junction) and selecting objects with certain speeds (e.g., finding animals that stop to drink water from a lake). Processing such predicates efficiently is challenging because they involve the movement of an object over several video frames. We propose a novel query-driven tracking approach that integrates query processing with object tracking to efficiently process object track queries and address the computational complexity of object detection methods. By processing video at low framerates when possible, but increasing the framerate when needed to ensure high-accuracy on a query, our approach substantially speeds up query execution. We have implemented query-driven tracking in MIRIS, a video query processor, and compare MIRIS against four baselines on a diverse dataset consisting of five sources of video and nine distinct queries. We find that, at the same accuracy, MIRIS accelerates video query processing by 9x on average over the IOU tracker, an overlap-based tracking-by-detection method used in existing video database systems.

4. AIDA-AT

   Outlier analysis of airport delay distributions in US and China

   Li, Max Z,  Gopalakrishnan, Karthik, Wang, Yanjun, and Balakrishnan, Hamsa

   2020 International Conference on Artificial Intelligence and Data Analytics for Air Transportation (AIDA-AT) 2020

   Abs HTML PDF

   Outlier detection is a key component of several machine learning approaches. However, many existing techniques, especially for multi-dimensional signals, are not interpretable and do not explain why a specific classification was assigned to a particular data point. Another limitation is that most methods only consider the magnitude or intensity of the signal, and not its spatial distribution. We present a spectral approach to identify outliers based on the spatial distribution of a signal across the nodes of a graph without any explicit assumptions on the underlying probability distribution of the signal. By applying these techniques to airport delays, we not only identify outliers in the spatial distribution of delays, but also gain insights into the delay dynamics. Specifically, we compare spatial delay distributions in the US and China during the period 2012–17, and identify several interesting characteristics pertaining to critical airports for outlier detection. We characterize typical variabilities in the delay distributions, and the frequency of occurrence of outliers. Our results highlight the differences between the operational dynamics of the US and Chinese air transportation systems, and contribute to performance benchmarking between different airspace systems.

5. MobiSys

   Beecluster: drone orchestration via predictive optimization

   He, Songtao, Bastani, Favyen, Balasingam, Arjun,  Gopalakrishnan, Karthik, Jiang, Ziwen, Alizadeh, Mohammad, Balakrishnan, Hari, Cafarella, Michael, Kraska, Tim, and Madden, Sam

   Proceedings of the 18th International Conference on Mobile Systems, Applications, and Services 2020

   Abs HTML PDF

   The rapid development of small aerial drones has enabled numerous drone-based applications, e.g., geographic mapping, air pollution sensing, and search and rescue. To assist the development of these applications, we propose BeeCluster, a drone orchestration system that manages a fleet of drones. BeeCluster provides a virtual drone abstraction that enables developers to express a sequence of geographical sensing tasks, and determines how to map these tasks to the fleet efficiently. BeeCluster’s core contribution is predictive optimization, in which an inferred model of the future tasks of the application is used to generate an optimized flight and sensing schedule for the drones that aims to minimize the total expected execution time. We built a prototype of BeeCluster and evaluated it on five real-world case studies with drones in outdoor environments, measuring speedups from 11.6% to 23.9%.

6. CDC

   Approximate Projection-Based Control of Networks

   Li, Max Z,  Gopalakrishnan, Karthik, and Balakrishnan, Hamsa

   2020 59th IEEE Conference on Decision and Control (CDC) 2020

   Abs HTML PDF

   Modern infrastructures such as transportation and communication networks are large-scale systems with complex dependence structures between various sub-systems. Human-interpretable performance targets in such systems are often represented in terms of lower-dimensional projections of the high-dimensional state space. We consider the problem of designing control strategies for high-dimensional systems that lack a detailed model. To do so, we leverage the ability of copulas to represent dependant structures in high-dimensional data, and approximate the state space model through inverse sampling. We demonstrate the applicability of the control policies obtained from our methodology through a data-driven case study of controlling flight delays within the US air transportation network.

2019

1. CDC

   Identification of outliers in graph signals

   Gopalakrishnan, Karthik, Li, Max Z, and Balakrishnan, Hamsa

   2019 IEEE 58th Conference on Decision and Control 2019

   Abs HTML PDF

   Outlier detection, or the identification of observations that differ significantly from the norm, is an important aspect of data mining. Conventional outlier detection tools have limited applicability to networks, in which there are interdependencies between the variables. In this paper, we consider the problem of identifying unusual spatial distributions of nodal signals on a graph. Leveraging tools from graph signal processing and statistical analysis, we propose a methodology to identify outliers in graph signals in a computationally efficient manner. Specifically, we examine a projection of the graph signal into a lower dimensional representation that enables easier outlier identification. Additionally, we derive analytical expressions for the outlier bounds. We apply our technique by identifying off-nominal days in the context of the US airport network using aviation delay data

2. ATM

   A spectral approach towards analyzing air traffic network disruptions

   Li, Max Z,  Gopalakrishnan, Karthik, Balakrishnan, Hamsa, and Pantoja, Kristyn

   Best Paper in Performance Analysis and Metrics track, 13th USA/Europe Air Traffic Management Research and Development Seminar 2019

   Abs HTML PDF

   The networked nature of the air transportation system leads to systemwide delays and cancellations as a result of disruptions at an airport. A comprehensive analysis of system performance requires understanding the inherent interdepen- dencies between various airports, in order to characterize off- nominal disruptions and to aid in recovery. In this work, we apply Graph Signal Processing (GSP) techniques to the analysis of flight delay networks, yielding two novel contributions: (1) We use the notion of the total variation (TV) of a graph signal in order to identify and quantify unexpected distributions of delays across airports; and (2) we present a spectral eigendecomposition analysis of airport disruption and delay networks. We investigate and characterize different patterns of delay distribution based on the relationship between TV and total delay, using 10 years worth of operational data from major US airports. We show that attributes of the resultant eigenvector modes and energy contributions are useful metrics to characterize specific disrup- tions caused by events such as nor’easters, Atlantic hurricanes, and equipment outages at airports.

2017

1. ATM

   A comparative analysis of models for predicting delays in air traffic networks

   Gopalakrishnan, Karthik, and Balakrishnan, Hamsa

   ATM Seminar 2017

   Abs HTML PDF

   In this paper, we compare the performance of different approaches to predicting delays in air traffic networks. We consider three classes of models: A recently-developed aggregate model of the delay network dynamics, which we will refer to as the Markov Jump Linear System (MJLS), classical machine learning techniques like Classification and Regression Trees (CART), and three candidate Artificial Neural Network (ANN) architectures. We show that prediction performance can vary significantly depending on the choice of model/algorithm, and the type of prediction (for example, classification vs. regression). We also discuss the importance of selecting the right predictor variables, or features, in order to improve the performance of these algorithms. The models are evaluated using operational data from the National Airspace System (NAS) of the United States. The ANN is shown to be a good algorithm for the classification problem, where it attains an average accuracy of nearly 94% in predicting whether or not delays on the 100 most-delayed links will exceed 60 min, looking two hours into the future. The MJLS model, however, is better at predicting the actual delay levels on different links, and has a mean prediction error of 4.7 min for the regression problem, for a 2 hr horizon. MJLS is also better at predicting outbound delays at the 30 major airports, with a mean error of 6.8 min, for a 2 hr prediction horizon. The effect of temporal factors, and the spatial distribution of current delays, in predicting future delays are also compared. The MJLS model, which is specifically designed to capture aggregate air traffic dynamics, leverages on these factors and outperforms the ANN in predicting the future spatial distribution of delays. In this manner, a tradeoff between model simplicity and prediction accuracy is revealed. Keywords- delay prediction; network delays; machine learning; artificial neural networks; data mining

2. CDC

   Privacy and stability in airport ground delay programs

   Gopalakrishnan, Karthik, and Balakrishnan, Hamsa

   2017 IEEE 56th Annual Conference on Decision and Control (CDC) 2017

   Abs HTML PDF

   Adverse weather can reduce airport capacity. When the number of arriving aircraft exceeds this reduced capacity, flights can get delayed. A Ground Delay Program (GDP) is a strategy by which aircraft landing slots can be redistributed so that the flights are delayed on the ground itself and not in the air. This increases safety, reduces the fuel consumption and hence the operating costs for airlines. In this paper, we present six algorithms that perform this slot reassignment. These algorithms differ in the extent to which slots can get re-arranged in real-time and the amount of information that the airlines must reveal to the central planner during the implementation. These two features of the algorithm are called as stability and privacy respectively. The efficiency of these six algorithms, measured in terms of the expected delay cost for flights, is compared using operational data for La Guardia Airport in New York. A two-step Receding Horizon Static (2-step RHS) model is shown to be a good compromise based on present expectations of privacy and stability in the system.

2016

1. ICRAT

   Deconstructing Delay Dynamics: An air traffic network example

   Gopalakrishnan, Karthik, Balakrishnan, Hamsa, and Jordan, Richard

   Best Paper in System Performance track, International Conference on Research in Air Transportation 2016

   Abs HTML PDF

   This paper develops and analyzes a simplified model of the dynamics of delay propagation in air traffic networks. The proposed model considers the redistribution of delays by accounting for aircraft flows between airports, the persistence of delays at an airport, the mitigation of delays due to slacks or buffers in flight schedules, and inputs such as sudden impulsive disruptions or sustained impacts due to longer duration traffic management initiatives. Using inter-airport traffic flows from operational data, different properties of the model are studied, including the resilience of different airports (as measured by the length of time before delays mitigate after a disruption), the amount of delay induced by disruptions at a particular airport, and the number of airports that are impacted when a given airport experiences disruptions. These properties are evaluated for different levels of delay sustainment, and for different values of available slack in schedules.

2. ACC

   Clusters and communities in air traffic delay networks

   Gopalakrishnan, Karthik, Balakrishnan, Hamsa, and Jordan, Richard

   American Control Conference, 2016

   Abs PDF

   The air transportation system is a network of many interacting, capacity-constrained elements. When the demand for airport and airspace resources exceed the available capacities of these resources, delays occur. The state of the air transportation system at any time can be represented as a weighted directed graph in which the nodes correspond to airports, and the weight on each arc is the delay experienced by departures on that origin-destination pair. Over the course of any day, the state of the system progresses through a time-series, where the state at any time-step is the weighted directed graph described above. This paper presents algorithms for the clustering of air traffic delay network data from the US National Airspace System, in order to identify characteristic delay states (i.e., weighted directed graphs) as well as characteristic types-of-days (i.e., sequences of such weighted directed graphs) that are experienced by the air transportation system. The similarity of delay states during clustering are evaluated on the basis of not only the in- and out-degrees of the nodes (the total inbound and outbound delays), but also network-theoretic properties such as the eigenvector centralities, and the hub and authority scores of different nodes. Finally, the paper looks at community detection, that is, the grouping of nodes (airports) based on their similarities within a system delay state. The type of day is found to have an impact on the observed community structures.

3. ATIO

   Multi-scale data mining for air transportation system diagnostics

   DeLaura, Richard, Jordan, Richard, Reynolds, Tom, Avery, Jacob, Balakrishnan, Hamsa, Conde Rocha Murca, Mayara,  Gopalakrishnan, Karthik, and Hansman, R John

   16th AIAA Aviation Technology, Integration, and Operations Conference 2016

   HTML
4. CDC

   Stability of networked systems with switching topologies

   Gopalakrishnan, Karthik, Balakrishnan, Hamsa, and Jordan, Richard

   55th IEEE Conference on Decision and Control 2016

   Abs HTML PDF

   The evolution of many networked systems, such as air transportation, can be modeled using a combination of the network topology and the resultant dynamics. In particular, time-varying networks can be represented by switching between candidate topologies. This paper models such systems as discrete-time, positive Markov Jump Linear Systems. Time-varying, periodic Markovian transition matrices and continuous state resets during discrete-mode transitions are also incorporated. Two notions of stability are considered: Mean Stability and Almost-Sure Stability, and appropriate conditions are derived for both of them. The analysis techniques are demonstrated using models determined from operational air traffic delay data. The results show that air traffic delay networks satisfy the proposed conditions for both mean stability and almost-sure stability, implying that delays tend to decay over time, even though several of the component discrete modes are unstable. Different nodes (airports) are also evaluated in terms of the persistence of delays and their susceptibility to network effects.

1. Modeling and Control of Networked Systems: Applications to Air Transportation

   Gopalakrishnan, Karthik

   2021

   PDF
2. Analysis of efficiency and fairness in stochastic ground holding models

   Gopalakrishnan, Karthik

   2016

   PDF