Search

We propose a comprehensive approach to increase the reliability and resilience of future power grids rich in distributed energy resources. Our distributed scheme combines federated learning-based attack detection with a local electricity market-based attack mitigation method. We validate the scheme by applying it to a real-world distribution grid rich in solar PV. Simulation results demonstrate that the approach is feasible and can successfully mitigate the grid impacts of cyber-physical attacks., Comment: Submitted to CIRED 2024 USA: Workshop on Resilience of Electric Distribution Systems

The electricity grid has evolved from a physical system to a cyber-physical system with digital devices that perform measurement, control, communication, computation, and actuation. The increased penetration of distributed energy resources (DERs) that include renewable generation, flexible loads, and storage provides extraordinary opportunities for improvements in efficiency and sustainability. However, they can introduce new vulnerabilities in the form of cyberattacks, which can cause significant challenges in ensuring grid resilience. %, i.e. the ability to rapidly restore grid services in the face of severe disruptions. We propose a framework in this paper for achieving grid resilience through suitably coordinated assets including a network of Internet of Things (IoT) devices. A local electricity market is proposed to identify trustable assets and carry out this coordination. Situational Awareness (SA) of locally available DERs with the ability to inject power or reduce consumption is enabled by the market, together with a monitoring procedure for their trustability and commitment. With this SA, we show that a variety of cyberattacks can be mitigated using local trustable resources without stressing the bulk grid. The demonstrations are carried out using a variety of platforms with a high-fidelity co-simulation platform, real-time hardware-in-the-loop validation, and a utility-friendly simulator., Comment: Submitted to the Proceedings of the National Academy of Sciences (PNAS), under review

In this paper, we propose a market design based on game theory to optimally utilize the flexibility of distributed energy resources (DERs) such as solar PV, batteries, electric vehicles, and flexible loads. Market agents perform multiperiod optimization to determine their feasible flexibility limits for power injections while satisfying all constraints of their DERs. This is followed by a Stackelberg game between the market operator and the agents. The market operator as the leader aims to regulate the aggregate power injection around a desired value by leveraging the flexibility of their agents, and computes optimal prices for both electricity and flexibility services. The agents follow by optimally bidding their desired flexible power injections in response to these prices. We show the existence of an equilibrium among the market agents between all agents and the operator, along with simulation results for a small example system., Comment: This work has been submitted to IFAC for possible publication

We propose using a hierarchical retail market structure to alert and dispatch resources to mitigate cyber-physical attacks on a distribution grid. We simulate attacks where a number of generation nodes in a distribution grid are attacked. We show that the market is able to successfully meet the shortfall between demand and supply by utilizing the flexibility of remaining resources while minimizing any extra power that needs to be imported from the main transmission grid. This includes utilizing upward flexibility or reserves of remaining online generators and some curtailment or shifting of flexible loads, which results in higher costs. Using price signals and market-based coordination, the grid operator can achieve its objectives without direct control over distributed energy resources and is able to accurately compensate prosumers for the grid support they provide., Comment: Accepted to the 15th ACM/IEEE International Conference on Cyber-Physical Systems (ICCPS) and as part of the CPS-IoT Week 2024

In this paper, we formulate optimization problems to perform optimal transmission switching (OTS) in order to operate power transmission grids most efficiently. In any given electrical network, several of the transmission lines are generally equipped with switches, circuit breakers, and/or reclosers. The conventional practice is to operate the grid using a static or fixed configuration. However, it may be beneficial to dynamically reconfigure the grid through switching actions in order to respond to real-time demand and supply conditions. This has the potential to help reduce costs and improve efficiency. Furthermore, such OTS may be more crucial in future power grids with much higher penetrations of renewable energy sources, which introduce more variability and intermittency in generation. Similarly, OTS can potentially help mitigate the effects of unpredictable demand fluctuations (e.g. due to extreme weather). We explored and compared several different formulations for the OTS problems in terms of computational performance and optimality. I also applied them to small transmission test case networks as a proof of concept to see what the effects of applying OTS are.

We propose a hierarchical local electricity market (LEM) at the primary and secondary feeder levels in a distribution grid, to optimally coordinate and schedule distributed energy resources (DER) and provide valuable grid services like voltage control. At the primary level, we use a current injection-based model that is valid for both radial and meshed, balanced and unbalanced, multi-phase systems. The primary and secondary markets leverage the flexibility offered by DERs to optimize grid operation and maximize social welfare. Numerical simulations on an IEEE-123 bus modified to include DERs, show that the LEM successfully achieves voltage control and reduces overall network costs, while also allowing us to decompose the price and value associated with different grid services so as to accurately compensate DERs., Comment: 9 pages, 13 figures, Accepted to the 7th IEEE Conference on Control Technology and Applications (CCTA) 2023

