On Compiling System Models for Faster and More Scalable Diagnosis

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.