A Diagnostic Algorithm based on Models at Different Level of Abstraction

1 Introduction

The difficulties encountered in applying knowledge-based system (KBS) technology to complex systems have made the need for representing and using deep knowledge about system behavior increasingly clear to KBS designers. This knowledge is typically well structured, formal, rely­ ing on established theories. For example, knowledge about solid state physics, semiconductor technology, and elec­ tronic design in circuit testing [Brown et a/., 1982, Davis, 1984], knowledge about macro-economic laws in financial forecasting [Iwasaki and Simon, 1986], and physiological knowledge and biochemical knowledge in medical diag­ nosis [Kuipers, 1985]. As opposed to empirical associa­ tional knowledge, such knowledge is said to provide a deep model of the domain.

While the impact of the new techniques for dealing with deep models on real applications is still poor, a rather large number of approaches to modeling and rea­ soning with deep knowledge have been experimented. They can be classified into two broad categories:

1. Several authors basically aim at identifying and representing the causal structure underlying a specific expertise. Rieger and Grinberg [1977] first practised such an approach, which has been recently experienced again by Fink [1985], Guida [1985]. Torasso and Console [1987] among others.
2. A different line of thought avoids explicit represen­ tation of causal dependency, conforming to the clas­ sical approach of physical sciences. This approach is often referred to as qualitative modelling (refer to Bobrow [1984] for a comprehensive review of the major relevant works), but the term is rather inap­ propriate, as many works, and especially the ones coping with realistic applications [Genesereth, 1984, de Kleer and Williams, 1987] actually make use of quantitative models.

Most of these applications, and especially the ones faced according to the latter approach, we will focus on hereinafter, concern diagnosis. For instance DART [Genesereth, 1984] and GDE [de Kleer and Williams, 1987] represent two of the most mature attempts of transferring new modeling concepts in the realm of practi­ cal applications. Both focus on the same task, i.e. diag­ nosis of electronic circuitry, and adopt a quantitative model of the system to be diagnosed. Compliant with the current way of representing and reasoning about electronic circuitry, they represent the system to diagnose as a set of interconnected components of known transfer function 1 · The inference mechanism adopted is basically different, however, as Genesereth uses a linear input resolution algorithm on a set of first order clauses, while de Kleer and Williams couple constraint propagation with an Assumption-based Truth Maintenance System (A TMS) for managing different diagnostic hypotheses.

Nevertheless, both worlcs adopt the same basic diagnostic strategy which consists of:

1. identifying that a fault exists by comparing the simulated device behavior with the actual one;
2. generating a list of candidate faulty components by reasoning on the system structure;

1 Both the direct and the invene transfer function are actually used

for solving the diagnostic problem.

1. identifying a set of new test points allowing to further discriminate among the candidate sets;
2. completing the discrimination process through examination of further test cases (which are automatically generated by DART).

This paper presents a novel model-based diagnostic method, whose distinctive features make it suitable for diagnosis of continuous processes, an application field which is deemed to be highly promising and challenging for the application of knowledge based systems, and has received much attention in recent years.

The method we introduce makes use of models at different levels of abstraction2, qualitative and quantita­ tive. In particular, we discuss an algorithm using a quanti­ tative, real-valued algebraic model, and a qualitative causal model that can be easily derived from the former in an automated way. The causal model is used for candidate generation, and the real-valued model for validation/rejection of candidates. This way, candidate generation based on a qualitative causal model provides explanations for the diagnoses validated on a quantitative ground. Candidate generation is performed with rather simple new techniques, compared to previous approaches, and candidate validation makes use of consolidated numerical methods.

We discuss in the following sections:

• the diagnostic situation which has motivated and determined our approach;
• the method based on reasoning at different levels of abstraction;
• the algorithm using a causal and a real-valued model;
• a comparison between our method and previous approaches.

2 The Diagnostic Problem

The behaviour of a dynamic system can be modeled by a set of differential equations relating its actual state to the input vector and to the previous state:

where F is expressed using both algebraic and differential operators.

Most industrial processes are designed to operate, however, in a stationary condition identified as a max­ imum of a defined function of merit. In these situations, we may assume that the observable stationary state of the system solely depends on the values attributed to the set of input values:

