A Two-Step Hierarchical Algorithm for Model-Based Diagnosis

Alexander Feldman, Arjan J. C. van GemundAAAI 2006

Introduction

Model-based diagnosis (MBD) is a fundamental engineering task: identifying which components in a system have failed based on a model of nominal behavior and actual observations. While theoretically powerful, MBD is computationally expensive (NP-hard). As systems scale from simple circuits to complex industrial architectures, traditional "flat" diagnostic algorithms often encounter a computational bottleneck, failing to exploit the inherent structure of well-engineered systems.

In their research, Alexander Feldman and Arjan van Gemund propose a two-step hierarchical algorithm designed to overcome these limitations by leveraging the natural hierarchy and locality found in complex systems.

Methodology: The Hierarchical Approach

The proposed framework breaks the diagnostic process into two distinct phases: an offline compilation step and an online search step.

1. Compile-Time: Hierarchical DNF

The system model, initially represented in Hierarchical Conjunctive Normal Form (CNF), is converted into a Hierarchical Disjunctive Normal Form (DNF). A key innovation is the introduction of an adjustable depth parameter. This allows engineers to choose the level of hierarchy preserved in the model, enabling a trade-off between the initial compilation time (and memory footprint) and the subsequent run-time diagnostic speed.

Once compiled, the model is used by a Hierarchical A* search algorithm to identify the most likely diagnoses. This search utilizes a-priori health probabilities—the statistical likelihood of specific component failures—as a heuristic. This guides the search toward the most probable failure modes first, significantly reducing the search space compared to exhaustive flat methods.

Experimental Evaluation

To validate the approach, the authors utilized several benchmark datasets, including standard 74XXX series logic circuits and the ISCAS-85 combinatorial circuit benchmarks. Because standard ISCAS-85 files are typically distributed as flat netlists, the authors employed reverse-engineered versions to restore the original design hierarchy, ensuring a fair test of the hierarchical algorithm's capabilities.

Extracted figure from page 6 of A Two-Step Hierarchical Algorithm for Model-Based Diagnosis

Performance and Scalability

The experimental results demonstrate substantial performance gains. For well-decomposed problems, the hierarchical approach (HA) was found to be 20 to 90 times faster than traditional flat A search. In specific instances, such as the 74181 circuit, the speedup reached as high as 270x.

One of the most critical findings concerns fault cardinality—the number of simultaneous component failures. Traditional flat algorithms scale poorly as the number of faults increases. For a 5-fault diagnosis, the flat A* algorithm can take nearly 800,000 times longer than in a nominal case. In contrast, the hierarchical version remains significantly more stable, demonstrating superior scalability for multi-fault scenarios.

Extracted figure from page 7 of A Two-Step Hierarchical Algorithm for Model-Based Diagnosis

Key Insights and Future Directions

The primary advantage of this hierarchical approach is its ability to reduce global diagnostic complexity to that of the largest individual subsystem. By isolating faults to specific modules, the algorithm avoids the exponential explosion of state combinations inherent in flat models. While the initial compilation into DNF is computationally expensive, it represents an amortized investment that pays off over thousands of real-time observations.

Future work aims to address the challenge of "optimal partitioning"—finding the best hierarchy for diagnosis, which may differ from the hierarchy used during the design phase. Additionally, integrating advanced conflict-learning techniques from modern SAT solvers could further enhance the efficiency of the A* search heuristic.

By respecting the structural hierarchy of complex systems, this two-step algorithm provides a scalable path forward for high-reliability model-based diagnosis.

Summary updated

BibTeX
@inproceedings{feldman2006two,
  author = {Alexander Feldman and Arjan J. C. van Gemund},
  title = {{A Two-Step Hierarchical Algorithm for Model-Based Diagnosis}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure