TreeMerge: Efficient Generation of Minimal Hitting-Sets for Conflict Sets in Tree Structure for Model-Based Fault Diagnosis

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 nearly
no
enough 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 called

TreeMerge

, which considers a special type of
tree
structure 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 becomes
linear
rather than
quadratic
. Furthermore, experimental results on multiple synthetic and benchmark examples show that the proposed
TreeMerge
algorithm is more efficient than many other state-of-the-art methods, with a reduction of
several orders of magnitude
runtime (seconds).