Effective Fault Identification Approach for Model-Based Diagnosis

What the paper says

In the domain of model-based diagnosis (MBD), the identification of the most probable faulty components entails the initial computation of candidate diagnoses across all system elements, followed by the application of Bayesian inference to derive their posterior failure probabilities. However, this conventional approach necessitates the extraction of minimal conflict sets (MCSs) for all components—a prerequisite for generating candidate diagnoses—and subsequently solving for minimal hitting sets (MHSs) of the MCSs. Both tasks are inherently NP-hard, imposing prohibitive computational complexity as system scale increases. Even most advanced diagnostic algorithms encounter significant challenges in enumerating all diagnoses, or even a cardinality-minimal solution, within tractable time constraints for large-scale systems. To address these limitations, this work introduces a novel incremental methodology for efficiently approximating posterior component failure probabilities. A foundational framework is first proposed, leveraging structural relationships inherent to hitting sets to probabilistically characterize component fault likelihoods. Building upon this foundation, two minimization theorems are formally established, accompanied by closed-form parameterizations to optimize computational efficiency. Crucially, the proposed method bypasses the explicit enumeration of diagnoses by directly inferring the most probable faulty components from conflict set analyses. Empirical evaluations demonstrate that the approach not only sustains diagnostic accuracy exceeding 95% but also achieves a substantial computational acceleration—surpassing contemporary state-of-the-art algorithms by multiple orders of magnitude.