Consistency-Based Diagnosis

Dr. Dobb's Journal March 2001

Identifying faulty components

By Girish Keshav Palshikar

Girish is a scientist at the Tata Research Development and Design Centre (TRDDC), Pune, India. His research interests are in AI and mathematical logic. He can be contacted at girishp@pune.tcs.co.in.

When a device or a system generates expected outputs for given inputs, we say that it is functioning normally; for instance, normally a bulb lights up when the switch is pressed. However, when a system behaves unexpectedly — the bulb fails to light up when the switch is pressed — we have a diagnostic problem on hand. Essentially, the presence of a fault in a system is indicated by observing outputs, which are incompatible with inputs given to the system, based on some (explicit or implicit) model of the system's normal behavior. A diagnosis involves identifying the cause for a specific fault, which may be a faulty component (a broken bulb or an open switch) or a fault condition (no electricity supply).

It is easy to appreciate that diagnosis of large real-world systems is a complex problem. It requires keen observation of the problem symptoms, formation and ranking of the most likely hypotheses that can account for the observations, patient exploration of the system under various experiments or tests, and zeroing in on (and confirming) the actual diagnosis. A confirmed diagnosis is often followed by selection and implementation of remedial actions such as repairs or reconfigurations. Diagnosis is, of course, a cornerstone of medicine. Even outside the exalted world of medicine, diagnosis, repairs, maintenance, and support of engineering systems are integral functions in a range of industries — automobiles, aerospace, chemical and petrochemicals, power, manufacturing, electronic circuits, mechanical equipment, and more. In computing, debugging can be thought of as a diagnosis problem. Of course, software is not a physical artifact and bugs are actually logical conditions that cause a mismatch between program specification and the behavior of the code. In a general sense, diagnosis is actually a fundamental human skill. Many human activities include diagnostic reasoning in some form, such as with analysis of battle situations, business problems, crime, financial irregularities, and the like.

Troubleshooting handbooks are the simplest and widely used representations of diagnostic knowledge. They are useful in simple situations when there is a (nearly) one-to-one match between observations and diagnosis. However, such approaches are ineffective in dealing with large systems with a large number of components as well as with complex combinations of a large number of observations. They are also brittle, not extendible, and limited in interpreting and grouping observations, selecting tests, handling uncertainty, generating/testing hypotheses, and so on. The diversity of systems embodying a variety of phenomena (electronic, electrical, mechanical, chemical, biological, and social) and the knowledge-intensive nature of the task of diagnosis has given rise to a need for human experts and inevitably, for specialized automation software that captures the diagnosis expertise.

There are many ways in which computers can assist in the diagnosis tasks. In this article, I focus on the perspective of artificial intelligence (AI) where the goal is to symbolically represent diagnosis knowledge within computers and build diagnosis procedures that use this knowledge in problem solving. As a matter of fact, diagnostic expert systems have traditionally been among the most common applications of AI. For simplicity and ease of presentation, I'll focus on the diagnosis of simple systems such as digital circuits; they are simple in the sense that they can be precisely presented by simple mathematical logic.

In the rule-based expert-system approach, a number of rules can relate symptoms to diagnoses for a specific system. For example:

IF switch is off,

AND light is on,

THEN switch is shorted.

However:

IF switch is on,

AND bulb is off,

AND fan is working,

THEN bulb is faulty.

However, the latter approach is unsatisfactory for several reasons:

It is not based on any insight about how the normal system behaves.
It needs considerable rework, even when small changes are made to the system's structure or function (a fuse may be added to the bulb example).
It is difficult to test whether the rules are complete (cover all possible faults and associations between causes and diagnoses).

What can be done to handle these problems? The fundamentally different "model-based diagnosis" (MBD) approach attempts to work out the diagnosis from a model of the normal behavior of the system, rather than work with an exhaustive list of faults and methods to diagnose each of them. It proposes a separation of the diagnostic knowledge and the diagnostic procedure (see Figure 1). The diagnostic procedure is general enough so that it can systematically analyze the given model (of any system) for generating diagnoses. Like a human expert, the MBD approach attempts to reason from the model of the normal (or expected) behavior to work out all possible diagnoses that can explain the observations; for this reason, MBD is also called "deep-knowledge diagnosis" or "diagnosis from first principles."

MBD has been used for diagnosis in a variety of practical domains such as digital circuits, onboard aerospace systems, automobile systems, and the like. The MBD approach is also a hot research subfield, particularly to extend its applicability to more complex systems represented in a variety of notations for specifying system models.

