Karthik Gopalakrishnan

ASL Publications

A. Singhal, D. Gammelli, J. Luke, K. Gopalakrishnan, D. Helmreich, and M. Pavone, “Real-time Control of Electric Autonomous Mobility-on-Demand Systems via Graph Reinforcement Learning,” in European Control Conference, Stockholm, Sweden, 2024. (In Press)
[BibTeX] [Abstract]

Abstract: Operators of Electric Autonomous Mobility-on-Demand (E-AMoD) fleets need to make several real-time decisions such as matching available cars to ride requests, rebalancing idle cars to areas of high demand, and charging vehicles to ensure sufficient range. While this problem can be posed as a linear program that optimizes flows over a space-charge-time graph, the size of the resulting optimization problem does not allow for real-time implementation in realistic settings. In this work, we present the E-AMoD control problem through the lens of reinforcement learning and propose a graph network-based framework to achieve drastically improved scalability and superior performance over heuristics. Specifically, we adopt a bi-level formulation where we (1) leverage a graph network-based RL agent to specify a desired next state in the space-charge graph, and (2) solve more tractable linear programs to best achieve the desired state while ensuring feasibility. Experiments using real-world data from San Francisco and New York City show that our approach achieves up to 89% of the profits of the theoretically-optimal solution while achieving more than a 100x speedup in computational time. Furthermore, our approach outperforms the best domain-specific heuristics with comparable runtimes, with an increase in profits by up to 3x. Finally, we highlight promising zero-shot transfer capabilities of our learned policy on tasks such as inter-city generalization and service area expansion, thus showing the utility, scalability, and flexibility of our framework.
```
@inproceedings{SinghalGammelliEtAl2024,
  author = {Singhal, A. and Gammelli, D. and Luke, J. and Gopalakrishnan, K. and Helmreich, D. and Pavone, M.},
  title = {Real-time Control of Electric Autonomous Mobility-on-Demand Systems via Graph Reinforcement Learning},
  booktitle = {{European Control Conference}},
  year = {2024},
  address = {Stockholm, Sweden},
  month = jun,
  note = {In press},
  keywords = {press},
  owner = {gammelli},
  timestamp = {2023-11-15},
  url = {https://arxiv.org/abs/2311.05780}
}
```
D. Jalota, K. Solovey, K. Gopalakrishnan, S. Zoepf, H. Balakrishnan, and M. Pavone, “When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes,” in IEEE Transactions on Control of Network Systems, 2023. (In Press)
[BibTeX] [Abstract]

Abstract: Congestion pricing has long been hailed as a means to mitigate traffic congestion; however, its practical adoption has been limited due to the resulting social inequity issue, e.g., low-income users are priced out off certain roads. This issue has spurred interest in the design of equitable mechanisms that aim to refund the collected toll revenues as lump-sum transfers to users. Although revenue refunding has been extensively studied for over three decades, there has been no thorough 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. We also study a more complex behavior model wherein users are influenced by and react to the amount of refund that they receive. Although, in general, the two models can result in different outcomes in terms of system efficiency and wealth inequality, we establish that those outcomes coincide when the aforementioned optimal CPRR scheme is implemented. Overall, our work demonstrates that through appropriate refunding policies we can achieve system efficiency while reducing wealth inequality.
```
@inproceedings{JalotaSoloveyGopalakrishnanEtAl2023,
  author = {Jalota, D. and Solovey, K. and Gopalakrishnan, K. and Zoepf, S. and Balakrishnan, H. and Pavone, M.},
  title = {When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes},
  booktitle = {{IEEE Transactions on Control of Network Systems}},
  note = {In press},
  year = {2023},
  month = oct,
  keywords = {press},
  owner = {devanshjalota},
  timestamp = {2021-06-22},
  url = {https://ieeexplore.ieee.org/document/10319707}
}
```
M. Tsao, K. Gopalakrishnan, K. Yang, and M. Pavone, “Privacy-Aware Control of Cyber Physical Systems,” in Smarter Cyber Physical Systems: Enabling Methodologies and Application, CRC Press, 2023. (Submitted)
[BibTeX] [Abstract]

