A Two-Step Hierarchical Algorithm for Model-Based Diagnosis

Alexander Feldman, Arjan van Gemund

For many large systems the computational complexity of complete model-based diagnosis is prohibitive. In this paper we investigate the speedup of the diagnosis process by exploiting the hierarchy/locality as is typically present in wellengineered systems. The approach comprises a compile-time and a run-time step. In the first step, a hierarchical CNF representation of the system is compiled to hierarchical DNF of adjustable hierarchical depth. In the second step, the diagnoses are computed from the hierarchical DNF and the actual observations. Our hierarchical algorithm, while sound and complete, allows large models to be diagnosed, where compiletime investment directly translates to run-time speedup. The benefits of our approach are illustrated by using weak-fault models of real-world systems, including the ISCAS-85 combinatorial circuits. Even for these non-optimally partitioned problems the speedup compared to traditional approaches ranges in the hundreds.

Subjects: 3. Automated Reasoning; 1.5 Diagnosis

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.