The MBD approach can be specialized to work with a number of mathematical or textual notations to express and analyze models of systems. Here, I focus on functional models of systems expressed using the propositional logic. I then discuss a particular approach to MBD, called "consistency-based diagnosis" (CBD), which relies on the notion of logical consistency. To be sure, propositional logic is simple and not very expressive — it prohibits a proper modeling of dynamic systems having time-evolving inputs and outputs (process control systems, for example). However, it is adequate to model important aspects of static systems such as digital circuits. The original papers in CBD (see "A Theory of Diagnosis from First Principles," by R. Reiter, Artificial Intelligence, 1987, which first proposed the CBD approach and is the basic reference for this article), do not presume any particular logic. CBD can work with predicate logic or Horn clause logic as in the programming language Prolog.

Propositional Logic

A "proposition" is an atomic symbol (without any internal structure) that stands for a declarative statement that can be true or false. Let PROP denote the set of propositions. Propositional logic provides the logical connectives (and), (or), (not), (implies), and (if-and-only-if). Additional connectives like (XOR) can also be defined. is a unary connective and the others are binary connectives. A formula is a string of symbols constructed from propositions in PROP and the logical connectives; for example, p(q (r)) and (pq)r. An interpretation is a function I:PROP{true, false} that associates a Boolean truth-value with each proposition in PROP. Truth-value TV(F) of a formula F is computed by combining the truth-values of its subformulae, according to the truth-table in Figure 2.

For example, the formulae pp and pp are both true under all possible interpretations (p=true or p=false); such a formula is called a "tautology" or "validity." The formula pp is not true (it is always false) under any possible interpretation; such a formula is called "unsatisfiable" or a "contradiction." A formula like pq evaluates to true in at least one interpretation; such a formula is called "consistent" or "satisfiable" and the corresponding interpretation is called a "model" for F. Given a formula F, checking whether F is satisfiable is called the "satisfiability problem." There is no known efficient (polynomial time) algorithm to solve this problem that works for any arbitrary formula F in propositional logic.

Checking Satisfiability

A literal is a proposition or its negation; for example, p and q. A clause is a disjunction () of zero or more literals; for example, pq. A unit clause is the clause containing exactly one literal; for instance, p. The empty clause, denoted [], is the clause that contains no literals; it is unsatisfiable. A formula F is said to be in conjunctive normal form (CNF) if F has the form F₁F₂...F_n_,where each F_i is a disjunction of literals; for instance (pq)(rs). There are efficient algorithms to transform any given formula in propositional logic into an equivalent formula in CNF. You represent a formula F in CNF by the set {F₁,F₂,...,F_n}.

Figure 3 shows the basic Davis-Putnam algorithm (see "Implementing the Davis-Putnam Method," by H. Zhang and M. Stickel, Journal of Automated Reasoning 24(1-2), February 2000) for checking the satisfiability of a propositional formula in CNF. The unit subsumption rule is as follows: If there is a unit clause L in S, obtain S' from S" by deleting those clauses in S containing L; if S' is empty, then S is satisfiable. The unit resolution rule is as follows. Obtain a set S" from S' by deleting L from every clause in which it occurs; S" is unsatisfiable if-and-only-if S' is. Note that if L is a unit clause, then it becomes [] when L is deleted from it. These rules are based on the facts that A(AB) is equivalent to A and A(AB) is equivalent to AB.

It is easy to verify, using the algorithm in Figure 3, that the set {pqr,pq,p,r,u} is unsatisfiable, the set {pq,q,pqr} is satisfiable, and the set {pq,pq, qr,qr} is satisfiable.

You could also add the tautology rule to the algorithm: Delete all clauses from S that are tautologies; the remaining set is unsatisfiable if-and-only-if S is. We could also add the pure literal rule, which is as follows: A literal L is pure in S if the literal L does not appear in any clause in S. If a literal L is pure in S, delete all clauses in S which contain L. The remaining set S' is unsatisfiable if-and-only-if S is.

System Models in Propositional Logic

Propositional logic can be used to model (which has nothing to do with a model as an interpretation that makes a formula true) the functionality of simple circuits. We use the set notation {F₁,..., F_n} to express the formula F₁...F_n. A system description is a tuple (SD, COMPONENTS) where SD is a set of formulae in propositional logic, constructed over the set PROP of propositions and where COMPONENTS is a subset of PROP that corresponds to components in the system. Since each component is a proposition, we adopt the convention that a truth-value of true (respectively false) for a component corresponds to a normally functioning (respectively faulty) component. Figure 4 shows a simple digital circuit for a 3-bit adder, and Figure 5 shows a model in propositional logic for this circuit.

