Automated Benchmark Model Generators for Model-Based Diagnostic Inference

Automated Benchmark Model Generators for Model-Based Diagnostic Inference∗Gregory Provan and Jun WangDepartment of Computer Science,University College Cork, Cork, Irelandg.provan,jw8@cs.ucc.ieAbstract generator can be applied to any domain, and can generatemodels that accurately capture the properties of complex sys-The task of model-based diagnosis is NP-complete, tems, given as input a library of domain-dependent compo-but it is not known whether it is computationally nent models. In particular, we propose a real-world graphdifficult for the “average” real-world system. There model, that, given a model with n components, uses a smallhas been no systematic study of the complexity set of domain-dependent parameters to specify the complex-of diagnosing real-world problems, and few good ity of diagnostic inference for a device. We compare thebenchmarks exist to test this. Real-world-graphs, predictions made by our model to results obtained from IS-a mathematical framework that has been proposed [ ]CAS circuit benchmark models Harlow, 2000 . By empir-as a model for complex systems, have empirically ically comparing generated models with benchmark modelsbeen shown to capture several topological proper- we show the model-generation parameters best suited for IS-ties of real-world systems. We describe the ad- CAS circuits. This approach circumvents the difficulty ofequacy with which a real-world-graph can char- assembling a large suite of test problems ...