Roy Dong

Katherine Driggs-Campbell, Roy Dong, S. Shankar Sastry et al.

In order to develop provably safe human-in-the-loop systems, accurate and precise models of human behavior must be developed. In the case of intelligent vehicles, one can imagine the need for predicting driver behavior to develop minimally invasive active safety systems or to safely interact with other vehicles on the road. We present a optimization based method for approximating the stochastic reachable set for human-in-the-loop systems. This method identifies the most precise subset of states that a human driven vehicle may enter, given some dataset of observed trajectories. We phrase this problem as a mixed integer linear program, which can be solved using branch and bound methods. The resulting model uncovers the most representative subset that encapsulates the likely trajectories, up to some probability threshold, by optimally rejecting outliers in the dataset. This tool provides set predictions consisting of trajectories observed from the nonlinear dynamics and behaviors of the human driven car, and can account for modes of behavior, like the driver state or intent. This allows us to predict driving behavior over long time horizons with high accuracy. By using this realistic data and flexible algorithm, a precise and accurate driver model can be developed to capture likely behaviors. The resulting prediction can be tailored to an individual for use in semi-autonomous frameworks or generally applied for autonomous planning in interactive maneuvers.

Henrik Ohlsson, Lillian Ratliff, Roy Dong et al.

Blind system identification is known to be a hard ill-posed problem and without further assumptions, no unique solution is at hand. In this contribution, we are concerned with the task of identifying an ARX model from only output measurements. Driven by the task of identifying systems that are turned on and off at unknown times, we seek a piecewise constant input and a corresponding ARX model which approximates the measured outputs. We phrase this as a rank minimization problem and present a relaxed convex formulation to approximate its solution. The proposed method was developed to model power consumption of electrical appliances and is now a part of a bigger energy disaggregation framework. Code will be made available online.

Roy Dong, Eric Mazumdar, S. Shankar Sastry

The widespread applicability of analytics in cyber-physical systems has motivated research into causal inference methods. Predictive estimators are not sufficient when analytics are used for decision making; rather, the flow of causal effects must be determined. Generally speaking, these methods focus on estimation of a causal structure from experimental data. In this paper, we consider the dual problem: we fix the causal structure and optimize over causal imputations to achieve desirable system behaviors for a minimal imputation cost. First, we present the optimal causal imputation problem, and then we analyze the problem in two special cases: 1) when the causal imputations can only impute to a fixed value, 2) when the causal structure has linear dynamics with additive Gaussian noise. This optimal causal imputation framework serves to bridge the gap between causal structures and control.

Heling Zhang, Siqi Du, Roy Dong

Follow-the-regularized-leader (FTRL) algorithms have become popular in the context of games, providing easy-to-implement methods for each agent, as well as theoretical guarantees that the strategies of all agents will converge to some equilibrium concept (provided that all agents follow the appropriate dynamics). However, with these methods, each agent ignores the coupling in the game, and treats their payoff vectors as exogenously given. In this paper, we take the perspective of one agent (the controller) deciding their mixed strategies in a finite game, while one or more other agents update their mixed strategies according to continuous-time FTRL. Viewing the learners' dynamics as a nonlinear control system evolving on the relative interior of a simplex or product of simplices, we ask when the controller can steer the learners to a target state, using only its own mixed strategy and without modifying the game's payoff structure. For the two-player case we provide a necessary and sufficient criterion for controllability based on the existence of a fully mixed neutralizing controller strategy and a rank condition on the projected payoff map. For multi-learner interactions we give two sufficient controllability conditions, one based on uniform neutralization and one based on a periodic-drift hypothesis together with a Lie-algebra rank condition. We illustrate these results on canonical examples such as Rock-Paper-Scissors and a construction related to Brockett's integrator.

Roy Dong, Heling Zhang, Lillian J. Ratliff

