Time Decomposition for Diagnosis of Discrete Event Systems (Extended Abstract)

Xingyu SuIJCAI 2016

Introduction

As critical infrastructure—most notably the modern "smart grid"—grows in complexity, the task of real-time monitoring becomes a significant data processing challenge. Researchers typically model these networks as Discrete Event Systems (DES). In this framework, diagnosis involves analyzing a continuous stream of observable events, such as alarms or status changes, to determine if a hidden fault has occurred. However, the sheer volume of data generated by large-scale systems often overwhelms traditional diagnostic tools.

The Computational Bottleneck

The standard approach to DES diagnosis involves maintaining a "belief state," which represents the set of all possible states the system could occupy given the observations received so far. As time progresses and the observation sequence grows, the size of this belief state tends to increase exponentially.

Existing exact methods, including those utilizing Binary Decision Diagrams (BDDs) or SAT solvers, eventually encounter a "state explosion" problem. These methods either exhaust available memory or become too computationally expensive for real-time, on-line monitoring. To address this, there is a critical need for diagnostic algorithms that can maintain high precision while operating within strict memory and time constraints.

Proposed Methodology: Window-Based Decomposition

This research proposes a shift away from the "conservative" approach of retaining the entire system history. Instead, the author introduces two classes of algorithms that utilize time-based decomposition to manage computational load:

1. Independent-Window Algorithms (IWAs)

Algorithms $Al_1, Al_2,$ and $Al_3$ partition the observation sequence into distinct, independent time windows. By diagnosing each window in isolation and "forgetting" the preceding history, these algorithms prevent the belief state from growing indefinitely. While this approach risks losing historical context, it significantly reduces the memory footprint.

2. Time-Window Algorithms (TWAs)

Algorithms $Al_5$ and $Al_6$ represent a hybrid approach. Rather than forgetting the past entirely, they carry over an abstracted belief state between windows. This abstraction captures the essential information required to maintain diagnostic precision in the current window without the overhead of the full state history.

To ensure these simplified approaches remain reliable, the paper introduces a formal definition of precision and a simulation-based verification method. This framework allows researchers to prove that a window-based algorithm will detect faults as effectively as a full, exact model.

Key Insights and Performance Trade-offs

The evaluation of these algorithms against an exact BDD-encoded diagnostic model ($Al_0$) revealed several critical insights into the nature of system monitoring:

  • The Efficiency of Forgetting: The study demonstrates that the entire history of a system is often unnecessary for accurate fault detection. Specifically, algorithm $Al_3$ (an IWA) achieved the same precision as the exact algorithm while consistently reducing both runtime and average memory usage.
  • The Abstraction Tax: While TWAs successfully reduced peak memory usage, making them ideal for hardware with strict memory limits, they were occasionally slower than exact methods. This is due to the computational overhead required to calculate the abstracted belief states during window transitions.
  • Precision vs. Completeness: A system can be "imprecise" regarding its general state while remaining perfectly "precise" regarding fault detection. By focusing specifically on fault-related precision, the proposed algorithms achieve high utility with lower resource consumption.
  • Optimal Window Sizing: There is a strategic balance to be struck in window duration. Larger windows reduce the frequency of window transitions (saving time) but result in larger belief states within each window (increasing memory usage).

Conclusion and Future Directions

This work provides a theoretical and practical foundation for more scalable diagnostic systems. By decomposing the diagnostic task into manageable time windows, it is possible to monitor complex DES models in real-time without the exponential growth of belief states.

Future research will focus on expanding this framework to handle non-diagnosable systems, where fault scenarios may be inherently ambiguous. Additionally, the author aims to explore "backbone diagnosis" to identify certainties within the diagnostic process and integrate these fast diagnostic tools with automated planning systems. Such integration would enable "self-healing" protocols, allowing infrastructure like power grids to respond autonomously and immediately to detected faults.

Summary updated

BibTeX
@inproceedings{su2016time,
  author = {Xingyu Su},
  title = {{Time Decomposition for Diagnosis of Discrete Event Systems (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure