A Two-Step Hierarchical Algorithm for Model-Based Diagnosis

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Reasoning about Plans and Actions

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.