Louise Travé-Massuyès
email: louise@laas.fr

Bridging Control and Artificial Intelligence Theories for Diagnosis: A survey

Keywords: model based diagnosis, data based diagnosis, abstractions, fault management architectures

Diagnosis is the process of identifying or determining the nature and root cause of a failure, problem, or disease from the symptoms resulting from selected measurements, checks or tests. The different facets of this problem and the wide spectrum of classes of systems make it interesting to several communities and require bridging several theories. Diagnosis is actually a functional fragment in fault management architectures and it must smoothly interact with other functions. This paper presents diagnosis as it is understood in the Control and Artificial Intelligence fields, and exemplifies how different theories of these fields can be synergistically integrated to provide better diagnostic solutions and to achieve improved fault management in different environments 1 .

Introduction

The goal of diagnosis is to identify the possible causes explaining a set of observed symptoms. A set of concomitant tasks contribute to this goal and the following three tasks are commonly identified:

• fault detection, which aims at discriminating normal system states from abnormal ones, i.e. states which result from the presence of a fault,

• fault isolation, also called fault localization, whose goal is to point at the faulty components of the system,

• fault identification, whose output is the type of fault and possibly the model of the system impacted by this fault.

Faced with the diversity of systems and different views of the above problems, several scientific communities have addressed these tasks and contributed with a large spectrum of methods. The Signal Processing, Control and Artificial Intelligence (AI) communities are leading actors in this field.

Diagnosis is carried out from the signals that permit efficient fault detection towards the upper levels of supervision that call for qualitative interpretations. Proposing relevant abstractions to interpret the available signals is hence a key issue.

Signal processing provides specific contributions in the form of statistic algorithms for detecting changes in signals, hence detecting faults. This remains out of the scope of this paper and has been surveyed in several reference books and papers [START_REF] Basseville | Detecting changes in signals and systems : a survey[END_REF][START_REF] Basseville | Detection of abrupt changes: theory and application[END_REF][START_REF] Basseville | Statistical model-based damage detection and localization: subspace-based residuals and damage-to-noise sensitivity ratios[END_REF][START_REF] Fillatre | Non-Bayesian detection and detectability of anomalies from a few noisy tomographic projections[END_REF][START_REF] Fouladirad | Optimal fault detection with nuisance parameters and a general covariance matrix[END_REF].

Interfaces between continuous signals and their abstract interpretations, in symbolic or event-based form, implement qualitative interpretations of the signals that are required for supervision. To do that, discrete formalisms borrowed from AI find a natural link with continuous models from the Control community. These two communities have their own model-based diagnosis track :

• the FDI (Fault Detection and Isolation) track, whose foundations are based on engineering disciplines, such as control theory and statistical decision making,

• the DX (Diagnosis) track, whose foundations are derived from the fields of logic, combinatorial optimization, search and complexity analysis.

In the last decade, there has been a growing number of researchers in both communities who have tried to understand and bridge FDI and DX approaches to build better, more robust and effective diagnostic systems.

Data-based diagnosis approaches based on machine learning techniques, such as pattern recognition [START_REF] Fukunaga | Introduction to statistical pattern recognition[END_REF][START_REF] Denoeux | Advanced pattern recognition techniques for system monitoring and diagnosis: a survey[END_REF], are present in both the Control and AI communities and complement modelbased approaches to provide solutions to a variety of diagnostic problems where the difficulty arises from the scarce nature of the instrumentation or, conversely, from the massive amounts of data to be interpreted to extract hidden knowledge. Interesting bridges also arise when we consider data-based and model-based approaches.

Other bridges can be found when considering that diagnosis is not a goal per se but a component in fault management architectures. It takes part in the solutions produced for tasks such as failure-mode-and-effects analysis, sensor placement, on-board recovery, condition monitoring, maintenance, repair and therapy planning, and prognosis. The contribution of diagnosis in such architectures requires close links with decision tasks such as control and planning and calls for innovative integrations.

In this paper, different facets of diagnosis investigated in the Control or the AI fields are discussed. While (Venkatasubramanian et al., 2003a,b,c) provide three interesting surveys of the different approaches that exist in these fields, this paper aims at reporting the works that integrate approaches of both sides, hence creating "bridges". In particular, the concepts and results of the FDI and DX tracks are put in correspondence and the lessons learned from this comparative analysis are pointed out. Causal model-based diagnosis is presented as a typical example of integration of FDI and DX theories, in which fault detection is implemented along an FDI approach and fault isolation calls for the logical DX framework. Hybrid model-based diagnosis is then used to illustrate several interesting bridges, in particular, how FDI estimation schemes can be combined with search algorithms rooted in AI to achieve hybrid state tracking efficiently. Combining FDI estimation filters with the logical DX theory is also illustrated. Finally, it is shown that the hybrid model-based diagnosis problem can also find a solution by combining the FDI approach with the so-called diagnoser approach of the discrete event systems (DES) field. Subsequently, learning the models that support diagnosis reasoning is shown to be a rich field for bridging theories. It has been intensively investigated for continuous model identification for which regression analysis is essential. Learning discrete event models calls for other bridges, which are illustrated with chronicle learning. Finally, diagnosis is discussed in relation with theories that participate to provide global solutions to fault management problems. On one hand, autononous architectures exemplify the integration of diagnosis, control and planning. On the other hand, it is shown how diagnosis can enhance prognosis in condition maintenance architectures.

The paper is organized as follows. After the introduction section, section 2 first presents a brief overview of the approaches proposed by the FDI and DX model-based diagnosis communities. Although quite commonplace, this overview is necessary because it provides the basic concepts and principles that form the foundations of any diagnosis method. It is followed by the comparison of the concepts and techniques used by these communities and the lessons learned from this comparative analysis. Section 3 is concerned with the trends that integrate and take advantage of techniques from both sides, in particular causal model based diagnosis in subsection 3.1 and diagnosis of hybrid systems in subsection 3.2. Section 4 then raises the problem of obtaining the models supporting diagnosis reasoning and discusses bridges that can contribute to learning them in an automated manner. Section 5 widens the scope of diagnosis and is concerned with diagnosis as a component of fault management architectures, discussing the several links with control and planning. Finally, section 6 concludes the paper.

DX and FDI model-based diagnosis bridge

The FDI and DX streams both consider the diagnosis problem from a system point of view, which results in significant overlaps. Even the name of the two tracks are the same : Model-Based Diagnosis (MBD).

The diagnosis principles are the same, although each community has developed its own concepts and methods, guided by different modeling paradigms and solvers. FDI relies on analytical models, linear algebra, and non-linear system theory whereas DX takes its foundations in logic. In the 2000s, catalyzed by the "Bridging AI and Control Engineering model-based diagnosis approaches" group, known as the BRIDGE group (BRIDGE), within the European Network of Excellence MONET II (MONET), and its French counterpart, the "Intégration de Méthodes Alliant Automatique et IA" group, known as the IMALAIA group, supported by GDR MACS (GDR MACS), GDR I3 (GDR-I3), as well as AFIA (AFIA), there were more and more researchers who tried to understand and synergistically integrate methods from the two tracks to propose more efficient diagnostic solutions. This collaboration launched several events : • the co-location, in Washington DC (USA), of the two main events of the FDI and the DX communities, namely the IFAC International Symposium on Fault Detection, Supervision and Safety for Technical Processes SAFEPROCESS'03 and the International Workshop on Principles of Diagnosis DX'03, including a BRIDGE Workshop in the form of a join day.

• a BRIDGE Workshop in
These events were followed by the publication of a special issue of the IEEE SMC Transactions, Part B, on the topic "Diagnosis of Complex Systems: Bridging the methodologies of the FDI and DX Communities" in 2004 [START_REF] Biswas | Diagnosis of complex systems: Bridging the methodologies of the FDI and DX communities[END_REF]. The BRIDGE track was launched and paved its way until today. Other events followed like the two invited sessions "AI methods for Model-based Diagnosis" and "Bridge between Control Theory and AI methods for Model-based Diagnosis", recently organized in the framework of the 7th IFAC International Symposium on Fault Detection, Supervision and Safety of Technical Processes SAFAPROCESS'09, Barcelona, Spain, 30 July-3 August 2009.

The next subsections first summarize the foundations of the FDI and DX approaches, then proceed with a comparative analysis that allows us to draw some practical assessments in the form of lessons learned. The lessons summarize the respective strengths and weaknesses of the two approaches and provide the guidelines that drive the proposals combining the two approaches.

Brief overview of FDI approaches

The detection and diagnosis methods of the FDI community rely on behavioral models that establish the constraints between system inputs u ∈ U and outputs y ∈ Y , gathered in the set of measurable variables Z, and the system internal states defining the set of unknown variables X. The variables z ∈ Z and x ∈ X are functions of time. The typical model may be formulated in the temporal domain, then known as a state-space model :

BM : dx/dt = f (x(t), u(t), θ) OM : y(t) = g(x(t), u(t), θ).
(1)

where x(t) ∈ R nx is the state vector, u(t) ∈ R nu is the input vector and y(t) ∈ R np is the output vector. θ ∈ R n θ is a constant parameter vector. The components of f and g are real functions over R. BM is the behavioral model and OM is the observation model. The whole system model is noted SM (z, x), like in [START_REF] Krysander | An efficient algorithm for finding minimal overconstrained subsystems for model-based diagnosis[END_REF], and assumed noise-free. The equations of SM (z, x) may be associated to components but this information is not represented explicitly. The models can also be formulated in the frequency domain, for instance in the form of transfer functions in the linear case. Models are used in three families of methods:

• the methods based on parameter estimation that focus on the value of parameters as representing physical features of the system,

• the methods based on state estimation, like observers and filters, that rely on the estimation of unknown variables,

• the methods based on the parity space that rely on the elimination of unknown variables.

The books [START_REF] Gertler | Fault Detection and Diagnosis in Engineering Systems[END_REF], [START_REF] Blanke | Diagnosis and fault-tolerant control[END_REF], [START_REF] Dubuisson | Automatique et statistiques pour le diagnostic[END_REF], [START_REF] Patton | Fault diagnosis in dynamic systems[END_REF] provide excellent surveys, which cite the original papers that the reader is encouraged to consult. The paper (Venkatasubramanian et al., 2003c) also provides a quite comprehensive survey. The equivalence between observers, parity space and paramater estimation has been proved in the linear case [START_REF] Patton | A re-examination of the relationship between parity space and observer-based approaches in fault diagnosis[END_REF].

The concept central to FDI methods is the concept of residual and one of the main problems is to generate residuals. Let's consider the model SM (z, x) given by (1), then SM (z, x) is said to be consistent with an observed trajectory z, or simply consistent with measurements z, if there exists a trajectory of x such that the equations of SM (z, x) are satisfied.

Definition 1 (Residual generator for SM (z, x)) A system that takes as input a sub-set of measured variables Z ⊆ Z and generates as output a scalar r, is a residual generator for the model SM (z, x) if for all z consistent with SM (z, x), lim t→∞ r(t) = 0.

When the system model is consistent with measurements, the residuals tend to zero as t tends to infinity, otherwise some residuals may be different from zero. In practice, the residuals never happen to be exactly zero because the noise-free assumption adopted for (1) is never met. Evaluating the residuals and assigning them a Boolean value -0 or non 0 -requires statistical tests that account for the statistical characteristics of noise [START_REF] Basseville | Detection of abrupt changes: theory and application[END_REF][START_REF] Dubuisson | Automatique et statistiques pour le diagnostic[END_REF]. The residuals are often optimized to be robust to disturbancies [START_REF] Qiu | Robust FDI and H inf optimization[END_REF] and to take into account uncertainties [START_REF] Adrot | Fault detection with model parameter structured uncertainties[END_REF].

The methods based on parameter estimation are used for linear as well as non linear systems [START_REF] Pouliezos | Fault detection using parameter estimation[END_REF]. Fault detection is achieved by comparing the estimated parameter values to the nominal values. With these methods, fault detection, isolation, and identification are achieved at once, provided that model parameters can be put in correspondence with physical parameters. The results rely on the identifiability of the system as explained in [START_REF] Grewal | Identifiability of linear and nonlinear dynamical systems[END_REF] and [START_REF] Jauberthie | Set-membership identifiability: Definitions and analysis[END_REF] in the set-membership framework.

The methods based on state estimation take the form of observers or optimized filters, such that the Kalman filter, and provide an estimation of the state of the system. Specific filter architectures are often designed to structure the residuals, i.e. to sensitize different residuals for different faults, and isolate the faults [START_REF] Frank | On-line fault detection in uncertain nonlinear systems using diagnostic observers: a survey[END_REF]. Numerous diagnosis solutions rely on state estimation, particularly for hybrid systems. These works are surveyed in section 3.2. In this case, the continuous state is augmented by a discrete state that corresponds to the operation mode -normal or faulty -of the system components.

The methods based on the parity space [START_REF] Chow | Analytical redundancy and the design of robust failure detection systems[END_REF] generate residuals from relations that are inferred from the system model. These relations, called Analytical Redundancy Relations (ARR), are determined offline.

Definition 2 (ARR for SM (z, x)) A relation of the form r(z, ż, z, . . . ) = 0 is an ARR for the model SM (z, x) if for all z consistent with SM (z, x), the relation is satisfied.

ARRs are constraints that only involve measured input and output variables and their derivatives. For linear systems, ARRs are obtained eliminating unknown state variables by linear projection on a particular space, called the parity pace [START_REF] Chow | Analytical redundancy and the design of robust failure detection systems[END_REF]. An extension to non-linear systems is proposed in [START_REF] Staroswiecki | Analytical redundancy relations for fault detection and isolation in algebraic dynamic systems[END_REF]. On the other hand, the structural approach [START_REF] Staroswiecki | Analytical redundancy in non linear interconnected systems by means of structural analysis[END_REF][START_REF] Armengol | Minimal Structurally Overdetermined sets for residual generation: A comparison of alternative approaches[END_REF] is an interesting approach because it allows one to obtain, for linear or non-linear systems, the just overdeterminated sets of equations from which ARRs can be derived.

Every ARR can be put in the form r(t) = 0, where r(t) is the residual. If the behavior of the system satisfies the model constraints, then the residuals are zero because the ARRs are satisfied. Otherwise, some of them may be different from zero when the corresponding ARRs are violated. Given a set of n residuals, a theoretical fault signature F S j = [s 1j , s 2j , . . . , s nj ] given by the Boolean evaluation of each residual is associated to each fault F j . The signature matrix is then defined as follows.

Definition 3 (Signature Matrix) Given a set of n ARRs, the signature matrix F S associated to a set of n f faults F = [F 1 , F 2 , . . . , F n f ] is the matrix that crosses ARRs as rows and faults as columns, and whose columns are given by the theoretical signatures of the faults, i.e.

F S = [F S 1 , F S 2 , . . . , F S n f ].
Diagnosis is achieved by comparing the observed signature, i.e. the Boolean residual values obtained from the actual measurements, and the theoretical signatures of the n f faults.

Brief overview of the DX logical diagnosis theory

In the model-based logical diagnosis theory of DX as proposed by [START_REF] Reiter | A theory of diagnosis from first principles[END_REF][START_REF] Kleer | Characterizing diagnoses and systems[END_REF], the description of the system is driven by components and relies, in its original version, on first order logic. A system is given by a tuple (SD, COM P S, OBS) where:

• SD is the system description in the form of a set of first order logic formulas with equality,

• COM P S represents the set of components of the system given by a finite set of constants,

• OBS is a set of first order formulas, which represent the observations.

SD uses the specific predicate AB, meaning abnormal. Applied to a component c of COM P S, ¬AB(c) means that c is normal and AB(c) that c is faulty. For instance, the model of a two inputs adder would be given by :

¬AB(x) ∧ ADD(x) ⇒ Output(x) := Input1(x) + Input2(x) (2)
Definition 4 (Diagnosis) A diagnosis for the system (SD, COM P S, OBS)

is a set ∆ ⊆ COM P S such that SD ∪ OBS ∪ {AB(c) | c ∈ ∆} ∪ {¬AB(c) | c ∈ COM P S -∆} is satisfiable.
The above definition means that the assumption stating that the components of ∆ are faulty and all the others are normal is consistent with the observations OBS and the system description SD. A diagnosis hence consists in the assignment of a mode, normal or faulty2 , to each component of the system, which is consistent with the model and the observations.

Definition 5 (Minimal diagnosis) A minimal diagnosis is a diagnosis ∆ such that ∀∆ ⊂ ∆, ∆ is not a diagnosis.
To obtain the set of diagnoses, it is usual to proceed in two steps, basing the first step on the concept of conflict introduced in [START_REF] Reiter | A theory of diagnosis from first principles[END_REF] and later extended in [START_REF] Kleer | Characterizing diagnoses and systems[END_REF]. The original definition, that we call R-conflict, i.e. conflict in the sense of Reiter, is the following : Definition 6 (R-conflict and minimal R-conflict) An R-conflict is a set C ⊆ COM P S such that the assumption that all the components of C are normal is not consistent with SD and OBS. A minimal R-conflict is an R-conflict that does not contain any other conflict.

The set of diagnoses can be generated from the set of conflicts. [START_REF] Reiter | A theory of diagnosis from first principles[END_REF] proved that minimal diagnoses are given by the hitting sets3 of the set of minimal R-conflicts. An algorithm based on the construction of a tree, known as the HS-tree, was originally proposed by [START_REF] Reiter | A theory of diagnosis from first principles[END_REF].

The parsimony principle indicates that preference should be given to minimal diagnoses. Another reason why minimal diagnoses are important is because in many cases, they characterize the whole set of diagnoses. In other words, all the supersets of minimal diagnoses are diagnoses. [START_REF] Kleer | Characterizing diagnoses and systems[END_REF] provided the conditions for this to be true by extending the definition of an R-conflict to a disjunction of AB-literals, AB(c) or ¬AB(c), containing no complementary pair, entailed by SD ∪ OBS. Then, a positive conflict is a conflict for which all of its literals are positive and one can identify a positive conflict with an R-conflict [START_REF] Reiter | A theory of diagnosis from first principles[END_REF] as defined above.

Diagnoses are characterized by minimal diagnoses if and only if all minimal conflicts are positive [START_REF] Kleer | Characterizing diagnoses and systems[END_REF]. Unfortunately, only sufficient conditions exist on the syntactic form of SD and OBS. One of those is that the clause form of SD ∪ OBS only contains positive AB-literals. This is verified, for instance, if all sentences of SD are of the same form as (2), which means that only necessary conditions of correct behavior are expressed.

Lessons learned from comparing the FDI and DX approaches

This section summarizes the results of [START_REF] Cordier | Conflicts versus analytical redundancy relations: a comparative analysis of the model based diagnosis approach from the artificial intelligence and automatic control perspectives[END_REF] obtained from the comparative analysis of the DX approach and the parity space FDI approach presented in the two preceding sections. It presents the concept of ARR support that is the articulation of the two approaches and gives rise to the important properties of ARR-d-completeness and ARR-i-completeness. It then discusses the lessons learned, outlining the different hypotheses adopted by the two approaches and sheding light on their respective strengthes and drawbacks.

Frst, it should be noticed that the modeling paradigm of FDI does not make explicit use of the concept of component. The behavioral model (1) describes the system as a whole. On the contrary, the DX approach models every component independently, and specifies the structure of the system, i.e. how the different components are connected. Another important difference is that the assumption of correct behavior is represented explicitly in SD thanks to the predicate AB. If F is a formula describing the normal behavior of a component, SM only contains F whereas SD contains the formula ¬AB(c) ⇒ F.

The comparison of the two approaches is only possible if the models on both sides represent the same system and the observations/measurements capture the same reality. This is formalized by the System Representation Equivalence (SRE) property introduced in [START_REF] Cordier | Conflicts versus analytical redundancy relations: a comparative analysis of the model based diagnosis approach from the artificial intelligence and automatic control perspectives[END_REF], which requires that SM is obtained from SD by setting to false all the occurrences of the predicate AB. It is also assumed that the same observation language is used, i.e. OBS is a conjunction of equality relations, which assign a value to every measured variable. In addition, the faults refer to the same entities assumed to be components, without loss of generality.

The comparison is based on the concept of signature matrix F S, as defined in definition 3. F S crosses ARRs in rows and faults/components in columns (faults are univocally associated to components). The comparison also relies on the concept of ARR Support.

Definition 7 (ARR Support) Consider ARR i to be an ARR for SM (z, x), then the support of ARR i , noted supp(ARR i ), is the set of components {c j } (columns of the signature matrix F S) whose corresponding matrix cells F S ij are non zero on the ARR i line.

The support of an ARR of the form r(z, ż, z, . . . ) = 0 indicates the set of components whose models, or submodels, are involved in the obtention of the relation r(z, ż, z, . . . ) = 0. The equations of the model SM (z, x) can indeed be partitioned in component models and every equation of SM (z, x) can be labelled as being part of the model of some component. Let SM (c) denote the subset of equations defining the model of a component c ∈ COM P S and SM (C) = c∈C SM (c) the subset of equations corresponding to C ⊆ COM P S.

Let us now introduce two completeness properties, which refer to "detectability" indicated by a "d", and to "isolability" indicated by an "i".

Property 1 (ARR-d-completeness) A set E of ARRs is said to be d- complete if: • E is finite; • ∀OBS, if SM ∪ OBS |=⊥, then ∃ARR i ∈ E such that {ARR i } ∪ OBS |=⊥.
Property 2 (ARR-i-completeness) A set E of ARRs is said to be icomplete if:

• E is finite;

• ∀C, set of components such that C ⊆ COM P S, and ∀OBS, if

SM (C)∪ OBS |=⊥, then ∃ARR i ∈ E such that supp(ARR i ) is included in C and {ARR i } ∪ OBS |=⊥.
ARR-d-completeness and ARR-i-completeness express the theoretical capability of a set of ARRs to be sensitive, hence to detect, any inconsistency between the model SM and observations OBS.

Example -Consider the following signature matrix F S ex assumed to refer to a system with model SM ex . It gathers the signatures of the faults, single and multiple, that may affect four components c 1 , c 2 , c 3 , and c 4 . These are composed by the Boolean values of three residuals arising from three ARRs ARR 1 , ARR 2 , and ARR 3 and are given by the columns of the fault matrix. For example, the fault signature of f c 1 is the Boolean vector (1, 0, 1) T . The support of each ARR is given by the rows of the submatrix corresponding to single faults. For example, supp(ARR 1 ) = {c 1 , c 2 , c 3 }.

Let us consider the set of ARRs E 1,2 = {ARR 1 , ARR 2 }, then it can be noticed from F S ex that it is d-complete. Indeed, in any of the faulty situations implying a violation of SM ex , there is one ARR in E 1,2 that is 1, i.e. meaning that it is violated by the corresponding observations. One can also notice that E 1,2 is not i-complete. The existence of ARR 3 means that we may have a situation in which the subset of components C = {c 1 , c 2 , c 4 } is inconsistent, i.e. SM ex (C)∪OBS |=⊥. Nevertheless, since supp(ARR 1 ) ⊆ C and ARR 2 ⊆ C, property 2 is not fulfilled. As a matter of fact, eventhough ARR 3 seems useless for isolating single faults, one can notice from F S ex that, without ARR 3 , no multiple fault of the last column can be discriminated from

f c 3 . f c 1 f c 2 f c 3 f c 4 f c 1 c 2 all other multiple faults ARR 1 1 1 1 0 1 1 ARR 2 0 0 1 1 0 1 ARR 3 1 1 0 1 1 1 Table 1: Example of a fault signature matrix F S ex
ARR-d-completeness and ARR-i-completeness are key to the comparison of the FDI and DX approaches. The main results can be summarized by the following proposition.

Proposition 1 [START_REF] Cordier | Conflicts versus analytical redundancy relations: a comparative analysis of the model based diagnosis approach from the artificial intelligence and automatic control perspectives[END_REF] Assuming the SRE property and that OBS is the set of observations for the system given by SM (or SD), then :

1. If ARR i is violated by OBS, then supp(ARR i ) is an R-conflict;
2. If E is a d-complete set of ARRs, and if C is an R-conflict for (SD, COM P S, OBS), then there exists ARR i ∈ E that is violated by OBS;

3. If E is an i-complete set of ARRs, then given an R-conflict C for (SD, COM P S, OBS), there exists

ARR i ∈ E that is violated by OBS and supp(ARR i ) is included in C.
The result 1 of proposition 1 is intuitive and can be explained by the fact that the inconsistencies between the model and observations are captured by R-conflicts in the DX approach and by ARRs violated by OBS in the FDI approach. Consequently, the support of an ARR can be defined as a potential R-conflict. This concept is also called possible conflict in (Pulido and Gonzalez, 2004a).

The results 2 and 3 of proposition 1 refer to fault detectability and fault isolability. The result 2 outlines the ARR-d-completeness property as the condition for fault detectability. From the result 3, the ARR-i-completeness property appears as the condition under which a formal equivalence between R-conflicts and ARR supports holds, as stated by the following corollary.

Corollary 1 If both the SRE and the ARR-i-completeness properties hold, the set of minimal R-conflicts for OBS and the set of minimal supports of ARRs (taken in any i-complete set of ARRs) violated by OBS are identical.

The detailed proofs of proposition 1 and corollary 1 can be found in [START_REF] Cordier | Conflicts versus analytical redundancy relations: a comparative analysis of the model based diagnosis approach from the artificial intelligence and automatic control perspectives[END_REF].

Let us now analyze the results from a more practical point of view, and point at the differences of the two approaches and how their respective advantages can be put together.

Lesson one: redundant ARRs

An important result coming from ARR-i-completeness refers to redundant ARRs. In FDI, it is generally accepted that if ARR j is obtained from a linear combination of two other ARRs, ARR i 1 and ARR i 2 , then ARR j is redundant (unless some considerations about noises and sensitivity to faults come into play). Nevertheless the i-completeness property states that not only the analytical expression of ARR j must be taken into account but also its support to conclude about the fact that it is redundant. The formal conditions are stated in the proposition below from [START_REF] Cordier | Conflicts versus analytical redundancy relations: a comparative analysis of the model based diagnosis approach from the artificial intelligence and automatic control perspectives[END_REF].

Proposition 2 A given ARR j is redundant with respect to a set of ARR i s, i ∈ I, j / ∈ I, where I is a set of integer indexes such that card(I) ≥ 2, if and only if ∃I ⊆ I such that : 1) ∀OBS, if all ARR i s, i ∈ I , are satisfied by OBS, then ARR j is satisfied by OBS,

2) supp(ARR j ) ⊇ supp(ARR i ), ∀i ∈ I .
The above proposition can be explained by the fact that if supp(ARR j ) does not satisfy condition 2, then it captures an inconsistency that is not captured by the initial ARR i s, i ∈ I. It is hence apt, added to the initial ARR i s, to contribute to the achievement of ARR-i-completeness.

Lesson two: exoneration assumptions

The exoneration assumptions, ARR-exoneration and component-exoneration, used by DX and FDI, respectively, are different.

Definition 8 (ARR-exoneration) Given OBS, any component in the support of an ARR satisfied by OBS is exonerated, i.e. considered as normal.

Definition 9 (Component-exoneration) Given OBS and c ∈ COM P , if SM (c)∪OBS is consistent, then c is exonerated, i.e. considered as normal.

The FDI approach generally uses the ARR-exoneration assumption without formulating it explicitly. On the other hand, the DX approach generally proceeds with no exoneration assumption at all. When this is not the case, it uses the component-exoneration assumption and represents it explicitly. If a component c is exonerated, its model is written as:

COM P (c) ∧ ¬AB(c) ⇐⇒ SM (c)
where the simple logical implication, found in (2) for instance, is replaced by a double implication. Explicit assumptions guarantee logical correctness of the DX diagnoses obtained by the DX method. Interestingly, ARR-exoneration cannot be expressed in the DX formalism and conversely, component-exoneration cannot be expressed in the FDI formalism.

It has been shown that under the same assumptions, in particular in the case of no exoneration, the diagnoses that are obtained by the DX and the FDI approach are the same.

Theorem 1 [START_REF] Cordier | Conflicts versus analytical redundancy relations: a comparative analysis of the model based diagnosis approach from the artificial intelligence and automatic control perspectives[END_REF] Under the i-completeness and no exoneration assumptions, the diagnoses obtained by the FDI approach are identical to the (non empty) diagnoses obtained by the DX approach.

Lesson three: single and multiple faults

In the FDI approach, because the fault signatures are determined off-line for every fault, the number of considered faults is generally limited. Most of the time, only single faults are considered. On the contrary, the DX approach naturally deals with multiple faults. A consequence is that the number of diagnoses is exponential and this is why it is common to introduce preference criteria, like fault probabilities, to order the diagnoses. Several search methods have been proposed to find the preferred diagnoses or to retrieve the diagnoses in preference order (see for instance [START_REF] Williams | Conflict-directed A* and its role in modelbased embedded systems[END_REF][START_REF] Sachenbacher | Diagnosis as semiring-based constraint optimization[END_REF])).

Lesson four: off-line versus on-line

In the FDI approach, ARRs are determined off-line and only a simple consistency check is performed on-line. This may be quite relevant for real-time applications with hard temporal constraints. Inversely, in the DX approach, the whole diagnosis process is on-line, the advantage being that only the models need to be updated in case of any evolution of the system. The two approaches have been integrated to obtain the advantages of both: some DX works have used the idea of the FDI community to construct ARRs off-line [START_REF] Katsillis | Can dependency-based diagnosis cope with simultaneous equations[END_REF][START_REF] Loiez | Polynomial temporal band sequences for analog diagnosis[END_REF][START_REF] Washio | Discovering Admissible Model Equations from Observed Data[END_REF]Pulido and Gonzalez, 2004b) and some FDI works have proposed to base the fault isolation phase on the conflicts derived from violated ARRs [START_REF] Vento | Fault detection and isolation of hybrid systems using diagnosers that reason on components[END_REF].

Causal model-based diagnosis

In the 90s, the synergies between the FDI and DX approaches found fulfillment in a series of studies proposing causal models for diagnostic reasoning. These are perfect examples of integration of the FDI and the DX approaches, the FDI approach being used for fault detection and the DX approach for fault isolation. At that time, causal models were intensively studied by the Qualitative Reasoning community [START_REF] Dague | Raisonnement causal en physique qualitative[END_REF][START_REF] Travé-Massuyès | Modèles et raisonnements qualitatifs[END_REF][START_REF] Weld | Readings in qualitative reasoning about physical systems[END_REF]. Whereas (Venkatasubramanian et al., 2003a) overviews how causal models can be used to represent the qualitative behavior of a system and the various ways in which qualitative models can support diagnosis reasoning, this section focuses on another subset of works that enrich the causal structure with quantitative models, hence providing a framework to integrate FDI and DX concepts.

Causal models are based on a graph structure expressing explicitly the dependencies between variables by edges called influences. This structure is called a Causal Graph from which explanations for the values -normal or abnormal -of variables can be exhibited. Accounting for the dependencies between variables is the basic principle of many diagnostic algorithms. Whereas the standard diagnosis algorithms of DX, such as GDE [START_REF] De Kleer | Diagnosing multiple faults[END_REF], use the technique known as "dependency recording" (implemented with an ATMS for example) that records dependencies during the inferences, the dependencies used by causal models are exhibited from the outset. These are obtained either directly from expert knowledge as in [START_REF] Leyval | Model-based causal reasoning for process supervision[END_REF][START_REF] Gentil | Combining FDI and AI approaches within causal-model-based diagnosis[END_REF], by techniques of causal ordering of the QR community as in [START_REF] Travé-Massuyès | The CA-En Diagnosis System and its Automatic Modelling Method[END_REF], or from bond-graph models as in [START_REF] Mosterman | Diagnosis of continuous valued systems in transient operating regions[END_REF][START_REF] Feenstra | Bond graph modeling procedures for fault detection and isolation of complex flow processes[END_REF].

Causal diagnosis uses the causal graph as an abstract parameterized representation of the system in which every influence is associated with a physical component of COM P . Early work was limited to labeling causal influences by the signs giving the direction of change of the influenced variable in relation to the cause variable, thus representing a Signed Oriented Graph [START_REF] Oyeleye | Qualitative simulation of chemical process systems: Steady-state analysis[END_REF][START_REF] Kramer | A rule-based approach to fault diagnosis using the signed directed graph[END_REF]. Subsequently, the labeling of influences became more sophisticated and local quantitative models as used in FDI were attached [START_REF] Leyval | Model-based causal reasoning for process supervision[END_REF][START_REF] Gentil | Combining FDI and AI approaches within causal-model-based diagnosis[END_REF][START_REF] Travé-Massuyès | The CA-En Diagnosis System and its Automatic Modelling Method[END_REF]. Then, FDI standard techniques for evaluating the residuals could be used for fault detection in the form of a local procedure attached to every measured variable of the causal graph. More precisely, fault detection is implemented as an (online) procedure that determines, at each time t and for each measured variable y, the consistency of the measured value ȳt and the predicted value ŷt obtained with the -causal -behavioral model of the system. Checking consistency comes back to evaluate the residual:

r y t = ȳt -ŷt If r y t = 0, then y is concluded to be misbehaving, noted MISB(y), and this triggers a diagnostic session.

Diagnostic reasoning is a global procedure underpinned by the causal (2007). The detection of a misbehaving variable is interpreted as the violation of one of the influences involved in the prediction of the variable, i.e. of one of the upstream influences in the causal graph. Each influence being associated with a component, the set of upstream influences can be identified as an Rconflict as defined in section 2.2 (or as the support of the ARR that could be built from the local models by performing the variable eliminations indicated by the causal chains). In (Travé-Massuyès and Calderon-Espinoza, 2007), the influences have a delay attribute corresponding to the time required for a disturbance acting on the source variable to propagate to the effect variable. Figure 1, right side, provides the causal graph with delay labels for the reservoir system, which involves eight components Ci, i = 1, . . . , 8, shown on the left side. Influences are denoted I 1 to I 14 . With this information, the elements of the generated R-conflicts can be labeled by a temporal label indicating the latest time at which a component can be considered faulty, i.e. Ci τ indicates that the component Ci may be faulty from at least t-τ . Diagnoses can be obtained from the R-conflicts by an incremental HS-tree algorithm that generates the hitting sets, according to [START_REF] Reiter | A theory of diagnosis from first principles[END_REF], while managing the temporal labels [START_REF] Travé-Massuyès | Timed fault diagnosis[END_REF]. Figure 2 provides the HS-tree corresponding to the occurrence of two R-conflicts, C (dy 2 ) and C (dy 1 ), indicated by MISB(dy 2 ) at time t and MISB(dy 1 ) at time t + δt, respectively :

C (dy 2 ) = {C1 τ 1 +1 , C2 1 , C4 1 , C5 τ 1 +1 , C6 1 , C8 0 } C (dy 1 ) = {C1 1 , C2 τ 2 +1 , C3 1 , C5 1 , C6 τ 2 +1 , C7 0 }
The nodes of the HS-tree but leaves are labelled by a conflict set. For each element s in the conflict label of node n, an edge labelled s joins n to a successor node. H(n) is defined as the set of edge labels on the path from n to the root node. The HS-tree is built by considering every conflict in chronological order. Every new conflict is compared to every leaf of the HS-tree, and some new leaves are built if necessary. The resulting HS-tree is pruned for redundant or subsumed leaves before the next conflict is considered. At the end of the procedure, the minimal hitting sets, and hence the minimal diagnoses that explain the detected misbehaving variables, are given by the set of edge labels H(l) associated to the open leaves l of the HS-tree.

In our example, C (dy 2 ) is first developed from the Root node at time t. When the second conflict C (dy 1 ) is detected, at time t + δt, the temporal labels of the edge labels from the leaves to the Root are first updated by δt. Then, C (dy 1 ) is developed from nodes 3 and 6, given that for n ∈ {1, 2, 4, 5},

H(n) ∩ C (dy 1 ) = ∅.
The open leaves of the HS-tree determine the timed diagnoses given in Table 2.

Model-based diagnosis of hybrid systems

Hybrid systems [START_REF] Zaytoon | Systèmes dynamiques hybrides[END_REF][START_REF] Mcilraith | Hybrid systems diagnosis[END_REF][START_REF] Henzinger | The theory of hybrid automata[END_REF]Lunze and , Eds.) address the need to capture phenomema at different time scales in the same model. They are more particularly devoted to represent systems that have double continuous and discrete dynamics. Forming a specific class of hybrid systems, switched systems undergo abrupt changes of

= {C1 τ 1 +1 } D1 = {C1 τ 1 +1+δt } D2 = {C2 1 } D2 = {C2 τ 2 +1 } D3 = {C4 1 } D3 = {C5 τ 1 +1+δt } D4 = {C5 τ 1 +1 } D4 = {C6 τ 2 +1 } D5 = {C6 1 } D5 = {C4 1+δt , C3 1 } D6 = {C8 0 } D6 = {C4 1+δt , C7 0 } D7 = {C8 0+δt , C3 1 } D8 = {C8 0+δt , C7 0 }
dynamics upon switches. They are particularly relevant to diagnosis because switching dynamics is just representative of fault occurrence. Switched systems may be modeled by a state transition system whose states represent the modes of operation -normal or faulty -for which the continuous dynamics are specified. The modeling of such systems and the associated diagnostic algorithms make use of continuous and discrete formalisms, defining an ideal field for the integration of FDI and DX methods. In this case, the emphasis is on coupling the search methods used by DX with FDI methods in the form of state estimators, parameter estimators or sets of ARRs. Search methods allow one to deal with the combinatorial explosion of the number of trajectories to be tracked. FDI methods can also be coupled with discrete event system methods that are investigated in both the FDI and DX communities.

In the DX community, researchers dealing with hybrid systems first tried to abstract the continuous dynamics in qualitative terms. The Livingstone diagnostic engine [START_REF] Pell | An autonomous spacecraft agent prototype[END_REF]; [START_REF] Williams | A model-based approach to reactive selfconfiguring systems[END_REF], from NASA, that flew on board the DS-1 probe, was among the first to be qualified as hybrid. This engine was rooted in the DX approach, with a model written in propositional logic, and behavioral equations reflecting the continuous dynamics in the form of logical relationships expressing qualitative constraints. The qualitative abstraction required monitors between the sensors and the model to interpret continuous signals in terms of discrete modalities. This approach suffered from two drawbacks : the thresholds were extremely difficult to determine, and detection sensitivity was quite poor. Subsequent research thus replaced the qualitative abstractions by classical differential equations, resulting in real hybrid models interlinking continuous and discrete states.

Although the different classes of hybrid models show differences in their formalization, a hybrid model may be exemplified by the following tuple, which makes explicit continuous and discrete dynamics as well as their interaction (Bayoudh et al., 2008a):

S = (ζ, Q, Σ, T, C, (q 0 , ζ 0 )) (3)
where:

• ζ is the set of continuous variables including state variables, input/output variables, and possibly noises, which are functions of time t. Some are measured, others not.

• Q is the set of discrete system states. Each state q i ∈ Q represents a mode of operation of the system.

• Σ = Σ s ∪Σ c ∪Σ f is the set of events including spontaneous mode switching events, discrete control inputs, and fault occurrences. Events corresponding to spontaneous mode changes are issued upon guards that depend on continuous variables, as defined below. Σ can be partitioned as Σ o ∪ Σ uo where Σ o represents the set of observable events and Σ uo represents the set of unobservable events. Σ f ⊆ Σ uo , Σ c ⊆ Σ o and Σ s may have elements in both sets.

• T ⊆ Q × Σ → Q is the partial transition function. A transition t(q i , σ ij , q j ) may be guarded by a condition given as a set of equations G(t(q i , σ ij , q j )) = g ij (x, θ g ) = 0, θ g being a constant parameter vector. Then σ ij results from the state x(t) hitting the guard g ij at some time instant t * and is not observable. A reset map R ij , possibly equal to the identity, is specified.

• C = i C i is the set of system constraints linking continuous variables. C i denotes the set of constraints associated to mode q i , which are given in state-space form by the following continuous time state-evolution and output equations:

ẋ(t) = f i (x(t), u(t), (t)) y(t) = g i (x(t), u(t), (t)) (4)
where u ∈ R nu , x ∈ R nx , y ∈ R ny are the input, output, state vectors, respectively, and ∈ R n denotes some noise vector. The variables gathered in these vectors belong to ζ.

• (ζ 0 , q 0 ) ∈ ζ × Q is the initial condition of the hybrid system.

In the hybrid state (ζ, Q), only the discrete state Q is representative of the operation mode of the system and estimating Q is hence the target of diagnosis. Because the evolution of discrete states is closely tied to the evolution of the continuous states, the diagnosis problem is often brought back to the problem of estimating the full hybrid state.

In theory, hybrid estimation must consider all the possible mode sequences with the associated continuous evolutions, which is exponentially complex. Consequently, many sub-optimal methods have been proposed, of which we can distinguish the following three classes:

• methods known as multiple-model estimation, rather rooted in the FDI field [START_REF] Ackerson | On state estimation in switching environments[END_REF][START_REF] Blom | The interacting multiple model algorithm for systems with markovian switching coefficients[END_REF][START_REF] Li | Multiple-model estimation with variable structure[END_REF],

• particle filtering methods [START_REF] De Freitas | Rao-blackwellised particle filtering for fault diagnosis[END_REF][START_REF] Verma | Real-time fault diagnosis[END_REF]Narasimhan et al., 2004a), which are found both in FDI and DX,

• methods that address hybrid aspects in a dedicated manner (Hofbaur and Williams, 2002b;[START_REF] Benazera | State tracking of uncertain hybrid concurrent systems[END_REF][START_REF] Narasimhan | An approach to model-based diagnosis of hybrid systems[END_REF][START_REF] Benazera | Set-theoretic estimation of hybrid system configurations[END_REF], taking advantage of FDI and DX approaches.

Multiple-model estimation methods

Multiple-model estimation methods, inspired by the IMM algorithm of [START_REF] Blom | The interacting multiple model algorithm for systems with markovian switching coefficients[END_REF], are formulated in a probabilistic framework. IMM considers the problem of estimating the state of a system with Markovian switching parameters:

x(t) = a(θ t )x(t -1) + b(θ t ) 1 (t) y(t) = h(θ t )x(t) + g(θ t ) 2 (t)) (5)
where θ t is a finite state Markov chain taking a finite number of N values according to a transition probability matrix, and 1 (t) and 2 (t) are mutually independent white Gaussian processes. IMM avoids the exponential growth of the number of Gaussian hypotheses by merging the hypotheses. Continuous estimates arising from N Kalman filters are merged according to a likelihood measure to provide a belief state in the form of a probability distribution over states at the current time. The likelihood measure is provided by every filter and expresses the degree of consistency between an hypothesis and observations but it takes also into account the information carried by the probabilities of transitions. The timing for merging is studied in [START_REF] Blom | The interacting multiple model algorithm for systems with markovian switching coefficients[END_REF], which provides an efficient procedure. In [START_REF] Washington | On-board real-time state and fault identification for rovers[END_REF], which suggests combining a process of continuous state estimation given by Kalman filters with an estimation process of the discrete state based on a POMDP (Partially Observed Markov Decision Process), the estimation method is successfully applied to fault identification on rovers. (Hofbaur and Williams, 2002b) also unifies continuous state estimators with a belief calculated from Hidden Markov Models (HMM). The approach is quite similar to the one of [START_REF] Washington | On-board real-time state and fault identification for rovers[END_REF] in that it uses a set of Kalman filters, but it adopts an aggressive strategy for adjusting the number of tracked trajectories to the computing resources available. This strategy uses an A * algorithm, which selects the most likely state trajectory branches and takes into account unknown fault modes. It is implemented in the hME engine by (Hofbaur andWilliams, 2002a, 2004).

Interestingly, it was shown by [START_REF] Benazera | Set-theoretic estimation of hybrid system configurations[END_REF]) that considering bounded instead of probabilistic uncertainty for noises and parameters of the continuous processes allows one to merge the hypotheses with the same discrete state estimate by computing the convex hull of continuous estimates. This kind of merging, only possible in a set-membership framework [START_REF] Milanese | Optimal estimation theory for dynamic systems with set membership uncertainty: an overview[END_REF][START_REF] Kieffer | Guaranteed estimation of the parameters of nonlinear continuous-time models: Contributions of interval analysis[END_REF] was implemented by interval analysis methods in [START_REF] Benazera | Set-theoretic estimation of hybrid system configurations[END_REF] and later in [START_REF] Ramdani | Computing reachable sets for uncertain nonlinear hybrid systems using interval constraint-propagation techniques[END_REF] and [START_REF] Maiga | A fast method for solving guard set intersection in nonlinear hybrid reachability[END_REF]. It controls effectively the number of tracked hypotheses and may avoid truncating/approximating the set of hypotheses.

Particle filtering methods

Particle filtering methods are based on simulation and a Bayesian update of prior beliefs. They proceed by sampling the initial probability distribution. The underlying principle is the approximation of the conditional state probability distribution p(x 0:t | y 0:t ) by a swarm of points called particles. These particles sample the state-space and carry a weight representing a discrete probability masse. Particles are generated and recursively updated given a nonlinear process model, which describes the evolution in time of the system under analysis, and a measurement model:

x(t) = f t (x(t -1), w(t)) y(t) = h t (x(t), v(t)) (6)
where {w(t)} t≥0 and {v(t)} t≥0 are sequences of random variables, not necessarily Gaussian, as well as a set of available measurements Y = {Y t , t ∈ N} and an initial estimation for the state probability density function p(x(0)).

With enough samples, particle filtering approaches the optimal Bayesian estimate while presenting the advantage to accept probability distributions of any kind. We refer the reader to [START_REF] Arulampalam | A tutorial on particle filters for online nonlinear/non-gaussian bayesian tracking[END_REF] for a tutorial on particle filtering methods. Despite their advantage, it should be noted that they are difficult to apply to the diagnosis problem since the probabilities of faults are generally very low compared to those of nominal states. The number of particles needed to track the faulty states is hence very high. Different strategies were tested to provide solutions to this problem [START_REF] Verma | Variable resolution particle filter[END_REF][START_REF] Thrun | Risk sensitive particle filters[END_REF]. Among them, (Narasimhan et al., 2004b) combines particle filtering and the DX based diagnosis approach Livingston L3 [START_REF] Williams | A model-based approach to reactive selfconfiguring systems[END_REF]; [START_REF] Kurien | Back to the future for consistency-based trajectory tracking[END_REF]. In this approach Rao-Blackwellized Particle Filtering is used to track the nominal behavior, an n-step prediction scheme is used for fault detection and L3 is used to generate a set of candidates that are consistent with the discrepant observations. This candidates are then tracked by the particle filtering scheme.

Hybrid system diagnosis dedicated methods

As we have seen before, the combinatorial explosion inherent to hybrid estimation leads to solutions providing an approximated belief state. All previous methods suffer from the problem of hypothesis loss, which may be critical for a diagnosis application. The set of modes estimated over time, i.e. the diagnoses, takes the form of a set Γ of trajectories generated by a decision process that abandons the trajectories whose belief is below a given threshold. Unfortunately, Γ is reused in the calculation of future estimates and it may happen that the actual trajectory of the system is no longer in Γ, thus producing an erroneous diagnosis. Several studies have addressed this problem. [START_REF] Nayak | Back to the future for consistency-based trajectory tracking[END_REF] proposes a solution based on a a posteriori progressive exploration of the space guided by fault ranks. However, this requires considering a large time window backwards from the current time, which may even include the initial time. In this case, the current state must be re-predicted from the whole system's history. The diagnostic engine KOALA [START_REF] Benazera | The Consistency approach to the on-line prediction of hybrid system configurations[END_REF] proposes a variant of the previous algorithm with a revision procedure that produces diagnoses from the current trajectory by performing minimal partial changes.

There have been other attempts to remedy the loss of solutions. In [START_REF] Lerner | Bayesian fault detection and diagnosis in dynamic systems[END_REF] [START_REF] Lerner | Monitoring a complex physical system using a hybrid dynamic bayes net[END_REF], the authors reduce the set of tracked trajectories by aggregating those using similar assumptions. In addition, they develop a smoothing strategy that propagates the current beliefs back in time to improve the prediction of system states.

Recently, an alternative approach to hybrid state estimation, called rME, was proposed based on the hybrid model (3). rME focuses on mode estimation, the actual diagnosis, and ignores continuous state estimation (Bayoudh et al., 2008c). rME is based on the parity space approach as presented in section 2.1 for processing continuous data. A set of ARRs is determined for each mode of the hybrid system from the associated continuous model. They are all put together in a vector. When evaluated with the measurements in a given mode, this vector defines its mode signature. The mode signature changes that result from transitioning from one mode to another are abstracted as a set of events, called signature-events, by the abstraction function f Sig :

f Sig : Q × T (Q, Σ) -→ Σ Sig (q i , q j ) -→ δ ij (7)
The event δ ij is observable and noted Ro ij if the mode signature of the source mode q i is different from the mode signature of the destination mode q j , i.e. Sig(q i ) = Sig(q j ). δ ij is unobservable and noted Ruo ij otherwise4 . Hence Σ Sig is partitionned in a set of observable signature-events Σ Sig o and a set of unobservable signature-events Σ Sig uo . The set Σ Sig = Σ Sig o ∪ Σ Sig uo is used to enrich the underlying DES M = (Q, Σ, T, q 0 ), producing an automaton that captures both the abstraction of the continuous dynamics and the discrete dynamics. A classical DES diagnosis approach, like the diagnoser approach [START_REF] Sampath | Diagnosability of discrete-event systems[END_REF], then permits to track the current mode of the system based on the received observable events, i.e. to provide the diagnosis.

Lately, the mode estimation rME approach (Bayoudh et al., 2008c) was combined with the state estimation approach hME [START_REF] Hofbaur | Hybrid estimation of complex systems[END_REF], resulting in mutual enrichment [START_REF] Rienmuller | Hybrid estimation through synergic mode-set focusing[END_REF][START_REF] Rienmüller | Mode set focused hybrid estimation[END_REF]. hME brings an estimate of the continuous state that is not provided by rME. In addition, among all modes corresponding to the current hypotheses of hME, rME can identify those that are consistent with observations, providing a reduced set of possible modes to hME and significantly reducing the number of hypotheses to be tracked by the hybrid estimator.

4 Bridges for learning diagnosis models : an example with chronicle learning from time series

The main weakness of MBD diagnosis approaches, either from FDI or from DX, is to require well-formalized models that must be built from the available knowledge about the system. However, knowledge may be scarce. On the other hand, nowadays systems generate big amounts of data that are stored. Data-driven diagnosis approaches take advantage of these data and use a whole spectrum of machine learning methods to directly assess the state of a system and provide a diagnosis. An alternative way is to use machine learning to generate models automatically, hence bridging with MBD diagnosis methods. Regression analysis is well-known for learning continuous models from measured time series but learning diagnosis-oriented discrete event models requires bridges with symbolic learning rooted in AI. This is a promising research track that can produce methods benefiting from all the available information in the form of data and knowledge.

To exemplify this track, let us consider the problem of generating discreteevent models automatically from raw data in the form of time series. Some works have built on classifiers to generate automata or Markov chain models, in which states represent operation modes of the system (Kempowsky et al., 2006a;[START_REF] Omlin | Fuzzy finite-state automata can be deterministically encoded into recurrent neural networks[END_REF]Kempowsky et al., 2006b). In this paper, we illustrate the generation of chronicles as used in the AI community [START_REF] Dousson | Discovering chronicles with numerical time constraints from alarm logs for monitoring dynamic systems[END_REF][START_REF] Cram | A complete chronicle discovery approach: application to activity analysis[END_REF].

We are interested in learning high level temporal patterns that capture the behavior of dynamic processes at an abstract level based on events. In the diagnosis context, these patterns can be used as signatures of specific situations and associated to decision rules specifying which actions must be taken in different situations [START_REF] Subias | Self-adapting strategies guided by diagnosis and situation assessment in collaborative communicating systems[END_REF].

Event-based abstraction

The system is assumed to be described through a set of features whose values change over time with the system's evolution. The data samples are given in terms of the set of features {χ 1 , . . . , χ n }. Every χ j takes its value in the set U j , called the domain of χ j . Therefore any sample can be represented by a vector

x = (x 1 , . . . , x n ) T of U = U 1 × • • • × U n ,
so that every component x j corresponds to the feature value χ j qualifying the object x. The subset of U formed by these vectors is called the data base.

Samples are indexed by time, a sample taken at time t i is represented by a vector x t i = (x 1 t i , . . . , x n t i ) T . The value taken by the feature χ j across time can be considered as a random variable x j t , t ∈ Z. Then the time series corresponding to the samples, taken from time t i to time t f , is noted

X t i -t f = { x t , t = t i , . . . , t f } = x t i , . . . , x t f .
Events are a symbolic representation of time-stamped specific singularities of the signals represented by the time series. The concept of event type expresses a change in the value of a given domain feature or set of features. Let us define E as the set of all event types and define the concept of event.

Definition 10 (Event) An event is defined as a pair (e i , t i ), where e i ∈ Σ is an event type and t i is an integer called the event date. Time representation relies on the time point algebra and time is considered as a linearly ordered discrete set of instants whose resolution is sufficient to capture the system's dynamics [START_REF] Vilain | Constraint propagation algorithms for temporal reasoning[END_REF].

Definition 11 (Temporal sequence) A temporal sequence on Σ is an ordered set of events denoted S = (e i , t i ) i∈N l = {(e i , t i )} i∈N l such that e i ∈ Σ, i = 1, . . . , l and t i < t i+1 , i = 1, . . . , l -1, where l is the dimension of the temporal sequence S.

The time series X t i -t f for a set of features can be abstracted in terms of a temporal sequence. This abstraction can be achieved as proposed in [START_REF] Aguilar-Castro | A chronicle learning approach for self-adapting strategies in collaborative communicating systems[END_REF] by applying clustering methods to the set of samples in X t i -t f . The samples are thus clustered into a set of classes. The conditions that underly the transitions between classes can then be used to define event types and the transition dates provide the event dates.

Chronicle concept

Chronicles have been introduced in AI as a way to express temporal information about a domain [START_REF] Dousson | Situation recognition: representation and algorithms[END_REF]. Chronicles are a rich formalism allowing one to describe observable event patterns corresponding to the behaviors one wants to detect. Most importantly, chronicles come together with powerful event recognition engines that are able to recognize them on the fly given a temporal sequence as input [START_REF] Artikis | Logic-based event recognition[END_REF]. With chronicles one may want to represent dynamic situations like :

-an event type e i is immediately followed by event type e j , -an event type e i is followed by event types e j and e k after less than 10 time units, -an event type e i occurs after 8 occurrences of an event type e j .

To represent this type of domain evolutions, we consider that event dates may be constrained. A time interval I is expressed as a pair I = [t -, t + ] corresponding to the lower and upper bound on the temporal distance between two time points t i and t j , i ≤ j. Given two event dates t i and t j , we express temporal constraints of the form t j -t i ∈ [t -, t + ]. Consider two events (e i , t j ) and (e j , t j ), then if their dates t i and t j satisfy the temporal constraint t j -t i ∈ [t -, t + ], we write τ ij = e i [t -, t + ]e j and say that the events are temporally constrained by τ ij .

Definition 12 (Chronicle) A chronicle is a pair C = (E, T ) such that E ⊆ Σ and T = {τ ij } 1 i<j<|E| . E is called the typology of the chronicle and T is the set of temporal constraints of the chronicle.

