Research On Algorithm For Diagnosability Verification Of Discrete Event Systems

With the rapid development of modern society, more and more large complex systemsare applied to our life and production. While enjoying the convenience and efficience whichall kinds of systems bring to us, we also suffer the bothers of inconvenience and disastercaused by system failure. Therefore, timely detecting and troubleshooting the fault become akey issue in the process of system operation and system control. Fault diagnosis come intobeing a dedicated technology, which mainly used to detect the fault, locate the fault,determinethe type of fault and assist fault recovery. Model based diagnosis(MBD) is a novel automaticdiagnostic reasoning technology appeared in recently years. Unlike traditional diagnosticapproachs, MBD approach need to build the structural model or behavior model of system.The predicted behavior should be obtained through the system model, then comparing thesystem prediction and actual observation, reasoning the diagnostic results which can explainthe discrepancy. According to the running characteristics of the diagnosed system, MBD isdivided into diagnosis of static systems, of continuous dynamic systems, of discrete eventsystems(DESs), of hybrid systems. We mainly focuse on the diagnosis of DESs, especially onthe research on diagnosability verification algorithm of DESs.In this paper, to optimize the diagnosability verification algorithm, we had do somethingfrom two aspects: on the one hand, the paper extended the scope of application of DESs byproposing corresponding verification algorithm under different frameworks; on the other hand,the paper accelerated basic diagnosability verification process to improve the efficiency of thealgorithm by model simplification. Specific details are as follows:(1) In the decentralizeddiagnostic framework, a new polynomial algorithm for verification of codiagnosability wasproposed. The specific algorithm is divided into two case, one is used to verify theF-codiagnosability, and the other is used to verify the NF-codiagnosability. Both of them are achieved by constructing a testing automaton which extracts the fault path and the normalpath to compare, then searching for offending cycles to determine the codiagnosability. Thedifference is that, the former is built by taking fault path automaton as major matching object,but the latter taking normal path automaton as major matching object. In fact the mainpurpose of verifing codiagnosability is the verification of the F-codiagnosability, but previousverification algorithm does not distinguish them, so it contains a lot of invalid operation.Moreover, this algorithm only considers observable events but omits unobservable eventsduring the process of building testing automata, so it can reduce a lot of redundant space.Both experimental results and case study have proven the efficiency and effectiveness of thealgorithm.(2) In the distributed diagnostic framework, a new algorithm for verification ofregional diagnosability was proposed. The region is the subsystem obtained by synchronizingsome local model through communication events. Previous distributed diagnosability isachieved by synchronizing twin plant model, this time will use NF plant model. First takingthe local model where fault occurred to build NF plant model, then checking diagnosability ofthe fault. Here regional model also is the faulty local model. If the fault is not diagnosable, tofind a neighboring local model to merge a new regional model, then building new NF plantmodel and checking diagnosability again. Extending the regional model until the fault con bediagnosed or the regional model become global model. Because NF plant model is easier thanthe twin plant model, new regional diagnosability is more efficent.(3) Traditional methods areall based on original model but this paper is based on reduced model. Model reduction ismainly used to reduce unobservable events of original model. First it introduces the threerepresentation of automaton–two dimensional matrix, transition set, linked automaton. Thenintroducing the transition set reduction(TSR) method, and proposing a linked listreconstruction (LLR) algorithm based on linked automaton. LLR is achieved by changing thelinked relation of state node, it only need add the linked out transitions of end node to thebegin node. Therefore, the operation of LLR is simple and efficient.