A Formal Framework for Representing Diagnosis Strategies in Model-Based Diagnosis Systems

Wolfgang Nejdl, Peter Fröhlich, Michael SchroederIJCAI 1995

Introduction

Model-Based Diagnosis (MBD) traditionally relies on a mathematical "system description" to identify faults when observed behavior deviates from predictions. While MBD systems excel at modeling behavior, their diagnostic strategies—the logic governing how to find a fault—are typically hard-coded into the software. This paper introduces a formal meta-language based on modal logic to explicitly represent these strategies, transforming them from implicit algorithms into declarative, first-class citizens of the diagnostic system.

The Problem: Implicit Diagnostic Logic

The traditional approach of embedding diagnostic strategies within core algorithms creates several challenges:

  1. Inflexibility: Modifying how a system selects measurements or refines a model requires rewriting the underlying software.
  2. Lack of Transparency: There is no formal method to verify the correctness or optimality of a diagnostic process.
  3. Integration Barriers: It is difficult to combine rigorous logical models with empirical "rules of thumb" or heuristic knowledge.

Meta-Level Architecture

To address these issues, the authors propose a meta-level architecture that separates the object-layer (the system model and observations) from the meta-level (the diagnostic strategies).

The meta-level architecture separating diagnosis strategies from the physical device model.

As illustrated in Figure 2, the meta-level interacts with the physical device by initiating actions and receiving observations. It manages the diagnostic process by generating hypotheses that guide the object-layer's reasoning ($SD \cup OBS \cup WH$).

The Meta-Language ($L_{strat}$)

The authors define a language based on modal logic to express strategies. Key components include:

  • Working Hypotheses ($WH$): Assumptions made during the process (e.g., "Assume the fault is in Subsystem A").
  • Modal Operators for State: $\square p$ (Knowledge: $p$ is true in all possible diagnoses) and $\diamond p$ (Belief: $p$ is true in at least one diagnosis).
  • Modal Operators for Action: $\blacksquare wh$ (Hypothesis $wh$ is necessary to continue) and $\blacklozenge wh$ (Hypothesis $wh$ is allowed).

By providing a formal "State Transition Relation," the authors mathematically define correct diagnostic paths. They also introduce the concept of Monotonicity, ensuring that as the system gathers hypotheses, it moves steadily toward a stable diagnosis without infinite loops.

Key Insights: Structural Refinement and Heuristics

One of the most powerful applications of this framework is structural refinement, or the ability to "zoom in" on potentially faulty components.

An example of structural refinement where component C is decomposed into sub-components C1, C2, and C3.

In Figure 1, a high-level component $C$ is only decomposed into its constituent parts ($C_1, C_2, C_3$) if the meta-level strategy determines that $C$ is likely faulty. This prevents the system from being overwhelmed by unnecessary detail. Additionally, the framework allows for the formalization of heuristics—such as "prefer cheap measurements over expensive ones"—as logical rules that guide the search process, blending empirical knowledge with hard logic.

Conclusion and Future Work

By decoupling strategy from the diagnostic engine, the authors demonstrate that it is possible to define application-specific diagnostic processes that are both flexible and formally verifiable. While the computational complexity of modal logic remains a challenge for implementation, the framework provides a rigorous foundation for making model-based diagnosis smarter and more adaptable. Future work focuses on efficient implementation within the "DRUM" diagnosis system using transformations into first-order logic.

Summary updated

BibTeX
@inproceedings{nejdl1995formal,
  author = {Wolfgang Nejdl and Peter Fröhlich and Michael Schroeder},
  title = {{A Formal Framework for Representing Diagnosis Strategies in Model-Based Diagnosis Systems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure