PII: 0270-0255(87)90579-3 IDES: INFLUENCE DIAGRAM BASED EXPERT SYSTEM Alice M. Agogino & Ashutosh Rege Department of Mechanical Engineering, University of California, 5 I36 Etcheverry Hall. Berkeley. California 94720,U.S.A. Abstract. Infhrence diagrams have been used effectively in applied decision analysis to model complex ~. systems, identify probabilistic dependence and characterize the flow of information. Their graphical representation and intuitive framework are particularly effective in representing knowledge from experts with diverse backgrounds and varying degrees of technical proficiency. They allow both a symbolic representation of the system interrelationships and a quantitative measure that can be of discrete or con- tinuous functional form. By exploiting this abstraction hierarchy. successive degrees of specification can be made by several individuals. each encoding his or her expert knowledge of the problem and bounds on critical parameters. It is proposed that an interactive computer program that automates this influence diagram technology would provide an excellent tool for building expert systems. This paper describes such a modeling tool: the IDES (Influence Diagram Based Expert System) developed at the University of California at Berkeley as a modeling tool for building expert systems requiring reasoning with uncertain or incomplete information. The Diagnostician’s Problem is presented as a tutorial for describing the IDES solution procedure. Keywords. Expert systems: influence diagrams; probabilistic modeling: diagnostic reasoning: probabilis- tic inference. INTRODUCTION WHAT ARE INFLUENCE DIAGRAMS? Human beings possess an unparalleled ability for processing complex types of information and for making inferences based on this knowledge. First generation expert systems try to capture human knowledge by means of logic predi- cates or If-Then statements that involve measurable and quantifiable parameters. Consider the following example from MYCIN, a well known rule-based medical diagnostic expert system (Buchanan et al.. 1984:82). MYCIN RULE NO. 37: IF: I) The idenrirv of’rhe organism is no! known nith ccrruintr und 2) The stuln of rhc organtsm IS gamneg and 3) The morphotqw ofrhr organism is rod, and 4) The aerohiclrl, of rhr or,anism is aerobic THEN: There is .srrongI~~ .srcgg:‘.rrr ve evidence (0.8) that the class of /he orgun~sm IS mrerobacleriaceae. Following this rule. a conclusion about the class of organism present can be drawn (with a certain degree of confidence) from satisfaction of all of the antecedents. Influence diagrams were conceived of and developed by researchers in the Decision Analysis Group at SRI Interna- tional in order to automate the modeling of complex deci- sion problems involving several uncertain variables (Miller et a1.,1976). Knowledge of the interrelationships between variables is represented in a compact graphical and numeri- cal framework which identifies the critical variables and explicitly reveals any conditional independence between them. Although the original objective in the development of influence diagrams was for computer-aided modeling. they have been used effectively in improving communication among people. Use of influence diagrams in participative modeling of complex decision problems is described in Owen (1978) and Howard and Matheson (1984). A direct solution procedure to automate influence diagrams has been developed by Olmsted (1984) nd formalized in algorithmic form by Shachter (I 984a&b). The application of influence diagrams as a development tool for building expert systems has been proposed by Agogino (1985) and Holtzman ( 1985). In addition to explicit rules of Inference like those in MYCIN, human beings also have unique skills in holistic reasoning, in the use of intuition. in deciding what parame- ters or variables are important to a problem. and in know- ing what questions to ask when more information is needed, We are able to synthesize the interrelationshtps of complex problems and gam quahtative insights about them. If a computerized system is expected to capture any of this deeper human knowledge. it should at least be able to represent and process expert knowledge in both a symbolic and numeric fashion. As with the example from MYCIN. the inference mechanism and representation must be able to work with the uncertainties and imprecise data of both the material world and the human mind. The approach presented in this paper is based on the intuitive graphical framework of influence diagrams coupled with the powerful Bayesian inference engine and automation algorithms sup- porting them. In the next section. we review the theoretical framework for the IDES (Influence Diagram Based Expert System) An influence diagram can be interpreted at several levels: (I) relational, (2) functional, and (3) numerical. On the rela- tional or symbolic level the nodes in the influence diagram represent the important variables in the system being modeled and the directed arcs identify conditional influences between them. The nature of these influences is specified at the functional level and further quantified at the numerical level. Relational Level This is perhaps the most powerful level of the diagram. An influence diagram at the relational level is a graphical representation of the interrelationships between the vari- ables involved in the problem under examination. It reveals visually the flow of information. influences, and the overall structure of the problem. Three different kinds of nodes will be considered in building an influence diagram: 1) state (circular nodes), 2) decision or control (rectangular nodes). and 3) value nodes (diamond- shaped). Addition or deletion of nodes is analogous to simi- lar operations on rules in rule-based expert systems but the 227 22.3 5th ICMM effect of the same is much more apparent and intuitive with influence diagrams. State Variables Consider the following two-state variable influence diagram shown in Figure 1. The circular nodes represent two state variables, x and y, and the arc can be considered informally to signify that a conditional influence may exist. On the relational level, one interpretation of the influence diagram in Figure 1 is : “x may influence J’“. A variable x is said to influence a state variable )’ if given information about x tells you something about J’. However, this should non be interpreted to mean that x causes .r_ No sense of causality is implied. Conversely, if knowing x gives you no new information about state variable I’, then variables x and .r are said to be independenf and no influence exists between them. This strong information about the interrelationship (or rather lack of) between variables x and y is signified by the absence of an arc between the corresponding nodes as illus- trated in the influence diagram in Figure 2. It should be noted that the lack of an arc is in some ways a stronger statement of our knowledge than the existence of an arc. The presence of an arc indicates that a possible dependency exists, while the lack of an arc states that no dependency exists. In other words. an arc can be thought of as representing our state of ignorance rather than our state of knowledge. Decision Variables In addition to state variables, influence diagrams represent decision or control variables by square nodes, following the same symbolism used in decision trees. The nature of an influence arc going into a state node and that going into a control node is conceptually and mathematically distinct. Arcs leading into state nodes represent conditional injluences as discussed previously. Two examples of influence arcs are shown in Figure 3: probabilistic and fuzzy. Arcs going into decision or control nodes represent informational influences and show exactly which variables will be known by the decision maker or controller at the time that the decision is made. An arc from a decision node to a chance node indicates causality in the sense that the selection of one decision option over the other choices restricts, in general, the space or the universe of values the state variable can take on. Thus the meaning of an arc must be viewed relative to the types of nodes it connects. Control nodes are the only nodes where the directions of the arcs (to and from control nodes) are immutable aspects of the structure of an influence diagram and should not be reversed unless the intent is to reformulate the problem. Although not always shown explicitly. it is assumed that once a decision has been made. that decision is not forgot- ten. Hence the term no-jhgnring arcs is used to signify the invisible but implicit arcs between decision nodes which must always appear sequentially in time. Value Function The value jimction, signified by a diamond-shaped value node is a model of the objectives of the decision maker or computer system user. There can be at most only one value node in an influence diagram. However, as will be applied in the diagnostic expert system example. the location of the value node will vary depending on the question being asked of the expert system. Structural Matrix In a more rigorous sense, but still at the symbolic or rela- tional level, the influence diagram can be defined as an acy- clic directed graph consisting of N variables represented by N nodes and a set of directed arcs between them. This rela- tional information may be captured in a structural matrix that relates direct predecessors to each node in the diagram. A node j is called a direct predecessor of node i if and only if (itI) there is an influence arc directed from node j into node i. 0 FIG. 1. x influences J a 0 FIG. 2. x is independent of y Probabilistic o-----: 0 Fuzzy Informational CallSal 04 ‘No-Forgetting’ FIG. 3. Five Interpretations of Arcs The N xN structural matrix A for an influence diagram of N nodes (each representing a distinct state or control variable) is a Boolean matrix of elements n,, defined as follows: o’J = 1 I if the ith node is a direct predecessor of the jth node 0 if the ith node is not a direct predecessor of the jth node A node j is called a direct successor of node i iff there is an influence arc directed from node i into node j. The tran- spose of the structural matrix, A’, represents the Boolean matrix of direct successors in an influence diagram. Although this relational information may appear trivial, the existence or lack of influence and independence between variables is an important part of understanding any complex problem. Too often expert systems will assume indepen- dence at a certain level or between levels in hierarchical data structures, such as semantic nets, to simplify the data storage and computational complexity. Various forms of conditional independence were assumed in PROSPECTOR (Duda et al., 1978 and Pednault et al., 1981) and MYCIN (Buchanan et al., 1984). The philosophy behind modeling with influence diagrams, is that this structural information is important domain knowledge of the problem, and should be captured along with more in-depth rules and numerical measures. This structural information is represented in a graphical fashion that experience has shown to be intuitive to many experts regardless of their level of mathematical proficiency. A knowledge of the mathematical calculus behind influence diagrams is not needed to model at the relational level. Functional Level In what follows, we shall outline the Bayesian or probabilis- tic approach to manipulating influence diagrams. It should be pointed out that influence diagrams on the relational level do not need a probabilistic basis to justify themselves. Rather probabilistic analysis is one approach to the deeper level interpretation of an influence diagram. Although not discussed in this paper, it is possible to incorporate other logics or inference techniques into the framework of the influence diagram (e.g., fuzzy logic and first-order predicate calculus) when appropriate. IDES 229 Mathematical Definition of Influence conditional independence between the variables involved. An influence between two random variables x and y is said to exist iff (y ) x,ff) # (y 1 H), where the inferential notation (y ( x, H) represents the probability distribution for y condi- tioned on x and the history or state of information H (Owen, 1978). Arc Reversals If the functional influence of y given x in Figure 1 is proba- bilistic, the influence diagram represents one expansion of the joint probabilities of state variables x and y: (x,y 1 H). Regardless of whether x and y are probabilistically indepen- dent, the probabilistic expansion represented by the influence diagram in Figure I can be written: The framework for arc reversals was established in previous sections. We shall now study a heuristic justification of the rules for the same. Arc reversals in an influence diagram should be performed such that they are consistent with the probabilistic information the diagram represents at the numerical and functional levels. Any rules for arc reversals must be therefore justified in terms of the calculus of condi- tional probabilities. As an example, consider the arc rever- sal between nodes x and z in the influence diagrams in Fig- ures 5a and 5b. (X,Y IN) = (Y lx,H)(x IH) (1) This implies that we know both the unconditional or margi- nal probability distribution on x and the probability of y conditioned on X. Suppose, however, that our human expert or statistical data base can not directly produce the marginal probability distribution on X, but does have the conditional distribution of x given y. Suppose also that we can obtain the marginal distribution on y. Using the laws of conditional probability , we can still obtain the joint dis- tribution on x and y using the following expansion: The expansion of the joint probability distribution represented in Figure 5a is: (x.Y.~ IH) = (x lff)(y IH)(z P,Y>H) (3) As explained before, if we know the terms on the right side of (3). we can construct the joint distribution on the left. Consider now the influence diagram in Figure Sb. The expansion in this case is: (X,V IH) = (x IY,H)(Y IH) (2) This expansion is represented by the influence diagram shown in Figure 4. Although both Figures 1 and 4 are equivalent in the joint system they represent, they differ in their suitability for probability assessment. Suppose now that x and y are independent in the sense that having information about x gives no additional information about y. Then the conditional probability of x given y, (X ly,H), is equal to the marginal distribution on x, (X ( H). The expansion of the joint probability distribution, (x,y 1 H), is then the product (x I H) (y (H) corresponding to the influence diagram shown previously in Figure 2. The lack of an arc between the state variables in Figure 2 graphi- cally illustrates their probabilistic independence at the func- tional level. (X,Y,Z IH) = (Y lH)(z ly,Hl(x l~.z.Hl (4) The problem facing us now is: Using only the terms on the right-hand side of (3), can we arrive at the terms in the right-hand side of (4)? Since (y I H) is known, our problem is now reduced to expressing (z 1y.H) and (x Iy,;,H) in terms of the quantities in (3). This can be done as follows (q, is the sample space for x): (2 IY,H) = /,,(c.r ly,H)~ = Jn,(z Ix,y.ff).(x IY.H)dx- = @ lx,~.H).(x IH)dx Using Bayes’ rule: Acyclicity = (z Ix,.v,H)‘(x IH) (2 1y.H) Cycles are not permitted in influence diagrams. This is because a cyclic diagram does not represent any expansion of the joint distribution of the variables involved. On the functional level it would lead to an infinite loop in which information on a particular variable (say X) is needed to get information on x itself. On the other hand, one might try to reverse the arc directly in Figure Sa to obtain the representation in Figure 5c. Here the expansion is: Numerical Level The numerical form of the probability distributions can be of either discrete or continuous form. The numerical data base for any node, however, must be conditioned on all of the nodes with arcs directed into it. (~,Y,=IH)=(~IH~~(~I~.H)~(~Is,H~ However, it would then not be possible to obtain the condi- tional probability (x 1 z.H) from the quantities in (3) without violating the conditional independence shown in Figure 5a. Thus we see heuristically the consequence of the arc reversal is the addition of an arc from node y to node x. This brings us to the following rules of arc reversal. RULE 1 for arc reversals: An arc from state node y to state node x can be reversed iff y is not a multi-path predecessor of x . TOPOLOGICAL TRANSFORMATIONS In the functional level description, we defined the proba- bilistic interpretation of the topology of influence diagrams, Now let us consider how Bayesian inference relates to topo- logical transformations on an influence diagram. RULE 2 for arc reversals: On reversal of an arc from y to x, node y inherits the direct predecessors of x and vice-versa. Arc Addition Recall that the existence of an arc signifies that an influence may exist. Therefore an arc can always be added between nodes as long as no cycles are introduced. A cycle implies that one can condition one’s knowledge of a variable on that variable itself, resulting in an endless loop; a sort of proba- bilistic Klein bottle. The addition of an arc, however, results in a loss of (possibly vital) information regarding the The purpose of Rule 1 is to disallow any arc reversal that may cause a cycle to be introduced in the diagram. A node y is called a mulfi-pafh predecessor of node x if it has more than one path to y, e.g. see Figure 5b. Clearly, the reversal of the arc from y to x without first reversing the arc from y n n n o---o (b) FIG. 4. y influences x FIG. 5. Examples of Arc Reversals 230 5th ICMM to z in Figure 5b will cause a cycle, which as explained before, invalidates the diagram. The example cited above for Rule 2 is of course not sufficient justification for the same. However, a little thought will show that the crux of obtaining the termgin the expansion represented by the new diagram is the joint distri- bution of the variables involved (x and z in our example), conditioned on the set of nodes formed by the union of the sets of their direct predecessors. In other words, this set of nodes will always precede the variables involved in the reversal in the hierarchy of the expansion. Hence they will always occur as conditioned on the aforementioned set of predecessors. A formal proof for the same can be found in Olmsted (I 984:Chapter 2) and Shachter (I 984b: 14- 16). Furthermore, it should be noted that arcs to and from deci- sion nodes cannot be reversed. This arises from the infor- mational nature of the arc to a decision node and the causal nature of the arcs from decision nodes to state nodes. Reversal of the former would violate chronological pre- cedence and that of the latter, causality. Barren Node Removal Although strictly speaking barren node removal need not form an integral part of the transformations to the influence diagram, we will refer to this operation since it is a con- venient technique to visualise the flow of information graph- ically. A node is said to be barren if it is not a member of the set of total predecessors of the node designated as the value node. In other words, the node is not concerned with the inference problem in hand. Furthermore, a node can become barren due to arc reversals. Such nodes (as a result of the topological transformations of the diagram) can be removed, and the diagram redrawn without changing the solution. Repeated application of this procedure leads to a shrinking infl.uence diagram concluding in a representation of the solution to the inference or decision problem under consideration. Details of the procedures for solving influence diagrams will be given in the following section. In expert system applications, barren node removal can be used as a mechanism to delete nodes and influences that are irrelevant to the specific question that is being asked of the system. The question and topological transformations needed to answer it. create what will be referred to as the currenl slruclure of the influence diagram. SOLVING INFLUENCE DIAGRAMS Two kinds of uses of influence diagrams will be described herein: I) probabilistic inference and 2) decision making under uncertainty. In either case there must be some ques- tion to be answered as represented by the diamond-shaped value node. Probabilistic Inference Probabilistic inference is equivalent to determining the pro- bability distribution (G(X)) Y.H) where X and Y are sets of nodes given in the diagram. The function G(X) is analogous to a value function and is called the goal-value function for probabilistic inference. This new goal-value node G(X) is added to the diagram with conditioning arcs from the set X. Because an influence diagram can contain at most one value node at a time, all previous goal-value nodes are converted to state nodes. The procedure involves manipulating the influence diagram to obtain a representation of the problem under consideration. The relevant arcs are reversed until the resulting diagram includes the goal: the desired represen- tation (G(X) 1 Y,H). Decision Analysis The transformations or operations involved in decision analysis are the same as that for probabilistic inference; that is arc reversals and barren node removal. However the difference is that here instead of determining a probability distribution. we are computing the expected value (or util- ity) of a sequence of decisions, comparing them and assess- ing the optimal sequence by maximizing the expected value of the utility function represented by the value node. The topological or symbolic solution procedure is equivalent to ordering the nodes in the correct sequence(s) of integration of state nodes or optimization over decision nodes. As pointed out by Shachter (1984a:l4) the steps involved at the numerical level are those used in evaluating a stochastic dynamic program. Note that the order so determined would correspond to one of the orderings that might be used in a decision tree based technique in which the variables in an expanded decision tree are either integrated or optimized over. The principle of dynamic programming allows pruning of suboptimal branches in this implicit decision tree. However. the influence diagram algorithm allows solution without the need of an intermediate tree representation. AI1 intermedi- ate calculations are performed directly from the influence diagram knowledge base and thus retain their original mean- ing. Node Removal Concept An equivalent way of looking at the above procedure is to consider node removal as a topological transformation that corresponds to manipulations of probabilistic functions. Nodes are removed in the order cf integration/optimization described above. Rules can be formulated that allow one to develop a topologicat solution to the problem, without expli- citly performing functional or numerical evaluations. If the topological transformations are to be useful, these rules need to have a basis in the probabilistic analysis of the problem. Given an acyclic influence diagram the optimal sequence of decisions can be found by ordering or removing nodes from the diagram according to the following rules: RULE 1 for State Node Removal: A state node i can be absorbed into the value node iff it directly precedes the value node and no other node. On its removal the value node inherits all the direct predecessors of i. Absorption of the node is equivalent to integration over the corresponding state variable, i.e., conditional expecta- tion. RULE 2 for Decision Node Removal: A decision node i can be removed from the influence diagram iff it directly precedes the value node and directly succeeds ail other direct predecessors of the value node. Removal of the node is then equivalent to maximization of the (condi- tioned) expected utility. Therefore, combining these rules with appropriate arc rever- sals, the topological solution procedure can be determined. The justification of the rules can be found in the literature on decision making under uncertainty (see Raiffa, 1970 or Bunn, 1984). COMPUTER ASSEMBLY DIAGNOSTICS TUTORIAL As an illustration of the use of influence diagrams, we present the Diagnostician’s Problem in the context of the automated assembly of microcomputers. In order to sim- plify the presentation, we will assume that during the final testing of a microcomputer, a system failure can be traced to failures in either of two components: (1) the logic board or (2) the I/O board. Let us further assume that a sensor is available that gives rudimentary information about the operating status of the assembled microcomputer and is a function of the operating status of the logic board and the I/O board. The associated influence diagram is shown in Figure 6a. This represents the Diagnostician’s Problem on the relational level. In the present structure of the influence diagram, the joint probability can be obtained from the conditional probablil- ity of the system status 3” and the marginal distributions on the state of the logic board “L” and the I/O Board “I/O” as given in the expansion below. (S,L,IIO IH) = (S I L,IIO,H)(L I H)(IIO 1 H) Note that L and I/O are conditionally independent (there is no arc between them) and thus their joint probability distri- bution is the product of each marginal distribution. IDES 231 FIG. 6. Probabilistic Injluence Diagram FIG. 7. Solvejor (L 1 E.H) The nature of the influences is specified at the functional level. The influence diagram in Figure 6a implies that the conditional distribution on S is known along with the margi- nal distributions on L and I/O. Let us assume for illustra- tion that the test for system status gives a deferministic result based on the status of the I/O and logic boards: if any of these boards (or both) is in a failure state the system status will show a failed system state. Using a subscript of “0” for a failed state and “1” for the operational state, this implies on the numerical level that the conditional distrihu- tion of the system status, S is: I for S, given L, and I/O, I for So given L, and I/O0 (S 1 L,IIO,H) = 1 for SO given Lo and I/O, (5) I for SO given Lo and I/O, 0 elsewhere Let us further assume that the marginal probability of failure is 5% for the logic board and 1% for the I/O board, giving the marginal probability distributions: (I’OIH) = 1 0.99 for I/O = I/O, 0.01 forl/O=l/O~ I 0.95 for L = L, (L 1 H) = 0.05 forL =LO (6) Probabilistic Reasoning The diagram m Figure 6a represents the diagnostician’s knowledge of the problem and system interrelationships. In diagnostic reasoning. however. we are more apt to want to know the cause of the failure given information about the system status. One question that might be asked is: What is the likelihood that the logic board has failed given a system failure has occurred? In this case, the evidence E = S = S,,. the event that there is a system failure. The joint probabil- ity distribution on L and f/O given the evidence can be obtained mathematically by use of conditional probability: (7) Equation (7) is summed (or integrated for continuous proba- bility distributions) over all possible states of the I/O board to find the conditional probability of the logic board status given a system failure, (L / E = So.H): I (L IE,H) = ~(L.llO 1E.H) w 0 where R,,o is the sample space for the possible states of the II0 board. This is an example of probabilistic reasoning. On the rela- tional level of the associated influence diagram. equation (7) corresponds to a sequence of arc reversals leading to the influence diagrams shown in Figure 7a. The logic board node, L, is overlayed with a diamond to signify that this is the goal of our probabilistic reasoning. If the evidence E is known with certainty the probabilistic node S is now deter- ministic and updated with the new information on the sys- tem status. Because S is no longer probabilistic, we are only interested in events that are conditioned on this new infor- mation, i.e., we want to reverse all arcs leading into S. In Figure 7a the arc between L and S is reversed and node L inherits all of the direct predecessors of S, which in this case is the I/O node. Next the arc between I/O and S is reversed in Figure 7b without the addition of any new arcs. Finally the I/O node is absorbed in Figure 7c by summing over the states of the I/O board according to Rule 1 for state node removal. In numerical terms, the topological transformation shown in Figure 7a can be considered a combination of two steps as shown in Figure 6h & 6c: (1) Aggregation of the two nodes on each side of the arc to be reversed. Aggregation corresponds to calculating the joint probability distribution of the nodes condi- tioned on the union of the predecessors of both. In this case, aggregation means finding the joint probability dis- tribution of S and L conditioned on I/O (Fig. 6b). (2) Disaggregalion of the joint distribution by condition- ing it on the node that the new arc will be directed away from. In this case, the joint distribution should be con- ditioned on S given I/O (Fig. 6~). The denominator in the disaggregation step is obtained by summing (or integrating for continuous distributions) the joint distri- bution from the aggregation step over the outcome space of the node the new arc will be directed towards (in this case, L). Although shown graphically in Figure 6 as separate steps, all information in the original diagram must be stored until the arc reversal transformation is complete. At the numerical level, the aggregation step corresponds to the following expansion using equations (5) and (6): {L,SIIIO,H) = {SIL,IIO.H)~{L lll0.H) (8) = (S(L.IIO,H)‘(L \H) 0.95 for S, and L I given I/O, 0.95 for SO and L , given I /Oa = 0.05 for So and Lo given I/O, 0.05 for SO and Lo given I/O0 0 elsewhere The disaggregation step involves conditioning this joint dis- tribution on the conditional distribution on S. The numerator in equation (9) is the joint probability distri- bution in equation (8). The denominator (S (II0.H) is obtained by “integrating” the joint probability (L,S ) IIO,H) from equation (8) over the state space of L. Substituting in the numerical values from equations (6) and (8) into equation (9) gives the conditional distribution on L : I for L, given S, and I/O, 0.95 for L, given So and I/O, (L ) IIO,S,H) = I for Lo given So and I/O, 0.05 for L, given S0 and I/O,, 0 elsewhere (10) The influence diagram in Figure 7b represents an arc rever- sal between S and I/O. The new conditional probability (II0 1S.H) is obtained from (S ll/O,H) and (I/O ( H) as represented in Figure 6c or 7a. This can also be thought of as aggregating nodes II0 and S and then disaggregating by 232 5th ICMH conditioning the joint distribution on S. = (S.IIO I H) (S(H) _- Figure 7c represents the conditional probability distribution (L 1.7, H) and the marginal distribution (S 1 H). (L IS,H) = z(L l.S,~IO,H)(~IO 1.S.H) Q,0 On a topological level, summation or integration corresponds to absorption of nodes. In this example, after the arc reversals shown in Figure 7a & 7b are performed, the I/O node is absorbed leaving the influence diagram in Figure 7c. Suppose that we are given that a system failure has occurred i.e., S = St,. Let us define this as event E = S = So. Thus the likelihood that the logic board is the cause of the failure may be quantified by (L =LO ) E =S =S,,, H). From equa- tions (IO) and (I 1): (L=L,,JE-S=S,,H) = (LoIE,I/Oo,H).(lIOo(E,H) +(LoIE,IIOI.H)~(IIO, 1E.H) = (0.05)~(0.1681) + (1).(0.8319) = 0.8403 Decision Problem Let us now look at a decision problem. The Diagnostician’s Problem is to decide which component should be tested for failure first and repaired if appropriate. In an automated assembly operation, this could mean deciding where the computer should be sent for “rework”. If the diagnostician is wrong in his or her decision for rework, valuable time would have been wasted by the rework technician and hence in producing the final product. For purposes of illustration, let us assume that the costs of rework, which involves open- ing the computer and pulling out the appropriate board, testing, and repairing it, is a constant for each board. The inguence diagram in Figure 8 has been modified to show these decision and value nodes. Recall that there is an implicit arc between all decision nodes and the value node. This “No-Forgetting Arc” has been added to the influence diagram in Figure 8. It has been assumed that a system failure has occurred and this information is known at the time that the rework decision is made. The diagnostician has two choices given that the system status shows a failure (E =S =.S,): (1) DL = Send the logic board to rework first and (2) D,,* = Send the l/O board to rework first Each of the two decisions has three possible outcomes corresponding to the possible states of the boards given that a system failure has occurred S = So: (1) LdlOo, (2) L ,1/O,, and (3) &J/O,. If the wrong board is sent to rework, then debug time has been wasted on that board and the other board must be sent to be debugged and reworked. It is also possible that the board sent to rework has failed but the other board has failed also and must be repaired. The two decisions, possible outcomes, and cost consequences are shown in the decision tree in Figure 9. From the influence diagram in Figure 8 and the decision tree in Figure 9, we see that the rework decision influences the value node. If this were not the case the decision would be irrelevant (a “worry” over which the decision maker has no control). Furthermore, the outcome of the rework deci- sion also influences the cost. This is due to the fact that though we pick one of the two boards (say I/O) for rework, it could well turn out that the other board (L in this case) has really failed. In such a case, the cost of debugging and reworking the second board would have to be added to the original expenditure. Given that a system failure has occurred. which board should be tested first? Diagnostician’s Problem Solved Applying the rules for influence diagram manipulation, dis- cussed previously, we get the topological or symbolic solu- FIG. 8. Diagnostician S Problem peckzion_ Results “R” CostValue l&O1 $Lkbw(L) + WepaW) $Debug(L+I/O) + $Repair(VO) $Debug(L+VO) + $Repak(L+VO) $Debug(l/O+L) + $Aepair(L) $Debug(VO)+ $Repair(llO) $Debug(l/O+L) + $Repair(l/O+L) FIG. 9. Decision Tree D c v L 110 S (8) D C v I/O s (c) D C w s (e) 0 C D C v I/O W S B-4 (1) Optimal Expected Utility FIG. 10. Topological Solution of the Diagnostician S Problem. tion as the following sequence of node removals: R , L, I/O, S, and D. The modified intluence diagram in the above . stages of node removal is shown in Figure 10. A numerical example of the solved diagnostician’s problem can be found in Agogino and Rege (1985:30-37). Value of Imperfect Information (Value of Testing) A generalization of the Diagnostician’s Problem is the addi- tion of another test or sensor that gives more information IDES 233 lNrERRcGAx)Fy INTERFACE SOL”T72Y%%_E ? I FIG. 1 I. IDES Structure about the state of the boards without having to go through expensive debugging procedures. Unfortunately the test is imperfect and the diagnostician must still make a decision under uncertainty after viewing the results of this imperfect test. To make matters worse, this test is not free and thus the costs of the additional test must be weighed against its benefits in reducing the uncertainty in the decision. The decrease in expected value due to the additional sensor is called the expected value of additional testing. The influence diagram solution procedure remains !he same, except the optimal result will now include two decisions: (I) Dr = testing decision and (2) DR = rework decision. AUTOMATION OF INFLUENCE DIAGRAMS The IDES (Influence Diagram Based Expert System) is an expert system development tool based on the automation of influence diagram technology described previously. Because the underlying interpreter is written entirely in the compiled language C, IDES is transportable to a large number of mainframe and microcomputer systems. The IDES system provides several levels of automation and inference from the graphical influence diagram representation: (1) Bayesian inference, (2) optimization, and (3) sensitivity analysis. Principles of dynamic programming and influence diagram logic allow efficient numerical optimization of the decision or control problem without ever having to consider inter- mediate representations such as fault trees, simulation models, or decision trees. An upper bound on the value of additional information or testing can be evaluated through use of IDES’s unique features for simulation and sensitivity analysis. Figure 11 shows a schematic_outline of the various modules of IDES and their interaction with each other. SUMMARY As illustrated in the Diagnostician’s Problem, influence diagrams can be applied to expert systems requiring both reasoning under uncertainty (probabilistic inference) and advising (or controlling at the machine level). The lnterro- gator module or the IDES (Influence Diagram Based Expert System) elicits information from the expert/user on the topological structure of the influence diagram which represents a model of the problem under consideration as well as the functional relationships and numerical probabili- ties associated with it. The topological solution module in IDES finds a symbolic solution without any numerical com- putauons. The topological solution is equivalent to ordering the state and decision variables in a sequence same as that of the corresponding decision tree. Once the order in which to integrate chance nodes and optimize over decision nodes is known, the actual computations are relatively straightfor- ward and calculated in the numerical computational module of the IDES program. Because the control structure is independent of the knowledge base, new knowledge can be added or subtracted from the data base without adjusting the basic Bayesian control structure. The sensitivity analysis module can be used to add new evidence and test failure hypotheses in real-time diagnostic applications in process control and automated manufacturing environ- ments. REFERENCES Agogino, A.M. and A. Rege (1985). A Tutorial on influence diagrams. Working Paper #85-0702-2, Expert Systems Laboratory, Department of Mechanical Engineering, University of California. Berkeley 94720. Agogino, A.M. (1985). Use of probabilistic inlluence in diagnostic expert systems, Proceedings of the 1985 ASME International Computers in Mechanical Engineering, Boston, MA, Aug. 4-8, Vol. 2, pp. 305- 310. Buchanan, B.G. and E.H. Shortliffe (1984). Rule-Based Expert Sysfems, Addison-Wesley Pub. Co., Menlo Park. CA. Bunn, D.G. (1984). Applied Decision Anal,vsis. McGraw- Hill. New York. N.Y. Duda, R.i)., P. E. I&t, and N. J.,Nilsson, (1978). Semantic network representations in rule-based inference sys- tems. Pattern Directed Inference Systems, Waterman, D.A. & F. Hayes-Roth, eds., pp. 1075-1082, Academic Press, London LTD. Holtzman, S. (1985). Intelligent decision systems. Ph.D. Dissertation, Department of Engineering-Economic Systems, Stanford University. Howard, R.H. and J.E. Matheson (1984). Influence diagrams. Readings on the Principles and Applications of Decision Analysis, Strategic Decisions Group, Menlo Park, CA. Miller, A.C., M.M. Merkhofer and R.A. Howard (1976). Development of automated aids for decision analysis. Stanford Research Institute, Menlo Park, CA. Olmsted, S.M. (1984). On representing and solving decision problems. Ph.D. Dissertation, Engineering-Economic Systems Department, Stanford University. Owen, D.L. (1978). The use of influence diagrams in struc- turing complex decision problems. Proceedings, Second Lawrence Symposium on Systems and Decision Sciences, Oct. 3-4. Also in Bunn. D.W. (1984:2 12). Pednault, E.P.D., S.W. Zuker, and L.V. Muresan (1981). On the independence assumption underlying subjective Bayesian updating. Artificial Intelligence, Vol. 16, pp. 2 13-222. Raiffa, H. (1970). Decision Anai.vsis: Introductoql Lectures on Choices Under Uncertainty, Addison-Wesley Pub- lishing Company, Menlo Park, CA. Shachter, R.D. (1984a). Evaluating influence diagrams, Department of Engineering-Economic Systems, Stan- ford University. Shachter, R.D. (1984b). Automating probabilistic inference. Department of Engineering-Economic Systems, Stan- ford Univ., presented at the Nineteenth Actuarial Research Conference, University of California, Berke- ley.