Approximating All Most-Preferred Diagnoses using Greedy Algorithms

For applications in which computing the set of all diagnoses is important, algorithms that compile the system model, such as the ATMS, are well-known. However, the space- and time-complexity of such approaches can be prohibitively large. We show how we can use a preference function over the space of diagnoses to develop approximation algorithms for computing the most-preferred diagnoses (MPD). We show that the MPD problem can be approximated by greedy algorithms such that the preference weighting of the approximate set of diagnoses is within (1 – 1/e) of that of the exact set of diagnoses. We demonstrate how the MPD problem can be solved for iterative diagnosis using a fast stochastic diagnosis engine, and by compilation approaches using prime implicant and DNNF compilation languages. We present empirical evidence that the compilation algorithms enable space reductions of several orders-of-magnitude over the full compilation, while losing relatively little query completeness.