Model-Based Probabilistic Reasoning for Electronics Troubleshooting

1. Introduction

IN-ATE is an on-going project aimed at developing expert consultant systems for guiding novice technicians through each step of an electronics trouble-shooting ses­ sion. This paper describes the current. Mark I implemen­ tation of the IN-ATE system. The basic design of this imple­ mentation grew out of a series of preliminary conversa­ tions with our domain expert- a master technician. Using a Tektronix Model 465 oscilloscope as a potential Unit Under Test (UUT) for particular examples, these discus­ sions focused on the general types of information used in troubleshooting electronic equipment. To achieve an implementation in a reasonable amount of time, we chose for inclusion a proper yet important subset, namely:

• circuit topology
• .cost of individual tests
• component failure rates
• conditional probability of test results
• proximity to a solution

In the remainder of this introduction (Section 1) we describe their importance in electronics troubleshooting, and brietly how they have been incorporated in the current implementation. The final section (Section 4) of this paper brietly discusses how other important types of information (e.g., component function) could be added to the current system. The body cf this paper (Sections 2 and 3) describes in detail the current system- a novel application of heuristic search guided by a rule-based reasoning com­ ponent that makes use of both traditional, expert-supplied rules and rules approximated by a novel. model-guided Rule Generator.

Still another problem with using any minimax method for this application is the built-in assumption that the "and" branches in the and/or search space are decided by an opponent . In physical systems, such as electronic dev­ ices, the "and" branches are governed by nature, or chance, and can be estimated using probability. This observation by Slagle and Lee motivated their creation of the gamma miniauerage method [Slagle and Lee, 1971]. In the miniaverage mP.thod, the backed-up value of an "and" branch is not a maximum, but a weighted average - weighted by the conditional probabilities associated with each branch. It allows for efficient pruning of the search space with cut-offs, similar to alpha-beta cut-offs, called gamma cut-offs. It also allows for termination of the search when the cost of continuing the search exceeds the cost of simply replacing the suspect components.

While the cost of each test can often be estimated a priori, two other parameters that guide the gamma miniaverage method - the conditional probability of a test outcome, discussed above , and a static evaluation func­ tion, which estimates the proximity to a solution - are based on the results of earlier tests . Even with only 2 pos­ sible outcomes (i.e., pass/fail) for a test, for n possible tests there may be as many as 3n possible combinations to consider (since each test could either pass, fail, or not be made.) Rather than require that values for these two parameters be established a priori for all possible combi­ nations of test results, IN-ATE estimates these values through rule-based simulation.

Figure 1 shows the overall structure of the rule-based reasoning component, which is the heart of the IN-ATE sys­ tem. Test results, real or hypothetical, are introduced one at a time to the Inference Engine . Given a test result, the Inference Engine uses a single , triggered rule to update a dynamic, a posteriori model of an expert technician's beliefs about what in the UUT could be bad and what should be good.

In the traditional expert systems approach, the rules used to update these beliefs would come from a stored, a priori collection of expert-supplied ::.-ymptom -> possible­ cause rules. Randall Davis [ 1982a, 1982b] has pointed out that the task of extracting a separate rule from the expert for every conceivable symptom that might arise in a sophisticated piece of electronics equipment is unrealistic. Because of this, Davis stresses the importance of an alter­ native means with which to reason - a model of the system being diagnosed. Davis argues that expert systems should have both compiled rules (which he calls "compiled experi­ ence") and the ability to reason from a model. IN-ATE incorporates these two knowledge sources through its small expert-supplied, device-specific a priori rulebase, and a model-guided, device-independent Rule Generator.

