Diagnosis as a Variable Assignment Problem: A Case Study in a Space Robot Fault Diagnosis

1 Introduction

In many real-word applications, diagnostic reasoning is often embedded in a larger task which may involve mon­ itoring, gathering of additional information for hypothe­ sis discrimination, reconfiguration, repair, etc .. . In such a complex situation, the diagnostic component has to summarize the results of the diagnostic reasoning in such a way that the intelligent agent (either human or arti­ ficial) who has to use the diagnostic results is able to perform the task. Unfortunately, for most artifacts the number of possible diagnoses is quite large. In the model­ based diagnosis community there is long tradition to use some preference criterion for representing the set of pos­ sible diagnoses: the notion of minimal diagnosis [Reiter, 1987] has been often used, but its drawbacks are well

Pietro Torasso

Dipartimento di Informatica Universita' di Torino Torino (ITALY)

e-mail: torasso@di. unito.it

known when the domain theory includes also models of the faulty behavior. The characterization of diagnoses in terms of partial and kernel diagnosis [de Kleer et al., 1992] is useful, but it does not guarantee at all that the number of diagnoses is small.

In model-based diagnosis a number of approaches based on information theory have been proposed for suggest­ ing additional measurements, in order to discriminate between competing diagnostic hypotheses and to reduce the number of diagnoses. However , it is not always pos­ sible to get additional measurements and therefore, in such cases, other techniques have to be developed for representing diagnoses in a more compact way. In sev­ eral domains fault localization is not sufficient for solving the diagnostic task: fault identification is needed because of different repair actions and/or criticality of the fault . In modeling such domains, the behavior of the diagnosed system is represented in term of behavioral modes and the space of possible solutions is usually quite large. The introduction of a preference criterion among diagnoses is not only useful for representing in a compact way the set of solutions, but it should also guide the search process of diagnoses generation, in such a way that preferred di­ agnoses are generated before non-preferred ones (see, for example, [de Kleer , 1991] for a probabilistic approach). This is a very important requirement in complex do­ mains where the computation of diagnoses is time (or space) consuming and therefore the computation is time (or space) bounded.

The present paper aims at solving some of the prob­ lems mentioned above by introducing a characterization of diagnostic problem solving (in particular abductive diagnosis) as a type of Variable Assignment Problem (VAP). In section 2, we introduce the notion of VAP as a problem in which some variables have to be assigned, depending on the constraints induced by some other en­ tities, called findings, through a set of rules. Several kinds of problem solving tasks can be viewed as specific instances of a VAP including planning, diagnosis, clas­ sification, learning of operational concepts, etc .. . In the present paper, we will concentrate on the view of diag­ nostic problem solving as a VAP: in section 3 we discuss some general issues arising on VAPs, in particular the compact representation of set of solutions (sect. 3.1) , the use of information theoretic criteria for preference among solutions (sect. 3.2) and the use of heuristic search for solving YAPs (sect. 3.3). In section 4 we will introduce a real-world diagnostic problem, related to the identifi­ cation of faults in a space robot arm [Mugnuolo et al., 1998] and we will show how mapping such a problem to a YAP can allows us to define diagnostic strategies able to provide the user with a powerful tool for detecting and identifying faults in such a complex system.

2 Variable Assignment Problems

A Variable Assignment Problem or YAP is characterized by a set of variables having a finite set of admissible val­ ues, and a set of observable parameters (that we will call findings) that may constraint the variable values through a suitable set of rules representing the domain theory.

Definition 2.1 A Variable Assignment Problem (VAP) is a triple (V, F, DT) where:

• V = { x 1, x2, ... Xn} is a set of variables taking val­ ues from a predefined set of mutually exclusive val­ ues Dx, (for i = 1 ... n) called the domain of x;;
• F = {h, h, .. . fm} is a set of findings represented as atomic propositions;
• DT = { R1, R2, ... Rk} is a set of rules relating variables and findings and called the domain theory

