Fault Diagnosis of Hierarchical Discrete-Event Systems Based on State-Tree Structures

In this article, fault diagnosis of hierarchical discrete event systems (HDES) is investigated using state-tree structures (STS). As a structured formalism, an STS provides a compact representation for an HDES model and utilizes binary decision diagrams (BDDs) for efficient symbolic computation. Building on the above advantages of STS, with "on-the-fly" analysis technique addressed, the issue of offline diagnosability verification can be efficiently tackled. A symbolic approach of diagnoser construction is presented based on predicates and predicate transformers. With the BDD representation of predicates, the state space of the diagnoser is compressed and managed such that the occupied computer memory space is greatly reduced. Besides, instead of flattening an STS model to its equivalent monolithic model at first and then constructing the entire diagnoser for such a model, a heuristic on-the-fly algorithm based on the depth-first search, which unfolds the STS model gradually, is proposed for the level-by-level diagnosability analysis. Finally, several case studies are provided for evaluating the effectiveness and the scalability of the proposed method.