No Faults in Structure? How to Diagnose Hidden Interactions

1. Introduction

Look at figure 1. Pitilessly it reveals that kind of sore spot of model based diagnosis systems we want to tackle in this paper: how to cope with structural faults in a model based diagnosis framework. It shows a ballast tank system as needed on off-shore plants or ships to keep the balance. Some of the tanks are built on top of each other. A hole in the bottom/top of such a pair of tanks caused by corrosion results in an additional flow between them and hence in a change of the structure of the system. A conventional con­ sistency-based diagnosis system (GDE, [deKleer, Williams 87]) generates diagnosis candidates based solely on a model of the correct function of the system. From a approach has a very limited scope of applicability. One has to pay for potential faults with increased computational cost in every diagnosis case even if structure faults are known to appear seldom. In contrast HiDe&Seek modifies the system description at runtime and only when it has to consider a structural fault.

* This work was started at the Fraunhofer Institute for Information- and Dataprocessing (FhG/ITTB) in Karlsruhe, Germany. supported by the Bundesminister fiir Forschung und Technologie, joint project PT-FKZ:Ol IW 203 B:8 and finished during a temporary research stay at the UPN, supported by the EU under the contract CHBI.Cf941409 in the context of the human capital and mobility program.

HiDe&Seek is based on the two presuppositions, that unintended interactions lead to apparently unrelated dis­ crepancies and that the law of parsimony is a reasonable diagnosis preference criterion. Structural faults are consid­ ered only, if no single fault can be found. If forced to, those multiple faults which match a structure fault constel­ lation are preferred.

To this end we introduce a representation for patterns of structural faults called hidden interaction models. A hidden interaction model has to serve two tasks. First, it specifies the structural fault constellation to be matched. This former task has two further aspects. On the one hand it specifies a required contextual constellation, e.g. a de­ scription of the physical layout of the components in­ volved. The constellation specification acts as an interface to a constellation recognition module. Usually such kind of information is much easier to get than behavioural models. On the other hand, besides the constellation, the behavioural modes of the respective components have to be matched. E.g. a structural fault "leak between tanks" should be hypothesised only when the behavioural modes corresponding to a material flow/leak are actually consis­ tent with the current observations. As a second task, the hidden interaction model provides basic information for how the system description has to be changed, i.e. a char­ acterisation how the interaction affects the overall system behaviour.

In section 2 we introduce a ballast system as an exam­ ple to be used throughout the paper. The diagnostic frame­ work is sketched in section 3. Section 4 describes the extension of the diagnostic procedure to include the method sketched above and introduces the definition of a hidden interaction model. In section 5 we show how our procedure copes with the application example and fmally, we reconsider the notorious bridge fault [Davis 84].

2. The Example

A ballast system consists of a set of ballast tanks distributed over the plant, connected by pipes with pumps. In order to stabilise the plant, valves are opened and closed to pump sea water in or out of the tanks according to the external requirements (sea motion, changing load). A conventional system consists of up to 40 ballast tanks. We shall restrict ourselves to a minimal configuration which is qwte representative, however. since only a small number of tanks is allowed to be connected by open valves at any time.

The main components included in our simplified pres­ entation comprise ballast tanks, tank vent pipes, valves which can be opened/closed automatically or by hand, pipes, a pump, a filter, pressure sensors. control valve, and the sea tank (see figure 1. for details see [Ruemelin 92]).

The following gives a rough approximation of the be­ haviour of each component. Besides the correct behaviour two fault modes are relevant for each. We shall discuss only the fault mode of a leaking tank, since it gives some insight into the problem to be solved.

The task of a tank is to keep water. For that purpose it is provided with one inlet and a vent pipe. Its behaviour is characterised by the water level. The water level changes according to the flow across the inlet. The vent pipe allows adjusting the pressure of the air in the upper part of the tank. So the static pressure at the tank bottom corresponds to the height of the water contained (see fig­ ure 2).

To represent a leaking tank, an additional flow ileak influencing the water level has to be considered. h' = i/F has to be replaced by h'= (i + ileak)/F. Note, however that the actual law guiding the behaviour, i.e. consistency of flows, has not changed: h' = I.i IF, where I.i denotes the sum of all flow influences on the tank. Only the number of relevant influences changed.!

A pressure sensor reports the static pressure at the bot­ tom of a tank.

tank :height h, height change h' flow i, static pressure p h = p/(pg) h' = p' I (rg) h'= i/ F where F is the tank's bottom surface, pis the density of sea water and g is gravity acceleration

figure 2: tank behaviour description

A pump provides a flow into or out of the system. This flow is caused by producing a pressure drop and opening the control valve accordingly. The pressure values before and behind the pump are reported by two further sensors. Similarly. the behaviour of a pipe is characterised by the flow caused by the pressure drop between its ends. For an ascending pipe the static pressure has to be taken into account additionally (see figure 3).

figure 3: pipe behaviour

A valve establishes a common pressure point between two partial systems or keeps them independent of each other. If it is closed, the flow across a valve is zero (see figure 4). If a tank pressure sensor indicates that the water level is at its maximum, the corresponding valve is closed automatically. The state of a valve is continuously reported to the control system.

3. Diagnostic Framework

We follow a framework similar to those of [deKleer,Williams 89], [Hamscher 88], [Dressler, Struss 92] and [B6ttcher, Dressler 94]. That is we perform consistency based diagnosis based on a computational model of the device, i.a. the system description (SD). The basic idea o~ these approaches is to guide the search for diagnoses by discrepancies found between behaviour predictions based on the system description and the observations of the actual system.

1 Note that the behavioural mode "leaks" covers both a loss and a gain of fluid.

valve

The system description consists of a collection of local behavioural models for each component and descriptions of the connections between the components. [deKleer,Williams 89] and [Struss,Dressler 89] show how to profit from a system description differentiating between the different possible behavioural modes of each compo­ nent. In the context of HiDe&Seek this kind of structuring the system description into component modes and models is cruc:ial. It provides a basis for controlling when to hy­ pothesise a structural fault as we shall see in section 4.

Then a diagnosis is defmed as an assignment n of be­ havioural modes to the components of the system such that it is consistent with the current set of observations (Obs) and the system description.

. For complex systems the system description may con­ tam even more structure. Each component can be de­ scribed at different levels of structural detail and each mode can be described at different levels of abstraction ([Struss 92]). It is profitable to exploit such structure during a diagnosis process in form of model switch operations such as structural decomposition or behaviour­ al refinement ([Hamscher et al. 92]). To control the activation of those parts of the system description relevant in a ~articular sta~e of .the diagnosis process. we adopt a technique as descnbed m [B~ttcher. Dressler 94]. As the other approaches mentioned above. this one views a di­ agnosis as an assignment of behavioural modes to compo­ nents. But additionally it introduces a handle to control the p~al ~ctivation of the system description and, hence, the diagnosis process. This will be the starting point to control the process of hypothesising hidden interactions.

The approach assumes that each piece of model can be addressed in a form such as

modg A mode( component) -7 <model constraint>, where modg is a conjunction of working hypotheses char­ acterising that piece of model and mode(component) corresponds to the assumption that the component is in that particular behavioural mode. Adding the attached working h~otheses to a current set of working hypotheses (w-hyp) activates the related model constraint and allows testing the component mode assumption.

For example consider modelling a tank as used in the ballast system (section 2). If a tank is ok. the quantitative description of the water level h can be inferred from the static pressure p based on the gravity acceleration g and the density of water p:

quantitative-view A ok(tank) -7 h = p/(pg)

By adding the working hypothesis quantitative-view to the current set of working hypotheses, the related pieces of the model are activated and the component mode assumption is tested.