In the following, given a variable x;, we will indicate as Xi a particular instance of the variable (i.e. an assignment to x; from Dx.). It should be clear that, since values in Dx, are mutually exclusive, x~ 1\ x~ f- l. for (k #h). Moreover, in the present work we will discuss the case where DT is a Horn theory.

A diagnostic problem can be characterized in terms of YAP as follows : each variable corresponds to a compo­ nent of the system to be diagnosed, with each value rep­ resenting a behavioral mode of the component [de Kleer and Williams, 1989]; each finding corresponds to an ob­ servation, i.e. to an observable parameter of the system; the theory represents the model of the system (usually a behavioral model relating behavioral modes of com­ ponents to observable manifestations). In this paper, for the sake of simplicity, we will ignore the influence of input observations in determining the output observa­ tions and we will restrict our attention to two-layers di­ agnostic problems [Peng and Reggia, 1991], where faults (and possibly normal behavior) are directly related to observations 1 .

1 The whole framework can be generalized to more com­ plex models with arbitrary long chains of rules between be­ havioral modes of the components (and input parameters) and observations. In such models, variables not correspond­ ing to components but to internal states (endogenous vari­ ables) are present . Also these variables have finite domains and the domain theory DT contains rules relating input pa­ rameters and components with internal variables as well as rules relating internal variables to findings. Input parameters can be viewed as variables whose assignment is already given as an external constraint .

Solving a YAP means to determine the possible assign­ ments to the variables that "satisfy" the rules concerning the observed findings. This may mean different things: it may be sufficient to require the logical consistency of an assignment with respect to observed findings or it may be the case that a covering of the findings is required. From the diagnosis point of view this corresponds to the classical distinction between consistency-.based diagnosis and abductive diagnosis. In the following we will consider the stronger choice of coverability 2 ·

Definition 2.2 A solution to a VAP (V, F, DT) zs a vector X = (x1 , x2 , ... Xn) such that DT U X f- F .

3 Solving VAPs

3.1 Basic Issues

Given a YAP as defined in def. 2.1, each finding/; con­ strains the values of a subset of the variables; this means that given /; the set of possible variable assignments is restricted by the rules in DT related to /;.

Example 1. Let ({xl,x2},{h , /2} ,DT) be a YAP defined on two ternary variables having values x{, z = 1, 2; j = 1, 2, 3 and with the following theory:

xl -+ h; xf -+ h ; x~ -+ h; x~ -+ h Solving this YAP produces the following variable assign­ ments:

For problem solving efficiency, it may not be reasonable to "expand" all the possible assignments generated by a given finding. By considering one finding at the time, we can notice that each J; constraints only Xi via the disjunction xl V x~, so a more compact representation for the above variable assignments can be the conjunction of disjunctions (xi V xf) 1\ (x~ V x~)

In general, we can represent the set of assignments generated by each finding by means of a set of scenarios, each being a particular kind of conjunctive normal form (CNF) formula.

Definition 3.1 Given a VAP ({x1, .. . xn} , F, DT) , a scenario is a CNF formula of the type

where each conjunct is a disjunction of (at most Dx,) instances of the same variable x; .

In particular, in the case of diagnosis, if the space of el­ ementary variable assignments is very large, a scenario can represent in a compact way multiple assignments with two potential benefits: 1) easier analysis of diag­ noses for a human or artificial agent, since they are fac­ tored; moreover, remaining sources of indeterminacy re­ quiring further discrimination are pointed out, for each component within each scenario; 2) reduction in the size of the search space. In fact, each finding imposes a con­ straint on a subset of the variables, represented as a set of k admissible tuples for such a subset and this may be summarized in at most k scenarios. On the other hand, the adoption of scenarios does not guarantee that search will produce solutions that are elementary assignments, even if they can be easily generated from final scenarios. Therefore, a good reason for adopting scenarios is their ability of trading-off search effort with respect to speci­ ficity of assignments. In complex domains, the adoption of scenarios may reduce the· search space, but it may still be large (as well as the final set of scenarios) : the introduction of a measure of preference among scenarios can then help to focus their generation to most preferred ones.

2 This choice is justified when the model is reasonably com­ plete (see [Console and Torasso, 1991]): as we shall see in section 4, in our case study the behavioral modes as well as their relation to observations are known.

Example 2. Suppose that the VAP of example 1 is modified by adding to DT the following rules:

xi 1\ x~ ·--* h ; xi 1\ x~ --* h

