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

1 Introduction

Research on future energy systems shows that an electricity network is often tolerant to failures but may collapse after encountering a certain number of failures that take place within a short period of time. The smart grid is the upcoming generation of electricity networks. Challenges faced in the smart grid include prompt, reliable, and informative alarm processing to detect the points of failure. Another aspect is inferring the root cause for failures. Being able to accurately and promptly determine the fault occurrences allows rapid intervention, which leads to faster restoration and lower vulnerability to multiple faults. This work focuses on systems modeled by a Discrete Event System (DES). A DES is a system model representing state dynamics in a discrete manner [Cassandras and Lafortune, 2008]. DES provides a common modeling framework for diagnosis problems retaining the properties with a discrete nature.

2 Research Questions and Contributions

Diagnosis is a topic of Artificial Intelligence (AI) knowledge representation and reasoning. AI diagnosis refers to the detection and identification of failures in a system, which offers the capability to address some of the challenges mentioned above while research questions still remain in the context of on-line diagnosis for DES. The problem of on-line diagnosis of a DES was initially defined by [Sampath et al., 1995]. Given a flow of observable events generated by the underlying system, the problem consists in determining whether the DES is operating normally or not, based on a behavioral model of the system. This work uses the term belief state to represent the set of global states that the system is possibly in after the given observations [Pencolé and Cordier, 2005; Rintanen, 2007]. On-line diagnosis means diagnosing a system on the fly and in real time such that constraints on computational time and memory space are imposed. The challenge is to deal with the complexity of a diagnostic algorithm that monitors on the fly the observable flow and generates a succession of belief states consistent with the flow. However, the size of each belief state and their representation, e.g., in Binary Decision Diagrams (BDD), are exponential w.r.t. the number of system states in the worst case [Rintanen, 2007]. The existing work, except SAT diagnosis, proposes diagnostic algorithms that attempt to compute at any

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

Xingyu Su

The Australian National University, Australia u4383016@anu.edu.au

time a belief state consistent with the observable flow from the time when the system starts operating to the current time. The main drawback of such a conservative strategy is the inability to follow the observable flow for a large system due to the exponential size of the generated belief states and therefore the temporal complexity to handle them. Although SAT diagnosis computes one trace in the system for an observation sequence, the complexity of a SAT problem is proved to be exponential w.r.t. the number of propositional variables, which is linear to the number of state variables [Grastien et al., 2007]. Therefore, SAT diagnosis is not suitable for online diagnosis as the number of observations keeps increasing. Because diagnosis of DES is a hard problem, the use of faster diagnostic algorithms is inevitable. However, these algorithms may be less precise to diagnose a diagnosable system than using an exact model-based diagnostic algorithm, e.g., the diagnoser [Sampath et al., 1995]. Faults are very harmful to a system and expensive to recover from if not correctly diagnosed. Hence, it is essential to examine how to measure the quality of using a potentially imprecise diagnostic algorithm w.r.t. a diagnosable DES model.

This work has made four contributions. First, it defines the precision of a diagnostic algorithm w.r.t. a DES model and proposes a novel approach to verify the precision by constructing a simulation [Su and Grastien, 2014a]. Diagnosability of DES is an important property to measure the quality of diagnosis and the capability of a diagnostic system to identify faults. Diagnosability holds if using the model, a fault can always be diagnosed after it occurs [Sampath et al., 1995]. Furthermore, diagnosability testing has been a well-studied problem. [Jiang et al., 2001] showed that proving non-diagnosability amounts to finding a critical witness, which is a pair of infinite executions on the model that are indistinguishable, i.e., they produce the same observations where one of them is faulty and the other one is nominal. Thus, diagnosability is proved by showing that there is no such witness. This approach is known as the twin plant method. A diagnostic algorithm is defined as precise if the algorithmwill diagnose the fault after it occurs. Precision can be verified using the twin plant method on the condition that a simulation is built. This work defines simulation, which is a modified model that simulates how a diagnostic algorithm runs on a given DES model. The precision holds iff there is no critical witness in the synchronization of the DES model and the simulation.

Second, this work proposes a new class of on-line DES diagnostic algorithms, called Independent-Window Algorithms (IWAs), namely Al1, Al2, and Al3 [Su and Grastien, 2013]. The strategy of IWAs differs from the conservative approach. IWAs only apply on the very last events of an observable flow and forget about the past, which helps to reduce the size of a belief state representation, e.g., in BDD. IWAs slice an observation sequence into time windows so that each time window is diagnosed independently. IWAs diagnose a specified number of observations for one time window and move to another time window without keeping any information. The differences among three IWAs are the time window selections.

Third, this work proposes Time-Window Algorithms (TWAs), namely Al5 and Al6 [Su and Grastien, 2014b]. A TWA is a compromise between the extreme strategies of exact diagnosis and imprecise diagnosis, e.g., a compromise between the diagnoser [Sampath et al., 1995] and IWAs [Su and Grastien, 2013]. Such a compromise is achieved by looking for the minimum piece of information to remember from the past, called abstracted belief state, so that a window-based algorithm will certainly ensure the same precision as using an exact diagnostic algorithm. Compared to Al5, Al6 improves the precision without requiring a more detailed state categorization, called abstract states.

Finally, this work evaluates the performance of IWAs and TWAs measured by the precision of diagnosis, computational time, peak memory use, average memory use, and diagnostic distance. Diagnostic distance refers to the number of observations between a fault occurrence and the fault diagnosis of a diagnostic algorithm. This work compares IWAs and TWAs in the above aspects with the exact diagnostic algorithm encoded by BDD [Schumann, 2007], named as Al0. This work also examines the impact of the time window size. The results of IWAs show that Al3 can achieve the same precision as using Al0 to diagnose a component-based DES model. Also, the run time and the average memory use are consistently reduced compared to using Al0. The results of Al3 indicate that using a larger time window, i.e., fewer time windows, leads to shorter computational time, as well as lower peak and average memory use than using a smaller time window. The results of TWAs demonstrate that Al5 and Al6 reduce the peak and average memory use compared to using Al0. However, the trade-off is that the computational time is longer than that of using Al0 due to the operations performed on abstract belief states between the time windows.

3 FutureWork

The future work consists of four aspects. The first aspect is to investigate the impact of using an imprecise diagnostic algorithm on a non-diagnosable system, e.g., categorizing a scenario into nominal, faulty, or ambiguous. The performance needs to compared with the result of using an exact diagnostic algorithm. Second, backbone diagnosis aims to identify what is known for sure during a diagnostic process. Both TWAs and backbone diagnosis remember some of the information from the past. The difference is that TWAs keep track of the abstract belief state of a system while backbone diagnosis maintains the known information, e.g., a certain variable holds or not. The third aspect is to join diagnosis with planning so that diagnosis leads to accurate alarm processing while planning leads to robust configuration and restoration. The goal is to improve the efficiency of event handling, minimize the impact of power loss, and restore to a robust state withholding the diagnosability property. The fourth aspect is extending to research on activity recognition and real-time sensor data segmentation using varied time windows [Okeyo et al., 2014].