Graph approach for observability analysis in power system dynamic state estimation

arXiv:2510.26701 · eess.SY, cs.SY · Submitted 2025-10-30 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: Today's paper: "Graph approach for observability analysis in power system dynamic state estimation".

Dev: The proposed approach yields a numerical method that provably executes in linear time with respect to the number of nodes and edges in a graph,

Rosa: First, who's behind it and why it matters.

Paper summary: Rosa: So, we’re talking about this new paper called "Graph approach for observability analysis in power system dynamic state estimation," and basically, they’re proposing a numerical method that runs in linear time based on the number of nodes and edges. It claims this is a scalable solution for analyzing observability in power system dynamic state estimation.

Dev: That sounds pretty promising, Rosa. What's the core idea behind their thesis? They seem to be tackling the computational complexity of traditional methods like Lie differentiation because it doesn't scale well with systems having thousands of state variables, which is a huge problem for large power systems.

Rosa: The paper argues that instead of relying on those complex numerical simulations or repeated empirical Gramians, they build a directed graph from the nonlinear differential equations themselves. This graph represents the dependencies between state and output variables directly. They use this structure to analyze observability, aiming to get results comparable to the established Lie derivative approach but with much less computational overhead.

Taro: From an autonomy research standpoint, I’m interested in how this dependency structure helps when things go sideways in a decentralized environment. If we can map out these dependencies, it gives us a clear view of what information is actually accessible from the measurements we have.

Dev: Exactly, Taro. The methodology they describe involves constructing this digraph D where an edge exists if one state variable explicitly depends on another in the differential equations, which they represent with an adjacency matrix. They then use graph theory concepts like paths and strongly connected components to check for structural observability using a specific condition involving root SCCs.

Rosa: It sounds like the main claim is that this structural observability condition is a direct analytical counterpart to the algebraic rank conditions used in the L approach, which is pretty significant because it bypasses some of the heavy numerical lifting. They examine both decentralized and centralized dynamic state estimation scenarios.

Taro: And they showed that for centralized DSE, their method reduced computation time by one thousand four hundred forty times when compared to the L approach, which is a massive difference in terms of feasibility for real-time applications.

Dev: That factor of one thousand four hundred forty is what really catches my attention from a control perspective; reducing an analysis time from hours down to less than five seconds makes implementing this kind of deep state estimation analysis much more practical for high-frequency control loops where latency is critical.

Conclusion: Rosa: Looking at the title, "Graph approach for observability analysis in power system dynamic state estimation," it really captures the essence of what they’ve done: using graph theory to solve a problem that was previously intractable computationally for dynamic state estimation. The authors, Akhila Kandivalasa and Marcos Netto, have put forward a method that uses the dependency structure inherent in the equations to determine observability.

Dev: I think the implication here is really about scalability in power systems. If this graph-based approach can handle systems with thousands of variables efficiently, it moves observability analysis out of the realm of theoretical study and into practical, real-world operational monitoring for dynamic state estimation.

Rosa: Right, and what we need to focus on is the practical side—how long does this work outside a controlled lab environment? Can we deploy this on actual field robotic systems or remote monitoring stations? That’s a key question for me as a field roboticist.

Taro: I think the real impact is in understanding system resilience under adverse conditions, especially in decentralized setups. If we can quickly assess observability using this graph method, it means that when the world misbehaves and measurements get noisy or sparse, we can rapidly determine which parts of the system state are truly unobservable.

Dev: From a control standpoint, if this method provides fast feedback on observability during an operational event—say, a fault occurs—we can make much faster decisions about what measurements to prioritize or how to stabilize the system based on what we know is actually observable. It gives us a way to quantify uncertainty without needing those lengthy simulations.

Rosa: So, in simple terms, this paper suggests that we don't need exhaustive numerical checks for observability; we can just map the connections and look for certain structural patterns in those connections to guarantee observability, and it does so incredibly fast.

Dev: Precisely. It shifts the bottleneck from massive matrix inversions to efficiently traversing a dependency graph, which is fundamentally a different kind of computational problem entirely. This has big implications for how we design monitoring systems for complex electrical infrastructure.

Akhila Kandivalasa, Marcos Netto

eess.SY, cs.SY

Submitted: 2025-10-30

Updated: 2025-10-30

DOI: 10.1109/PESGM58988.2026.11693506

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 74/100

The gist: The proposed approach yields a numerical method that provably executes in linear time with respect to the number of nodes and edges in a graph, offering a scalable solution for observability analysis

Key concepts

Directed Graph (Digraph): A structure where nodes represent system state variables and directed edges show how one variable explicitly depends on another in the system's equations. This map helps visualize the flow of influence between different parts of the power system dynamics.
Root SCC: A strongly connected component (SCC) within a digraph that has no incoming edges from other components. In this context, it represents a group of state variables where the measurements depend on them, making them critical for determining if the entire system is observable.
Structural Observability Condition: A rule stating that a dynamical system is observable if at least one measured variable exists within every root SCC found in its dependency graph. This provides an analytical way to check observability without needing full numerical simulations.

Terminology

Adjacency Matrix — 13× in this paper · explained in 1 episode
Core — 3× in this paper · explained in 2 episodes
Computational overhead — 1× in this paper · explained in 2 episodes
Fisher Information — 1× in this paper · explained in 3 episodes

Summary

The proposed approach yields a numerical method that provably executes in linear time with respect to the number of nodes and edges in a graph, offering a scalable solution for observability analysis in power system dynamic state estimation.

Introduction and Motivation

Observability refers to the ability to determine a system’s state from measurements, which is crucial for dynamic state estimation (DSE) but remains computationally challenging due to the complexity of traditional numerical methods like Lie differentiation (the L approach). The L approach does not scale effectively, making it impractical for power systems with thousands of state variables. An alternative, the empirical observability Gramian (EOG), requires repeated numerical simulations across many operating conditions, limiting its scalability. This paper introduces a new method that departs from both the EOG and L approaches by using a directed graph (digraph) constructed from nonlinear differential equations to analyze observability, aiming for significantly less computational effort while producing results equivalent to the L approach.

The Graph Approach Framework

The core of the proposed method is based on constructing a digraph, denoted as D = (V, E), where nodes represent state variables and directed edges exist whenever one state variable explicitly depends on another in the differential equations (i.e., ∂x˙ i/∂xj ≠ 0). This dependency structure is compactly represented by an adjacency matrix with entries aij = 1 if the edge (xj → xi) exists. The paper defines concepts such as paths, reachability, and strongly connected components (SCCs), which are central to the analysis.

Structural Observability Condition

The method leverages Proposition 1, which states that a dynamical system is termed structurally observable if for a digraph D built from (1), at least one node from every root SCC is measured. A root SCC is defined as an SCC with no incoming edges. This structural condition serves as the analytical counterpart to the algebraic rank condition used in the L approach. The paper notes that this condition implies that the system is structurally observable if measurements depend on variables within these root SCCs, linking the graph theory directly to observability criteria.

Application in Decentralized Dynamic State Estimation (Case 1)

In Case 1, decentralized DSE scenarios are considered. The state vector and output vectors are defined based on synchrophasor measurements. The adjacency matrix is constructed from the differential equations governing the system dynamics, and a modified Kosaraju-Sharir’s Algorithm is applied to identify SCCs and root SCCs. For the specific test case examined (Example 7.1), the analysis revealed that E′qi, E′di, ωi and δi form a root SCC, indicating structural observability when measurements depend on these variables. This result was verified using the L approach, which yielded a full-rank observability matrix of dimension 7.

Application in Centralized Dynamic State Estimation (Case 2)

