Abstract
This paper rests on several contributions. First, we introduce the notion of a consequence, which is a boolean expression that characterizes consistency-based diagnoses. Second, we introduce a basic algorithm for computing consequences when the system description is structured using a causal network. We show that if the causal network has no undirected cycles, then a consequence has a linear size and can be computed in linear time. Finally, we show that diagnoses characterized by a consequence and meeting some preference criterion can be extracted from the consequence in time linear in its size. A dual set of results is provided for abductive diagnosis.
Introduction
In model-based diagnosis, the objective is to identify failing components within a system based on its description and observed behavior. Traditionally, the Assumption-Based Truth Maintenance System (ATMS) has been the standard tool, using "labels" to characterize diagnoses. However, ATMS labels often suffer from exponential growth in size, even for simple systems, leading to significant computational bottlenecks. This paper addresses this "exponential headache" by leveraging the physical topology of systems through causal networks to simplify diagnostic reasoning.
Methods: Causal Networks and Consequences
The proposed approach shifts from flat logic to structured Causal Networks. The system is modeled as a Directed Acyclic Graph (DAG), where nodes represent components or signals and edges represent causal dependencies.
Key methodological components include:
- Consequences: Instead of exhaustive ATMS labels, the paper introduces the "consequence"—a compact boolean expression representing all possible diagnoses. A consequence is guaranteed to be no larger than a traditional label.
- Structural Decomposition: By utilizing d-separation, the algorithm decomposes a global diagnostic problem into independent local sub-problems based on the network's topology.
- Recursive Algorithm: A recursive algorithm computes local consequences. For "singly-connected" networks (polytrees), this process runs in linear time.
- Focusing via And-Or Trees: To identify the most probable diagnosis, the algorithm generates an and-or tree. If the tree structure avoids shared symbols between branches, the preferred diagnosis can be extracted in linear time relative to the tree's size.
Results and Scalability
The theoretical efficiency of this approach is validated through structured examples, most notably the Audio Switching Matrix. This system, comprising 1,000 output amplifiers and 1,000 switches, would typically cause an exponential explosion in an ATMS.
Key findings include:
- Linear Complexity: For singly-connected causal structures, consequences are linear in size and computable in linear time.
- Exponential Savings: The paper demonstrates cases where ATMS labels are exponential while consequences remain linear.
- Efficient Extraction: Preferred diagnoses can be extracted in linear time from the computed consequence.
- Abductive Duality: Similar linear-time results apply to abductive diagnosis (finding explanations for observations).
Discussion and Limitations
While the causal network paradigm offers significant advantages for trees and polytrees, multiply-connected networks (those with undirected cycles) remain a challenge. In such cases, complexity scales exponentially with the "network cutset" size. Additionally, the efficiency of extracting preferred diagnoses depends on the specific "and-or" syntax of the consequence. Future work involves refining techniques to guarantee response times in real-time engineering applications by adjusting network parameters.
Summary updated