The role of obdds in controlling tha complexity of model based diagnosis

The computation of consistency-based diagnoses is addressed by using OBDDs (Ordered Binary Decision Diagrams) for encoding both the system model and the resulting diagnoses. We show that the time needed for solving a diagnostic problem is polynomial in the size of the OBDD encoding the system model. While in the worst case such OBDD may have an exponential size, a suitable ordering of the domain variables can lead to OBDDs of small size. The paper introduces heuristics for selecting a suitable ordering of the variables and discusses their impact on the encoding size of complex system models. The approach is extended to deal with ambiguous observations and non-deterministic domain theories. Extensive experimental data concerning a complex real world domain show the effectiveness of the approach in efficiently solving a large test set of diagnostic problems involving multiple faults. Such efficiency is preserved when we consider diagnostic cases with ambiguous observations.