Adaptive Model-Based Diagnostic Mechanism Using a Hierarchical Model Scheme

Yoichiro Nakakuki, Yoshiyuki Koseki, Midori TanakaAAAI 1992

Abstract

Model-based diagnosis (MBD) is a robust approach for identifying faults in complex systems, yet it often struggles with the computational costs of high-fidelity models. This paper presents HIMA (Hierarchical Model Adaptation), an algorithm that dynamically selects the optimal level of abstraction within a hierarchical model. By integrating an entropy-based diagnosability criterion with an efficiency metric that considers both computation and physical observation costs, HIMA provides a rational framework for diagnostic decision-making. Evaluation on a simulated ripple carry adder demonstrates that HIMA outperforms static abstraction heuristics, particularly in scenarios with high physical measurement costs.

Introduction

Model-based diagnosis (MBD) identifies system faults by comparing observed behaviors against formal specifications. While effective, the computational complexity of MBD scales poorly with model detail. Engineers often employ hierarchical models—representing systems as nested layers of boards, chips, and gates—to manage this complexity. However, traditional hierarchical diagnostic systems often rely on rigid heuristics, such as remaining at the highest level of abstraction as long as possible. Such "strawman" approaches fail to account for the economic trade-off: in some cases, a more detailed (and computationally expensive) model is preferable if it reduces the number of costly physical observations required from a technician.

The HIMA Algorithm

The HIMA algorithm introduces a formal mechanism to balance diagnostic precision against cost. It evaluates potential model abstractions using two primary metrics:

  1. Model Diagnosability Criterion ($D(M)$): Utilizing Information Theory (Entropy), this metric estimates the information gain a model provides relative to the user's required precision. A model that cannot distinguish between potential faults has low diagnosability.
  2. Efficiency Criterion ($E(M)$): HIMA selects models that maximize efficiency, defined as: $$E(M) = \frac{D(M)}{T(M) + C}$$ where $T(M)$ is the estimated computation time for the model and $C$ is the average cost of a physical observation.
The hierarchical structure of the diagnostic model, illustrating the levels from board to chip to gate.

HIMA starts with the most abstract model and expands components into finer detail only if the expansion improves the overall efficiency $E(M)$. This allows the system to adapt to different environments, such as switching from automated sensors (low $C$) to manual probing (high $C$).

Experimental Evaluation

The researchers evaluated HIMA using a simulated 16-bit ripple carry adder with a three-level hierarchy (Board, Chip, and Gate). The model comprised 2 components at the top level, 32 at the middle, and 160 at the most detailed level. Performance was tested across three observation cost scenarios: 1ms, 1s, and 100s.

Gate-level diagnostic state showing fault probabilities ($P(G_{ij})$) updated after different observations (Obs. A and Obs. B).

Key Results

HIMA consistently outperformed both fixed-detail (FIX) and "as abstract as possible" (AHAP) algorithms:

  • Low Observation Cost (1ms): HIMA was significantly faster (0.8s) than the FIX approach (4.0s) by utilizing abstract models and more probes.
  • High Observation Cost (100s): HIMA (730.8s) was far more efficient than AHAP (2041.3s), which stayed abstract for too long and necessitated excessive expensive observations.
  • Dynamic Adaptation: The system successfully demonstrated that it could adapt its strategy based on whether the user required chip-level or gate-level precision, optimizing the "information gain" relative to the goal.

Conclusion

HIMA provides a principled, adaptive approach to hierarchical diagnosis. By explicitly modeling the costs of both computation and physical inspection, it avoids the pitfalls of static heuristics. While current limitations include a single-fault assumption and uniform observation costs, HIMA represents a significant step toward more rational and efficient automated diagnostic systems.

Summary updated

BibTeX
@inproceedings{nakakuki1992adaptive,
  author = {Yoichiro Nakakuki and Yoshiyuki Koseki and Midori Tanaka},
  title = {{Adaptive Model-Based Diagnostic Mechanism Using a Hierarchical Model Scheme}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1992},
}
Figure