Model-Based Fault Diagnosis Of Discrete Event Systems Using Petri Nets And Integer Linear Programming

The rapid development of contemporary electronic information technology has spawned many large and complex systems,such as high-speed trains,launch vehicles,etc.Complex systems are often composed of a considerable number of subcomponents that transmit and exchange information according to specific rules,which undoubtedly increases the risk of system failure.A fault is any event that changes the expected behavior of a system,which degrades the performance and throughput of the system,and even causes serious accidents.Thus,in recent decades,in both academia and industry,fault diagnosis is an active research area.Fault diagnosis consists in timely and accurately detecting the number and locations of faults according to the system output such that the engineers can repair the faults and restore the system.A straightforward approach of diagnosing a system is to quantitatively measure the operat-ing parameters of its components.Although this approach is simple and easy to implement,it can only be applied to a system that has already been built and cannot provide theoreti-cal guidance and qualitative analysis for the design and maintenance of a system.Thus,a variety of mathematical model based and systematical fault diagnosis approaches have been reported in literature,which not only describe algorithms for fault detection but also provide various theoretical tools for analyzing faults.In this thesis,we deal with fault diagnosis is-sue using faulty Petri nets and fault-free Petri nets.A faulty Petri net describes not only the regular but also the faulty behavior of a system,which can always offer an accurate diagno-sis decision regarding the occurrence of faults.However,we have to exhaustively foresee all possible faults when constructing a faulty Petri net model of a system and thus it is difficult to obtain a faulty net model in reality.On the other hand,a fault-free Petri net characterizes only the regular behavior of a system,which is easier to obtain than a faulty net.However,a fault-free Petri net can only provide multiple estimations on the number and locations of faults.A further testing of the real physical system is required to precisely localize the faults.This paper is devoted to reducing the computational complexity of the faulty Petri net based approaches and improving the identification accuracy of the fault-free Petri net based ones.The main contributions of this research are summarized as follows.1.In order to improve the diagnostic accuracy and operational efficiency of faulty Petrinet based methods,we introduce the notion of an overall fault status and developa diagnosis algorithm based on integer linear programming(ILP)and labeled Petri nets(LPN).The existing faulty Petri net based fault diagnosis approaches usually detect the individual fault separately,which will miss a kind of fault:the system has failed,but the diagnosis of individual fault does not reveal this.The introduction of overall fault status remedy this scenario and can predict the occurrence of faults in advance such that the security of fault-sensitive systems can be improved.A fault diagnosis approach is often originally reported for a special class of labeled Petri nets,called partially labeled Petri nets.In order to extend the approaches based on partially LPN to the case of LPN,the observable transition sequences corresponding to an observation require to be enumerated,which will greatly increase the computational complexity.The proposed ILP-based diagnosis algorithm avoids enumerating these sequences and reduces the computational complexity.2.To apply theoretical approaches to the real-world industry,an important step is to properly categorize the existing fault diagnosis approaches and compare their compu-tational efficiency in different situations.Based on the different definitions of diagno-sis function in existing studies,we define optimistic and pessimistic diagnoses,which provide a novel criterion for the classification of diagnosis approaches.Meanwhile,we explore a general technique that extends a given diagnosis approach for partial-ly LPN to the case of LPN,and verify its availability by successfully extending the basis-marking-based diagnosis approach.In order to make the diagnosis approaches have the same interface for comparison,we convert pessimistic diagnosis approaches to optimistic ones and extend them to the case of LPN by employing the proposed extension technique.3.The diagnosis approaches based on fault-free Petri nets can only provide multiple estimations of the number and locations of faults.Thus,a key issue is how to reduce the number of estimations and improve the diagnostic efficiency.By equipping places with sensors,some unobservable places become practically observable and thus the system output contains not only transitions but markings of observable places(called partial marking).We formally define the system evolution as a sequence composed by transitions and partial markings.The partial marking significantly reduces the solution space of possible faults,making it easier to identify the exact locations of faults.Based on the observed system evolution,we construct and solve an ILP model to obtain an estimation of the number and locations of faults.To test the various possibilities of failures,we propose an iterative algorithm that updates and solves the previously built ILP model multiple times.Finally,we identify an acyclic unobservable subnet that corresponds to the actual system faults.4.When constructing the faulty Petri net model of a complex system,it is always unre-alistic to predict all possible faults.Thus,we develop an algorithm that automatically identify a faulty model of a system.By allowing the original fault-free Petri net to contain unobservable transitions,we define a new type of system output and build the corresponding ILP problem based on the output.By solving the ILP problem,several faulty transitions(also unobservable transitions)are obtained that are added into the original fault-free Petri net.Then,the system output is re-recorded and the algorithm is executed again to identify the subsequent faulty transitions.Finally,a conclusion is reached and the future works concerning fault diagnosis based on faulty and fault-free Petri nets are prospected.