The Rule Generator can dynamically produce rules , with the same syntax as the compiled rules , by consulting an a priori model of the UUT. The model of the UUT that has been implemented, thus far , is an augmented block diagram · - augmented in the sense that it contains such non-traditional information as component failure rates. Although the rules that IN-ATE generates from its model may be less accurate than expert-supplied rules, the gen­ erated rules can fill in whatever gaps exist in the expert­ supplied rulebase, and then only when needed. The motivation for this design was a statement by our domain expert that in troubleshooting any sophisticated piece of electronic equipment, including equipment with which he is very familiar, a set of block/schematic diagrams is indispensible. He also says that given a good set of such diagrams he can troubleshoot essentially any piece of ana­ log electronics. The Rule Generator tries to capture this generality by producing approximations of the rules which normally make up "compiled experience."

The rules in IN-ATE, both compiled and generated, are probabilistic (or , more properly, evidential) rules of belief. Each rule is triggered by a single test result. The conse­ quences of each rule are probabilistic assignments of guilt or innocence, given this one particular finding , to various components and lines in· the UUT. These probabilistic assignments are used by the system's inference engine to update the system's a posteriori model of beliefs about what in the UUT is good and what is bad. Since the system does not make use of a "single fault assumption" that at most one of the UUT's components is faulty, for each com­ ponent and line the system gathers both evidence that is it good and evidence that it is bad. And, because of the uncertainty inherent with approximated probabilities, the probabilities associated with these two mutually exclusive possibilities may not necessarily sum to 1. The system combines evidence from separate, independent sources (i.e ., test results) using Dempster's Rule [Shafer, 1976]. Dempster's Rule does allow for a sum less than 1, yet reduces to the traditional Bayesian approach when the sum is exactly 1.

Dempster's Rule works fine for combining evidence from sources that are i:ndependent. But because of circuit connectivity, test results are not always independent . In IN-ATE, non-independent test results are defined as those that are taken from a common path in the UUT circuitry. The interpretation assigned by the inference engine given two non-independent results depends upon whether the tests passed or failed and upon which result is upstream or downstream from the other. For example, if two non­ independent results are both bad (good), then only the more useful - the upstream (downstream) result - is retained and interpreted by the inference engine. As another example , when one passed test result later clears away the blame from some component - assigned as a result of an earlier failed test result - that blame is removed from the component and the original failed test result is re-interpreted in light of this new information. This form of non-monotonicity has been implemented using the basic truth maintenance facility in the electron­ ics simulation system EL [Stallman and Sussman, 1979].

The current IN-ATE system is made up of two basic components. Section 2 of this paper discusses the proba­ bilistic rule-based reasoning component that guides the heuristic search component discussed in Section 3. Sec­ lion 4 is a discussion of future plans.

· _Fault isolation and testability analysis based upon block diagrams has. come to be known as logic modeling or logic moilel a"}ulyS'!.S. One notable example of this is the STAMP system [Simpson and Balaban, 1982] which makes use of iilformat10n theory to generate, in a proprietary manner binary decision trees of the type generated by the IN-ATE system.

2. Probabilistic Rule-Based Reasoning

The rules in IN-ATE incorporate probabilistic meas­ ures of belief. Probabilistic measures of belief, or cer­ tainty factors, have played an important role in such suc­ cessful rule-based expert consultant systems as MYCJN [Shortliffe, 1976) and PROSPECTOR [Duda et.al., 1979). The expert consultant system for electronics fault isolation ARBY [McDermott, D. and Brooks, R:. 1982] totals "amounts" of evidence for and against hypotheses, but since these "amounts" are not related to probabilities, it does so in a very ad hoc manner [Brooks, R., 1982].

Probabilistic measures of belief can play an important role in troubleshooting electronic devices . For example, consider the simple circuit depicted by Figure 2,

where it is known, through testing, that the input is good and that both outputs are bad. One explanation for these test results could be that both components C2 and C3 are faulty. While this is possible, and should not be ruled out, the possibility that C1 is ·broken is much more probable.

Also, consider the slightly different ci,rcuit depicted by Figure 3, where it is known that the input of C1 is good, the output of C2 is bad, and the output of C3 is good. Since the output of C3 is good, its input must be good, which also