We have now five variable assignments solving the problem that may be compacted into two scenarios, one very general (x~ V x;) 1\ (x~ V x~) and one very specific xi 1\ x~ ; the problem is how to compare them.

The mechanism we propose to approach this problem is based on the Minimum Description Length principle (MDL) [Rissanen, 1983] adapted to the particular prob­ lem we are tackling. Next section discusses this topic , while sect. 3.3 addresses the problem of using such a preference information during search.

3.2 Comparing Scenarios

The MDL is a principle of parsimony often used in ma­ chine learning or in probabilistic reasoning; the main idea is that hypotheses that may be described more con­ cisely should be preferred over other competing hypothe­ ses. The MDL principle is basically motivated by the fact that, using concepts from information theory, most prob­ able hypotheses have shortest descriptions (see [Mitchell , 1997] for a detailed discussion). In particular, given a hy­ pothesis h having probability p(h), the optimal encoding for h assigns - log2 (p( h)) bits to the hypothesis descrip­ tion. Notice that in our case, the direct encoding of a compound hypothesis represented by a given scenario is not really appropriate; indeed, if a scenario represents the compound hypothesis h1 V h2 , the coding length had to be proportional to - log2 (p( h 1)) -log2 (p( h2)) which is strictly greater than the coding length of the compound hypothesis given by -log2(p(h1 V h2)) . In fact , from the information theoretic point of view we want to pro­ vide the receiver with the information that there is some indeterminacy in deciding which is the right hypothesis for the variable, so we have to transmit two separate messages: one for describing h1 and another message for describing h2.

To apply a comparing principle based on MDL in our case, we first need to introduce some notational facilities. Given a VAP ({x1, ... Xn}, {!1, ... /m} , DT) we associate with each variable x; a bitmap B; of length l; = IDx, I such that B;(k] = 1 if the variable x; may be assigned the kth value and B;[k) = 0 otherwise. We then define B = B1 · B2 · .. . Bn to be a bitmap associated with the whole set of variables, · being the concatenation operator.

It should be clear that every scenario generated by the findings can be encoded as a bitmap B defined as above. Of course, a scenario is inconsistent if there exist a B; in B such that 'v'kB;[k] = 0. A bitmap B is said to be elementary if it represents an elementary variable as­ signment (i.e. an assignment of exactly one value to each variable x;), thus if and only if'v'i = l..n 3! k : B;[k] = 1. Every generic bitmap B represents one or more elemen­ tary bitmap B 1 , B 2 , ..· B' such that B = B 1 IB 2 1 . .. B' being I the "bitwise or" operator.

In the following , we make the assumption that variables may be assigned independently to each other 3 . Under this assumption, given an elementary bitmap Bi we de­ fine its coding length (or equivalently the coding length of the corresponding variable assignment) as:

The above definition requires the specification of some probability priors on single variable assignments; in case no specific information is available on such assignments we can assume a uniform prior for each variable.

Given a generic bitmap B and its elementary bitmaps B 1 , B2, ... B', the coding length of B (or equivalently of the corresponding scenario) is then defined as

In particular, we will be interested in considering dif­ ferent preference criteria among scenarios represented as bitmaps, defined by considering a suitable transform r(B) of the bitmap Band by computing f(r(B)). The choice of r and equation 1 allow us to trade-off the like­ lyhood of a given scenario and its specificity /generality with respect to specific requirements concerning the cur­ rent task and application. In general, the coding length of each elementary scenario weights the probability of the corresponding assignment, while the sum over the elementary assignments of the scenario gives a penalty to less specific and then less informative ones. The r transform allows one to tune the amount of penalty for less informative scenarios, by taking into account the expected use of such scenarios. In particular, for YAPs representing diagnostic problems, we identified the fol­ lowing basic transforms:

3 In diagnostic terms this corresponds to the usual assump­ tion of prior independence among faults.

where f!; is the empty bitmap if B; has all bits set to 1 and B; = B; otherwise; B; is the bitmap having all zeros, but in the most probable position if B; is a bitmap having all ones and B; = B; otherwise; B; is the bitmap obtained from B; by resetting to zero all but the most probable position.

