A Framework for Decentralized Qualitative Model-Based Diagnosis

1 Introduction

Developing diagnostic software for complex systems is a challenging task especially when a system is composed of many subsystems coming from different suppliers (a very common situation in industry). Decomposition has been recognized as an important leverage to manage architectural complexity of the systems to be diagnosed. Most of the approaches, however, focus on hierarchical decomposition [Genesereth, 1984; Mozetic, 1991], while decentralization has been explored less frequently (see e.g. [Pencol´e and Cordier, 2005]). On the other hand, new problems have to be faced when independently manufactured subsystems are assembled. Each subsystem may come with its own (possibly embedded) diagnostic software whose details should not be disclosed to the customers. A diagnostic software for a complex system has thus to take into account all its subsystems and their diagnosers. The structure of the system and the paths of interaction of the subsystems may be defined statically, or they may change dynamically, e.g. due to redundant design, and for software systems like Web Services.

In this paper we propose a decentralized supervised approach to diagnosis. We assume that a system is formed by subsystems each one having its Local Diagnoser, while a Supervisor is associated with the overall system, with the aim of coordinating Local Diagnosers and producing global diagnoses. The approach computes a set of partial diagnoses [de Kleer et al., 1992] that represents all the consistency-based diagnoses; it is designed to avoid commitment on parts of the model that are unnecessary to explain the observations. In this way local diagnosers are not queried on global hypotheses where their contribution is irrelevant.

∗This work has been partially supported by EU (Ws-Diamond Project, IST-516933) and by MIUR-PRIN (Quadrantis Project).

The paper is organized as follows: in the next section we describe the decentralized architecture we propose. Section 3 introduces the type of models used for diagnosis and a running example. Then, we discuss how the decentralized diagnostic process is carried out in our approach (Section 4) and analyze its complexity (Section 5). We finally conclude with a discussion on related work.

2 Architecture

We propose a supervised diagnostic architecture where:

• A Local Diagnoser is associated with each subsystem. The model of the subsystem is private.
• A Supervisor of the diagnostic process is associated with the system. It coordinates the work of the diagnosers optimizing their invocations during a diagnostic session.

In the definition we consider the general case where:

• (i) The Supervisor needs no a-priori knowledge about the subsystems and their paths of interaction (they can be reconstructed at run time), and Local Diagnosers do not necessarily know each other. This ensures that subsystems can be added/removed/replaced independently of each other at any time.
• (ii) Each Local Diagnoser must implement a given communication interface with the Supervisor (which is reasonable in an assembler-supplier relationship).
• (iii) It should be possible to have a hierarchical architecture of Supervisors corresponding to a hierarchical decomposition of the system.

The architecture defines a communication interface between the Local Diagnosers and the Supervisor. They must share a modeling ontology even though this allows each Local Diagnoser to use its own modeling language and assumptions, provided that it is able to map it over the common one during communications.

Local diagnosers are awakened by the subsystem they are in charge of whenever an anomaly (fault) is detected. They may explain the fault locally or may put the blame on an input received from another subsystem. They communicate to the Supervisor their explanations (without disclosing the details of the possible local failure(s)). The Supervisor may invoke the Local Diagnoser of the blamed subsystem asking it to generate explanations. The Supervisor may also ask a Local Diagnoser to check some predictions.

3 Models

In this section we discuss the modeling ontology used in the interface. First of all, as it is common in model-based diagnosis, we consider component-oriented models, where each component has one correct behavior and possibly one or more faulty behaviors. Each behavior of a component is modeled as a relation over a set of variables.

We consider qualitative models where all variables have a finite, discrete domain, thus representing either a discretization of the corresponding physical quantity, or an abstraction over some of its properties. This implies that the model of a component C is a finite relation including a mode variable C.m, that ranges over the set of behavior modes {ok, ab1, . . . , abn} of the component itself.

In the example in this paper we will use deviation models [Malik and Struss, 1996] where each physical quantity q represented in the model has a corresponding variable Δq representing a qualitative abstraction of the deviation of q with respect to its expected value; in particular, the sign abstraction {-, 0,+}, expressing whether q is lower than, equal to, or higher than its expected value.

In this paper we only deal with atemporal diagnosis, assuming that the models abstract away the temporal information, which is of course restrictive [Brusoni et al., 1998].

As a running example we use a simplified part of an Aircraft System, namely the part concerned with the Landing Gear. Figure 1 represents a high-level view of the system in terms of subsystems. The ones pictured with a dashed line do not directly take part in the example, but are shown for the sake of completeness.

The Hydraulic Extraction System (HES) creates a pressure that mechanically pushes the Landing Gear, thereby extracting it. The HES is also connected to some leds on the cockpit, that showwhether the subsystem is powered up or not. In order to create the pressure, the HES takes power from two sources. The main source is the Power Transmission from the aircraft engine, which actually powers up the main pump of the HES. A secondary source (used to transmit the pilot command from the cockpit, and to light up leds) is the Independent Power Supply, which produces a low-amperage DC current.

4 Decentralized Diagnostic Process

In this section we will describe how the diagnostic process is carried out. As we have already mentioned, a Supervisor coordinates the activities of several Local Diagnosers

{LD1, . . . , LDn}. In order to obtain a loosely coupled integration, the Supervisor assumes that each LDi is stateless, that is, every invocation of a Local Diagnoser is independent of the others. The interaction is thus defined by:

• An interface that each Local Diagnoser must implement, discussed in section 4.1. The role of each Local Diagnosers consists in generating hypotheses consistent with the model of its subsystem and the corresponding observations.
• An algorithm for the Supervisor that computes diagnoses by coordinating the Local Diagnosers through the above interface, as explained in section 4.2. The role of the Supervisor is to propagate hypotheses to the neighbors of a Local Diagnoser.

4.1 The Extend interface

We assume that each Local Diagnoser LDi reasons on a model Mi of its subsystem Si. From the point of view of the Supervisor and its interactions with Local Diagnosers, each model Mi is a relation over a set of variables where:

• mode variables, denoted by Si.m, express the behavior mode of components in Si;
• input/output variables express values of quantities that Si exchanges with other subsystems.
• there may be additional internal (private) variables.

The interface between the Supervisor and the Local Diagnosers is made of a single operation called EXTEND that the Supervisor invokes on the Local Diagnosers. Moreover, upon an abnormal observation, Local Diagnosers autonomously execute EXTEND and send the results to the Supervisor.

The goal of EXTEND is to explain and/or verify the consistency of observations and/or hypotheses made by other Local Diagnosers. Thus, the input to EXTEND when invoked on LDi is a set of hypotheses on the values of input/output variables of Mi. Such hypotheses are represented as a set of partial assignments over the variables of interest.

In the particular case where EXTEND is autonomously executed by a Local Diagnoser upon receiving an abnormal observation from its subsystem, the set of hypotheses contains only the empty assignment (i.e. the one with empty domain).

For each hypothesis α received in input, LDi must first check whether α is consistent with the local diagnostic model Mi and the local observations ωi. The extension that LDi should perform may be interpreted as follows (in causal terms): backwards, to verify whether the hypothesis needs further assumptions to be supported within Mi and ωi; forwards, to see whether the hypothesis has consequences on other subsystems, which can be used to discard or confirm it.

Let us consider as an example the Hydraulic Extension System (Figure 2) and suppose the Local Diagnoser LDHES, associated to the HES, receives in input an assignment that assigns the value "-" to its output data variable HES.ΔE, representing the mechanical extraction of the Landing Gear. This value means that the Landing Gear did not extract when expected. LDHES may then see that, with respect to the local model, one of the following must have happened:

• An internal component has failed, for example the pump is stuck or the pipe is leaking.
• One of the two inputs of the pump is wrong, for example the pump is not powered or it has not received the command.

This means that the partial assignment HES.ΔE = - can be extended in four ways: by assigning HES.m = stuck, or HES.m = leaking, or HES.ΔV = -, or HES.ΔC = -.

What is important regarding extensions is that they should include everything that can be said under a given hypothesis, but nothing that could be said also without it. In other words, we are interested in knowing whether a given assignment constrains other variables more than the model alone does. The following definition captures and formalizes this notion.

Definition 1 Let Mi be a local model with local observations ωi, and let γ be an assignment. We say that γ is admissible with respect to Mi and ωi if:

1. γ is an extension of ωi;
2. γ is consistent with Mi;

iii. ifMi,γ is themodel obtained by constrainingMi with γ, its restriction to variables not assigned in γ is equivalent to the restriction of Mi itself to the same variables:

Thus, for each assignment α received in input, the EXTEND operation of a Local Diagnoser LDi returns a set of assignments Eα that contains all minimal admissible extensions of α with respect to Mi and ωi, restricted to input, output and mode variables of Mi. Notice that, whenever α is inconsistent with the observations or the model, Eα is empty.

Minimal admissibility avoids unnecessary commitments on values of variables that are not concretely constrained by the current hypothesis.

In order to illustrate these definitions, let us consider a (simplified) model MP of the pump P alone. The model includes four variables: P.m represents the behavior mode, P.ΔV the power supply to the pump, P.ΔC the command that turns on the pump, and P.ΔF the flow coming out from the pump. The extensional representation of MP is:

Suppose EXTEND is called on MP alone, having in input an assignment α such that Dom(α) = {P.ΔF} and α(P.ΔF) = -. It can be verified that α itself is not admissible, while the minimal admissible extensions of α wrt MP are:

γ1, γ2 and γ3 express the three possible explanations for ΔF = -: either the pump is stuck, or it is not powered, or it did not receive the command. For each of the three assignments, unassigned variables are those whose value is irrelevant to the explanation.

4.2 The Supervisor algorithm

The Supervisor is started by a Local Diagnoser LDs that sends to it the results of an EXTEND operation executed as a consequence of an abnormal observation.

During its computation, the Supervisor records the following information:

• a set H of assignments, representing current hypotheses;
• for each assignment α and for each variable x ∈ Dom(α), a modified bit mdf(α(x)).

Moreover, we assume that given an input or output variable x that has been mentioned by one of the Local Diagnosers, the Supervisor is able to determine the variable(s) conn1(x), . . . , connk(x) connected to it. We do not make any assumption on whether this information is known a priori by the Supervisor, or it is retrieved dynamically, or it is provided by the Local Diagnoser itself.

The Supervisor initializes its data structures with the results of the initial EXTEND operation that has awakened it:

• H contains all the assignments that were sent by LDs as the result of EXTEND;
• for each α ∈ H, and for each x ∈ Dom(α), the Supervisor extends α to conn1(x), . . . , connk(x) by assigning α(connj(x)) = α(x) for j = 1, . . . , k. Then the Supervisor sets mdf(α(connj(x))) = 1.

Modified bits are used by the Supervisor to understand whether it should invoke a Local Diagnoser or not, according to the following:

Rule R. If a subsystem Si has a variable x with mdf(α(x)) = 1 for some α, then LDi is a candidate for invocation and α should be passed on to EXTEND.

After initializing data structures, the Supervisor loops over the following four steps:

Step 1: select the next LDi to invoke. The Supervisor selects one of the Local Diagnosers LDi for which there is at least one assignment α meeting Rule R. If there is none, the loop terminates.

• Step 2: invoke EXTEND. If LDi has never been invoked before in this diagnostic process, then the input to EXTEND is the set of all assignments in H, restricted to variables of Mi. Otherwise the input consists only of those assignments α that meet Rule R.
• Step 3: update H. The Supervisor receives the output of EXTEND from LDi. For each α in input, EXTEND has returned a (possibly empty) set of extensions Eα = {γ1, . . . , γk}. Then α is replaced in H by the set of assignments {β1, . . . , βk} where βj is obtained by:
• combining α with each γj ∈ Eα;
• extending the result of this combination to connected variables, so that for each x ∈ Dom(γ) representing an input/output variable, βj(conn(x)) = βj (x).

This implies that rejected assignments, having no extensions, are removed from H. This step and the following take place in exactly the same way if the EXTEND operation was not invoked by the Supervisor, but rather autonomously executed by a Local Diagnoser upon receiving an alarm. This is treated as an extension of the empty assignment, thus applicable to all α in H.

Step 4: update the mdf bits. For each assignment βj added in Step 3 mdf bits are set as follows:

• (i) For each variable x not belonging to Mi such that x ∈ Dom(βj) and x ̸∈ Dom(α), mdf(βj(x)) is set to 1.
• (ii) For each variable x belonging to Mi such that x ∈ Dom(βj), mdf(βj(x)) is set to 0.
• (iii) For any other variable x ∈ Dom(βj), x ∈ Dom(α) and mdf(βj (x)) = mdf(α(x)).

Notice that the diagnostic process terminates: new requests for EXTEND are generated only if assignments are properly extended, but assignments cannot be extended indefinitely.

We can prove the following:

Theorem 1 Let M denote the global model, and let ω denote the set of observations obtained during the diagnostic process. At the end of the Supervisor loop, the set H of partial assignments has the following properties:

1. each partial assignment α ∈ H is admissible with respect to M and ω;
2. the set of extensions is complete wrt M and ω, that is, for each total assignment γ consistent with M and ω, there exists α ∈ H such that γ is an extension of α.

The proof of this theorem relies on the following property of admissible extensions:

Proposition 2 Let M1 and M2 denote two interacting models, with observables ω1 and ω2, and let α be a partial assignment over M1 ✶ M2 (where ✶ denotes the composition of the two models). If α is admissible both wrt M1, ω1 and wrt M2, ω2 then it is admissible wrt M1 ✶ M2, ω1 ✶ ω2.

We need now to establish a relation between H and consistency-based diagnoses. Let us first extract diagnostic information from assignments in H:

Definition 2 Let α be an assignment in H at the end of the diagnostic process. The diagnostic information Δ(α) associated with α is its restriction to mode variables.

As a consequence of Theorem 1 we have:

Proposition 3 The set {Δ(α) | α ∈ H} is a complete set of partial diagnoses [de Kleer et al., 1992] wrt the model M and observations ω, meaning that every total mode assignment completing a Δ(α) is a consistency-based diagnosis for M and ω, and every consistency-based diagnosis is a completion of some Δ(α).

Corollary 4 Let D be the set of diagnoses obtained by completing all Δ(α) with ok assignments. The set of minimal diagnoses in D coincides with the set of minimal consistencybased diagnoses for M and ω.

Notice that in the Supervisor algorithm the role of mode variables is rather peculiar. Since these variables are local to a given system, the Supervisor never communicates their value to a Local Diagnoser different than the one originating them. Thus, they are not needed for cross-consistency checks. There are two main reasons why we need the Supervisor to be aware of them:

• They provide the connection between two different invocations on the same Local Diagnoser; by having the Supervisor record them and send them back on subsequent calls, we allow the Local Diagnosers to be stateless.
• The Supervisor needs them to compute globally minimal diagnoses.

Notice however that, for both of these goals, the values of mode variables need not be explicit: Local Diagnosers may associate to each fault mode a coded Id and use it as a value for mode variables. In this way, information on what has happened inside a subsystem can remain private.

Let us sketch a scenario of execution of the Supervisor algorithm for the system in Figure 1. Suppose that LDLG notices that the landing gear did not extract and blames it on the Hydraulic Extraction System. Then the Supervisor asks LDHES for an explanation, and receives back four extensions. In two of them, the HES takes responsibility for the problem (either the pump is stuck or the pipe is leaking). In the other two, it blames respectively the Power Transmission (input ΔV ) and the DC Power (input ΔC).

The Local Diagnoser of the Power Transmission is then asked to explain the blame; it has an observation confirming that its input ΔT is ok, thus it can explain it only as an internal failure. Then the Local Diagnoser of the DC Power is asked to explain its blame. Also the DC Power can explain it only as an internal failure, but it also states that this type of error would produce a problem also on its other output ΔX. At this point LDHES is invoked again to verify the consequences of this prediction, and it states that a problem on ΔX would produce a similar problem on ΔY . The Local Diagnoser of the LEDs subsystem discards this possibility thanks to its local observations; thus the causes of the failure can only be in the Hydraulic Extraction System or in the Power Transmission.

4.3 Hierarchies of Supervisors

In this section we discuss the problem of having a multilayered hierarchical structure of diagnosers. As we will see in section 5, this has also a relevant impact on complexity issues.

Let us consider a Supervisor S ′ at an intermediate level of the hierarchy, in charge of a portion M ′ of the global model M, with observations ω′ . When S ′ is invoked from a higherlevel Supervisor S, its loop starts with data structures initialized as follows:

• H contains all the assignments that S asked to extend;
• for each α ∈ H, and for each x ∈ Dom(α), S ′ sets mdf(α(x)) = 1.

In general, at the end of its loop, S ′ does not compute all minimal admissible extensions of the initial assignments in H wrt M ′ and ω′ . In fact, Theorem 1 guarantees that all the returned extensions are admissible, and that for each input assignment a complete set of extensions is returned, but not that such extensions are also minimal.

It is however possible to give a sufficient condition which guarantees minimality. Moreover, this provides a way to estimate the distance that returned extensions have from minimality. Intuitively, minimality cannot be guaranteed when the context where a subsystem is operating (i.e., the other subsystems it is connected to) limits its possible behaviors wrt those described in its model.

More formally, let us consider a Supervisor S with n Local Diagnosers: the model M is thus partitioned in M1, . . . ,Mn each owned by a different LDi. Let M|VAR(Mi) denote the projection of M over variables in Mi. If, for every i = 1, . . . , n, Mi ≡ M|VAR(Mi), then the Supervisor actually computes minimal admissible extensions. The more Mi is larger than M|VAR(Mi), the farther the returned extensions may be from minimality.

The operation computed by a Supervisor S with model M and observations ω is then, in the general case, a RELAXEDEXTEND that, for each input assignment α, returns a complete set of admissible extensions of α wrt M and ω.

Replacing EXTEND with RELAXEDEXTEND has no effect on the correctness of the algorithm, since Theorem 1 does not exploit the assumption that the extensions returned by Local Diagnosers are minimal:

Proposition 5 If all Local Diagnosers involved in a diagnostic process implement the RELAXEDEXTEND operation, then the Supervisor coordinating them implements RELAXEDEXTEND as well.

Thus, a multi-layered hierarchy of Supervisors is possible, although choosing to treat a subsystem with multiple Local Diagnosers, rather than as a whole, can result in non-minimal admissible extensions.

Not having minimal extensions has impact on at least three aspects of the diagnostic process. First, the contents of the exchanged messages and of the hypotheses set H may be larger. Second, some local diagnoser could be invoked even if the information it can provide is irrelevant to the diagnostic process. Third, as we will see in the next section, RELAXEDEXTEND has a lower complexity than EXTEND. This trade-off must be taken into account when selecting a diagnostic architecture.

5 Complexity

In this section we discuss the complexity of the proposed algorithm. Diagnosis is NP-complete, therefore we cannot expect anything better.

In our approach, the core of the diagnostic process is the Supervisor loop. This task can is composed by two activities: invocations of Local Diagnosers and merging of the results. The latter depends on the size of the results themselves; we need however to recall that the Supervisor builds a set of partial assignments, which in the worst case is exponential in the number of variables k. Thus the merging activity is in the worst case exponential in k. As to Local Diagnoser invocations, each of them is invoked at most once for each interface variable in its model. If we denote by ki the number of variables in model Mi, and by ˜ ki ≤ ki the number of interface variables in Mi, then we can express the complexity of the Supervisor as:

where CLD(ki) denotes the complexity of a Local Diagnoser invocation over a model with ki variables.

Let us now consider the EXTEND operation performed by Local Diagnosers. Given a model M, and an input assignment α, the task of finding an admissible extension for α in M is essentially a satisfiability problem: it suffices to find a total assignment satisfyingMα. Thus, this task is exponential in the number of involved variables.

Unfortunately, finding minimal admissible extensions is harder: it is NP-hard, and belongs to NP NP (although it does not appear to be complete for this class).

However, analyzing the complexity expression above, we see that, if the model can be split in subsystems with an upper bound on the number of variables in each of them, then ki can be treated as a constant, and the complexity of the overall algorithm goes back to O(ek ).

In component-oriented systems and models this decomposition is straightforward: components are usually reasonably sized, and the complexity of systems depends on the number of components rather than on the complexity of individual components. This suggests that the best way to tackle the complexity of EXTEND is to increase the number of local diagnosers and decrease the size of models in their care. In this case, the multi-layered architecture in section 4.3 can be profitable. In particular, if the split models can be obtained by projecting the global model (as it is the case when the split is due to efficiency reasons and not to subsystem privacy), there is no loss in the quality of the results, while the complexity of the algorithm is lower.

6 Conclusions

In this paper we discuss a supervised decentralized approach to diagnosis that allows to loosely couple multiple diagnosers, in order to deal with systems consisting of several subsystems, whose models cannot be composed.

The goal of the paper is to show that we can effectively perform the diagnostic task and define intelligent strategies for the Supervisor, even if it is not aware of the internal aspects of Local Diagnosers, the Local Diagnosers do not know each other, and their paths of interaction dynamically change.

The approach proposed in this paper builds on [Ardissono et al., 2005], which deals with diagnosis of Web Services. In particular, the definition of the EXTEND interface is borrowed from [Ardissono et al., 2005], while the Supervisor algorithm is generalized in order to loosen the assumptions while not losing diagnostic coverage. Moreover, the properties of this algorithm are proved and its complexity analyzed.

The proposed framework was presented for atemporal models, where dynamic features are either absent, or have been abstracted away. The extension to temporal issues in diagnosis [Brusoni et al., 1998] is subject for future work. Dynamic models (possibly including feedback loops) should be dealt with, as well as using temporal information on observations for discrimination (with the additional problem of possible communication delays among diagnosers).

The approach in [Pencol´e and Cordier, 2005] has some relevant similarity with that of this paper, from the point of view of diagnostic architecture: a Supervisor is in charge of computing global diagnoses exploiting the work of several local diagnosers. However, this work focuses on quite different theoretical and practical problems:

• the system to diagnose is modeled as a discrete-event system;
• the main problem is to avoid composing the whole model, because this would produce a state-space explosion;
• as a consequence, the supervisor is aware of the subsystem models, but cannot compose them: it can only compose local diagnoses to obtain a global one;
• due to the nature of the considered systems, reconstructing global diagnoses is a difficult task, and as such it is one of the main focuses of the paper.

Other papers in the literature deal with completely distributed approaches to diagnosis, where diagnosers communicate with each other and try to reach an agreement, without a supervisor coordinating them. Our choice of a supervised approach was motivated by the need of having loosely coupled diagnosers, while a purely distributed approach requires diagnosers to establish diagnostic sessions and exchange a greater amount of information in order to compute diagnoses that are consistent with each other.

Nevertheless, the distributed approach proposed in [Roos et al., 2003] has some similarity with ours because it is based on the idea of diagnosers explaining blames received from others, or verifying hypotheses made by others. Needless to say, the proposed algorithms are completely different, having to deal with a distributed approach. Moreover, in order to reduce computational complexity, the authors introduce some fairly restrictive assumptions on the models (e.g. requiring that explanations imply normal observations, or that output values are either completely undetermined or completely determined).

Finally, [Provan, 2002] deals with a scenario similar to ours: each diagnoser has a local model and observations, which are not shared with the others. Each local diagnoser computes local minimal diagnoses, and then engages in a conversation to reach a globally sound diagnosis. However, being the approach purely distributed, solutions are different. In particular, in order to propose a solution with reduced complexity, the author focuses on systems whose connection graph has a tree-like structure. On the contrary, our approach (thanks to the presence of the supervisor) does not need to make any assumption on system structure.