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:
- 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.
- 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.
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.
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