Focusing strategies based on simplifying diagnostic hypotheses (e.g. ..no multiple faults") can be easily

integrated into such a control framework as well. Then a diagnosis under w-hyp is an assignment n of be­

havioural modes to the components of the system such that,

SD uTI u Obs u w-hyp is consistent

In general given a set of observations many mode as­ signments may fulfil this requirement. We assume that for each c?mpone~t eac:h of its. behavioural modes is weighted ~or~g to Its diagnostic relevance (e.g. probability, nsk),l.e. for every component a partial ordering is defmed on the set of all its modes. The mode of the correct function precedes all other. Then only the most plausible or c~t.ical mode assignment~ in this sense satisfying the conditio~ above are of real mterest. Hence. the diagnosis search will focus on the so-called preferred diagnoses.

A mode assignment TI = {mij(Ci)} is preferred over another TI' = {I? ij ' ( Ci) } if. for all components Ci n assigns a mode mij which precedes or is equal to miJ.' assigned by TI'. .

Then a diagnosis is a preferred diagnosis under w­ hyp, if no other diagnosis is strictly preferred over it ([Dressler, Struss 92]).

This. characterisation implies that as long as no dis­ crepancies have been detected, the mode assignment .. all components work correctly" is the most preferred one. Only if a preferred mode assignment has been refuted. i.e. turned out to imply discrepancies, successors are considered. Then the diagnostic process has to identify those mode assignments which deviate as few as possible from the previous one while being consistent with the observations. the system description and the current set of working hypotheses. That is. a preferred diagnosis stating :·com~nent c ~s consistent with modem" actually says "c IS consistent With a modem and we don't know about less preferred ones yet".

The key to control the diagnosis process is the set of working hypotheses. Changing it activates different parts of the system description and results in a different set of diagnoses. A catalogue of partial preferences between sub­ sets of wo~king h~potheses representing general diagnostic and do~am specific control knowledge. is used to guide the chOice of an adequate set of working hypotheses in a given situation ( [Bmtcher, Dressler 94]).

4. Integrating Interaction Detection into the Diagnosis Process

The problem of the diagnosis approach sketched above is that it depends on the system description which may be in~ adequate. Besides specifying how components behave and are co~ected,. the system description states implicitly where mteractions are not allowed. Structural faults violate the closed world assumption inherent in the model.

In order to integrate the consideration of structural faults two issues have to be addressed

• when to consider a violation of the closed world as­ sumption and how to control it,
• how to change the system description to reflect the violation and how to control that.

Our answer is based on the presumption that an interaction hidden with respect to a model results in apparently unre­ lated discrepancies and, hence, in multiple fault candidates. As long as no multiple fault diagnosis has to be generated (according to the known discrepancies and current working hypotheses), the diagnosis process proceeds in the usual way2. If we are forced to consider multiple faults, we should still prefer a single explanation. Therefore, we shall look for an interaction acting as a single cause.

4.1 Hidden Interaction Models

For that purpose we introduce an explicit representation for interaction types: the hidden interaction model. The question is, what has to be included in such a model.

Consider the ballast system example. If working cor­ rectly, the water level of each tank can be changed only by a flow across the inlet (see figure 2 in section 2): h'=i/F. Now the structure of the system is changed by an addi­ tional flow-interaction between two tanks. This means, the behavioural modes of each of the tanks is changed. Each behaves according to an additional influence on the water level. Due to the hidden interaction path these additional influences constrain each other. Finally the character of the hidden interaction is a result of the particular construction of the tanks, i.e. one on top of the other, so as to share a steel plate between them. Considering all this, the flow interaction between the tanks is represented in the following way.