Within vector .i. we can also distinguish between proper input variables (D), which are observable, and unk­ nown disturbances that can modify some parameters p of the system, whose values are defined when the system is designed and should be constant in order to maintain the system at the desired state. From (2) the state .s. can be expressed as:

l When a qualitative model is derived from a quantitative one [Kuipers, 1984, de Kleer and Brown, 1984], the former is an abstraction of the latter in that qualitative variables range in a finite set of values vs. an infinite seL

In these systems a diagnostic problem arises when the sys­ tem state changes independently from a variation of the input vector y, due to disturbances affecting one or more system parameters. Under well known conditions upon (1) the system is stable and one must assume that, follow­ ing parameters variations, the system recovers a station­ ary state .( such that:

The diagnostic problem consists of determining which variations:

may have occurred to generate the displacement:

At=.(- .s.

(5)

of the observable system state.

Let's notice that we refer to system anomalies that are said malfunctions, rather than faults, in that the struc­ ture of the system model (as defined by (1)) remains unchanged. Recovery from early malfunction conditions is the proper function of most control systems, both automated and manually controlled (the latter are often said monitoring or supervisory systems). In these latter systems, which apply to most industrial processes (e.g., power generation), diagnosis is often mandatory for deter­ mining the most appropriate control and/or repair opera­ tion.

In malfunction conditions it is often reasonable to assume that variation fl{z is small enough that ~.s. linearly depends on ~/l.:

where the coefficients of the sensitivity matrix C are given by

Ordinarily Cis a rectangular mxn matrix with n > m, and diagnosis consists in identifying, among the infinite solu­ tions to system (6), the ones which comply with some minimality criterion. Peng and Reggia [1986] individuate in non-redundancy the most appropriate criterion for diag­ nosis. In summary, we can state our diagnostic problem as the one of identifying the non-redundant solutions to sys­ tem (6). Formal definitions of diagnosis and non­ redundancy are given later in section 3.1.

Prior to analyzing how the problem can be solved, let's note here that it may be rather complex even for sys­ tems of moderate dimensions. A straightforward approach to its solution will be to look for non-redundant solutions of system (6) among the self contained subsystems of order m that can be obtained from (6) by imposing that a subset of n-m components of fl{z is null:

this gives, in the worst case, ~ J subsystems of order m to be solved. In most cases, the values of .s. in (3) are continuously monitored, so that one may assume to com­ pute di with the sampling rate of the monitoring equip­ ment, and start a diagnosis whenever a norm of di goes beyond a given threshold.

In conclusion, let's sttess the distinctive features of our problem compared to the circuitry diagnosis problem which models diagnostic systems like DART and GDE:

• In circuitry diagnosis, the problem is rather one of fault insulation (picking up the electric component(s) which do not behave correctly) than one of system state identification.
• In circuitry diagnosis, a fault alters radically the sys­ tem behaviour, so that one is aimed at identifying which component model(s) are contradictory with the observed circuit behaviour. In process control, one is aimed at identifying malfunctions, rather than faults. Early diagnosis of malfunctions and timely intervention is properly the way to avoid drastic alterations of the system behaviour.
• In circuitry diagnosis, an interesting subproblem is to identify which measurement and/or test take next on the system to refine/validate a diagnostic hypothesis. This suggests a strategy based on step­ wise refinement of diagnosis, starting from few symptoms.

In process control all the measurements are nor­ mally taken and available when diagnosis starts.

3 The Diagnostic Method

3.1 The Basic Diagnostic Strategy

With reference to system (6) of section 2 we may now introduce the following definitions:

• Definition: a set P of parameters is said to be a diagnosis of (6) iff a solution dm! of system (6) exists such that all and only the components of d}2Q corresponding to the elements of P are non-null.
• Definition: a diagnosis P is non-redundant iff there is no diagnosis P' such that P' c P.

We have noted that determining the non-redundant diag­ noses of (6) requires finding the base solutions of a real­ valued, linear, under-constrained system. This means to search in a space which is rather large, even for systems of moderate complexity. However, we may make an important remark: diagnosis (at least in the context of the problem we consider) is intrinsically Qualitative. In fact, rather than in the real value of each component of a non­ redundant solution P of (6), we are interested primarily in knowing which components of P are not null. Knowing which parameter is varied usually means to know what is the cause of the malfunction. This feature is clearly shown in [Gallanti et al., 1986] where we introduce an example (diagnosis of a steam condenser in a power plant) representative of a large class of diagnostic systems. Therefore, we may argue that a qualitative model abstracted from (6) would probably be sufficient to our purposes, and would be far simpler to reason about than (6).

We note here, however, that, being a qualitative model more abstract (thus less detailed) than a quantita­ tive one, there is a loss of resolution in the qualitative model, with respect to the real-valued one. Thus solutions obtained from a qualitative model will be possibly less detailed, but far less expensive to compute.

Hence we may devise a heuristic search strategy based on the qualitative model. Candidate solutions are to be searched on the qualitative model, and validated or rejected using the quantitative model.

When a qualitative solution P is quantitatively rejected, it can be refined considering for further valida­ tion on the quantitative model redundant solutions of the qualitative model encompassing P. This way . the qualita­ tive model is used for candidate generation, and the quan­ titative one for candidate validation.

3.2 Choice of the Qualitative Model

Among the several approaches to qualitative modeling, we could restrain ourselves to a rather simple model derived from (6), according to [de Kleer and Brown, 1984] simply by substituting in (6) real-valued variables !l.p's, ds's with the associated qualitative variables op's, as's, the real-valued sum and difference operators with the corresponding qualitative operators in a three values domain ( (+, -, 0): these values indicate respectively incre­ ment, decrement and stability with respect to a reference value), and the coefficients of the variables by their sign. Let's notice that, given the qualitative nature of diagnosis, this model alone may be sufficient to our purposes for rather simple diagnostic problems like the one presented in [Gallanti et al., 1986].

Unfortunately, it is easy to show [Struss, 1988] that in the domain defined by this simple qualitative calculus the additive inverse does not exist, and this makes it difficult to determine unique solutions to the set of quali­ tative equations derived from systems like (7); even when m is small. The limitations of the earlier qualitative cal­ culus were faced either resorting to order of magnitude reasoning [Raiman, 1986], or by resorting to quantitative operators when qualitative ones give ambiguous results [Williams, 1988]. The approach we are going to illustrate is rather similar to the latter; however, we keep a neat separation between qualitative and quantitative models, using them for separate purposes (candidate generation and validation, respectively), and with separate resolution algorithms. On this vein, we have chosen to increase, rather than decrease, as Raiman [1986] does, the level of abstraction of the qualitative model, considering that the advantages, in terms of computational costs, should amply compensate for the loss in resolution3.

The simpler qualitative model that can be abstracted from (6) is a purely causal model. Each equation:

3 However, we aclrnowledge that a thorough comparisoo to usess the relative merits of qualitative models at different levels of abstraction in the context of diagnosis is still to be done.

of system (6) can be interpreted as a statement of causal dependency between the variation of one, or more, param­ eters Pj· whose corresponding ¥j appear with non-null coefficients CiJ in (6i), and the vanation of the observable ~- In particular, a non-nun variation of ~ may be explained by a variation of at least one among the pj:

while a null variation of ~ implies that either none of the Pj is changed or that at least two parameters are changed but their combined effect on the observables is null:

Iwasaki and Simon [1986] outline a procedure for deriving from a set of quantitative equations a (partially ordered) causal model in form of a causal net. This net is generated from the connection matrix associated to C in (6). We present in the next section an algorithm for candi­ date generation (based on set operations) which does not need the generation of a causal net, in that it operates directly on the sensitivity matrix C.

4 The Diagnostic Algorithm

Compliant to the method outlined in section 3.1, the diagnostic algorithm consists of two steps: the first, candidate generation. derives possible diagnoses from an analysis of the qualitative model described in 3.2; the second, we will call candidate validation. consists of iden­ tifying among the candidates the non-redundant diagnoses consistent with the real-valued model (6). In this schema, dependency analysis based on the qualitative model is used as a heuristics for reducing the cardinality of the search space, in that it allows to reduce the number of self-contained subsystems like (7) to be solved.

4.1 Candidate Generation

The equations of (6) can be partitioned in two classes: the class of symptoms and the class of constraints. The former corresponds to those variables ~ whose measured values are different from the expected ones. The latter holds those equations whose associated state variables have nominal values.

Let's introduce accordingly two submatrices of C, C' and C" such that:

where the number of equations of (8) (the symptoms) is k and the number of equations of (9) (the constraints) is m-k.

According to (Ll), for each symptom E1 (i e {1 .. k}) a propositional formula A. is built, consisting of the disjunction of each parameter P; (j e { 1 .. n}) such that the coefficient c 'ij of llpj in equation E1 is different from zero:

The disjuncts of A. correspond to all and only the parame­ ters such that the variation of one (at least) of them explains symptom E1, i.e. the difference of observable ~ in (8) from the expected value.

According to (L2), for each constraint E1 (i e { 1 .. m-k)) the propositional formula B1 is built. If P; (j e {1 .. n}) are the parameters belonging to E1 such that c" ij is different from zero in equation E1, we have:

where the literal .., P; means that the parameter P; is not changed. Each disjunct belonging to B1 explains why observable s 1 in constraint E1 of (9) is not different from the expected value (either no parameter having influence on E1 is changed or two (at least) of them are changed, but their combined effect on the observable is null).

The formulas A. (i e {1 .. k}) are combined in for­ mula A:

This formula represents a11 the explanations4 that give an account for symptoms only.

In the same way, the formulas B1 (i e {1 .. m-k)), if they exist, are combined in formula B:

The formula B represents explanations that justify why the observables in (9) are not changed.

The logical formula (L) explaining a11 the observa­ tions is now obtained by the conjunction of the two for­ mulas A and B:

L may be used for computing candidates in that, when transformed in disjunctive normal form, its disjuncts represent the plausible diagnosis for both the symptoms and the constraints. A candidate consists of all the posi­ tive literals of a disjunct of L.

It is easy to prove that the set CAND of candidates corresponding to the disjuncts of L contains any candidate non-redundant diagnosis of (6). The actual diagnoses are determined by the validation procedure on the quantitative model, as outlined in the next subsection.

4.2 Candidate Validation

A candidate generated according to the procedure described in 4.1 will be a diagnosis of (6) if there exists a solution of (6) such that the value of any parameter included in the candidate is non-zero, and the value of any parameter not included in the candidate is zero.

Before performing validation, set CAND is ordered according to candidate cardinality; those candidates whose cardinality is greater than m are removed, as it is easy to prove that they cannot be non-redundant diagnoses.

Validation is then performed starting from minimum car­ dinality candidates; when a candidate P is validated, all its supersets are removed from CAND, as they would be redundant with respect to P.

Candidate validation is easily performed with con­ ventional methods for solving linear systems, e.g. the Gauss-Jordan algorithm.

4 Given a truth value assigmnent satisfying the formula, an explana­ tion is the set of all and only those positive lilerals (Le. parameters) whose assignment is the truth value True.

4.3 An Example

Let's consider the following system of three linear equa­ tions with five unknowns:

and suppose that the following variations are measured:

The number of systems of order three to be solved without prior candidate generation is:

The symptom class holds equations E1 and Ez. From the symptoms the formulas A1 and A1 are computed:

A1 and A2 include, respectively, those parameters the observables s1 and ~ depend on.

The constraint class includes equation E3 from which we may build B1 such that:

A=~"~=~v~v~v~v~"~"~"~"~ Formula A represents all the explanations of the variations of both s1 and ~·

From B1 formula B is built; it represents the possible explanations why the observable s3 is not changed:

B = B1 = {-,pi "-,p3 "-,p,) v (pi "P3) v (pl "p,) v (p3 "p,) Now formulas A and B are joined to obtain formula L:

L = A " B = (pi v P2 v P3 v p, v Ps) " (pi v P2 v P3 v Ps) " {{-,pi "-,p3 "-,p,) v (pi "p3) v (pi "p,) v (p3 "p,))

Formula L in disjunctive normal form is:

L =(pi "P3)v (pi "PJv (pl "P3"PJv (pi "P2"P3)v (pi" P2" pJ v (pi" Pz" P3 "p,)v (pl "P3 "Ps)v (pi "p," Ps) v (pi "P3" P· "Ps) v (p2" -,pi " -{J3" -,p,) v (p2" P3" P·) v (p2" Ps" -,pl " -{J3" -,p,) v (pl "Pz" P3 "Ps)v (pl "P2" P-." Ps)v (p2" P3" p," Ps)v (p3" p,) V (p3 "P-. "Ps) v (ps " -,pi " -{J3" -,p,)

Now set CAND is built from L and sorted with respect to candidate cardinality; then, element having cardinality greater than three (the number of equations of (10)) are deleted. The set of the candidate is the following:

CAND = { {p2},{ps}, } {p1p3}, {plp,}, {P2.Ps}, ~p,}, {p1p3,p,}, {pi P2P3}, {pi PzP·}, {p1J13Ps}, {pi P·.Ps}, {I'2P3P4}, ~P·Ps}

Now these proposed candidates must be validated on the quantitative model. The first candidate P of CAND is selected:

System (10) admits solution {~p1 = 0, .6p 2 = 2, b.p3 = b.p4 = b.p5 = 0} and therefore P is a non-redundant diagnosis.

From set CAND all the supersets of P are then removed so that CAND is reduced to:

CAND = { {p5}, {plp3},{pl,p4} ,{p3p,}, {p1J13P4}, {p1J13Ps} .{Pl.P·Psl .{P3.P·.Ps} }

Validation continues until CAND is empty. At the end of the process, i.e. when CAND is empty, the algorithm has computed four non-redundant diagnoses:

~},{pi ,p3}, {pi ,p4 .ps}, {p3 ,p4 .ps} which correspond to the following solutions: {b.pl = 10, .6p2 = .6p3 = 0, .6p, = 2, /}.p5 = -2}

{b.pl = 0, /}.pz = 2, .6p3 = .6p, = b.ps = 0} {.6pl = 5, /}.p2 = 0, .6p3 = 1, .6p, = /}.p5 = 0} {.6pl = b.p2 = 0, .6p3 = 2, b.p-. = -2, b.p5 = 2}

5 Conclusions

We may now restate and precise the comparison with pre­ vious works on model based diagnosis. In particular we will refer to GDE as presented by de Kleer and Williams [1987]. GDE uses a single, quantitative, model of the sys­ tem to diagnose; the basic Computation mechanism is con­ straint propagation. Candidate generation is based on comparing the results computed by constraints under different assumptions with measured values. Constraint propagation is the source of the incompleteness of GDE, due the inability to solve simultaneous equations [de Kleer and Williams, 1987]. that makes it unpractical for a large class of applications, including almost any continuous pro­ cess. Our approach exploits a causal view of the system for generation of candidates similar to causal ordering as proposed by Iwasaki and Simon [1986]. This is coupled to conventional techniques for candidate validation, thus overcoming the above limitation of constraint propagation. As candidates are determined on the basis of a causal model, it is easy to provide natural justifications to diag­ noses generated by the system.

Finally, an important difference with the approach to diagnosis taken by GDE is the neat separation between generation and validation of candidates. We have remarked in section 2 that this is suggested from the specific features of diagnosis in process control as opposed to diagnosis of electrical circuitry, because in the former measurements are usually all available before the diagnostic process is started. Thus stepwise refinement of diagnosis is not justified in our context.

Acknowledgements

This paper describes developments partially undertaken within ESPRIT project P820, partly funded by the Com­ mission of the European Communities within the ESPRIT programme. Project P820 consists of a consortium com­ posed of CISE, Aerospatiale, Ansaldo, CAP Sesa Innova­ tion, F.L.Smidth, Frarnentec and Heriot-Watt University. The authors want to acknowledge here the contribution of all the members of the project team, and in particular of Alberta Bertin of CISE, to the ideas expressed in this paper, while taking full responsibility for the fonn these ideas are expressed. Particular thanks to our colleague Ferruccio Frontini who helped focusing the mathematical formalization of the problem.