TreeMerge: Efficient Generation of Minimal Hitting-Sets for Conflict Sets in Tree Structure for Model-Based Fault Diagnosis
Xiangfu Zhao, Xiangrong Tong, Dantong Ouyang, Liming Zhang, Yanzhi Hou · IEEE Transactions on Reliability · 2021
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).