Scenarios having smaller coding length are then pre­ ferred over those having larger coding length. The choice of the proper transform essentially depends on the use of the scenarios representing final solutions. Let us con­ sider a diagnostic setting: in some cases , more specific diagnoses may be more conveniently used because they imply less discrimination effort (i.e. less tests), so Tl may be the most suitable choice; in some other cases the operator using the diagnostic system may be biased to­ wards preferring some particular assignments contained in a final scenario. For example the operator can ignore components for which no restriction on possible behav­ ioral mode has been provided by the observations ana­ lyzed so far . This is the basis of the notion of partial and kernel diagnoses [de Kleer et al., 1992]. Transform T2 assures that a component for which all behavioral modes are still possible do not contribute to the eval­ uation of the r function. Therefore it guarantees that the equivalent (in our framework) of a kernel diagnosis is preferred to a partial (or total) diagnosis generated by the kernel one. Also T3 treats in a different way components for which no information is provided (all the behavioral modes are possible): in such a case, T3 weights the component as it would be assigned the most probable (usually the normal) behavioral mode. It guar­ antees that the equivalent in our framework of a kernel diagnosis has a coding length r not larger of the one of a partial (or total) diagnosis generated by the kernel one. In transform T4 the contribution of each compo­ nent to the evaluation of r is given by the most prob­ able behavioral mode still admissible: this is equivalent to select the most probable diagnosis among all the ele­ mentary diagnoses represented by a final scenario. This preference criterion has usually the effect of preferring the diagnoses with minimum cardinality of faults4.

A further advantage of the proposed coding length is that it can be computed without determining all the ele­ mentary assignments of a given scenario. Given a bitmap B let as before B; be the sub-bitmaps relative to the single variables x; : let us define a; to be a coefficient associated with B; and representing the number of 1s in B;. The following property is trivially verified .

It is worth noting that the evaluation of the r function is not expensive since the number of operations involved in the evaluation is O(n2), where n is the number of compo­ nents (or the number of variables in the VAP problem).

4 This follows from the fact that normal behavioral mode has usually much higher probability than faulty modes.

In the next section we will show how the coding length of a scenario can be exploited to guide the search for the solutions of a given VAP.

3.3 Heuristic Search

One obvious way for addressing the problem of solving a VAP is to search in the space of all the scenarios gen­ erated by the findings . The assumption we made in this work is that findings are processed in a pipeline fashion following a specified order h , h , . .. f m . This assum p­ tion is made for two main reasons : first it simplify the description of the search strategies without loosing gen­ erality (the approach can be generalized if this assump­ tion is relaxed) , second in many applications this corre­ sponds to a real constraint on the problem (thus findings are only available in such a way or it is necessary to pro­ cess them in such a way as in many real-time diagnostic applications) .

Given a scenario S, the current finding fi to be con­ sidered plays the role of a state-space operator in state­ space search: it generates all the scenarios constraining the current one with respect to the rules related to fi . The initial st~e can then be defined as the trivial sce­ nario /\7=1 (Vj;.i xi) corresponding to a bitmap having all bits set to 1.