leak-structure-fault(tl,t2) --+ below(tl, t2) A distance(tl, t2, 0.0) A leaks(tl) A leaks(t2) A tl.iteak = -t2.i[eak In general a hidden interaction model is given as hidden-interaction-hypothesis(c 1 ·.. co) --+ constellation(c 1 ·... co) A mode-constellation(c 1 .... cn) A connection(q, .. cn)

The constellation description marks the interface to a module for recognising contextual. behaviour independent constellations such as a facility to represent and reason about geometrical or spatial information. What kind of constellation description is required or from what proper­ ties a constellation specification is made up of depends only on the application domain. The basic hidden interac­ tion procedure described herein is independent of a par­ ticular choice. The only requirement is a facility to answer queries about which interaction types are consistent with a given set of components.

For the ballast system domain we used a special tool "Space-box" which provides a facility to recognise spatial configuration patterns. For the ballast system domain simple qualitative spatial relations such as "on-top-of', and quantitative relations such as "distance" were sufficient (for details see [Schick et al. 94]. [Bottcher. Schick 94]). A more complex application might require additional technical properties such as .,the plate connecting the tanks has to be made of steel", and. hence. a more complex tool. Other applications may come along with simpler languages and reasoning to check a constellation.

2single fault diagnoses which are related to an unintended in­ teraction between a component and an external part are not covered by this scheme. But in principle they could be abstracted into a single faulty behavioural mode.

4.2 Controlling Hidden Interaction Hypotheses

Forced to consider multiple faults. but provided with a set of hidden interaction models representing relevant interac­ tion types, we want to look for diagnoses which can be re­ lated to a single problem source. That is, if a preferred di­ agnosis has been inferred which matches the structure fault pattern of a hidden interaction model. we want to explore the consequences of the respective interaction, i.e. to change the system description so as to represent the influence of the hidden interaction on the overall system behaviour.

Given the structure of a hidden interaction model as in­ troduced above and the framework to control the diagnosis as introduced in section 3. the system description change is realised by activating the related working hypothesis, in this case the related hidden interaction hypothesis. Activating a working hypothesis means adding it to the current set of working hypotheses. The decision when to switch to what set of working hypotheses is guided by a catalogue of partial preferences between subsets of work­ ing hypotheses ([Bottcher, Dressler 94]). This is the place where to state when to hypothesise a hidden interaction.

Before specifying the control preference rule to add, we have to precise, what is meant by a matching structure fault pattern. We introduce a predicate potential-interac­ tion to describe that a particular hidden interaction hy­ pothesis h(q, ... ,cn) is a potential candidate to represent an interaction between suspect components q, .... cn in the context of a mode assignment IT. To be valid, we require on the one hand that the components are arranged corre­ sponding to the constellation description of the hidden in­ teraction type in question. Furthermore, we exploit the fact, that preferred diagnoses indicate which behavioural modes have been refuted already. We require that the behavioural modes assigned to the components by the diagnosis in question are "consistent" with those required by the interaction. Given the definition of preference between mode-assignments and of preferred diagnoses (section 3), "consistent" has to be read as "for each component the mode assigned by the diagnosis has to be more preferred or equal to that mode resulting from the in­ teraction wrt. the partial mode ordering local to that component":

potential-interaction(h,IT,c I .... ,cn) --+

moderr(ci) <=ci modeh-mode-constellation(Ci) where modeM( c) denotes the behavioural mode assigned to component c by (partial) mode-assignment M.

Refering to potential-interactions(IT,q, .... cn) as the set of all hidden interaction hypotheses for which poten­ tial-interaction(h,IT,q, ... ,cn) is valid, we add a control preference rule P

• if 3 I1 E diagnoses(w-hyp): 3 q, ... ,cn: n > 1 A 'If ij E {1, .. ,n}: Ci -:I= Cj
• A ViE {1, .. ,n}: ok(ci) * moderr(ci)
• A 3 h(q, ... ,cn) E potential-interactions(IT,q, ... ,cn) then {h(q, ... ,cn)} >p {}

to the catalogue of partial preferences between subsets of working hypotheses. It states, that whenever in a multiple fault situation a valid potential hidden interaction hypothesis can be found for some of the suspect components, adopting it is preferred over not doing so.

5. Hidden Interaction Detection in Action

5.1 The Ballast System Example

Consider the following scenario (see figure 5). Tank 1 and tank 3 have to be filled. For that purpose valve 2 is closed, valve 1 and valve 3 opened, and the pump is set in state :fill. The valve states are reported accordingly. The bottom of tank 1 is perforated connecting it to tank 2 ·

Given the scenario and the models sketched in section 2 the following sets of component correctness assumptions lead to discrepancies

• { ok(tank), ok(sensor 2 ), ok(a-pipe 2 ), ok(valve,)} Since valve2 is closed, the flow across it should be zero. This flow value should be the same as that across a­ pipe2, and as that out of tank2. But sensor2 reports a pres­ sure change, and hence a flow unequal to zero.
• {ok(tank), ok(sensor), ok(a-pipe), ok(valve), ok(tank 3 ), ok(sensor), ok(a-pipe), ok(valve), ok(main­ pipe)}

This inconsistency is the result of comparing the values of the rate of change reported by sensor 1 and sensor 3 · Since valve 1 is open, each of these values can be used to calculate the pressure below valver The respective cal­ culations are based on the closed world assumption that the rate of change reported by a tank sensor is directly related to the flow out of the tank. But in the case of tank 1 this is not valid, since it loses water on another way. As a result different, contradictory values are calculated for the pressure below valve 1 ·

• {ok(tank), ok(sensor), ok(a-pipe), ok(valve), ok(pump), ok(control-valve), ok(main-pipe)} Supposing that the rate of change reported by the pres­ sure sensor at the pump corresponds to the flow across the main pipe, the pressure value below valve 1 can be calculated on a third way. Again this value is contradict­ ing that one calculated on the base of sensor 1 ·

So the hypothesis that everything is ok, has been refuted. Hence other combinations of behavioural mode assignments have to be tested, the conflicting sets indicating which correctness assumptions have to be changed. The conflicting assumption sets above implicate at least a dou­ ble fault of one of 16 component pairs or even a triple fault, where for each component two fault modes are rele­ vant (see [B6ttcher, Schick 94] for a more detailed discus­ sion). Even if the partial order of preferred diagnoses is considered, the remaining search space is huge.

One of the resulting preferred diagnoses is {leaks(tank), leaks(tank,)}. According to the constellation recognition this is the only double fault which could be caused by an additional interaction, since the components tank 1 and tank, satisfy the condition of being on top of each other, and because the behavioural modes assigned to them are equal, hence consistent with the . "Leaks "mode required by a hidden flow interaction. Therefore, the hid­ den interaction hypothesis leak-structure-fault(tank 1 , tank 2 ) is added to the set of current working hypotheses which in turn enforces the corresponding behavioural modes and activates the connection tankrileak = · tankrileak.

As a consequence a preferred diagnosis such as {leaks(tank), clogged(pipe)} is refuted, since it assigns the mode "leaks" only to tank 2 , but the mode "ok" to tankr Activating an interaction hypothesis results in changing the system structure. A connection between the tanks re­ quires, that a leak flow observed at tank, has to be ob­ served at tank 1 as well.

Note, that as long as the new working hypothesis is not added to the current set of working hypotheses, the exten­ sion of the system description does not affect the simula­ tion.

5.2 The notorious Bridge Fault

[Davis 84] revealed the problem of dealing with structural faults by introducing the classic bridge fault example. A bridge fault is an unintended connection between lines on a circuit board caused by solder splashes. As a result the behaviour of an input port is changed into one of an output port.

To illustrate the similarities and differences, we exam­ ine the bridge fault example as described in [Davis 84] in detail. A bridge may occur where two components are connected to adjacent pins. The system description con­ sists of gates (slices) and lines. It is structured according to the functional entities. Hence, pins are not modelled ex­ plicitly. The behaviour of two connected lines is dependent on the TIL technology. It corresponds to a connection by an and-gate (see figure 6).

To represent a bridge between lines as a hidden inter­ action model, suppose that the physical layout of the given circuit is represented in a constellation reasoning system. Then the adjacency of pins can be directly verified via their distance, e.g. pin-neighbour(p ,p) ::= distance(p ,p) d l 2 l 2 <= min.

bridge-fault(line 1 , line2) ~ 3 P 1 · P2:

internal-pin (p 1 ,Line) A internal-pin (p 1 ,line)

• A pin-neighbour(p 1 ,p 1 )
• A bridge-modes(line 1 ,line 2 )
• A (line rout= line,.out = logical-and(linerin.line 2 .in)).

Davis proposed a procedure to cope with bridge faults which starts with the assumption that the structure of the system is correct. If no single component fault can explain the observed behaviour, the assumption is relaxed and the procedure falls back on some special mechanism. The mechanism hypothesises structural modifications between components, if a particular pattern of values of the variables describing the components, has been derived and if they are neighboured in a particular way. The behaviour patterns required are specific for bridge faults and for the TIL technology.

The difference between the approach introduced by Davis and our lies in the notion of a diagnosis. In the for­ mer framework a diagnosis is viewed as a single compo­ nent supposed to be not ok. On the one hand this implies that the single fault assumption is built into it. More im­ portant, however. is the fact, that it ignores the notion of behavioural modes. The knowledge about the behaviour of bridged components can be exploited in a "compiled" form only. That is, it is used beforehand to derive a particular pattern of variable values. So the pattern can be viewed as a result of changing the behavioural modes of the compo­ nents in question and connecting them.

Common to both his and our approach is the presump­ tion that a bridge leads to a multiple fault candidate and the insight to enhance the search for structure fault candi­ dates by referring to the knowledge about adjacency be­ tween components.

6. Conclusions

We presented HiDe&Seek, . a method to hypothesise hidden interactions based on an analysis of the context of components. We defmed a hidden interaction model repre­ sentation scheme which links a required contextual con­ stellation to the description of the impact of an interaction on the overall system behaviour. We showed how to inte­ grate the search for hidden interaction hypotheses into a diagnosis process control framework thereby exploiting the information about behavioural modes of components contained in candidate diagnoses to guide the search.

A straightforward solution to cope with structural faults would be to incorporate all potential pathways of interaction explicitly into the model. [Preist, Welham 90] shows that for applications where these kinds of faults are the actual problem and not the exception such a procedure is feasible but time consuming, hence, of limited scope of applicability. Similar to [Preist,Welham 90] we build our procedure on basis of an explicit representation of an "interaction". Our approach, however. dynamically activates additional interactions as needed.

Davis' approach is tailored to the diagnosis of TIL-cir­ cuits and hard to adapt to other domains ([Davis 84]. section 5.2). But in some way our approach can be viewed as an extension of it. Analogous to that approach we based our procedure on the integration of contextual knowledge to hypothesise structure modifications. Additionally we exploit the structure of a diagnosis as a behavioural mode assignment.

Our procedure is based on the assumption that unin­ tended interactions lead to discrepancies in unrelated ar­ eas. It seems that this assumption is useful to treat struc­ tural faults resulting from unintended interactions between system components in some domains. It is, however. not obvious for what kind of applications this assumption is satisfied. Characterising the difference between a multiple fault hiding an interaction between system components and one hiding a interaction with some external part, or a fault (single or multiple) hiding an interaction with an ex­ ternal part from an ordinary fault still needs to be done. So future work will comprise characterising classes and prop­ erties of structural faults in different domains.

The procedure has been implemented in Allegro Common Lisp on a SUN Spare workstation and tested on the ballast system example.

Acknowledgements

Thanks to Philippe Dague. Oskar Dressler, Francois Levy, Karsten Poeck, Peter Struss and the anonymous referees for commenting on earlier versions of this paper. and last but no least to Matthias Schick who provided the Space Box as the basis of this work.