درباره KK-diagnosability از شبکه های پتری از طریق برنامه ریزی خطی عدد صحیح

This paper deals with the problem of diagnosability of a fault after the firing of a finite number events (i.e., KK-diagnosability). This problem corresponds to diagnosability of a fault within a finite delay in the context of discrete event systems. The main contribution of this paper is a necessary and sufficient condition for KK-diagnosability of bounded nets. The proposed approach exploits the mathematical representation of Petri nets and the Integer Linear Programming optimization tool. In particular no specific assumptions are made on the structure of the net induced by the unobservable transitions, since the proposed approach permits to detect also the undiagnosability due to the presence of unobservable cycles.

The fault diagnosis is crucial for the safety of both systems and operators in industry. Fault diagnosis has received a lot of attention in the discrete event systems (DES) community since the early 90s (Sampath, Sengupta, Lafortune, Sinnamohideen, & Teneketzis, 1995). Diagnosability of DES deals with the possibility of detecting, within a finite delay, the occurrences of unobservable fault events using the record of observed events. Fault detection consists of on-line monitoring the system using the record of observed events to timely provide the set of faults that could have happened. The formal definition of diagnosability has been given in the framework of finite state automata and regular languages (Sampath et al., 1995 and Zad et al., 2005). Necessary and sufficient conditions for diagnosability of DES modeled as automata have been given in Sampath et al. (1995). The diagnosability test is based on another automaton called diagnoser which gives, after each observed event, a set of faults that could have happened ( Sampath et al., 1995), or a set of fault states that the system could have reached ( Zad et al., 2005). The diagnoser approach has been used to extend the diagnosability concept to stochastic automata ( Lunze & Schröder, 2001), and to the decentralized case ( Debouk, Lafortune, & Teneketzis, 2000). The concept of diagnosability itself has been also extended in Paoli and Lafortune (2005). The problem of diagnosability has been recently tackled within the Petri nets (PNs) framework. PNs have a twofold representation: graphical and mathematical. The mathematical representation of PNs allows use of standard tools, such as Integer Linear Programming, to solve DES diagnosis problems. The graphical nature helps to recognize if a model belongs to a certain net subclass. If this is the case, efficient algorithms that exploit the peculiarity of a given subclass can be devised. Furthermore, the local state representation often helps in reducing both computational complexity and memory requirements when solving the diagnosis problem. Indeed, the building of a diagnoser requires the exploration of the state space, whose number of nodes grows exponentially with respect to the net size. Although a number of results are now available for fault detection when DESs are modeled as PNs, only few of them are available for diagnosability. Two approaches are mainly adopted when PNs are used: (1) the first consists in computing a graph from a net system; diagnosability test and/or online fault detection are then performed by using this graph; (2) the second provides algorithms which perform the diagnosability test and/or online fault detection working directly on the net model. In this case the mathematical representation of PNs is exploited. As for approach (1), in Ushio, Onishi, and Okuda (1998) the concept of diagnosability is formulated for PN systems, and a diagnoser-based approach is used to check this property assuming that the net marking is observable, all transitions are not observable, and the faults are associated to transitions. in this case the diagnoser turns to be equal to the reachability graph of the PN system with some additions. A sufficient condition for diagnosability of unbounded PNs is also presented. In Chung (2005) Chung presents a similar approach adding the assumption that some transitions are observable. In Cabasino, Giua, and Seatzu (2009b) two graphs are presented, the modified basis reachability graph (MBRG) and the basis reachability diagnoser (BRD), assuming that the net marking is not observable. This approach is derived from the one proposed by the same authors in Cabasino, Giua, and Seatzu (2010) for fault detection, and it recalls the idea of reduced observer for fault detection proposed by Boel et al. in Boel and Jiroveanu (2004). Both the approaches proposed in Boel and Jiroveanu (2004) and Cabasino et al. (2010) require the PN model to be bounded. Although in most of the cases these two graphs are in general smaller than the reachability graph, the procedure proposed to build the MBRG can require a number of steps equal to the cardinality of the reachability set. Furthermore, the proposed diagnosability test requires to check the existence of cycles in the BRD, which, in the worst case, is a task with exponential complexity in time ( Sampath et al., 1996 and Zad et al., 2003). Similarly, in Jiroveanu and Boel (2010) a automata called ROF-automaton, which may have state space that is significantly smaller than the reachability graph, is proposed to check diagnosability of bounded nets without unobservable cycles. In their recent work (Cabasino, Giua, Lafortune, & Seatzu, 2009a), Cabasino et al. have also presented a necessary and sufficient condition for unbounded nets, which is based on the analysis of a net, called verifier net, that is built from the initial system. As in Cabasino et al. (2009b), the proposed approach for unbounded nets requires to search for the existence of cycles in the coverability graph of the verifier net, which is computationally demanding. Furthermore, the authors claim that when applicable the approach proposed in Cabasino et al. (2009b) may be preferable to the one in Cabasino et al. (2009a), because it also allows to solve the diagnosis problem within the same framework. Different papers deal also with approach (2). In particular, using the assumption that the net marking and the transitions set are partially observable, and investigating the relation between diagnosability and the properties of the TT-invariants of the net, a sufficient condition for diagnosability based on linear programming is proposed in Wen, Li, and Jeng (2005). In Trevino, Ruiz-Beltran, Rivera-Rangel, and Lopez-Mellado (2007) a sufficient condition has also been presented for safe and strongly connected PNs with an output function that associates an output vector to each net marking (interpreted PNs). Two sufficient conditions have been presented by the authors in Basile, Chiacchio, and De Tommasi (2008): the first is for undiagnosability of a fault transition tftf, while the second is for diagnosability of tftf. Such conditions use the concept of g-marking introduced for online fault detection in Basile, Chiacchio, and De Tommasi (2009a). For the sake of completeness, different approaches to the fault diagnosis of DES modeled by PNs have been proposed in Lefebvre and Delherm (2007) and Wu and Hadjicostis (2005). In both cases it is assumed that the net marking is partially (Lefebvre & Delherm, 2007) or completely (Wu & Hadjicostis, 2005) observable, even if unobservable events (transitions) are admitted. However, they do not explicitly address the problem of diagnosability.

A necessary and sufficient condition to check KK-diagnosability of a fault transition in a bounded PNs has been provided in this paper for both unlabeled and labeled systems. The concept of KK-diagnosability corresponds to the diagnosability within a finite delay. The main results are expressed in terms of ILP problems, that can be easily solved by using off-the-shelf tools. The proposed approach does not require any specific assumption on the structure of the net induced by the unobservable transitions, and it allows to cast the diagnosability problem in the same framework adopted for fault diagnosis in Basile et al. (2009a) and Dotoli et al. (2009). Furthermore, the proposed approach does not require neither any explicit estimation of the reachability set, nor any search of paths in graphs.