Acquisition and Judgement of Implicit Hitting Sets for Model-Based Diagnosis

Model-based diagnosis mainly models the behavior of the system, and once the abnormal behavior is observed, a diagnosis algorithm is run on the system model to return a possible explanation. The existing diagnosis algorithm computes a minimal hitting set (MHS) each time a conflict set is identified, and then verifies whether this MHS satisfies the system observations. While this approach reduces the generation of redundant solution sets, the difficulty of computing the MHSs of conflict sets increases exponentially with the number of conflict sets. Since computing the MHS of a partial conflict set is not necessarily a diagnosis, it is also time-consuming to check whether the MHS satisfies the system observations. We have designed a filtering function to remove low-quality conflict sets based on the diagnosis cardinality and quantity, while ensuring that the obtained hitting sets are as diagnosis as possible. In addition, to facilitate the rapid verification of hitting sets for diagnosis, we have proposed an efficient decision algorithm based on the logical relationships of the circuit. In the experimental section, we conducted a detailed analysis comparing the runtime and diagnosis yield under varying numbers of fault conditions. Compared to state-of-the-art algorithms, our approach showed efficiency improvements of up to 2-40 times in runtime and diagnosis yield enhancements ranging from 5-200 times.