Abstract
Model-based diagnosis (MBD) has traditionally relied on structural topology to manage complexity. However, purely structure-based methods face exponential growth in computational cost when dealing with strongly connected devices. This paper introduces a novel approach that incorporates component behavioral models into the diagnostic process. By utilizing decomposition trees and behavioral look-ahead algorithms, the proposed method achieves significant speedups—often exceeding two orders of magnitude—by pruning the search space based on minimum cardinality assumptions.
Introduction
In Model-Based Diagnosis (MBD), the objective is to identify faulty components within a system based on observed discrepancies between expected and actual behavior. Historically, the "gold standard" for this task has been structure-based reasoning, which leverages the interconnection topology of a device to decompose the diagnostic problem. While efficient for "thin" structures with low connectivity, these methods encounter a "complexity wall" when applied to strongly connected systems, where structural width leads to exponential computational explosions.
This research addresses a fundamental limitation of traditional methods: the neglect of component behavior. By considering the actual logic of components rather than just their wiring, we can identify diagnostic shortcuts that topology alone cannot reveal.
Methodology: Decomposition Trees and Behavioral Pruning
The proposed framework moves away from standard jointree approaches toward Decomposition Trees. These are binary trees where leaf nodes represent individual components and internal nodes represent sub-devices or clusters of components. This hierarchical representation allows for a more granular application of behavioral logic.
The paper develops three progressive algorithms to exploit this structure:
- Algorithm A (Baseline): A recursive structure-based approach that serves as a performance benchmark.
- Algorithm B (Cardinality Pruning): This algorithm introduces a cardinality threshold. Given that diagnostic tasks often seek the simplest explanation (the minimum number of faults), Algorithm B aborts search branches that are guaranteed to exceed the current best candidate's fault count.
- Algorithm C (Behavioral Look-ahead): This represents the primary innovation. By precomputing "cardinality tables" for each component, the algorithm calculates a lower bound on the number of faults for any sub-device before initiating heavy computation. If this lower bound exceeds the pruning threshold, the entire branch is skipped.
Experimental Evaluation
The algorithms were evaluated using ten randomly generated synthetic devices, each containing 100 components (a mixture of buffers and AND/OR gates). The devices were designed with varying degrees of connectivity to test performance across a spectrum of structural widths. For each device, 20 sets of random observations (inputs/outputs) were generated, covering both nominal operations and single-fault scenarios.
Results: The Connectivity Paradox
The empirical results for Algorithm C demonstrate dramatic efficiency gains. In many instances, the number of required operations was reduced by factors exceeding 100x compared to the baseline.
A key finding is the "Connectivity Paradox": the relative improvement of the behavioral approach actually increases with the structural complexity of the device. While traditional methods struggle more as connectivity rises, the behavioral look-ahead becomes more effective at identifying and pruning impossible states. Furthermore, the performance gain is most pronounced when the number of actual faults is low, as the pruning threshold remains tight.
Conclusion and Future Directions
By integrating behavioral models into structure-based diagnosis, this work provides a path forward for diagnosing complex, highly interconnected systems that were previously computationally intractable. While the current focus on minimum cardinality provides a powerful pruning mechanism, future work could extend these techniques to handle multi-mode failures and broader diagnostic requirements beyond the simplest fault sets. This research demonstrates that in the realm of automated reasoning, structure is not destiny; behavior offers a vital dimension for optimization.
Summary updated