Several examples of Cyber-physical human systems (CPHS) include real-time decisions from humans as a necessary building block for the successful performance of the overall system. Many of these decision-making problems necessitate an appropriate model of human behavior. Tools from Utility Theory have been used successfully in several problems in transportation for resource allocation and balance of supply and demand \citep{ben1985discrete}. More recently, Prospect Theory has been demonstrated as a useful tool in behavioral economics and cognitive psychology for deriving human behavioral models that characterize their subjective decision-making in the presence of stochastic uncertainties and risks, as an alternative to conventional Utility Theory \citep{kahneman_prospect_2012}. These models will be described in this article. Theoretical implications of Prospect Theory are also discussed. Examples will be drawn from transportation use cases such as shared mobility to illustrate these models as well as the distinctions between Utility Theory and Prospect Theory., Comment: 26 pages, submitted chapter to upcoming Wiley book on Cyber-Physical Human Systems (CPHS). arXiv admin note: text overlap with arXiv:1904.04824

We study the Improving Multi-Armed Bandit (IMAB) problem, where the reward obtained from an arm increases with the number of pulls it receives. This model provides an elegant abstraction for many real-world problems in domains such as education and employment, where decisions about the distribution of opportunities can affect the future capabilities of communities and the disparity between them. A decision-maker in such settings must consider the impact of her decisions on future rewards in addition to the standard objective of maximizing her cumulative reward at any time. In many of these applications, the time horizon is unknown to the decision-maker beforehand, which motivates the study of the IMAB problem in the technically more challenging horizon-unaware setting. We study the tension that arises between two seemingly conflicting objectives in the horizon-unaware setting: a) maximizing the cumulative reward at any time based on current rewards of the arms, and b) ensuring that arms with better long-term rewards get sufficient opportunities even if they initially have low rewards. We show that, surprisingly, the two objectives are aligned with each other in this setting. Our main contribution is an anytime algorithm for the IMAB problem that achieves the best possible cumulative reward while ensuring that the arms reach their true potential given sufficient time. Our algorithm mitigates the initial disparity due to lack of opportunity and continues pulling an arm till it stops improving. We prove the optimality of our algorithm by showing that a) any algorithm for the IMAB problem, no matter how utilitarian, must suffer $\Omega(T)$ policy regret and $\Omega(k)$ competitive ratio with respect to the optimal offline policy, and b) the competitive ratio of our algorithm is $O(k)$.

Grid regulators and participants are paying increasing attention to Dynamic Line Ratings (DLR) as a new approach to address transmission system bottlenecks. In this paper, a thorough comparison of DLR, Ambient Adjusted Ratings (AAR), and the traditional Static Line Ratings (SLR) are conducted on a synthetic ERCOT grid. Estimates of DLR and AAR are calculated using an equation based on heat balance physics, along with high-resolution weather data of temperature and wind velocities. A constraint generation method for contingency screening is developed for solving security-constrained optimal power flow. Numerical results suggest that employing DLR could double the benefits compared to those of AAR relative to SLR, in terms of system costs, renewable curtailment, and emissions., Comment: 6 pages, 8 figures