A chronicle C represents an evolution pattern involving a subset of events E and a set of temporal constraints T linking event dates. Chronicles are a special type of temporal pattern, where the temporal order of events is quantified with numerical bounds and reflects the represented piece of temporal evolution. Figure 5

Learning chronicles

Let us consider a temporal sequence S corresponding to a given dynamic situation. The goal is to learn the chronicle(s) that best characterize this situation from S. A commonly used approach to elaborate a solution for this problem relies on the notion of frequency.

Definition 14 (Frequency of a chronicle in a temporal sequence) The frequency of a chronicle C in a temporal sequence S, noted f (C|S), is the number of instances of C in S.

It is understood that most frequent chronicles are those that supposedly best represent the situation. On the other hand, given a set of event types Σ, the space of possible chronicles can be structured by a generality relation.

Definition 15 (Generality relation among chronicles)

A chronicle C = (E, T ) is more general than a chronicle C = (E , T ), denoted C C , if E ⊆ E or ∀τ ij ∈ T , τ ij ⊇ τ ij .
Having defined the above concepts, the problem can be formulated as: given a temporal sequence S, find all less general chronicles C in S such that f (C|S) ≥ f th , where f th is a minimum frequency threshold. Symbolic learning methods like those proposed in [START_REF] Cram | A complete chronicle discovery approach: application to activity analysis[END_REF] can be used to solve this problem.

Chronicle mining is illustrated by figures 6 and 7. Figure 6 provides an example of three event sequences obtained from three time series corresponding to the same situation. Figure 7 gives the less general chronicle that characterizes the three sequences. In the last few years, accounting for fault analysis and diagnosis in the solutions produced for autonomous architectures on one side, and for maintenance architectures on the other side has been of concern. Diagnosis is thus seen as a piece of the puzzle that constitutes the whole fault management architecture. This section discusses the openings that exist and the challenges for future research bridges in these areas.

Autonomous architectures

During many years, the focus of the work dealing with autonomy has been put on planning and execution and a proper well-identified diagnosis module was absent from the proposed architectures [START_REF] Alami | An architecture for autonomy[END_REF][START_REF] Finzi | Model-based executive control through reactive planning for autonomous rovers[END_REF]. However, it is now more and more recognized that control and planning must cooperate with diagnosis so as to jointly solve the state tracking and decision problems as illustrated in the full template architecture of figure 8. The system is submitted to the controller actions, which are taken according to the plan decided by the Mission Planner, the current diagnoses provided by the Diagnoser and the plan elaborated by the Diagnosis Planner to disambiguate the diagnoses, i.e. to achieve active diagnosis. Two knowledge bases support the above mentioned tasks: the knowledge constituting the behavioral model of the system and the knowledge about the system mission. Examples of autonomous architectures that include a diagnoser can be found in (Williams et al., 2003;[START_REF] Verfaillie | A generic modular architecture for the control of an autonomous spacecraft[END_REF]. Although the presence of a diagnosis planner is still uncommon, examples can be found in [START_REF] Bayoudh | Active diagnosis of hybrid systems guided by diagnosability properties[END_REF][START_REF] Chanthery | An ao*-like algorithm implementation for active diagnosis[END_REF]. In this framework, the problem of fault tolerant control that refers to the interactions between the Diagnoser and the low level control, has been intensively studied by the Control community [START_REF] Blanke | Diagnosis and fault-tolerant control[END_REF]. Tools for deciding about system reconfigurability have been proposed as well as solutions to reconfigure control laws on line in order to guarantee the stability of the system and to keep the state of the system close to the desired state even when a fault occurs.

Nowadays challenges involve bridging diagnosis with high level planning. In the following, two types of interactions that involve the Diagnoser are analysed, those for which diagnosis serves planning, known as plan diagnosis, and those for which planning acts for improving diagnosis, known as active diagnosis.

Diagnosis for planning : plan diagnosis

Planning generates a control program, also known as a plan, which describes the sequence of actions necessary to achieve some pre-defined goals. Traditionally, the planning community works with the assumption of full observability [START_REF] Ghallab | Automated Planning: theory and practice[END_REF]. In practice, this assumption must be relaxed to consider partial observability, a situation that is more likely to be encountered in reality and where having diagnosis capabilities becomes essential [START_REF] Benazera | On the articulation of planning and diagnosis[END_REF].

Diagnosis serves in determining which action(s) failed and what went wrong in terms of the internal states of the system so that the system can possibly recover from the fault(s). [START_REF] De Jonge | Diagnosis of multi-agent plan execution[END_REF] introduced two general types of plan diagnosis: primary plan diagnosis identifying the incorrect or failed execution of actions, and secondary plan diagnosis that identifies the underlying causes of the faulty actions. This two types were later extended with agent diagnosis by [START_REF] Micalizio | Plan diagnosis and agent diagnosis in multi-agent systems[END_REF] because the problem of plan diagnosis is commonly formulated within a distributed perspective where each "agent" is responsible for a part of the total plan. In this context, [START_REF] Witteveen | Diagnosis of single and multi-agent plans[END_REF] showed how plan-diagnoses of the partial plans are related to diagnoses of the total plan and how global diagnoses can be obtained in a distributed way. Further work has considered challenging partial observability situations in which available information may not be enough for univocally determining the outcome of the actions that are executed [START_REF] Micalizio | Agent cooperation for monitoring and diagnosing a map[END_REF].

In the above works, actions are considered instantaneous. But real-world systems and processes (e.g. motors, actuators) operate dynamically in continuous time, denoted t. To know what is happening on such systems, we often need to make measurements using a sampling time, denoted t k , k ∈ N, at a sampling interval T s . When the behaviour of the system is abstracted for reasoning, and particularly for planning, both continuous time and sampling time considerations are not of immediate relevance. Rather, we are interested in what is happening at logical time (l), e.g. action execution cycle points (l act ) or observation time points (l obs ). Time considerations and different time scales are hence essential if one wants to consider the continuous dynamics effects. But considering nominal and fault models as continuous models has major implications on how planning and diagnosis are handled. Time must be introduced into the models of actions, i.e. actions must have a duration, allowing the specification of continuous dynamics in operation for the actions involved. On the other hand, the planning formalism must be able to express and handle temporal constraints. Let us notice that [START_REF] Micalizio | Intelligent supervision for robust plan execution[END_REF] considers plans with durative actions, although time is not continuous. The objective of this work is to prevent problems rather than repair them : when a temporal behavioral pattern expresses a deviation with respect to the nominal expected behavior, the modality of execution of the current action may be changed. Requirements about time and the problem of unifying diagnosis and planning models are still quite open and call upon novel developments.

Planning for diagnosis : active diagnosis

Active diagnosis is another aspect of the picture in which diagnosis and decision theories can cooperate. Active diagnosis relies on applying specific inputs to the system so that additional symptoms that permit refining the diagnosis are exhibited.

For DES, [START_REF] Sampath | Active diagnosis of discrete-event systems[END_REF] can be cited as the seminal work. A DES is modeled by an automaton, and active diagnosis is formulated as a supervisory control problem as defined in [START_REF] Ramadge | The control of discrete event systems[END_REF]. The idea of this approach is to design the controller so that specific actions that may drive the system into non diagnosable regions are forbidden. Diagnosability of the system at run time relies on the controller design performed off-line. The system is hence maintained "actively" diagnosable and its diagnoser produces non ambiguous outputs. In other words, active diagnosis is achieved by preventing inappropriate control actions. [START_REF] Daigle | Improving diagnosability of hybrid systems through active diagnosis?[END_REF] argues that active diagnosis requires both prevention and execution of actions and combines the two above perspectives, building on preliminary ideas presented in (Bayoudh et al., 2008b), and those of [START_REF] Sampath | Active diagnosis of discrete-event systems[END_REF]. Active diagnosis is split into two parts, a diagnoser and a controller that aims to compute an appropriate sequence of mode change control actions to best satisfy the control and diagnosis objectives.

The so-called pervasive diagnosis paradigm proposed in [START_REF] Kuhn | Pervasive diagnosis: The integration of diagnostic goals into production plans[END_REF] is based on different ideas, while still coupling diagnosis and planning. Because the planner is generally allowed to achieve mission goals in multiple ways, [START_REF] Kuhn | Pervasive diagnosis: The integration of diagnostic goals into production plans[END_REF] proposes a heuristic search for informative plans, which are the plans that provide best diagnosability. Here, no specific active diagnosis actions are synthesized. Finally, the safe diagnosability and active safe diagnosis approach defined by [START_REF] Paoli | Safe diagnosability for fault-tolerant supervision of discrete-event systems[END_REF] for DES and later extended by [START_REF] Liu | Safe diagnosability of stochastic discrete event systems[END_REF] to stochastic DES aims to achieve fault diagnosis prior to the execution of a given set of forbidden actions in the failed mode of operation of the system, hence preventing faults from developing into failures that could cause safety hazards. Unlike these two latter works, the approach of [START_REF] Bayoudh | Active diagnosis of hybrid systems guided by diagnosability properties[END_REF]) adopts the perspective that the operation of the system can be suspended, and that it is up to a decision module to decide whether it is best to continue operating the system or to run an active diagnosis session. The sequence of actions to be executed for active diagnosis hence do not interlink with actions dedicated to control. It is also different from [START_REF] Sampath | Active diagnosis of discrete-event systems[END_REF] in that regions of poor diagnosability are accepted because these are common for many systems in practice. When the system is in an ambiguous diagnosis state, active diagnosis relies on executing actions to drive the system towards more diagnosable regions. The method achieves the best possible diagnosis refinement, although it may happen that diagnosability cannot be improved.

