Research Theme


This is the research theme of our group.

Research Projects

Customized Local Differential Privacy for Multi-Agent Distributed Optimization

Roel Dobbe, Ye Pu, Jingge Zhu, Kannan Ramchandran, and Claire Tomlin


Many data-driven optimization problems may require sensitive information of participating users to calculate a solution for the overall group or network in real-time, such as in traffic or energy systems. Adversaries with access to coordination signals may potentially decode information on individual users and put user privacy at risk. Work in differential privacy so far has considered solving such problems, while protecting the privacy of user information, in a semi-distributed manner, i.e. with a central entity that computes and broadcasts certain public coordination signals to participating users. However, the lack of trust in central authorities or the lack of communication infrastructure may necessitate the full distribution of optimization algorithms, only relying on agent-to-agent communication and all calculations performed by agents. We present a fully distributed optimization algorithm that preserves local differential privacy, which is a strong notion that guarantees user privacy regardless of any auxiliary information an adversary may have. The local nature of the privacy result allows for each agent to customize its own level of differential privacy based on its needs and parameter sensitivities. We derive a sub-optimality bound as a function of the cumulative variance of the noise injected by all agents. We propose various allocation schemes to divide the maximum allowable noise, a emph{privacy budget}, among all participating agents, either through proportional sharing or well established pricing mechanisms. Our algorithm is implemented for a distributed version of the optimal power flow problem in distribution systems to mitigate voltage variations across electric networks due to the intermittent nature of renewable generation and the variability of electric loads.

A Broader View on Bias in Automated Decision-Making: Reflecting on Epistemology and Dynamics

Roel Dobbe, Sarah Dean, Thomas Gilbert, Nitin Kohli


Machine learning (ML) is increasingly deployed in real world contexts, supplying actionable insights and forming the basis of automated decision-making systems. While issues resulting from biases pre-existing in training data have been at the center of the fairness debate, these systems are also affected by technical and emergent biases, which often arise as context-specific artifacts of implementation. This position paper interprets technical bias as an epistemological problem and emergent bias as a dynamical feedback phenomenon. In order to stimulate debate on how to change machine learning practice to effectively address these issues, we explore this broader view on bias, stress the need to reflect on epistemology, and point to value-sensitive design methodologies to revisit the design and implementation process of automated decision-making systems.

FaSTrack (For more info, see this article)

Sylvia Herbert, Mo Chen


FaSTrack is a tool that is used in conjunction with any model-based motion planner to provide safety guarantees while planning and executing trajectories in real time. FaSTrack allows the planner to find trajectories using simple and easily computed planning models; this allows for the planner to operate in real time. To guarantee safety, a tracking error bound is precomputed to provide bounds on the largest deviation possible between the simple planner and the more complicated autonomous system.

Reachability Decomposition

Sylvia Herbert, Mo Chen


Hamilton Jacobi (HJ) reachability allows us to take the physical dynamics of a system and construct a set that describes all all initial states from which the system can achieve a goal (or avoid an unsafe area), even in worst case scenarios.

However, computing what is essentially all possible optimal trajectories of a system in order to perform this analysis is extremely computationally intensive; generally we can only use this method for very simplistic dynamics of 4 states or less. In our lab we work on developing creative ways to split complex dynamics into multiple subsystems, allowing us to compute these goal-based path-planning sets in lower dimensions that can then be reconstructed.

We can compute exact solutions for decoupled dynamics and dynamics that are coupled in a specific way that results in what we call “self-contained subsystems.” For dynamics that don't fall into this form we can compute approximate solutions. These advancements allow us to look into many new applications, from multi-vehicle avoidance to safety boundaries for the movement of elderly people as they transition from sitting to standing.

Hamilton-Jacobi (HJ) Reachability Analysis

Kene Akametalu, Somil Bansal, Mo Chen, Jaime Fernandez Fisac, Sylvia Herbert


HJ reachability analysis is all about optimal control and guarantees for reaching goals and staying safe. When given a dynamic system and a goal, this method produces the set of initial states from which your system is guaranteed to reach that goal when using optimal control. What’s more, the method provides the optimal control to reach the goal. This can also be done for obstacles and unsafe states: HJ reachability will provide a set of initial states that your system must stay out of in order to remain safe, as well as the control to accomplish this. We can combine scenarios with both goals and obstacles, and we can even consider worst-case disturbances (e.g. wind).

