Automated Benchmark Model Generators for Model-Based Diagnostic Inference

The task of model-based diagnosis is NP-complete, but it is not known whether it is computationally difficult for the “average ” real-world system. There has been no systematic study of the complexity of diagnosing real-world problems, and few good benchmarks exist to test this. Real-world-graphs, a mathematical framework that has been proposed as a model for complex systems, have empirically been shown to capture several topological properties of real-world systems. We describe the adequacy with which a real-world-graph can characterise the complexity of model-based diagnostic inference on real-world systems. We empirically compare the inference complexity of diagnosing models automatically generated using the realworld-graph framework with comparable models from well-known ISCAS circuit benchmarks. We identify parameters necessary for the real-worldgraph framework to generate benchmark diagnosis circuit models with realistic properties. 1 Diagnostic Inference for Complex Systems Model-based diagnosis (MBD) focuses on determining whether an assignment of failure status to a set of modevariables is consistent with a system description and an observation (e.g., of sensor values). This problem is known to be NP-complete [Bylander et al., 1991; Friedrich et al., 1990]. However, this is a worst-case result, and some NP-complete problems, such as graph colouring [Cheeseman et al., 1991], are known to be tractable for particular problem classes. We focus on the average-case complexity of MBD algorithms on real-world problem instances. At present, it is not known whether MBD is computationally difficult for the “average” system. There has been no systematic study of the complexity of diagnosing real-world problems, and few good benchmarks exist to test such a conjecture. This article makes two main contributions. First, it describes an algorithm for automatically generating diagnostic benchmark models that can be used to analyse the performance of diagnostic inference algorithms. This mode