means that one of the outputs of C 1 is good. This give some evidence that C1 is good. (lf it were known that both of the outputs of C 1 are good then we could be completely certain that C 1 is good.) So, in this case, C1 is slightly less suspect than C2, since there is some evidence that C1 is good while there is none at all that C2 is good.

2.1. The Inference Rules

In expert consultant systems, relative measures of belief. such as those discussed above, have been quantized using anteced.ent .... plausible-consequences rules . In IN­ ATE there are two types of rules - rules for passed tests and rules for failed tests. Also, each rule has two parts - one suggests consequences about components, while the other suggests consequences about other test-points in the circuit. The basic syntax of the rules is described using the following rule schemata:

Rule-la lf there is evidence with probability x that an output of a component is bad·, then if there are n components which could have caused this bad output, then for each such component there is evidence (with probability x ~ that this comn ponent is broken.

· Here, a "bad" input or output line just means that the signal on the line is not the same as when the entire UUT is good.

Rule-lb For each input I of each of the n components indicated by Rule-1a, if m of these n components feed line /, then there is evidence (with probability m ·x ~that I is bad. n

Rule-2a If there is evidence with probability x1 that out­ put 01 of a component with n outputs is good, then for each line that feeds this component, through some path, there is evidence (with proX · bability I; ....!...) that this line is good. i=l,n n

Rule-2b If there is evidence with probability x, that out­ put 0. of a component with n outputs is good, X· then there is evidence (with probability I; ....!...) that this component is good. t=J,n n

These schemata have actually been used by our domain expert as a guide for writing device-specific rules for the Tektronix 465 Oscilloscope, with the probabilities in parentheses merely suggestions.

Rather than requiring that a domain expert provide the system with a complete and exhaustive set of such rules for every test-point in a specific UUT, the system's Rule Generator can approximate missing rules using infor­ mation stored in the system's a priori model of the UUT. If information is missing from the model, the Rule Generator will use the probabilities within the parentheses in the schemata above as defaults . The types of information presently stored in the a priori model of the UUT and used by the Rule Generator are : the circuit structure (e.g., topology) , sub-structure, and relative component failure rates. For example, the Rule Generator can approximate a Rule-1a rule by making use of information about :

• o Topology: The grossest estimate of n is the total number of components in the entire circuit. This can be cut down significantly, using simple signal tracing, by considering only those components that lie upstream from the bad output.
• o Component Fa:ilure Rates: The probability ~is a n default probability. The failure rate of each com­ ponent is used as a weighting factor . For exam­ ple, if one of the n components has exactly twice the failure rate of each of the other n -1 com­ ponents then the probability of the evidence assigned to it would be 2 x 1 and ~ for each of the others. n+ n+

The Rule Generator can custom tailor a Rule-2b rule using information about:

• o Component Sub-Structure: Some of the outputs of a component could be more informative than others. For example, output i may be affected by 90% of the component's internal sub-components. By making use of such information, the probabil­ ity assigned is a weighted average rather than a simple average .

2.2. The Inference Engine

All the rules are triggered by a test result. When a new test result is entered into the system, the inference engine first looks in the small rulebase, which comprises compiled experience, for a rule that is appropriate. If there is none, it will call upon the Rule Generator to gen­ erate one. With either the retrieved or generated rule , the inference engine can then update the a posteriori model of beliefs about what in the UUT is good and what is bad.

In updating the model of beliefs, there are two cases that the inference engine must consider . · The new tes t ·result could either contribute new independent evidence 'that should be combined with earlier evidence; or it could provide new information upon which earlier plausible infer­ ences should be revised.

Combining New Independent Evidence

At any point in time, we may have evidence, say for a particular component C, that indicates with probability x 1 that C is good and y 1 that C is bad. Since we allow that z 1 = 1- (x 1 +y 1) may be greater than 0, these are not clas­ sical Bayesian probabilities.

When a new piece of independent evidence is intro­ duced concerning C, the new evidence can be combined with the old evidence using Dempster's Rule [Schafer, 1976). · For example, suppose that new evidence suggests, with probability x 2, merely that C is good. The uncertainty z2 associated with this evidence is simply 1- x2 (since, in this case, y 2 =0.) According to Dempster's Rule, the updated probabilities x 3 (good), y 3 (bad), and za (uncer­ tain) would then be computed as follows . First, using a cross product , let:

and then, through re-normalization:

(There are similar equations for combining new evidence that Cis bad.)

For example, suppose that at some moment the total probability that component C is good is x 1 = 113 and y 1=113 that Cis bad (with uncertainty z 1=1/3.) If new evidence is introduced with certainty x2=113 that C is good (and with uncertainty z 2=2/3) , then the updated pro­ babilities would be x3= 112 that C is good and y 3= 1/4 that Cis bad (with uncertainty z 3=1/4.)

The associativity and commutativity of Dempster's Rule are very important in this application since the results of independent tests should be. independent of the order in which the tests were made. The Rule'_s sound treatment of uncertainty is also important here, since in troubleshooting exact probabilities are often difficult or impossible to calculate .

Revising Earlier Plausible Inferences ("Shifting Blame")

Inferences made earlier in a troubleshooting session might need to be re-evaluated in light ot new information. For example, Rule-1a·rules distribute the blame for a fault among n components. If m (for m~n) of these are later cleared by a passed test result, then the blame assigned to thes.e. m components should be removed from them and re-distributed among the other n- m components. Simi· larly, when the plausible blame attributed to some lin~ L (by an instance of Rule-1b) is later confirmed by a failed test result then the blame that had been assigned to the m corilpo~ents that line L feeds (by the corresponding instance of Rule-1a) should be removed· and re-distributed to the other n- m components using a new instance of Rule-1a- one triggered by the new test re.sult.

· One notable use of Dempster's Rule has been ~ Garvey for integrating sensor information [Garvey, 1981 . It has also influenced Friedman's Extended Plausible easoning [Friedman. 1981].

This form of non-monotonicity has been implemented using the basic truth maintenance system incorporated in the electronics simulation system EL [Stallman and Suss­ man, 1979). Borrowing the terminology of Stallm~ and Sussman, at each moment an assertion can be bel!'.lved with some certainty, and labeled in, if there is some well­ founded support behind it (i.e ., a test result); otherwise 1t 1s labeled out . An assertion that is less than completely certain can move from in to out by the introduction of contradictory evidence that is completely certain. To Implement this capability we store with each discrete piece of evidence that is less than completely certain the test result and rule that originally introduced it to in. This 1s the only information necessary for removing and re­ evaluating the plausible consequences of a rule in light of new information.

3. Deciding the Best Test

The a posteriori model of beliefs has two basic pur­ poses. Firstly, the system can present to the user a list of suspect components, ordered by their current probability of being faulty. This can either be done at any time, upon request from the user; or automatically, when the max­ imum s.uch probabability exceeds some user established threshold. Secondly, the system can use the model of beliefs, in a hypothetical mode, to help decide the best test for the us~r to make next. If there are no initial symptoms the best test model of beliefs can be used to construct, a priori, a binary decision of best tests to be performed at each step of such a troubleshooting session. If there are initial symptoms, a custom tailored binary decision tree which takes these initial "test results" into account can be computed at the beginning of the troubleshooting session (or dynamically recomputed if the user later contributes, through his own initiative, other test result.s .)

The best test is basically that test which, for its cost, 'will bring the system closest to isolating the fault to a sin­ gle component. Since there ar:e two possible outcomes of each test (i.e.,pa.ss or fail), the system must consider both of them separately. It does this by simulating the effect that each such outcome would have on its model of beliefs. A heuristic static evaluation function is . applied, in each case, to the model of beliefs to estimate how far the sys­ tem would then be to having isolated the problem to one faulty component.

We have applied the gamma miniaverage method in a straight-forward manner (and refer the reader to [Slagle and Lee, 1971] for a detailed discussion of the method itself.) The nodes in the search tree represent, on alter­ nating levels, the possible tests that can be performed and the potential outcomes oi of the possible tests. A static . evaluation function G applied to an outcome node on the frontier of the search .represents the loss, or cost, of ter­ minating at that point. The value of the static evaluation function G which we have empirically chosen is the size of the component ambiguity set (the still suspect com­ ponents.) G could also represent the total cost of replacing all of the components in the ambiguity set, if this data were known.

· Although that blame is removed from these components, the components are not cleared since this test result pro­ vides no evidence that they are good, but merely that one of their inputs is bad.

To calculate the backed-up value of the "and" node which represents the cost R of terminating the search after performing test T~o. the static values �([o,,T~o .ED for each possible outcome o, of T~o (where [ o,, T~o ,E] represents the model of beliefs after outcome o, of test T~o is incor­ porated into the model of beliefs E) are combined with the cost Cr· of performing test T~o and the conditional proba­ bilities Pr· (oi I E) that test T~o will have outcome oi (given the evidence E that has been accumulated thus far) using the formula ·

An approximation of the a posteriori probability Pr· (o, I E) is maintained in the system's a posteriori model of beliefs (see, for example, rule schemata Rule-1b and Rule-2a.) The value of G([oi,r · . E]) is calculated by statically evaluating the a posteriori model of beliefs. The risk R basically represents the total of the actual cost and the potential cost if the troubleshooting session were to be terminated at that point.

Since we want to choose the test T~o of minimum risk R(E, T~;). the backed-up value of the "or" node which represents this decision is

To allow for multiple levels of look-ahead, this backing-up process can be repeated as many levels as resources permit . Not only can these backed-up miniaver­ age values be used for estimating the best test to make next, but using gamma cut-offs, this searcR. can be done efficiently.

4. Future Work

The algorithms have been implemented in Franz LISP on a VAX 111780 computer and produces reasonably good decision trees for block diagrams that include series, parallel, and feedback circuits. For example, in the case of a simple series circuit Where all test costs are equal, the system reduces to the staridard half-split method (i.e., binary search.) In the more realistic case of a 2dimensional circuit, where there is a real ambiguity about where the "middle" is, the system performs much better than the half-split method. In the next few months this basic system will first be applied to troubleshooting a stan­ dard oscilloscope, the Tektronix Model 465, and its perfor­ mance will be evaluated by olir domain expert. To test the generality of the system, it will then be applied to troub­ leshooting a sophisticat~d piece of military electronics, such as the WLQ-4 Intercept Receiver .

We will also be adding a learning component, in the style of the Self-Improving Diagnostics system SID [Hughes Aircraft Corp., 1980], to retain and periodically refine gen­ erated rules . . The probabilities within a rule, initially assigned by the Rule Generator, would be changed to refiect the actual distribution encountered by the system over time.

A more difficult improvement that we will be exploring is a more informed Rule Generator. We will attempt to incorporate an ability to r~ason with knowledge about component function (in addition to circuit topology and component failure rates.) Also the Rule Generator should know 1.Uhen to use assumptions that narrow the set of pos­ sible faults (e.g. , that faults are always upstream from a bad line) but are not always correct (see [Davis, 1982b ]).

ACKNOWLEDGEMENTS

We would like to thank our domain expert, master technician Mr. Mark Hulbert, for his time and patience; Prof. Kenneth DeJong, Prof . Michael Gaynor and Dr. James Slagle for their advice; Dr. Randall Schumaker (NAVAlR) for directing our attention toward the problem of automatic test program generation (ATPG), and Dr . Jude Franklin, especially, for introducing us to the general problem of electronics trouble!ihooting.