Dynamic Multiple Fault Diagnosis: Mathematical Formulations and Solution Techniques

Imperfect test outcomes, due to factors such as unreliable sensors, electromagnetic interference, and environmental conditions, manifest themselves as missed detections and false alarms. This paper develops near-optimal algorithms for dynamic multiple fault diagnosis (DMFD) problems in the presence of imperfect test outcomes. The DMFD problem is to determine the most likely evolution of component states, the one that best explains the observed test outcomes. Here, we discuss four formulations of the DMFD problem. These include the deterministic situation corresponding to perfectly observed coupled Markov decision processes to several partially observed factorial hidden Markov models ranging from the case where the imperfect test outcomes are functions of tests only to the case where the test outcomes are functions of faults and tests, as well as the case where the false alarms are associated with the nominal (fault free) case only. All these formulations are intractable NP-hard combinatorial optimization problems. Our solution scheme can be viewed as a two-level coordinated solution framework for the DMFD problem. At the top (coordination) level, we update the Lagrange multipliers (coordination variables, dual variables) using the subgradient method. At the bottom level, we use a dynamic programming technique (specifically, the Viterbi decoding or Max-sum algorithm) to solve each of the subproblems, one for each component state sequence. The key advantage of our approach is that it provides an approximate duality gap, which is a measure of the suboptimality of the DMFD solution. Computational results on real-world problems are presented. A detailed performance analysis of the proposed algorithm is also discussed.