In the hybrid framework, both continuous and discrete control actions can be used, in an interlinked way, to perform active diagnosis. These interlinked actions ultimately act towards putting the system in a goal configuration, i.e. a goal behavioral mode, by driving it through a selected sequence of intermediary operation modes.

In [START_REF] Bayoudh | Active diagnosis of hybrid systems guided by diagnosability properties[END_REF][START_REF] Chanthery | An ao*-like algorithm implementation for active diagnosis[END_REF] active diagnosis is formulated as a conditionnal planning problem. Starting with an ambiguous diagnosis state, a sequence of control actions that sequencially reduce the ambiguity of an initial diagnosis is delivered. To do so, given an initial uncertain state q D 1 , an active diagnoser5 is interpreted as an AND-OR graph rooted in q D 1 . The states with multiple outgoing transitions initiating sequences of consecutive controllable events c i are interpreted as "OR" nodes (squares in Figure 9), the states whose outgoing transitions are labelled with induced events ic i , i.e. induced by the continuous dynamics, are interpreted as "AND" nodes (circles in Figure 9). Then, planning algorithms rooted in the AI field can be applied to solve the conditional planning problem, for instance the classical MINIMAX algorithm [START_REF] Russell | Artificial intelligence: a modern approach[END_REF] or an AO*-type algorithm as proposed in [START_REF] Chanthery | An ao*-like algorithm implementation for active diagnosis[END_REF]. [START_REF] Mehra | Optimal input signals for parameter estimation in dynamic systems-survey and new results[END_REF][START_REF] Jauberthie | Optimal input design for a nonlinear dynamical uncertain aerospace system[END_REF].

Maintenance architectures

In maintenance programs, diagnosis appears as an ingredient for achieving condition monitoring and allows one to make adjusted predictions about the remaining useful life (RUL) of the system and its components. From this information, maintenance actions can be scheduled at best.

Prognostic is often the result of some reliability statistics drawn for an entire population of components of a given category from a set of scenarios implementing different stress conditions [START_REF] Vachtsevanos | Intelligent fault diagnosis and prognosis for engineering systems[END_REF][START_REF] Saxena | Metrics for offline evaluation of prognostic performance[END_REF]. The failure time of a system is represented by a random variable X for which the probability density function (pdf) is obtained from statistical prediction analyses. The probability for a system's RUL to be lower than a time t p is hence given by:

P (X ≤ t p ) = tp 0 f (t)dt, (8)
where f (t) represents the failure time pdf. The failure rate of a system, noted F (t), represents the probability for the system to fail in the time interval ]t, t + dt] given that it was sane at time t : F (t)dt = P (X ≤ t + dt|X > t)

= P (t<X≤t+dt) P (X>t)

.

(9)

For a specific component in operation, it is possible to assess its current healh status, resulting from the specific stress it undergoes, and this is where diagnosis comes into play. Diagnosis provides a regularly updated health status of specific components that can be used to update the initial state for predicting their RULs [START_REF] Ribot | Diagnosis and prognosis for the maintenance of complex systems[END_REF][START_REF] Ribot | Prognostics for the maintenance of distributed systems[END_REF][START_REF] Mohanty | Adaptive residual useful life estimation of a structural hotspot[END_REF][START_REF] Hedjazi | From chemical process diagnosis to cancer prognosis: an integrated approach for diagnosis and sensor/marker selection[END_REF]. Health status updating prognosis differs from prognosis performed from reliability analyses and it is sometimes called "adaptive prognosis". In most model-based prognosis literature [START_REF] Orchard | A particle-filtering approach for on-line fault diagnosis and failure prognosis[END_REF][START_REF] Daigle | Model-based prognostics with concurrent damage progression processes[END_REF][START_REF] Bregon | An integrated framework for model-based distributed diagnosis and prognosis[END_REF], it is understood that diagnosis is a necessary part of the architecture, so adaptive is generally omitted.

Diagnosis determines the state of the system, and of each of its components, as being consistent with the current observations, then prognosis can determine the state that will be reached in the future and that is consistent with the current diagnosis and with the ageing model of the system. The RUL can then be evaluated for every component in adaptation with the health status reported by diagnosis. Although diagnosis injects precision, the future stress conditions are inherently uncertain, resulting in uncertain RUL estimation. Scheduling maintenance actions from this information hence requires sophisticated algorithms to which the AU community contributes [START_REF] Pinedo | Scheduling: theory, algorithms, and systems[END_REF]. Other tools that are generally used in this area are statistics, machine learning and estimation methods.

Conclusion

In this paper, different facets of diagnosis investigated in the Control or the AI fields are discussed. Diagnosis benefits from a wide spectrum of methods and each of them brings in different potentialities. Having the whole picture helps understand the different variants of the diagnosis problem in relation with the different application domains. This is also essential to propose suitable and relevant solutions to real diagnosis problems.

This paper does not survey the different diagnosis approaches (see (Venkatasubramanian et al., 2003c,a,b) for a survey of this kind) but it surveys the "bridging" works that integrate approaches from the Control or the AI fields.

The model-based FDI and DX tracks are given special attention because they can be put in correspondence when they seem to have nothing in com-mon on the surface. Their comparative analysis is quite instructive and the lessons learned from this exercise are pointed out. The different hypotheses adopted by the two communities can be explained by their historical background. The Control community approaches the diagnosis problem from the fault detection point of view, providing numerous efficient methods to cope with stochastic or error bounded noisy and disturbed systems, whereas the AI community is prone to use abstract symbolic models that can support diagnosis reasoning, understood here as fault isolation. This is why hybrid models, that combine continuous and discrete paradigms, open nice perspectives for bridging diagnosis approaches from these two fields.

In section 4, learning the models that support diagnosis reasoning is shown to be a rich field for bridging theories. The machine learning methods that are the foundations of process history diagnosis-based methods can be exploited to build sophisticated models that can then support more sophisticated diagnosis reasoning. This is illustrated with the automatic generation of chronicles in section 4.3. Classification methods are commonly applied to historical data to provide a means to recognize on-line the operation mode of a system. It is shown that it can be used to learn sequences of events instead. Submitting these sequences to a second learning level allows one to generate temporal patterns that characterize the dynamic behavior of the system. Interestingly, these patterns capture the dynamics, which was not the case when producing the diagnosis directly from the classification.

Finally, diagnosis is discussed in relation with theories that participate to provide global solutions to fault management problems. The interactions of diagnosis with other modules, such as planning in autonomous architectures or prognosis in condition maintenance architectures, is key to the efficiency of such architectures. It is indeed the role of diagnosis to estimate the updated health status of the system and its components, henceforth allowing to make relevant and timely decisions. There is still work to be done before achieving perfectly unified frameworks in which diagnosis and the other tasks share the same models or can rely on model transformation technologies to share the same knowledge base. This is an active field of research.

To conclude, diagnosis is concerned with interpreting and explaining the observations acquired on a given system. In AI, diagnosis is often qualified as endowing a system with a "conscience". Diagnosis is not only concerned with faults and faulty situations, but with the state of the system and why it is in that state. This paper points at several opportunities central to the development of the diagnosis field, and that require integrative solutions. These opportunities are numerous and will participate to the richness of the field in the next few years.

  2001 in the framework of DX'01, the 12th International workshop on Principles of Diagnosis, Sansicario, Via Lattea, Italy, 5-9 Mars 2001 (DX'01, 2001).

Figure 1 :

 1 Figure 1: (left) Reservoir system (right) Causal graph with delay labels (from (Travé-Massuyès and Calderon-Espinoza, 2007))

Figure 2 :

 2 Figure 2: HS-tree with management of temporal labels (from (Travé-Massuyès and Calderon-Espinoza, 2007))

Figure 3 :

 3 Figure 3: Event-based abstraction with LAMDA

  is an example of chronicle in which E = {e 1 , e 2 , e 3 } and T = {τ 13 = e 1 [3, 6]e 3 , τ 23 = e 2 [3, 9]e 3 }.

Figure 5 :

 5 Figure 5: Example of chronicle

Figure 6 :

 6 Figure 6: Example of three event sequences obtained from time series of the same situation

Figure 8 :

 8 Figure 8: Autonomy template architecture

Figure 9 :

 9 Figure 9: Interpretation of the active diagnoser as an AND-OR graph

Table 2 :

 2 Timed diagnoses updated in time (from (Travé-Massuyès and Calderon-Espinoza, 2007)) Diagnoses at time t Diagnoses at time t + δt D1

This framework has been extended to fault models in[START_REF] Kleer | Characterizing diagnoses and systems[END_REF].

The hitting sets of a collection of sets are given by the sets that intersect every set of the collection.

Bridging the FDI and DX approachesBuilding on lessons learned, several works have integrated FDI and DX methods for providing new diagnostic solutions. This section illustrates these integrations with two specific lines, which are the most representative of the emerging synergies.

By construction, mode signatures cannot change while being in the same mode.

The active diagnoser is obtained from the diagnoser[START_REF] Sampath | Diagnosability of discrete-event systems[END_REF] by constraining the outgoing transitions of a state to those labelled by events (i.e. actions) permitted in all the underlying original automaton states[START_REF] Bayoudh | Active diagnosis of hybrid systems guided by diagnosability properties[END_REF]