Reachability analysis is extremely useful in safety-critical scenarios. When flying a plane or administering anesthetics, accidental mistakes from less rigorous planning methods can result in disaster. Reachability is able to provide guarantees on what is safe, as well as how to implement controls to accomplish your goal. What’s more, HJ Reachability can handle nonlinear dynamics and worst-case external disturbances.

The challenges in HJ reachability lie in its expensive computational cost. Due to the nature of dynamic programming the computational complexity of solving a reachability problem rises exponentially with the number of dimensions in the system. This means that systems with more than  4 dimensions become completely infeasible to solve. We have been working on methods to circumvent this issue by splitting systems into separate sub-systems that can be solved independently and then recombined. Depending on the system and the decomposition we can acquire either exact or conservative results of the true reachable set or tube.

Another fun research direction is to merge the guarantees of reachability with the speed and convenience of other path planning methods. We are working on a new project called FaSTrack: Fast and Safe Tracking. In this project we developed a tool to precompute a maximum tracking error bound between a simple and a complicated model of an autonomous system. This allows us to plan trajectories through an environment using the simple model, while ensuring a maximum bound on the tracking error between this planned trajectory and the executed trajectory.

Finally, we are always looking for new and interesting applications of reachability. Our core application area has been both manned aerial systems and UAVs, but with the recent advances we have made in theory we are able to expand our reach in applications. For example, right now we are working with the HART lab to analyze safety guarantees for the elderly when transitioning from a sitting to a standing position. We are also looking into using reachability for freshwater containment systems and watershed analysis.

Project Safe Learning

Anayo K. Akametalu


The growing popularity of learning in robotic applications faces the challenge of constraint satisfaction, which currently impedes its application to safety critical systems. Recently, there has been interest in developing safe learning methods that ensure constraint satisfaction. One particular method, developed in our group, involves the use of Hamilton-Jacobi-Isaacs (HJI) reachability analysis. Given a system model, HJI reachability yields a safe control law that explicitly guarantees that constraints will be satisfied. As long as the system is not in jeopardy of violating the constraints, any learning algorithm can be applied, otherwise the safe control law must be used. The framework is general in the sense that it can handle arbitrary state constraints and may be applied to any learning algorithm.This framework has been used for both constrained trajectory tracking and constrained surveillance (implemented on our quadrotor testbed).

There are two directions we are simultaneously exploring. One, we want to extend our framework to handle modeling inaccuracies and unprecedented external disturbances that may result in a lack of safety and/or degradation of learning performance. Specifically, we are interested in updating the boundary of the safe region online based on the data we collect from the system. Two, we want to improve the performance of the learning algorithm by incorporating safety metrics into the learning process.

Analysis of Multi-Agent Autonomous Systems

Mo Chen


In the past, autonomous vehicles such as unmanned aerial vehicles (UAVs) have been used for military operations. Recently, there has been rapidly growing interest in both the industry and the government. Companies like Amazon and Google are looking to launch UAVs into the airspace to deliver packages to consumers in the near future, and government agencies such as NASA and the FAA look to create the appropriate regulations to make this possible. Multi-agent problems are difficult to analyze due to their high dimensionality. To make them tractable for analysis, the large problems involving many vehicles are broken down into small unit problems. Sometimes, the small unit problems are simple enough to be solved using known methods such as the Hamilton-Jacobi-Isaacs approach for dynamic games; in other cases, other solution methodologies need to be used to allow for analysis in higher dimensions, or relaxations of the problem must be made in order to work in lower dimensions. The small-group interactions derived from the analysis of the unit problems are then combined together using for example graph theoretic approaches. Multi-agent systems of current interest include the multiplayer reach-avoid game, multi-vehicle collision avoidance, and next-batch vehicle scheduling.

Planar Cell Polarity

Qie Hu