Example 3. Let us consider a VAP slightly more complex that the one of example 2 in section 3.1: ({x1, x2 , xa}, {!1, /2, fa}, DT) involving three ternary variables having values x{, i = 1, 2, 3; j = 1, 2, 3 and with the following theory:

xi -T h ; xf -T h ; xt 1\ x~ -T h x~ -T h ; x~ -T h; xi 1\ x~ -T h x; -T fa; x2 1\ x3 -T fa x~ 1\ x; -T fa

The search process starts from the (trivial) initial sce­ nario, So : (xi V xf V xi) 1\ (x~ V x~ V x~) 1\ (x~ V x~ V x;} where all the assignments are possible since no finding has been taken into consideration.

By processing the first finding h we obtain two suc­ cessors of Sa : 51 : (xiVxf)/\(x~Vx~Vx~)/\(x~ Vx~vx;) and S2 : xi 1\ x~ 1\ ( x~ V x~ V xD. In both scenarios variable xa is unconstrained since there is no relation in theory DT between xa and h . The search process now consider h and starting from 51, only one scenario accounts for both hand /2, i.e. Sa: (xi Vxf}/\(x~Vx~)/\(x~Vx~vx;). In fact, the explanation of h in terms of xi 1\ x~ is in­ consistent with the constraints put on x1 in scenario 51. If we process finding h by taking into consideration sce­ nario S2 , we get just one successor: the scenario 52 it­ self. It is worth noting that the explanation of h in terms of (x~ V x~) is inconsistent with the constraints put by scenario S2 on x2. The final step concerns the explanation of fa ; starting from Sa we got two solu­ tions to VAP represented by scenarios 54 and 55 where S4: (xiVxf}/\(x~Vx~)/\x~ and Ss : (xiVxf}/\x~/\(x~Vx~) . Starting from 52 we get a single solution represented by the scenario Ss : xi 1\ x~ 1\ x~. In conclusion we have three different solutions (i.e. scenarios 54, Ss and Ss) to the VAP; together the three scenarios represents 9 different elementary assignments. Each scenario mentioned before can be represented by the corresponding bitmap; for instance B(So) = (111 · 111 · 111) since each of the three ternary variables can assume any value; B(St) = (110 ·111·111) since there is some constraints on variable X1, whereas the solution S4 is represented by the bitmap B(S4 ) = (110 · 110 · 100) where all the variables have to satisfy some constraints put by II, f2 and fa.

We can notice that, because we process one finding at the time, there is a one-to-one correspondence between a finding and a search graph. level , being the jth finding /j be processed at level j (assuming the initial node at level 0).

Since the coding length function r defined in sec­ tion 3.2 allows for a ranking of the solutions, the most natural way of searching through the space of possible scenarios is to define a heuristic search strategy guided by the principle of getting solutions with minimal coding length. In particular , it is possible to devise an admissi­ ble search strategy based on a Best-First Search (BFS). We can define as evaluation function for a generated sce­ narioS (with bitmap B(S)) at search level j the function

where min(B(S), j) is the minimal coding length bitmap that may be obtained from B(S) by processing findings from /i+1 to fm. This function is easily computed by considering the set of variables influenced by each finding k

Example 4. Consider a problem with 4 binary vari­ ables x1, ... x4 , 3 findings processed in the order II , /2, fa and r corresponding to Tl transform. Let the assign­ ments of each variable be equiprobable, but those for x2 , where p(x~) < p(x~).

Let us assume that the scenario produced after the processing of II is

sl : xf 1\ (x~ v x~) 1\ X~ 1\ (x~ v xD

with findings 12, fa still to be processed and influencing only x2 and x3 respectively; the best (minimal coding length) scenario that may be· generated from sl at level 1 is then:

Sbe·t : xf 1\ x~ 1\ x~ 1\ (x~ V xD since x4 will not be changed by /2 , fa and x2 will be set to x~ at the best . Considering a bitmap of length 8 where the ith pair of bits corresponds to xi and xi respectively, then B(St) = (10 ·1le 01·11) and B(Sbe·t) = (10 · 01· 01· 11) , so h(B(St)) = f(B(Sbe·t)) .

BFS using h is admissible, since the evaluation func­ tion h never over-estimates the actual minimal coding length scenario that may be generated from a given search node. If we force the diagnostic system to find not only the single best solution, but several solutions through backtracking, we are guaranteed that the di­ agnostic system produces solutions (in terms of scenar­ ios) in order of preference (according to the chosen crite­ rion). Since h is optimistic in foreseeing the discrimina­ tion power of the findings not yet examined, it is common that the coding length of final scenarios (i .e. the solu­ tions) is larger than the one foreseen by expanding inter­ mediate scenarios by using h. This means that in some cases h is not as informative as we would like and con­ sequently the search space explored by h could be large. In order to check the actual applicability of BFS to real­ word diagnostic problems , we have performed some tests on a reduced general experimental framework, where general VAPs have been randomly generated and solved by BFS. We have then implemented a random VAP gen­ erator, able to produce test sets of problems by setting the following parameters: the number and the cardinal­ ity of the variables, the probability distribution on the variable values, the number and the order of examination of findings, the maximum number of scenarios (MAXS) generated by each finding and some random seeds for having different random scenario generations for each finding. Using this VAP generator we have produced five batches of 20 test problems each (for a total of 100 test problems), characterized by 10 variables having car­ dinality varying from a minimum of 2 to a maximum of 4 values and with a probability distribution over such val­ ues ranging from uniforms to very extreme. Each batch was characterized by parameter MAXS varying from 10 to 15 and by a fixed number of findings that in the 5 batches, has been varied from 10 to 20 . Average results for each batch are reported on table 1. For each batch we report: the number of findings (NF), the average expan­ sion factor (EF) representing the percentage of the whole search space (in terms of expanded nodes) that has been visited to find the optimum, the average solution factor (SF) representing the percentage of solutions that BFS has been able to find within a time-out of 30 seconds on CPU time, the percentage of time-outs (TO) occurred in the batch and the percentage of cases in the batch for which no solution has been provided within the time- out (NS). The last row reports on the global average. As we can see in more than 20% of the cases BFS is not able to produce a solution within the time-out and in more than 40% of cases it cannot produce all the solutions. Moreover, we also experimented that as the complexity of the problem increases (essentially in terms of NF and MAXS), BFS is likely to run out of memory without giving any answer. For these reasons, we consider BFS suitable just for relatively simple domains and we focus our attention on alternative strategies based on Greedy Search (GS) with backtracking, where the scenario to be expanded is locally chosen among those generated at the previous step. By resorting to GS we have two general alternatives: still using h but in a local way, or directly using the coding length of a scenario as evaluation func­ tion. Because of the lack of space, we cannot describe in detail the experiments with GS using the random VAP generator. However, it is worth noting that the analysis with the VAP generator showed more benefits in directly using the coding length r as evaluation function. In the next section, we report on experimental results on the performance of GS on a real-world diagnostic problem.

4 The SPIDER Case Study

In this section we report on a recent work done inside the project SISRAS (Italian acronym for "An Intelli­ gent System for Supervising Autonomous Spatial Robot­ s") sponsored by ASI (the Italian Space Agency) aimed at demonstrating the feasibility of interactive autonomy for controlling and supervising a complex system in the space. The test-bed of the project is the space robot arm SPIDER fSpace Inspection Device for Extra~ehic­ ular Repairs) Mugnuolo et al., 1998] . SPIDER IS a 7 degrees offreedom (i .e. a 7 joints) space robot arm deve~­ oped inside the JERICO (Joint European Robot In-orbit Calibration and Operations) project. In the multi-agent architecture devoted to supervising SPIDER, one diag­ nostic agent is responsible to identify failures and mal­ functions during SPIDER activity, by analyzing symp­ toms obtained via monitoring of the arm and to provide the human operator with a concise and comprehensible description of the possible faults.

We have devised a behavioral model for SPIDER char­ acterized by 33 components with an average number of 5 behavioral modes each (ranging from a minimum of 2 to a maximum of 9) and 45 observable parameters (among which 16 not equipped with a sensor for direct observation) by taking into consideration the FMECA documents developed during the design and test of the SPIDER arm. Such documents list all the faults for each component and provides a short characterization of each fault in terms of observables. In this way the model we have developed is complete in terms of faults and is reasonably complete in terms of relations between be­ havioral modes and observations. Since several faults share the same set of symptoms with no possibility of discrimination through monitoring parameters, a very large number of diagnoses may be produced, even when all observable parameters are available and actually ob­ served. We have then approached this problem by con­ sidering the diagnostic problem as a VAP; this allowed us to take into account all the considerations we made in previous sections and in particular:

• the processing of observations in the order provided by the monitoring unit;
• an abductive characterization of the diagnostic pro­ cess, because of the possibility of obtaining a ( al­ most) complete model of both the normal and ab­ normal behavior of the arm;
• the compact representation of a set of elementary diagnoses through the notion of scenario;
• the definition of diagnostic strategies viewed as heuristic search in the space of possible scenarios;
• the definition of preference criteria for diagnoses obtained as final scenarios at the end of the process.

Actually the diagnostic system we have developed is more complex than the characterization of diagnosis we have described in previous paragraphs: in particular , the system has to deal with input parameters representing the predicted status of the arm joints (e.g. whether the current command executed by the robot control involves a movement of the joint). -As mentioned before, input parameters are dealt with as external constraints on the possible behavioral modes of components; a more de­ tailed description of the modeling issues involved in di­ agnosing SPIDER (including the exploitation of the de­ pendencies among findings) is reported in [Portinale et al., 1999].

As pointed out in section 3.3, we adopted a GS ap­ proach guided by the coding length function defined in section 3.2, also used to address the problem of prefer­ ence among diagnoses. We have implemented a simula­ tor on the behavioral model of SPIDER able to gener­ ate diagnostic cases by injecting faults in the model. In the present paper we report on some of the experiments performed so far: if particular we considered two test sets of 100 cases each, by injecting one and two faults respectively. Each test set has then been tested by run­ ning a GS algorithm guided by r under Tl, T2 and T3 transform. The average number of observations to be ex­ plained in each case was about 19 and a time-out of a 1 minute CPU time has been set. Table 2 summarizes the results in terms of number of injected faults (IF) , average expansion factor (EF), number of times where optimum is the first solution (01), number of times where opti­ mum is in the first 4 solutions (04) , average distance of the coding length of first solution with respect to the optimum (DO) normalized in [0, 1] with respect to the maximum value, number of time-outs (TO). First two lines of table 2 refer to transform Tl , next two lines to transform T2 , while the last two to transform T3. As we can see, more complex problems (i.e. those involving two faults) are more likely to be timed-out under the time constraint we set up 5 ; however, the performance of the algorithm appears to be very good, both in quanti­ tative (e.g. EF) and in qualitative terms ( e.g. 01, 04 and DO). In particular, it is worth noting that very often GS is able to get the optimum as a first solution (or at least in the first 4); moreover even when the optimum is not obtained as a first solution, the quality of such a first solution is very high as suggested by reported val­ ues on DO. This is particularly true for both transform T2 and T3 (with T3 being slightly better). The use of a greedy strategy guided by r seems then to be a very effective approach for domains, like SPIDER, where the complexity of the model and the large number of possible solutions have to be properly addressed.

5 Notice that the time-out refers to the algorithm searching

5 Discussion

In the present paper, we have discussed an approach to diagnosis based on viewing a diagnostic problem as a variable assignment problem, where variables (i.e. system components) are indirectly constrained through other observable entities (i.e. system observations). In particular, we addressed the problem of searching for solutions (i.e. diagnoses) in a large solution space, by proposing heuristic search in the space of scenarios (i.e. CNF formulae representing multiple elementary diag­ noses) . Such a characterization seems to be quite promis­ ing in domains where observable parameters do not allow in general a. precise discrimination between diagnostic hypotheses (so, we have a large number of competing diagnoses) and it is not possible to get additional mea­ surements. These characteristics are present in the SPI­ DER domain, but are not exclusive of such a domain: several other real-world applications can have the same problems. Experimental results show that even the use of non-admissible search algorithms based on a greedy strategy can provide interesting results, especially con­ cerning the production of the best scenario with respect to the given preference criterion.

Characterization of diagnosis as variable assignment has some similarities with work on diagnosis as con­ straint propa&ation as di~cuss:d in [ElFattah and Dechter, 1995j. The mam ·differences concern the fact that we are focusing on abductive diagnosis on causal/behavioral models rather than on consistency­ based diagnosis on structural/behavioral models; more­ over, modeling the type of diagnostic problems we dis­ cussed here with the dual graph technique proposed in [ElFattah and Dechter, 1995] is likely to produce com­ plex cycles in the graph , making the problem computa­ tionally hard in general.

Strategies based on heuristic search (in particu­ lar BFS) have also been proposed both in logical (consistency-based) [de Kleer , 1991] and in probabilis­ tic characterizations [Biswas et al., 1997; Peng and Reg­ gia, 1991]; in both cases (even when more sophisticated bayesian methods are applied), search is performed on the space of elementary assignments of behavioral modes to components, potentially producing an explosion of the number of possibilities to be examined; our approach aims at avoiding this by means of scenarios.

for all the solutions; in the examples we tested the algorithm is always able to find at least one solution within the time­ out .

Acknowledgments

The research described in this paper has been funded by ASI under grant n. 155/97. Partners in the project are IP-CNR, IRST-ITC, Universities of Genova, Palermo, Parma, Roma and Torino. We thank Gianluca Correndo for his valuable work in developing the prototype of the diagnostic system.