Jinbo Huang, Adnan Darwiche
Knowledge compilation is one of the more traditional approaches to model-based diagnosis, where a compiled system model is obtained in an off-line phase, and then used to efficiently answer diagnostic queries on-line. The choice of a suitable representation for the compiled model is critical to the success of this approach, and two of the main proposals have been Decomposable Negation Normal Form (DNNF) and Ordered Binary Decision Diagram (OBDD). The contribution of this paper is twofold. First, we show that in the current state of the art, DNNF dominates OBDD in efficiency and scalability for some typical diagnostic tasks. This result is based on a step-by-step comparison of the complexities of diagnostic algorithms for DNNF and OBDD, together with a known succinctness relation between the two representations. Second, we present a tool for model-based diagnosis, which is based on a state-of-the-art DNNF compiler and our implementations of DNNF diagnostic algorithms. We demonstrate the efficiency of this tool against recent results reported on diagnosis using OBDD.
Content Area: 5. Automated Reasoning
Subjects: 1. Applications; 1.5 Diagnosis
Submitted: May 10, 2005