As data-driven methods are deployed in real-world settings, the processes that generate the observed data will often react to the decisions of the learner. For example, a data source may have some incentive for the algorithm to provide a particular label (e.g. approve a bank loan), and manipulate their features accordingly. Work in strategic classification and decision-dependent distributions seeks to characterize the closed-loop behavior of deploying learning algorithms by explicitly considering the effect of the classifier on the underlying data distribution. More recently, works in performative prediction seek to classify the closed-loop behavior by considering general properties of the mapping from classifier to data distribution, rather than an explicit form. Building on this notion, we analyze repeated risk minimization as the perturbed trajectories of the gradient flows of performative risk minimization. We consider the case where there may be multiple local minimizers of performative risk, motivated by situations where the initial conditions may have significant impact on the long-term behavior of the system. We provide sufficient conditions to characterize the region of attraction for the various equilibria in this settings. Additionally, we introduce the notion of performative alignment, which provides a geometric condition on the convergence of repeated risk minimization to performative risk minimizers.

Samir Wadhwa, Roy Dong

Causal discovery methods seek to identify causal relations between random variables from purely observational data, as opposed to actively collected experimental data where an experimenter intervenes on a subset of correlates. One of the seminal works in this area is the Inferred Causation algorithm, which guarantees successful causal discovery under the assumption of a conditional independence (CI) oracle: an oracle that can states whether two random variables are conditionally independent given another set of random variables. Practical implementations of this algorithm incorporate statistical tests for conditional independence, in place of a CI oracle. In this paper, we analyze the sample complexity of causal discovery algorithms without a CI oracle: given a certain level of confidence, how many data points are needed for a causal discovery algorithm to identify a causal structure? Furthermore, our methods allow us to quantify the value of domain expertise in terms of data samples. Finally, we demonstrate the accuracy of these sample rates with numerical examples, and quantify the benefits of sparsity priors and known causal directions.

Kayvon Mazooji, Roy Dong, Ilan Shomorony

When an individual's DNA is sequenced, sensitive medical information becomes available to the sequencing laboratory. A recently proposed way to hide an individual's genetic information is to mix in DNA samples of other individuals. We assume that the genetic content of these samples is known to the individual but unknown to the sequencing laboratory. Thus, these DNA samples act as "noise" to the sequencing laboratory, but still allow the individual to recover their own DNA samples afterward. Motivated by this idea, we study the problem of hiding a binary random variable $X$ (a genetic marker) with the additive noise provided by mixing DNA samples, using mutual information as a privacy metric. This is equivalent to the problem of finding a worst-case noise distribution for recovering $X$ from the noisy observation among a set of feasible discrete distributions. We characterize upper and lower bounds to the solution of this problem, which are empirically shown to be very close. The lower bound is obtained through a convex relaxation of the original discrete optimization problem, and yields a closed-form expression. The upper bound is computed via a greedy algorithm for selecting the mixing proportions.

Vicenc Rubies-Royo, Eric Mazumdar, Roy Dong et al.

In this work we present a multi-armed bandit framework for online expert selection in Markov decision processes and demonstrate its use in high-dimensional settings. Our method takes a set of candidate expert policies and switches between them to rapidly identify the best performing expert using a variant of the classical upper confidence bound algorithm, thus ensuring low regret in the overall performance of the system. This is useful in applications where several expert policies may be available, and one needs to be selected at run-time for the underlying environment.

Ioannis C. Konstantakopoulos, Kristy A. Hamilton, Yashaswini Murthy et al.

