/*-------------------------------------------------------------*/ /* Model-Based Diagnosis in NCL */ /* (C) 1993 Zdravko Markov, II-BAS */ /*-------------------------------------------------------------*/ /* DESCRIPTION: ----------- This program illustrates the use of the NCL spreading activation mechanism for a typical constraint solving task - model-based diagnosis. We use the definition of the problem as described by Reiter (Reiter, R., A Theory of Diagnosis from First Principles, Artificial Intelligence, 32:57-95, 1987). A model of a system is a triple , where SD is a system description, COMPS is an n-tuple of the states (normal or abnormal) of the system components, and OBS, observations, is an m-tuple , containing the system inputs and outputs. We discuss a binary adder built out of five functional elements - two XOR gates (X1, X2), two AND gates (A1, A2) and an OR gate (O1), and has three inputs (In1, In2, In3), and two outputs (Out1, Out2). The system description comprises a net-clause and Prolog procedures (defining the functional elements used). Each system component is represented by a spreading activation node, where the node procedure defines its functionality. The component connectors are represented by net-variables. Each component is activated when two of its three input/outputs are bound (the threshold is 2). Thus a component can both calculate a Boolean function and check the consistency of the values supplied at its input/outputs. The states of the system components (COMPS = ) are represented by net-variables bound by the corresponding Prolog predicates "xorg", "andg" and "org". Each one of the latter is defined by three clauses, and thus each component can have three states - normal (ok), abnormal (ab), and don't care state (free state variable). A component is in a normal state, when the corresponding Boolean function (xor, and, or) is satisfied, otherwise it is in an abnormal state (strong fault model). The third state happens when at least one of the component input/output variables is free (unbound). The advantage of this model is that it can infer diagnoses (COMPS) from the observations (OBS). An important feature of these diagnoses is that they are minimal (a minimal diagnosis is such that, changing a status of any abnormal component to normal would make the diagnosis inconsistent with the observations). This feature is due to the use of a third state of the components. Usually the components used in the model-based diagnosis has two states (normal and abnormal) and the system description (e.g. a constraint logic program) is used to test whether an observation is consistent with a diagnosis. Then the problem is to find a proper algorithm for searching through the space of possible diagnoses (usually viewed as a lattice). Our approach extends the system description so that it can infer minimal diagnoses directly. The basic idea is that when a component is in a normal or in an abnormal state its input/outputs are fully determined (bound), and hence no change of the component state is possible, without a change of the states of the neighboring components. (This property is ensured by the global consistency of the net-clauses.) The state variables X1, X2, A1, A2, O1 are bound only in these cases, and since the spreading activation node indicating the diagnoses is activated only when all state variables are bound (its threshold is equal to the number of variables), it is clear that only minimal diagnoses are inferred. */ /*-------------------------------------------------------------*/ /*------------------------ Net-clause -------------------------*/ obs(In1,In2,In3,Out1,Out2): /* OBS */ node(In1,In2,A,2,xorg(In1,In2,A,X1)): /* X1 */ node(In3,A,Out1,2,xorg(In3,A,Out1,X2)): /* X2 */ node(In1,In2,B,2,andg(In1,In2,B,A1)): /* A1 */ node(In3,A,C,2,andg(In3,A,C,A2)): /* A2 */ node(B,C,Out2,2,org(B,C,Out2,O1)): /* O1 */ node(X1,X2,A1,A2,O1,5,assertz(comps(X1,X2,A1,A2,O1))). /*COMPS */ /*----------------- Delivering the diagnoses ------------------*/ diagnoses(A,B,C,D,E,_):-top(T),obs(A,B,C,D,E),spread(T),fail. diagnoses(A,B,C,D,E,L):-setof(comps(X1,X2,A1,A2,O1), comps(X1,X2,A1,A2,O1),L), delete(comps). /*--------------------- System Components ---------------------*/ /* XOR gate */ xorg(X,Y,Z,ok):-xor(X,Y,Z). xorg(X,Y,Z,ab):-not xor(X,Y,Z). xorg(X,Y,Z,_):-var(X);var(Y);var(Z). /* AND gate */ andg(X,Y,Z,ok):-and(X,Y,Z). andg(X,Y,Z,ab):-not and(X,Y,Z). andg(X,Y,Z,_):-var(X);var(Y);var(Z). /* OR gate */ org(X,Y,Z,ok):-or(X,Y,Z). org(X,Y,Z,ab):-not or(X,Y,Z). org(X,Y,Z,_):-var(X);var(Y);var(Z). /*--------------------- Boolean Functions ---------------------*/ /* XOR function */ xor(0,0,0). xor(0,1,1). xor(1,0,1). xor(1,1,0). /* AND function */ and(0,0,0). and(0,1,0). and(1,0,0). and(1,1,1). /* OR function */ or(0,0,0). or(0,1,1). or(1,0,1). or(1,1,1). /*--------------------------------------------------------------*/ /* EXAMPLES: */ /*--------------------------------------------------------------*/ ?- netmode(0). /* Breadth-first mode only ! */ ?- diagnoses(1,0,1,1,0,COMPS). /* Infer all diagnoses */ /* COMPS=[comps(ab,ok,ok,ok,ok),comps(ok,ab,ok,ab,ok), comps(ok,ab,ok,ok,ab)] */