An observation of a system is a set OBS of formulae over PROP. In normal system behavior, no components are faulty; this is expressed as a logical condition that SDOBS{c|cCOMPONENTS} is consistent (satisfiable). However, if SDOBS {c|cCOMPONENTS} is not consistent, then you need to perform a diagnosis; that is, identify the subset of faulty components that caused the observation.

Formally, a minimal subset COMPONENTS is a diagnosis if SDOBS{d| d}{c|cCOMPONENTS-} is consistent; is minimal in the sense that no proper subset of is itself a diagnosis. In the adder example, an observation may consists of OBS={in1, in2, in3, out1, out2} (for example, in1=1, in2=0, in3=1, out1=1, out2=0). Clearly, the adder is faulty; the expected output is out1=0 and out2=1. The diagnosis task now is to identify which of the five components from the set COMPONENTS={x1, x2, a1, a2, o1} are faulty; that is, whose faulty behavior can explain this observation. For the aforementioned example, there are three diagnoses: ₁= {x1}, ₂={x2, a2}, and ₃={x2, o1}. It is easy to check that each of these is indeed a diagnosis; that is, to check whether {x2, a2} is a diagnosis, you can verify that SDOBS {x2, a2} {x1, a1, o1} is consistent.

The central question in consistency-based diagnosis is how to systematically identify all possible diagnoses.

Consistency-Based Diagnosis

The fundamental result of consistency-based diagnosis consists of a characterization of the faulty components. For this purpose, you need the concepts of conflict sets, hitting sets, and an HS-tree.