For Case 2, centralized DSE is analyzed by performing a Kron reduction to eliminate algebraic constraints, resulting in three sets of state variables and outputs. The adjacency matrix for this scenario is constructed, and the algorithm identifies SCCs such as E˙′q1, E˙′d1, δ1, ω1 as a root SCC. The paper demonstrates that measuring specific variables within these root SCCs—such as VDi = g3 E′qi, E′di, δi and VQi = g4 E′qi, E′di, δi—yields structural observability. This graph-based method achieved an average computation time of less than 5 seconds for this centralized case compared to the L approach's average of 2 hours.

Conclusion and Comparison

The paper concludes that current methods do not scale effectively, especially in centralized DSE, but the proposed graph-based approach provides a substantial reduction in computation time. The method is described as parameter-agnostic and produces results equivalent to the L approach but requires significantly less computational effort, demonstrating a speedup of an average 1440× even for small test systems. Future work will focus on incorporating models of inverter-based resources and developing structure-preserving models.

Table II Summary

Approach Case 1: Decentralized DSE Case 2: Centralized DSE

:---:---:---

L Approach < 5 minutes 2 hours

Graph Approach (Average) 1 second (< 5 seconds) < 5 seconds (Average 1440× speedup)

Table III Summary

The adjacency matrix for the Centralized DSE case shows extensive connectivity among all state variables, leading to three SCCs and one root SCC identified by the algorithm. The paper confirms that measuring at least one variable in each root SCC yields a structurally observable system.

References Cited

[1] A. Abur and A. G. Exposito, “Power System State Estimation: Theory and Application.

Improvements for AI systems

As a fastidious researcher, I have analyzed the provided paper, Graph approach for observability analysis in power system dynamic state estimation. The core contribution of this work is replacing computationally prohibitive methods (like Lie differentiation and Empirical Observability Gramian) with a graph-based approach leveraging Kosaraju-Sharir's algorithm to perform observability analysis in linear time relative to the number of nodes and edges.

The paper demonstrates that structural observability can be determined by analyzing the Strongly Connected Components (SCCs) of a dependency digraph built from the nonlinear differential equations.

Here are specific, actionable improvements for AI systems, derived directly from this research:

A new class of AI-driven state estimation models capable of real-time structural observability verification.
Decentralized and centralized dynamic state estimation (DSE) algorithms optimized for scalability in large-scale power grids (e.g., thousands of nodes).

Specific capabilities of the improved AI system:

A Structural Observability Verifier module that can take a system's nonlinear differential equations (modeled as a directed graph) and instantly determine if the current measurement configuration is sufficient to uniquely determine all states, without performing expensive symbolic differentiation or long-horizon simulations.
An AI-enhanced State Estimator that uses the identified root SCC variables (the minimal set of measurements required for structural observability) to perform state estimation. This allows for optimal placement and selection of synchrophasor measurements in distributed power grids, ensuring maximum information gain with minimum measurement cost, as derived from the paper's analysis of Case 1 and Case 2.
A Speed-Optimized Observability Engine that provides a massive computational speedup (up to 1440x in centralized settings) for checking observability in complex power system models compared to traditional Lie derivative methods, making rapid system diagnostics feasible for real-time grid operations.
An AI framework capable of generating structure-preserving models of power systems that inherently satisfy the structural observability condition, leading to more robust and computationally efficient state estimation algorithms.

Abstract

The proposed approach yields a numerical method that provably executes in linear time with respect to the number of nodes and edges in a graph. The graph, constructed from the power system model, requires only knowledge of the dependencies between state-to-state and output-to-state variables within a state-space framework. While graph-based observability analysis methods exist for power system static-state estimation, the approach presented here is the first for dynamic-state estimation (DSE). We examine decentralized and centralized DSE scenarios and compare our findings with a well-established, albeit non-scalable, observability analysis method in the literature. When compared to the latter in a centralized DSE setting, our method reduced computation time by 1440x.