Abstract: In this chapter, we will discuss some of the privacy related challenges that have arisen in data-driven cyber-physical systems. While user data can help data-driven systems improve their efficiency, safety, and adaptability, the way that this data is collected and analyzed can lead to privacy risks to users. If left unaddressed, potential privacy risks may deter users from contributing their data to cyber-physical systems, thereby limiting the effectiveness of data-driven tools employed by the systems. To ensure that users are protected from privacy risks and feel comfortable sharing their data with cyber-physical systems, this chapter discusses how differential privacy and cryptography, techniques originally developed for privacy in health care and computer systems respectively, can be used to conduct data analysis and optimization with principled privacy guarantees in cyber-physical systems. Along the way, we will discuss and compare the properties, strengths weaknesses of these approaches. We will also show why these techniques address many of the privacy-related issues that arise when using data anonymization and data aggregation, two of the most common approaches to privacy-aware data sharing.
```
@incollection{TsaoGopalakrishnanEtAl2023b,
  author = {Tsao, M. and Gopalakrishnan, K. and Yang, K. and Pavone, M.},
  title = {Privacy-Aware Control of Cyber Physical Systems},
  booktitle = {Smarter Cyber Physical Systems: Enabling Methodologies and Application},
  year = {2023},
  publisher = {{CRC Press}},
  note = {Submitted},
  keywords = {sub},
  owner = {gkarthik},
  timestamp = {2022-12-06}
}
```
M. Tsao, K. Gopalakrishnan, K. Yang, and M. Pavone, “Differentially Private Stochastic Convex Optimization for Network Routing Applications,” in Proc. IEEE Conf. on Decision and Control, Singapore, 2023.
[BibTeX] [Abstract]

Abstract: 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.
```
@inproceedings{TsaoGopalakrishnanEtAl2023,
  author = {Tsao, M. and Gopalakrishnan, K. and Yang, K. and Pavone, M.},
  title = {Differentially Private Stochastic Convex Optimization for Network Routing Applications},
  booktitle = {{Proc. IEEE Conf. on Decision and Control}},
  year = {2023},
  address = {Singapore},
  doi = {10.1109/CDC49753.2023.10383207},
  url = {https://ieeexplore.ieee.org/abstract/document/10383207/},
  owner = {somrita},
  timestamp = {2024-02-29}
}
```
D. Jalota, K. Gopalakrishnan, N. Azizan, R. Johari, and M. Pavone, “Online Learning for Traffic Routing under Unknown Preferences,” in Int. Conf. on Artificial Intelligence and Statistics, 2023.
[BibTeX] [Abstract]

Abstract: 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.
```
@inproceedings{JalotaEtAl2022,
  author = {Jalota, D. and Gopalakrishnan, K. and Azizan, N. and Johari, R. and Pavone, M.},
  title = {Online Learning for Traffic Routing under Unknown Preferences},
  booktitle = {{Int. Conf. on Artificial Intelligence and Statistics}},
  year = {2023},
  keywords = {pub},
  owner = {devanshjalota},
  timestamp = {2022-05-03},
  url = {https://arxiv.org/abs/2203.17150}
}
```
M. Tsao, K. Yang, K. Gopalakrishnan, and M. Pavone, “Private Location Sharing for Decentralized Routing Services,” in Proc. IEEE Int. Conf. on Intelligent Transportation Systems, 2022.
[BibTeX] [Abstract]

Abstract: 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. 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. The protocol is computationally efficient and does not require specialized hardware; all it needs is GPS, which is included in most mobile devices. 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.
```
@inproceedings{TsaoYangEtAl2022,
  author = {Tsao, M. and Yang, K. and Gopalakrishnan, K. and Pavone, M.},
  title = {Private Location Sharing for Decentralized Routing Services},
  booktitle = {{Proc. IEEE Int. Conf. on Intelligent Transportation Systems}},
  year = {2022},
  doi = {10.1109/ITSC55140.2022.9922387},
  month = oct,
  url = {https://arxiv.org/abs/2202.13305},
  owner = {gkarthik},
  timestamp = {2022-11-21}
}
```
D. Jalota, K. Solovey, K. Gopalakrishnan, S. Zoepf, H. Balakrishnan, and M. Pavone, “When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes,” in ACM Conf. on Equity and Access in Algorithms, Mechanisms, and Optimization, Online, 2021.
[BibTeX] [Abstract]

Abstract: Congestion pricing has long been hailed as a means to mitigate traffic congestion; however, its practical adoption has been limited due to the resulting social inequity issue, e.g., low-income users are priced out off certain roads. This issue has spurred interest in the design of equitable mechanisms that aim to refund the collected toll revenues as lump-sum transfers to users. Although revenue refunding has been extensively studied for over three decades, there has been no thorough 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. We also study a more complex behavior model wherein users are influenced by and react to the amount of refund that they receive. Although, in general, the two models can result in different outcomes in terms of system efficiency and wealth inequality, we establish that those outcomes coincide when the aforementioned optimal CPRR scheme is implemented. Overall, our work demonstrates that through appropriate refunding policies we can achieve system efficiency while reducing wealth inequality.
```
@inproceedings{JalotaEtAl2021,
  author = {Jalota, D. and Solovey, K. and Gopalakrishnan, K. and Zoepf, S. and Balakrishnan, H. and Pavone, M.},
  title = {When Efficiency meets Equity in Congestion Pricing and Revenue Refunding Schemes},
  booktitle = {{ACM Conf. on Equity and Access in Algorithms, Mechanisms, and Optimization}},
  year = {2021},
  address = {Online},
  month = oct,
  owner = {devanshjalota},
  timestamp = {2021-06-22},
  url = {https://dl.acm.org/doi/10.1145/3465416.3483296}
}
```