Diagnosis using bounded search and symbolic inference

Model-based diagnosis can be framed as optimization for constraints with preferences (soft constraints). We present a novel algorithm for solving soft constraints that generalizes branch-andbound search by reasoning about sets of assignments rather than individual assignments. Because in many practical cases, sets of assignments can be represented implicitly and compactly using symbolic techniques such as decision diagrams, the setbased algorithm can compute bounds faster than explicitly searching over individual assignments, while memory explosion can be avoided by limiting the size of the sets. Varying the size of the sets yields a family of algorithms that includes known search and inference algorithms as special cases. Experiments indicate that the approach can lead to significant performance improvements.