Verifying Diagnosability of Discrete Event System with Logical Formula

GENG Xuena; OUYANG Dantong; HAN Cheng

doi:10.1049/cje.2020.01.008

Volume 29 Issue 2

Turn off MathJax

Article Contents

Article Navigation > Chinese Journal of Electronics > 2020 > 29(2): 304-311

GENG Xuena, OUYANG Dantong, HAN Cheng, “Verifying Diagnosability of Discrete Event System with Logical Formula,” Chinese Journal of Electronics, vol. 29, no. 2, pp. 304-311, 2020, doi: 10.1049/cje.2020.01.008

Citation:

GENG Xuena, OUYANG Dantong, HAN Cheng, “Verifying Diagnosability of Discrete Event System with Logical Formula,” Chinese Journal of Electronics, vol. 29, no. 2, pp. 304-311, 2020, doi: 10.1049/cje.2020.01.008

Citation:

PDF( 1996 KB)

Verifying Diagnosability of Discrete Event System with Logical Formula

doi: 10.1049/cje.2020.01.008

1.
College of Computer Science and Technology, Changchun University of Science and Technology, Changchun 130012, China;
2.
Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education, Jilin University, Changchun 130021, China

Funds: This work is supported by the National Natural Science Foundation of China (No.61702051, No.61602058) and Jilin Province Science and Technology Research Project of China (No.20180201069GX).

More Information

Corresponding author: HAN Cheng (corresponding author) received the B.E., M.S., and Ph.D. degrees in computer science from Changchun University of Science and Technology. He is currently a professor of Changchun University of Science and Technology. His current research interests include virtual reality. (Email:hancheng@cust.edu.cn)
Received Date: 2019-03-07
Rev Recd Date: 2019-11-29
Publish Date: 2020-03-10

Abstract

Abstract

Diagnosability is an important property in the field of fault diagnosis. In this paper, a novel approach based on logical formula is proposed to verify diagnosability of Discrete event systems(DESs). CNFFSM is defined to represent a new model for DES. Each transition in DES can be described as a clause. According to CNF-FSM, we construct a CNF-diagnoser. Based on the resolution principle and CNF-diagnoser, an algorithm is presented to test whether the failure events can be detected or not in a finite number of observable events. Our algorithm can be applied in both off-line diagnosis and on-line diagnosis. Experimental results show that our algorithm can solve the diagnosability problem efficiently.
- Fault diagnosis,
- Diagnosability,
- Discrete event system,
- Finite state machine,
- Conjunctive normal form

FullText(HTML)

References(18)

References

A. Boussif, B. Liu and M. Ghazel, “A twin-plant based approach for diagnosability analysis of intermittent failures”, Proc. of International Workshop on Discrete Event Systems, Xian, China, pp.237-244, 2016.

E. Fabre, L. Helouet, E. Lefaucheux, et al., “Diagnosability of repairable faults”, Discrete Event Dynamic Systems, Vol.1, No.4, pp.1-31, 2017.

M. Cabasino, A. Giua, C.N. Hadjicostis, et al., “Fault model identification and synthesis in Petri nets”, Discrete Event Dynamic Systems, Vol.25, No.3, pp.419-440, 2015.

M. Cabasino, A. Giua and S. Lafortune, et al., “Discrete event diagnosis using labeled Petri nets. An application to manufacturing systems”, Control Engineering Practice, Vol.19, No.9, pp.989-1001, 2011.

G. Zhu, Z. Li, and N. Wu, et al., “Model-based fault identification of discrete event systems using partially observed Petri nets”, Automatica, Vol.96, No.1, pp.201-212, 2018.

X. Geng, D. Ouyang and X. Zhao, “Failure diagnosis for distributed stochastic discrete event system”, Mathematical Problems in Engineering, Vol.2017, No.7680698, pp.1-12, 2017.

Q. He, X. Zhao, D. Ouyang, et al., “Performance analysis and comparison of algorithms for generating minimal hitting sets”, Acta Electonica Sinica, Vol.47, No.5, pp.1101-1110, 2019. (in Chinese)

M. Liu, D. Ouyang, B. Liu, et al., “Grouped diagnosis approach using the feature of problem”, Acta Electonica Sinica, Vol.47, No.5, pp.589-594, 2018. (in Chinese)

D. Ouyang, B. Liu, L. Zhang, et al., “A method of computing minimal conflict sets combining the structure property with the anti-depth SE-tree”, Acta Electonica Sinica, Vol.45, No.5, pp.1175-1181, 2017. (in Chinese)

D. Ouyang, B. Liu, M. Liu, et al., “A block-based diagnostic method combining with the circuit structure”, Chinese Journal of Electronics, Vol.46, No.7, pp.1571-1577, 2018. (in Chinese)

M. Sampath, R. Sengupta, S. Lafortune, et al., “Diagnosability of discrete event systems”, IEEE Transactions on Automatic Control, Vol.40, No.9, pp.1555-1575, 1995.

S. Jiang, Z. Huang, V. Chandra, et al., “A polynomial time algorithm for testing dianosability of discrete event systems”, IEEE Transactions on Automatic Control, Vol.46, No.8, pp.1318-1321, 2001.

C. Keroglou and C.N. Hadjicostis, “Distributed fault diagnosis in discrete event systems via set intersection refinements”, IEEE Transactions on Automatic Control, Vol.63, No.10, pp.3601-3607, 2018.

Y. Pencole, “Diagnosability analysis of distributed discrete event systems”, Proc. of European Conference on Artificial Intelligence, Valencia, Spain, pp.43-47, 2004.

A. Grastien, A. Anbulagan, J. Rintanen, et al., “Diagnosis of discrete-event systems using satisfiability algorithms”, Proc. of AAAI Conference on Artificial Intelligence, Vancouver, British Columbia, Canada, pp.305-310, 2007.

M. Davis and H. Putnam, “A computing procedure for quantification theory”, Journal of the ACM, Vol.7, No.3, pp.201-215, 1960.

A. Metodi, R. Stern, M. Kalech, et al., “Compiling modelbased diagnosis to Boolean satisfaction”, Proc. of AAAI Conference on Artificial Intelligence, Toronto, Canada, pp.305-310, 2012.

X. Zhao and D. Ouyang, “Deriving all minimal consistencybased diagnosis sets using SAT solvers”, Progress in Natural Science, Vol.19, No.4, pp.489-494, 2009.

Relative Articles

Supplements(0)

Cited By

Proportional views