Planar cell polarity (PCP) signaling controls the polarization of cells within the plane of an epithelium, orienting asymmetric cellular structures, cell divisions and cell migration. Two molecular modules (‘Fat(Ft)Dachsous(Ds)Four-jointed(Fj)’ and ‘core’ including Frizzled(Fz) and Dishevelled(Dsh)) contribute to polarization, but how polarity is globally coordinated with tissue axes is unresolved. Recent research has revealed that vesicles containing Fz move across the cell by vesicle transport on a polarized microtubule (MT) cytoskeleton and that the FtDsFj module plays a role in polarization of MTs, leading to the hypothesis that FtDsFj provides a signal to orient core PCP function. In this project, we collaborate with Jeffrey Axelrod's group at Stanford University School of Medicine. We are providing additional evidence for this model by (1) showing a spatiotemporal correspondence between Ds and Fj gradient directions, apical MT orientation and the direction of core PCP protein polarization, including the establishment of the apical MT cytoskeleton prior global alignment of core module (2) strengthening evidence that MT orientation and core PCP protein orientation are instructed by Hippo-independent Ft signaling, (3) showing that directional trafficking of vesicles containing Dsh depend on Ft signaling and (4) demonstrate feasibility of this model by mathematical simulation.

Berkeley Drosophila Transcription Network Project

Qie Hu


In mathematical modeling of genetic regulation networks, the classical assumption is that the direction of regulation by a regulator (activation or repression) on a specific target gene is fixed. However experimental studies have suggested that the direction of gene regulation might be concentration-dependent. Earlier modeling work assumed only specific transcription factors (TFs) behave in this concentration-dependent manner. Nevertheless, based on our in-vivo DNA occupancy measurements of TFs and target gene mRNA expressions, we propose that concentration-dependent activation or repression might be a more general phenomenon. We use the regulation of even-skipped stripe 2 (eve2) during Stage 5 of Drosophila Melanogaster embryogenesis as a case study. We assess the validity of this assumption by comparing mathematical models describing the eve2 mRNA transcription based on above assumption, against classical monotone models, which assume TFs only either activate or repress the target eve2 gene.

Distribution Grid State Estimation and Identification

Roel Dobbe and Ye Yuan


High penetration levels of distributed generation (DG) and electric vehicles (EVs) diversify power flow and bring uncertainty to distribution networks, making planning and control more involved for distribution system operators (DSOs). The consequent need to augment forecasts with real-time state estimation is economically and technically challenging since it requires investing in a large number of sensors and these have to communicate with an often older and slower supervisory control and data acquisition (SCADA) systems. We address distribution grid state estimation via combining only a limited set of sensors with load forecast information. Via a Bayesian method, we derive an estimator for balanced power networks via rigorous modeling, allowing for generalization to three phase unbalanced networks. An offline analysis of load aggregation, forecast accuracy and number of sensors provides concrete engineering trade-offs to determine the optimal number of sensors for a desired accuracy. This estimation procedure can be used in real time as an observer for control problems or offline for planning purposes to asses the effect of DG or EVs on specific network components.

Decentralized Optimal Power Flow and Voltage Regulation

Roel Dobbe


Electronic power inverters are capable of quickly delivering reactive power to maintain customer voltages within operating tolerances and to reduce system losses in distribution grids. This project proposes a systematic and data-driven approach to determine reactive power inverter output as a function of local measurements in a manner that obtains near optimal results. First, we use a network model and historic load and generation data and do optimal power flow to compute globally optimal reactive power injections for all controllable inverters in the network. Subsequently, we use machine learning techniques to find a function for each inverter that maps its local historical data to an approximation of its optimal reactive power injection. The resulting functions then serve as decentralized controllers in the participating inverters to predict the optimal injection based on a new local measurements. Our current methods achieve near-optimal results when performing voltage- and capacity-constrained loss minimization and voltage flattening, and allows for an efficient volt-VAR optimization (VVO) scheme in which legacy control equipment collaborates with existing inverters to facilitate safe operation of distribution networks with higher levels of distributed generation.

Analytical Tools for Studying Heterogeneity in Cancer Dynamics

Roel Dobbe, Margaret Chapman and Ye Yuan


Breast cancer tumors have inherently heterogeneous cell types that respond differently to treatments. Although there is a wealth of studies describing canonical cell signaling networks, little is known about how these networks operate in different cancer cells and treatments. This paper proposes a method to split a set of responses gathered from experiments on different cancer cells up into common and specific components. The key to this retrieval is the derivation of a linear time-varying model of the shared dynamics among the different cell lines. A convex optimization problem is derived that retrieves both the model and the common and specific responses without a priori information. The method is tested on synthetic data, and verifies known facts when tested on a biological data set with protein expression data from breast cancer experiments. The technique can be used to analyze specific responses to understand what treatments can be combined to persistently treat a heterogeneous cancer tumor. The linear time-varying model sheds light on how proteins interact over time.