As Internet of Things (IoT) technologies are increasingly being deployed, situations frequently arise where multiple stakeholders must reconcile preferences to control a shared resource. We perform a 5-month long experiment dubbed 'smartSDH' (carried out in 27 employees' office space) where users report their preferences for the brightness of overhead lighting. smartSDH implements a modified Vickrey-Clarke-Groves (VCG) mechanism; assuming users are rational, it incentivizes truthful reporting, implements the socially desirable outcome, and compensates participants to ensure higher payoffs under smartSDH when compared with the default outside option(i.e., the option chosen in the absence of such a mechanism). smartSDH assesses the feasibility of the VCG mechanism in the context of smart building control and evaluated smartSDH's effect using metrics such as light level satisfaction, incentive satisfaction, and energy consumption. Although previous studies on the theoretical aspects of the mechanism indicate user satisfaction, our experiments indicate quite the contrary. We found that the participants were significantly less satisfied with light brightness and incentives determined by the VCG mechanism over time. These data suggest the need for more realistic behavioral models to design IoT technologies and highlights difficulties in estimating preferences from observable external factors such as atmospheric conditions.

Tyler Westenbroek, Roy Dong, Lillian J. Ratliff et al.

In recent years, data has played an increasingly important role in the economy as a good in its own right. In many settings, data aggregators cannot directly verify the quality of the data they purchase, nor the effort exerted by data sources when creating the data. Recent work has explored mechanisms to ensure that the data sources share high quality data with a single data aggregator, addressing the issue of moral hazard. Oftentimes, there is a unique, socially efficient solution. In this paper, we consider data markets where there is more than one data aggregator. Since data can be cheaply reproduced and transmitted once created, data sources may share the same data with more than one aggregator, leading to free-riding between data aggregators. This coupling can lead to non-uniqueness of equilibria and social inefficiency. We examine a particular class of mechanisms that have received study recently in the literature, and we characterize all the generalized Nash equilibria of the resulting data market. We show that, in contrast to the single-aggregator case, there is either infinitely many generalized Nash equilibria or none. We also provide necessary and sufficient conditions for all equilibria to be socially inefficient. In our analysis, we identify the components of these mechanisms which give rise to these undesirable outcomes, showing the need for research into mechanisms for competitive settings with multiple data purchasers and sellers.

Oladapo Afolabi, Katherine Driggs-Campbell, Roy Dong et al.

Despite growing attention in autonomy, there are still many open problems, including how autonomous vehicles will interact and communicate with other agents, such as human drivers and pedestrians. Unlike most approaches that focus on pedestrian detection and planning for collision avoidance, this paper considers modeling the interaction between human drivers and pedestrians and how it might influence map estimation, as a proxy for detection. We take a mapping inspired approach and incorporate people as sensors into mapping frameworks. By taking advantage of other agents' actions, we demonstrate how we can impute portions of the map that would otherwise be occluded. We evaluate our framework in human driving experiments and on real-world data, using occupancy grids and landmark-based mapping approaches. Our approach significantly improves overall environment awareness and out-performs standard mapping techniques.

Miguel Alberto Mercado, Roy Dong, Allan Nerves

Supply Shortage Outages are a major concern during peak demand for developing countries. In the Philippines, commercial loads have unused backup generation of up to 3000 MW, at the same time there are shortages of as much as 700 MW during peak demand. This gives utilities the incentive to implement Demand Response programs to minimize this shortage. But when considering Demand Response from a modeling perspective, social welfare through profit is always the major objective for program implementation. That isn't always the case during an emergency situation as there can be a trade-off between grid resilience and cost of electricity. The question is how the Distribution Utility (DU) shall optimally allocate the unused generation to meet the shortage when this trade-off exists. We formulate a combined multi-objective optimal dispatch model where we can make a direct comparison between the least-cost and resilience objectives. We find that this trade-off is due to the monotonically increasing nature of energy cost functions. If the supply is larger than the demand, the DU can perform a least-cost approach in the optimal dispatch since maximizing the energy generated in this case can lead to multiple solutions. We also find in our simulation that in cases where the supply of energy from the customers is less than shortage quantity, the DU must prioritize maximizing the generated energy rather than minimizing cost.

Eric Mazumdar, Roy Dong, Vicenç Rúbies Royo et al.

We formulate a multi-armed bandit (MAB) approach to choosing expert policies online in Markov decision processes (MDPs). Given a set of expert policies trained on a state and action space, the goal is to maximize the cumulative reward of our agent. The hope is to quickly find the best expert in our set. The MAB formulation allows us to quantify the performance of an algorithm in terms of the regret incurred from not choosing the best expert from the beginning. We first develop the theoretical framework for MABs in MDPs, and then present a basic regret decomposition identity. We then adapt the classical Upper Confidence Bounds algorithm to the problem of choosing experts in MDPs and prove that the expected regret grows at worst at a logarithmic rate. Lastly, we validate the theory on a small MDP.

Ruoxi Jia, Roy Dong, S. Shankar Sastry et al.

Large-scale sensing and actuation infrastructures have allowed buildings to achieve significant energy savings; at the same time, these technologies introduce significant privacy risks that must be addressed. In this paper, we present a framework for modeling the trade-off between improved control performance and increased privacy risks due to occupancy sensing. More specifically, we consider occupancy-based HVAC control as the control objective and the location traces of individual occupants as the private variables. Previous studies have shown that individual location information can be inferred from occupancy measurements. To ensure privacy, we design an architecture that distorts the occupancy data in order to hide individual occupant location information while maintaining HVAC performance. Using mutual information between the individual's location trace and the reported occupancy measurement as a privacy metric, we are able to optimally design a scheme to minimize privacy risk subject to a control performance guarantee. We evaluate our framework using real-world occupancy data: first, we verify that our privacy metric accurately assesses the adversary's ability to infer private variables from the distorted sensor measurements; then, we show that control performance is maintained through simulations of building operations using these distorted occupancy readings.

Roy Dong, Walid Krichene, Alexandre M. Bayen et al.

As our ground transportation infrastructure modernizes, the large amount of data being measured, transmitted, and stored motivates an analysis of the privacy aspect of these emerging cyber-physical technologies. In this paper, we consider privacy in the routing game, where the origins and destinations of drivers are considered private. This is motivated by the fact that this spatiotemporal information can easily be used as the basis for inferences for a person's activities. More specifically, we consider the differential privacy of the mapping from the amount of flow for each origin-destination pair to the traffic flow measurements on each link of a traffic network. We use a stochastic online learning framework for the population dynamics, which is known to converge to the Nash equilibrium of the routing game. We analyze the sensitivity of this process and provide theoretical guarantees on the convergence rates as well as differential privacy values for these models. We confirm these with simulations on a small example.

Roy Dong, Alvaro A. Cárdenas, Lillian J. Ratliff et al.

The modernization of the electrical grid and the installation of smart meters come with many advantages to control and monitoring. However, in the wrong hands, the data might pose a privacy threat. In this paper, we consider the tradeoff between smart grid operations and the privacy of consumers. We analyze the tradeoff between smart grid operations and how often data is collected by considering a realistic direct-load control example using thermostatically controlled loads, and we give simulation results to show how its performance degrades as the sampling frequency decreases. Additionally, we introduce a new privacy metric, which we call inferential privacy. This privacy metric assumes a strong adversary model, and provides an upper bound on the adversary's ability to infer a private parameter, independent of the algorithm he uses. Combining these two results allow us to directly consider the tradeoff between better load control and consumer privacy.

Henrik Ohlsson, Allen Y. Yang, Roy Dong et al.

In many compressive sensing problems today, the relationship between the measurements and the unknowns could be nonlinear. Traditional treatment of such nonlinear relationships have been to approximate the nonlinearity via a linear model and the subsequent un-modeled dynamics as noise. The ability to more accurately characterize nonlinear models has the potential to improve the results in both existing compressive sensing applications and those where a linear approximation does not suffice, e.g., phase retrieval. In this paper, we extend the classical compressive sensing framework to a second-order Taylor expansion of the nonlinearity. Using a lifting technique and a method we call quadratic basis pursuit, we show that the sparse signal can be recovered exactly when the sampling rate is sufficiently high. We further present efficient numerical algorithms to recover sparse signals in second-order nonlinear systems, which are considerably more difficult to solve than their linear counterparts in sparse optimization.