A conflict set for (SD, COMPONENTS, OBS) is a set {c₁,c₂,...,c_k} ( COMPONENTS such that SDOBS{c₁,c₂,...,c_k} is inconsistent. A conflict set for (SD, COMPONENTS, OBS) is minimal if no proper subset of it is itself a conflict set for (SD, COMPONENTS, OBS). Intuitively, a conflict set (minimal or otherwise) consists of those components, at least one of which is definitely faulty.

Let C be a collection of sets. A "hitting set" for C is a set H of elements such that every element in H belongs to at least one set S in C and HS for every set S in C. A hitting set for C is minimal if no proper subset of H is itself a hitting set for C. The central characterization of a diagnosis is given by the following result. COMPONENTS is a diagnosis for (SD, COMPONENTS, OBS) if is a minimal hitting set for the collection C of conflict sets for (SD, COMPONENTS, OBS). This result holds even when C is a collection of only minimal conflict sets for (SD, COMPONENTS, OBS). For the adder, there are two minimal conflict sets {x1, x2} and {x1, a2, o1}. This is because SDOBS {x1, x2} is inconsistent and SDOBS {x1, a2, o1} is inconsistent. There are three diagnoses, given by the minimal hitting sets for C={{x1, x2}, {x1, a2, o1}}: ₁={x1}, ₂={x2, a2}, ₃={x2, o1}.

Let F be a collection of sets. An HS-Tree T is an edge-labeled and node-labeled tree if it is the smallest tree with the following properties:

Its root is labeled by if F is empty. Otherwise, it is labeled by an arbitrary set of F.
If n is a node of T, then define H(n) to be the set of edge labels on the path from the root to n. If n is labeled by , then it has no successor nodes. If n is labeled by a set in F, then for each in , n has a successor node n, joined to n by an edge labeled by . The label for n is a set A in F such that AH(n)= if such a set exists; otherwise, n is labeled by .
An HS-Tree has the following properties:
If n is a node of the HS-tree labeled by , then H(n) is a hitting set for F.
Each minimal hitting set for F is H(n) for some node n of the HS-tree such that n is labeled by . An HS-tree does not include all hitting sets for F but is does include all minimum hitting sets for F.

The essential idea behind Reiter's algorithm for computing all diagnoses for (SD, COMPONENTS, OBS) is to treat F as the set of all conflict sets for (SD, COMPONENTS, OBS) and to construct an HS-tree to generate all minimal hitting sets of F. F will not be explicitly available. We assume that a conflict-set generator function GetConflictSet(SD,COMPONENTS,OBS) is available to generate a conflict set whenever required. In this paper, I do not develop an algorithm for this function; it is not very complex for propositional logic. Computing a conflict set is a very time-consuming operation and Reiter's algorithm attempts to minimize the number of times this generator is called.

1. Generate the HS-Tree T in the breadth-first order, generating nodes at any fixed level in the tree from the left to right order.

2. Reusing node labels: If n is labeled by a set S in F and if n' is a node such that H(n')S= then label n' also by S. You indicate that the label of n' is a reused label by underlining it in the tree. Computing label(n') does not require a call to the function GetConflictSet().

3. Tree Pruning: (a) If a node n is labeled by and a node n' is such that H(n) H(n') then close n' — do not compute a label for n' and do not generate any successors for n'. (b) If node n has been generated and node n' is such that H(n')=H(n), then close n'. We indicate a closed node in the HS-tree by marking it with ×. (c) If nodes n and n' have been respectively labeled by sets S and S' of F, and if S' is a proper subset of S, then for each S-S' mark as redundant the edge from node n labeled . A redundant edge, together with the subtree beneath it, may be removed from the HS-tree. A redundant edge is marked with the symbol )( in the tree.

As a last heuristic to improve the efficiency, whenever a node n in the tree needs a conflict set as a node label, we call GetConflictSet(SD, COMPONENTS - H(n), OBS) rather than GetConflictSet(SD, COMPONENTS, OBS). Such a call is guaranteed to return a set S such that SH(n)= , if it exists.

An Example

The adder example in Figures 4 and 5 shows how the algorithm works (see Figure 6). Suppose the first call to GetConflictSet(SD, {x1,x2,a1,a2,o1},OBS) yields the set {x1,x2}; this is the label of the root. This generates two nodes, n1 and n2, on the next level where the edges from the root to them are labeled by x1 and x2, respectively. Node n1 is labeled by the call GetConflictSet(SD,{x1,x2,a1,a2,o1}-H(n1),OBS)=GetConflictSet(SD,{x2,a1,a2, o1},OBS), which returns , since SDOBS {x2, a1, a2, o1} is consistent. Node n2 is labeled by the call GetConflictSet(SD, {x1,a1,a2,o1},OBS); suppose it returns {x1, a2, o1}. Node n3 is marked closed because of rule 3(a); that is, since there is a node n1 marked by such that H(n1)= {x1} is a subset of H(n3)={x1,x2}. Node n4 is labeled by the call GetConflictSet(SD, {x1,a1,o1},OBS), which returns since SDOBS{x1, a1, o1} is consistent. Similarly, the node n5 is labeled by a call to GetConflictSet(SD, {x1,a1,a2},OBS). The set of all diagnoses is read from the tree of Figure 6 as {{x1}, {x2,a2}, {x2,o1}}. This particular HS-tree required five calls to the GetConflictSet() function. A different implementation for this function may yield different conflict sets in subsequent calls (see Figure 7).

Since the algorithm constructs the HS-tree in a breadth-first manner, it generates diagnoses in increasing order of cardinality (number of faulty components).

Conclusion

Consistency-based diagnosis systematically works out the set of all possible diagnoses by reasoning from a logical model of the normal behavior of the system. In CBD, the model of a system is a set of formulae in some mathematical logic and a diagnosis is a set of faulty components in the system, which explains the observations by means of the notion of logical consistency. CBD is a fundamental and robust approach to systematic diagnosis (as opposed to heuristic diagnosis). Its diagnostic procedure is independent to any changes in the system model. In this article, I discussed a specialized version of CBD where a model and an observation both consist of a set of formulae in propositional logic, and the components are a set of propositions. CBD has been applied in a variety of interesting practical domains.

Acknowledgments

I sincerely appreciate the support and encouragement of Professor Mathai Joseph. I also wish to thank Dr. Manasee Palshikar for her confidence and perseverance.

References

Hamscher,W., L. Console, and J. de Kleer. Readings in Model-based Diagnosis, Morgan Kaufmann, 1992. A collection of important papers in model-based diagnosis. Also includes a paper by Greiner, Smith, and Wilkerson containing a correction to Reiter's algorithm.

Palshikar, G.K. and D. Khemani. "Diagnosing Dynamic Systems Using Trace Patterns," Pattern Recognition Letters, July 1999. In this work, we used context-free grammar to model a dynamic system, and an observation was a string over an alphabet. The notion of logical derivations was used to identify nonterminals, corresponding to faulty behavioral components.

Reiter, R. "A Theory of Diagnosis from First Principles," Artificial Intelligence, 1987. Proposed the CBD approach and the basic reference for this article.

Zhang, H. and M. Stickel. "Implementing the Davis-Putnam Method," Journal of Automated Reasoning, February 2000. The issue also contains articles defining the state of the art about the SAT problem in propositional logic.

DDJ