Humans have come to rely on machines for reducing excessive information to manageable representations. But this reliance can be abused -- strategic machines might craft representations that manipulate their users. How can a user make good choices based on strategic representations? We formalize this as a learning problem, and pursue algorithms for decision-making that are robust to manipulation. In our main setting of interest, the system represents attributes of an item to the user, who then decides whether or not to consume. We model this interaction through the lens of strategic classification (Hardt et al. 2016), reversed: the user, who learns, plays first; and the system, which responds, plays second. The system must respond with representations that reveal `nothing but the truth' but need not reveal the entire truth. Thus, the user faces the problem of learning set functions under strategic subset selection, which presents distinct algorithmic and statistical challenges. Our main result is a learning algorithm that minimizes error despite strategic representations, and our theoretical analysis sheds light on the trade-off between learning effort and susceptibility to manipulation., Comment: ICML 2022

More than 5 million children under five years die from largely preventable or treatable medical conditions every year, with an overwhelmingly large proportion of deaths occurring in under-developed countries with low vaccination uptake. One of the United Nations' sustainable development goals (SDG 3) aims to end preventable deaths of newborns and children under five years of age. We focus on Nigeria, where the rate of infant mortality is appalling. We collaborate with HelpMum, a large non-profit organization in Nigeria to design and optimize the allocation of heterogeneous health interventions under uncertainty to increase vaccination uptake, the first such collaboration in Nigeria. Our framework, ADVISER: AI-Driven Vaccination Intervention Optimiser, is based on an integer linear program that seeks to maximize the cumulative probability of successful vaccination. Our optimization formulation is intractable in practice. We present a heuristic approach that enables us to solve the problem for real-world use-cases. We also present theoretical bounds for the heuristic method. Finally, we show that the proposed approach outperforms baseline methods in terms of vaccination uptake through experimental evaluation. HelpMum is currently planning a pilot program based on our approach to be deployed in the largest city of Nigeria, which would be the first deployment of an AI-driven vaccination uptake program in the country and hopefully, pave the way for other data-driven programs to improve health outcomes in Nigeria., Comment: Accepted for publication at International Joint Conference on Artificial Intelligence 2022, AI for Good Track (IJCAI-22)

With increasing penetration of DERs in the distribution system, it is critical to design market structures that enable smooth integration of DERs. A hierarchical local electricity market (LEM) structure is proposed in this paper with a secondary market (SM) at the lower level representing secondary feeders and a primary market (PM) at the upper level, representing primary feeders, in order to effectively use DERs to increase grid efficiency and resilience. The lower level SM enforces budget, power balance and flexibility constraints and accounts for costs related to consumers, such as their disutility, flexibility limits, and commitment reliability, while the upper level PM enforces power physics constraints such as power balance and capacity limits, and also minimizes line losses. The hierarchical LEM is extensively evaluated using a modified IEEE-123 bus with high DER penetration, with each primary feeder consisting of at least three secondary feeders. Data from a GridLAB-D model is used to emulate realistic power injections and load profiles over the course of 24 hours. The performance of the LEM is illustrated by delineating the family of power-injection profiles across the primary and secondary feeders as well as corresponding local electricity tariffs that vary across the distribution grid. Together, it represents an overall framework for a Distribution System Operator (DSO) who can provide the oversight for the entire LEM., Comment: 14 pages, 13 figures, 1 table. This work has been submitted to the IEEE Transactions on Smart Grid for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

We study the problem of determining the best intervention in a Causal Bayesian Network (CBN) specified only by its causal graph. We model this as a stochastic multi-armed bandit (MAB) problem with side-information, where the interventions correspond to the arms of the bandit instance. First, we propose a simple regret minimization algorithm that takes as input a semi-Markovian causal graph with atomic interventions and possibly unobservable variables, and achieves $\tilde{O}(\sqrt{M/T})$ expected simple regret, where $M$ is dependent on the input CBN and could be very small compared to the number of arms. We also show that this is almost optimal for CBNs described by causal graphs having an $n$-ary tree structure. Our simple regret minimization results, both upper and lower bound, subsume previous results in the literature, which assumed additional structural restrictions on the input causal graph. In particular, our results indicate that the simple regret guarantee of our proposed algorithm can only be improved by considering more nuanced structural restrictions on the causal graph. Next, we propose a cumulative regret minimization algorithm that takes as input a general causal graph with all observable nodes and atomic interventions and performs better than the optimal MAB algorithm that does not take causal side-information into account. We also experimentally compare both our algorithms with the best known algorithms in the literature. To the best of our knowledge, this work gives the first simple and cumulative regret minimization algorithms for CBNs with general causal graphs under atomic interventions and having unobserved confounders., Comment: 36 pages; metadata changed

This paper provides a framework to quantify the sensitivity associated with behavioral models based on Cumulative Prospect Theory (CPT). These are used to design dynamic pricing strategies aimed at maximizing performance metrics of the Shared Mobility On-Demand Service (SMoDS), as solutions to a constrained nonlinear optimization problem. We analyze the sensitivity of both the optimal tariff as well as the optimal objective function with respect to CPT model parameters. In addition to deriving analytical solutions under certain assumptions, more general numerical results are obtained via computational experiments and simulations to analyze the sensitivity. We find that the model is relatively robust for small to moderate parameter perturbations. Although some of the trends in sensitivity are fairly general, the exact nature of variations in many cases depends heavily on the specific travel scenarios and modes being considered. This is primarily due to the complex nonlinearities in the problem, as well as the significant heterogeneity in passenger preferences across different types of trips., Comment: 29 pages, 13 figures, submitted to Transportation Research Part B: Methodological

Strategic classification studies the interaction between a classification rule and the strategic agents it governs. Under the assumption that the classifier is known, rational agents respond to it by manipulating their features. However, in many real-life scenarios of high-stake classification (e.g., credit scoring), the classifier is not revealed to the agents, which leads agents to attempt to learn the classifier and game it too. In this paper we generalize the strategic classification model to such scenarios. We define the price of opacity as the difference in prediction error between opaque and transparent strategy-robust classifiers, characterize it, and give a sufficient condition for this price to be strictly positive, in which case transparency is the recommended policy. Our experiments show how Hardt et al.'s robust classifier is affected by keeping agents in the dark.

Fairness has emerged as an important concern in automated decision-making in recent years, especially when these decisions affect human welfare. In this work, we study fairness in temporally extended decision-making settings, specifically those formulated as Markov Decision Processes (MDPs). Our proposed notion of fairness ensures that each state's long-term visitation frequency is at least a specified fraction. This quota-based notion of fairness is natural in many resource-allocation settings where the dynamics of a single resource being allocated is governed by an MDP and the distribution of the shared resource is captured by its state-visitation frequency. In an average-reward MDP (AMDP) setting, we formulate the problem as a bilinear saddle point program and, for a generative model, solve it using a Stochastic Mirror Descent (SMD) based algorithm. The proposed solution guarantees a simultaneous approximation on the expected average-reward and fairness requirement. We give sample complexity bounds for the proposed algorithm and validate our theoretical results with experiments on simulated data., Comment: AAMAS 2022

Learning good interventions in a causal graph can be modelled as a stochastic multi-armed bandit problem with side-information. First, we study this problem when interventions are more expensive than observations and a budget is specified. If there are no backdoor paths from an intervenable node to the reward node then we propose an algorithm to minimize simple regret that optimally trades-off observations and interventions based on the cost of intervention. We also propose an algorithm that accounts for the cost of interventions, utilizes causal side-information, and minimizes the expected cumulative regret without exceeding the budget. Our cumulative-regret minimization algorithm performs better than standard algorithms that do not take side-information into account. Finally, we study the problem of learning best interventions without budget constraint in general graphs and give an algorithm that achieves constant expected cumulative regret in terms of the instance parameters when the parent distribution of the reward variable for each intervention is known. Our results are experimentally validated and compared to the best-known bounds in the current literature.

A butterfly network consists of logarithmically many layers, each with a linear number of non-zero weights (pre-specified). The fast Johnson-Lindenstrauss transform (FJLT) can be represented as a butterfly network followed by a projection onto a random subset of the coordinates. Moreover, a random matrix based on FJLT with high probability approximates the action of any matrix on a vector. Motivated by these facts, we propose to replace a dense linear layer in any neural network by an architecture based on the butterfly network. The proposed architecture significantly improves upon the quadratic number of weights required in a standard dense layer to nearly linear with little compromise in expressibility of the resulting operator. In a collection of wide variety of experiments, including supervised prediction on both the NLP and vision data, we show that this not only produces results that match and at times outperform existing well-known architectures, but it also offers faster training and prediction in deployment. To understand the optimization problems posed by neural networks with a butterfly network, we also study the optimization landscape of the encoder-decoder network, where the encoder is replaced by a butterfly network followed by a dense linear layer in smaller dimension. Theoretical result presented in the paper explains why the training speed and outcome are not compromised by our proposed approach., Comment: Accepted to UAI 2021

Equivalence testing for a polynomial family {g_m} over a field F is the following problem: Given black-box access to an n-variate polynomial f(x), where n is the number of variables in g_m, check if there exists an A in GL(n,F) such that f(x) = g_m(Ax). If yes, then output such an A. The complexity of equivalence testing has been studied for a number of important polynomial families, including the determinant (Det) and the two popular variants of the iterated matrix multiplication polynomial: IMM_{w,d} (the (1,1) entry of the product of d many w $\times$ w symbolic matrices) and Tr-IMM_{w,d} (the trace of the product of d many w $\times$ w symbolic matrices). The families Det, IMM and Tr-IMM are VBP-complete, and so, in this sense, they have the same complexity. But, do they have the same equivalence testing complexity? We show that the answer is 'yes' for Det and Tr-IMM (modulo the use of randomness). The result is obtained by connecting the two problems via another well-studied problem called the full matrix algebra isomorphism problem (FMAI). In particular, we prove the following: 1. Testing equivalence of polynomials to Tr-IMM_{w,d}, for d$\geq$ 3 and w$\geq$ 2, is randomized polynomial-time Turing reducible to testing equivalence of polynomials to Det_w, the determinant of the w $\times$ w matrix of formal variables. (Here, d need not be a constant.) 2. FMAI is randomized polynomial-time Turing reducible to equivalence testing (in fact, to tensor isomorphism testing) for the family of matrix multiplication tensors {Tr-IMM_{w,3}}. These in conjunction with the randomized poly-time reduction from determinant equivalence testing to FMAI [Garg,Gupta,Kayal,Saha19], imply that FMAI, equivalence testing for Tr-IMM and for Det, and the $3$-tensor isomorphism problem for the family of matrix multiplication tensors are randomized poly-time equivalent under Turing reductions., Comment: 36 pages, 2 figures

We study an interesting variant of the stochastic multi-armed bandit problem, called the Fair-SMAB problem, where each arm is required to be pulled for at least a given fraction of the total available rounds. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the fractions of guaranteed pulls. We define a fairness-aware regret, called $r$-Regret, that takes into account the above fairness constraints and naturally extends the conventional notion of regret. Our primary contribution is characterizing a class of Fair-SMAB algorithms by two parameters: the unfairness tolerance and the learning algorithm used as a black-box. We provide a fairness guarantee for this class that holds uniformly over time irrespective of the choice of the learning algorithm. In particular, when the learning algorithm is UCB1, we show that our algorithm achieves $O(\ln T)$ $r$-Regret. Finally, we evaluate the cost of fairness in terms of the conventional notion of regret., Comment: arXiv admin note: substantial text overlap with arXiv:1905.11260

We study an interesting variant of the stochastic multi-armed bandit problem, called the Fair-SMAB problem, where each arm is required to be pulled for at least a given fraction of the total available rounds. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the fractions of guaranteed pulls. We define a fairness-aware regret, called r-Regret, that takes into account the above fairness constraints and naturally extends the conventional notion of regret. Our primary contribution is characterizing a class of Fair-SMAB algorithms by two parameters: the unfairness tolerance and learning algorithm used as a black-box. We provide a fairness guarantee for this class that holds uniformly over time irrespective of the choice of the learning algorithm. In particular, when the learning algorithm is UCB1, we show that our algorithm achieves O(log(T)) r-Regret. Finally, we evaluate the cost of fairness in terms of the conventional notion of regret., Comment: Uploading the latest version with significant improvements

In this paper, we attempt to optimally schedule the charging of long-range battery electric vehicles (BEVs) along highway networks, in order to minimize aggregate costs to the overall system consisting of utilities or electricity providers, station operators and other infrastructure, as well as EV users. Thus, we approach the problem from the perspective of both customers (EV car owners), as well as charging station operators and utilities using a hybrid systems based formulation.

Matrix Factorization (MF) on large scale matrices is computationally as well as memory intensive task. Alternative convergence techniques are needed when the size of the input matrix is higher than the available memory on a Central Processing Unit (CPU) and Graphical Processing Unit (GPU). While alternating least squares (ALS) convergence on CPU could take forever, loading all the required matrices on to GPU memory may not be possible when the dimensions are significantly higher. Hence we introduce a novel technique that is based on considering the entire data into a block matrix and relies on factorization at a block level., Comment: Disagreement on success criteria of the method with my guide

Consider the approximate sparse recovery problem: given Ax, where A is a known m-by-n dimensional matrix and x is an unknown (approximately) sparse n-dimensional vector, recover an approximation to x. The goal is to design the matrix A such that m is small and recovery is efficient. Moreover, it is often desirable for A to have other nice properties, such as explicitness, sparsity, and discreteness. In this work, we show that we can use spectral expander graphs to explicitly design binary matrices A for which the column sparsity is optimal and for which there is an efficient recovery algorithm (l1-minimization). In order to recover x that is close to {\delta}n-sparse (where {\delta} is a constant), we design an explicit binary matrix A that has m = O(sqrt{{\delta}} log(1/{\delta}) * n) rows and has O(log(1/{\delta})) ones in each column. Previous such constructions were based on unbalanced bipartite graphs with high vertex expansion, for which we currently do not have explicit constructions. In particular, ours is the first explicit non-trivial construction of a measurement matrix A such that Ax can be computed in O(n log(1/{\delta})) time.