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.

Model-based diagnosis (MBD) with multiple observations is complicated and difficult to manage over. In this paper, we proposed two new diagnosis models, namely, the Compacted Model with Multiple Observations (CMMO) and the Dominated-based Compacted Model with Multiple Observations (D-CMMO), to solve the problem in which a considerable amount of time is needed when multiple observations are given and more than one fault is injected. Three ideas are presented in this paper. First, we propose to encode MBD with each observation as a subsystem and share as many system variables as possible to compress the size of encoded clauses. Second, we utilize the notion of gate dominance in the CMMO approach to compute Top-Level Diagnosis with Compacted Model (CM-TLD) to reduce the solution space. Finally, we explore the performance of our model using three fault models. Experimental results on the ISCAS-85 benchmarks show that CMMO and D-CMMO perform better than the state-of-the-art algorithms.

For many high-tech fields such as space exploration, nuclear technology, and smart automobiles, it is vital to timely find faulty components of man-made devices to ensure safety. However, there is nearlynoenough diagnostic experience accumulated in these new devices, and thus, it is hardly suitable to only apply the traditional expert/experience-based fault diagnosis approach. Thus, model-based diagnosis was proposed for efficient detection of faulty components; this approach explores the behavioral and structural information of the device to be diagnosed, and no experience is required. In model-based diagnosis, for a device to be diagnosed, minimal conflict sets of components are first generated, and all minimal hitting-sets for them will be derived as candidate diagnoses. Therefore, it is vital to efficiently generate all minimal hitting-sets to find the final diagnosis. Unfortunately, it is proven to be NP-hard when deriving all minimal hitting-sets for given minimal conflict sets. To improve the computing efficiency, in this article, we propose a novel approach calledTreeMerge, which considers a special type oftreestructure of minimal conflict sets of large sizes since structural information usually plays an important role in solving complex problems. Theoretically, compared with other algorithms, the time complexity of the new algorithm is greatly reduced, as the time complexity of the new algorithm becomeslinearrather thanquadratic. Furthermore, experimental results on multiple synthetic and benchmark examples show that the proposedTreeMergealgorithm is more efficient than many other state-of-the-art methods, with a reduction ofseveral orders of magnituderuntime (seconds).