Sequential fault diagnosis strategy with imperfect tests considering life cycle cost

Abstract

The problem of sequential fault diagnosis is to construct a diagnosis tree that can isolate the failure sources with minimal test cost. Pervious sequential fault diagnosis strategy generating algorithms only consider the execution cost at application stage, which may result in a solution with poor quality from the view of life cycle cost. Furthermore, due to the fact that uncertain information exists extensively in the real-world systems, the tests are always imperfect. In order to reduce the cost of fault diagnosis in the realistic systems, the sequential fault diagnosis problem with imperfect tests considering life cycle cost is presented and formulated in this work, which is an intractable NP-hard AND/OR decision tree construction problem. An algorithm based on AND/OR graph search is proposed to solve this problem. Heuristic search based on information theory is applied to generate the sub-tree in the algorithm. Some practical issues such as the method to improve the computational efficiency and the diagnosis strategy with multi-outcome tests are discussed. The algorithm is tested and compared with previous algorithms on the simulated systems with different scales and uncertainty. Application on a wheel momentum system of a spacecraft is studied in detail. Both the simulation and application results suggest that the cost of the diagnosis strategy can be reduced significantly by using the proposed algorithm, especially when the placement cost of the tests constitutes a large part of the total cost.

Keywords

test sequencing problem / sequential fault diagnosis / imperfect test / life cycle cost / AND/OR graph

References

[1] RaghavanV, ShakeriM, PattipatiK. Optimal and near-optimal test sequencing algorithms with realistic test models [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 1999, 29(1): 11-26

[2] GareyM R. Optimal binary identification procedures [J]. SIAM Journal on Applied Mathematics, 1972, 23(2): 173-186

[3] PattipatiK R, AlexandridisM G. Application of heuristic search and information theory to sequential fault diagnosis [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 1990, 20(4): 872-886

[4] RaghavanV, ShakeriM, PattipatiK R. Test sequencing problems arising in test planning and design for testability [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 1999, 29(2): 153-163

[5] RaghavanV, ShakeriM, PattipatiK. Test sequencing algorithms with unreliable tests [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 1999, 29(4): 347-357

[6] BoumenR, RuanS, de JongI S M, van de Mortel-fronczakJ M, RoodaJ E, PattipatiK R. Hierarchical test sequencing for complex systems [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2009, 39(3): 640-649

[7] KundakciogluO E, UnluyurtT. Bottom-up construction of minimum-cost and/or trees for sequential fault diagnosis [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2007, 37(5): 621-629

[8] ZhangS-g, HuZ, WenX-sen. Test sequencing problem arising at design stage for reducing life cycle cost [J]. Chinese Journal of Aeronautics, 2013, 26(4): 1000-1007

[9] ChenZ-s, YangY-m, HuZheng. A technical framework and roadmap of embedded diagnostics and prognostics for complex mechanical systems in prognostics and health management systems [J]. IEEE Transactions on Reliability, 2012, 61(2): 314-322

[10] ZengY-h, EJ-q, ZhuH, GongJ-ke. Fault diagnosis on cooling system of ship diesel engine based on Bayes network classifier [J]. Journal of Central South University: Science and Technology, 2010, 41(4): 1379-1384

[11] WangS-y, ZuoH-yan. Safety diagnosis on coal mine production system based on fuzzy logic inference [J]. Journal of Central South University, 2012, 19(2): 477-481

[12] YangP, YangS-m, QiuJ, LiuG-j, ChenG-yong. Sequential test strategies with unreliable tests [C]. IEEE AUTOTESTCON 2008, 2008Salt Lake City, UTIEEE587-592

[13] YangP, QiuJ, LiuG-jun. Optimization method for diagnostic strategy with unreliable test [J]. Chinese Journal of Scientific Instrument, 2008, 29(4): 850-854

[14] RuanS, ZhouY, YuF, PattipatiK R, WillettP, Patterson-hineA. Dynamic multiple-fault diagnosis with imperfect tests [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2009, 39(6): 1224-1236

[15] ErdincO, BrideauC, WillettP, KirubarajanT, DebS, MalepatiV. Real-time diagnosis and prognosis with sensors of uncertain quality [C]. Proceedings on 2004 IEEE Aerospace Conference, 2004Big Sky, Montana, USAIEEE3603-3614

[16] YingJ, KirubarajanT, PattipatiK R, Patterson- HineA. A hidden Markov model-based algorithm for fault diagnosis with partial and imperfect tests [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews, 2000, 30(4): 463-473

[17] SinghS, KodaliA, ChoiK, PattipatiK R, NamburuS M, SeanS C, ProkhorovD V, QiaoL. Dynamic multiple fault diagnosis: Mathematical formulations and solution techniques [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2009, 39(1): 160-176

[18] ShakeriM, PattipatiR, RaghavanV, Patterson- HineA. Optimal and near-optimal algorithms for multiple fault diagnosis with unreliable tests [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part C: Applications and Reviews, 1998, 28(3): 431-440

[19] YeX-h, PanJ-l, WangH-x, LiuS-shuang. Test set selection under unreliable test based on a new dynamic greedy algorithm [J]. Transactions of Beijing Institute of Technology, 20101350-1354

[20] PanJ-l, YeX-h, XueQiang. An heuristic genetic algorithm solve test point selecting with unreliable test [C]. 2009 Second International Workshop on Computer Science and Engineering, 2009Qingdao, ChinaIEEE Computer Society227-232

[21] ChenX-x, QiuJ, LiuG-jun. Optimal test selection of materiel based on Bayesian network under test uncertainty [J]. China Mechanical Engineering, 2011379-384

[22] TuF, PattipatiK R. Rollout strategies for sequential fault diagnosis [J]. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 2003, 33(1): 86-99

[23] HyafilL, RivestR L. Constructing optimal binary decision trees is NP-complete [J]. Information Processing Letters, 1976, 5(1): 15-17

[24] BertsekasD P. Rollout algorithms: An overview [C]. Proceedings of the 38th IEEE Conference on Decision and Control, 1999Phoenix, Arizona, USAIEEE448-449

[25] WangW, HuQ-h, YuD-ren. On a multivalued test sequencing problem [C]. Proceedings of the Sixth International Conference on Machine Learning and Cybernetics, 2007Hong Kong, ChinaIEEE2541-2546

[26] WangW, HuQ-h, YuD-ren. Application of multivalued test sequencing to fault diagnosis [C]. The Eighth International Conference on Electronic Measurement and Instruments, 2007Xian, Shanxi, ChinaIEEE737-740

[27] Chinese Journal of Scientific Instrument, 2011, 32(5

[28] YangP, QiuJ, LiuG-jun. Optimized diagnostic strategy generation with multivalued tests [J]. Chinese Journal of Scientific Instrument, 2008, 298): 1675-1678

[29] QSI. Testability engineering and maintenance system (teams) tool [EB/OL]. [2012-06-25]. http://www.teamsqsi.com.