Murti Salapaka

Deepjyoti Deka, Saurav Talukdar, Michael Chertkov et al.

Graphical models are a succinct way to represent the structure in probability distributions. This article analyzes the graphical model of nodal voltages in non-radial power distribution grids. Using algebraic and structural properties of graphical models, algorithms exactly determining topology and detecting line changes for distribution grids are presented along with their theoretical limitations. We show that if distribution grids have cycles/loops of size greater than three, then nodal voltages are sufficient for efficient topology estimation without additional assumptions on system parameters. In contrast, line failure or change detection using nodal voltages does not require any structural assumption. Under noisy measurements, we provide the first non-trivial bounds on the maximum noise that the system can tolerate for asymptotically correct topology recovery. The performance of the designed algorithms is validated with nonlinear AC power flow samples generated by Matpower on test grids, including scenarios with injection correlations and system noise.

Saurav Talukdar, Deepjyoti Deka, Michael Chertkov et al.

In this article, we present a method to reconstruct the topology of a partially observed radial network of linear dynamical systems with bi-directional interactions. Our approach exploits the structure of the inverse power spectral density matrix and recovers edges involving nodes up to four hops away in the underlying topology. We then present an algorithm with provable guarantees, which eliminates the spurious links obtained and also identifies the location of the unobserved nodes in the inferred topology. The algorithm recovers the exact topology of the network by using only time-series of the states at the observed nodes. The effectiveness of the method developed is demonstrated by applying it on a typical distribution system of the electric grid.

Harish Doddi, Saurav Talukdar, Deepjyoti Deka et al.

Learning the structure of a network from time series data, in particular cyclostationary data, is of significant interest in many disciplines such as power grids, biology and finance. In this article, an algorithm is presented for reconstruction of the topology of a network of cyclostationary processes. To the best of our knowledge, this is the first work to guarantee exact recovery without any assumptions on the underlying structure. The method is based on a lifting technique by which cyclostationary processes are mapped to vector wide sense stationary processes and further on semi-definite properties of matrix Wiener filters for the said processes.We demonstrate the performance of the proposed algorithm on a Resistor-Capacitor network and present the accuracy of reconstruction for varying sample sizes.

Harish Doddi, Deepjyoti Deka, Saurav Talukdar et al.

We consider a networked linear dynamical system with $p$ agents/nodes. We study the problem of learning the underlying graph of interactions/dependencies from observations of the nodal trajectories over a time-interval $T$. We present a regularized non-casual consistent estimator for this problem and analyze its sample complexity over two regimes: (a) where the interval $T$ consists of $n$ i.i.d. observation windows of length $T/n$ (restart and record), and (b) where $T$ is one continuous observation window (consecutive). Using the theory of $M$-estimators, we show that the estimator recovers the underlying interactions, in either regime, in a time-interval that is logarithmic in the system size $p$. To the best of our knowledge, this is the first work to analyze the sample complexity of learning linear dynamical systems \emph{driven by unobserved not-white wide-sense stationary (WSS) inputs}.

Harish Doddi, Deepjyoti Deka, Murti Salapaka

Topology learning of networked dynamical systems is an important problem with implications to optimal control, decision-making over networks, cybersecurity and safety. The majority of prior work in consistent topology estimation relies on dynamical systems excited by temporally uncorrelated processes. In this article, we present a novel algorithm for guaranteed topology learning of networks that are excited by temporally (colored) cyclostationary processes, which encompasses a wide range of temporal correlation including wide-sense stationarity. Furthermore, unlike prior work, the framework applies to linear dynamic system with complex valued dependencies, and leverages group lasso regularization for effective learning of the network structure. In the second part of the article, we analyze conditions for consistent topology learning for bidirected tree networks when a subset of the network is unobserved. Here, the full topology along with unobserved nodes are recovered from observed node's time-series alone. Our theoretical contributions are validated on simulated data as well as on real-world climate data.

Deepjyoti Deka, Harish Doddi, Sidhant Misra et al.

Estimating the structure of physical flow networks such as power grids is critical to secure delivery of energy. This paper discusses statistical structure estimation in power grids in the "under-excited" regime, where a subset of internal nodes do not have external injection. Prior estimation algorithms based on nodal potentials or voltages fail in the under-excited regime. We propose a novel topology learning algorithm for learning underexcited general (non-radial) networks based on physics-informed conservation laws. We prove the asymptotic correctness of our algorithm for grids with non-adjacent under-excited internal nodes. More importantly, we theoretically analyze our algorithm's efficacy under noisy measurements, and determine bounds on maximum noise under which asymptotically correct recovery is guaranteed. Our approach is validated through simulations with non-linear voltage samples generated on test grids with real injection data

Harish Doddi, Saurav Talukdar, Deepjyoti Deka et al.

System identification of smart buildings is necessary for their optimal control and application in demand response. The thermal response of a building around an operating point can be modeled using a network of interconnected resistors with capacitors at each node/zone called RC network. The development of the RC network involves two phases: obtaining the network topology, and estimating thermal resistances and capacitance's. In this article, we present a provable method to reconstruct the interaction topology of thermal zones of a building solely from temperature measurements. We demonstrate that our learning algorithm accurately reconstructs the interaction topology for a $5$ zone office building in EnergyPlus with real-world conditions. We show that our learning algorithm is able to recover the network structure in scenarios where prior research prove insufficient.

Deepjyoti Deka, Saurav Talukdar, Michael Chertkov et al.

The topology of a power grid affects its dynamic operation and settlement in the electricity market. Real-time topology identification can enable faster control action following an emergency scenario like failure of a line. This article discusses a graphical model framework for topology estimation in bulk power grids (both loopy transmission and radial distribution) using measurements of voltage collected from the grid nodes. The graphical model for the probability distribution of nodal voltages in linear power flow models is shown to include additional edges along with the operational edges in the true grid. Our proposed estimation algorithms first learn the graphical model and subsequently extract the operational edges using either thresholding or a neighborhood counting scheme. For grid topologies containing no three-node cycles (two buses do not share a common neighbor), we prove that an exact extraction of the operational topology is theoretically guaranteed. This includes a majority of distribution grids that have radial topologies. For grids that include cycles of length three, we provide sufficient conditions that ensure existence of algorithms for exact reconstruction. In particular, for grids with constant impedance per unit length and uniform injection covariances, this observation leads to conditions on geographical placement of the buses. The performance of algorithms is demonstrated in test case simulations.