Proceedings of the 26th International Workshop on Principles of Diagnosis (DX-15)
August 31-September 3, 2015
Yannick Pencole, Louise Trave-Massuyes, Philippe Dague, Editors The International Workshop on Principles of Diagnosis is an annual event that started in 1989, originating in the Arti cial Intelligence community. Its focus is on theories, principles and computational techniques for diagnosis, monitoring, testing, recon guration and repair of complex systems and applications of these techniques to real world problems.
This year, DX-15 received 41 submissions (39 full papers and 2 tool papers) from 15 countries, from 5 continents. Each paper was thoroughly peer reviewed by three reviewers. We accepted 17 regular papers (selection rate 43.6%), 18 posters and 2 benchmark/tool papers. We wish to thank all the authors of submitted papers, the program committee members for the time and e ort spent, the invited speakers for their participation.
As the DX-15 workshop is co-located with the IFAC International Symposium SAFEPROCESS 2015, its organization would not have been possible without the full support of the SAFEPROCESS organization team and especially Vincent Cocquempot who did a tremendous coordination job between the two events. Also special thanks to our local contact Nazih Mechbal at Ecole Nationale Superieure d'Arts et Metiers (ENSAM), ParisTech, where DX-15 and SAFEPROCESS take place. Thanks also to the local organization team at LAAS-CNRS and at the CNRS administrative department of Toulouse (DR14) for their full technical and administrative support.
We also wish to thank our sponsors: Centre National de la Recherche Scienti que (CNRS), Universite de Toulouse), Laboratoire de Recherche en Informatique, Universite Paris-Sud, Ecole Nationale Superieure d'Arts et Metiers (ENSAM), Institut National des Sciences Appliquees de Toulouse (INSAToulouse), Universite Pierre et Marie Curie (UMPC), and ACTIA.
Yannick Pencole, Louise Trave-Massuyes, Philippe Dague.
Word cloud generated from the titles of the DX-15 papers by http://www.wordle.net. Workshop Organization
LAAS-CNRS, Universite Paul Sabatier, Univ. Federale Toulouse, France LAAS-CNRS, INSA Toulouse, Univ. Federale Toulouse, France
LAAS-CNRS, INSA Toulouse, Univ. Federale Toulouse, France
ADS2 : Anytime Distributed Supervision of Distributed Systems that Face Unreliable or Costly Communication by Herpson Cedric, El Fallah Seghrouchni Amal, Corruble Vincent Data Driven Modeling for System-Level Condition Monitoring on Wind Power Plants by Eickmeyer Jens, Li Peng, Givehchi Omid, Pethig Florian, Niggemann Oliver Using Incremental SAT for Testing Diagnosability of Distributed DES by Ibrahim Hassan, Dague Philippe, Simon Laurent Improving Fault Isolation and Identi cation for Hybrid Systems with Hybrid Possible Con icts by Bregon Anibal, Alonso-Gonzalez Carlos, Pulido Belarmino State estimation and fault detection using box particle ltering with stochastic measurements by Blesa Joaquim, Le Gall Francoise, Jauberthie Carine, Trave-Massuyes Louise Minimal Structurally Overdetermined Sets Selection for Distributed Fault Detection by Khorasgani Hamed, Biswas Gautam, Jung Daniel Condition-based Monitoring and Prognosis in an Error-Bounded Framework by Trave-Massuyes Louise, Pons Renaud, Ribot Pauline, Pencole Yannick, Jauberthie Carine Con guration as Diagnosis: Generating Con gurations with Con ict-Directed A* - An Application to
by Grigoleit Florian, Struss Peter Decentralised fault diagnosis of large-scale systems: Application to water transport networks by Puig Vicenc, Ocampo-Martinez Carlos 3 11 19 27 35 43 51 59 67 75 83 91 99 Self-Healing as a Combination of Consistency Checks and Conformant Planning Problems by Grastien Alban
by Stern Roni, Kalech Meir, Shinitzky Hilla Formulating Event-Based Critical Observations in Diagnostic Problems by Christopher Cody, Grastien Alban
by Provan Gregory, Feldman Alexander
A General Process Model: Application to Unanticipated Fault Diagnosis by Wang Jiongqi, He Zhangming, Zhou Haiyin, Li Shuxing
by Carrera Rolando, Verde Cristina, Cayetano Raul Automatic Model Generation to Diagnose Autonomous Systems by Santos Simon Jorge, Muhlbacher Clemens, Steinbauer Gerald Methodology and Application of Meta-Diagnosis on Avionics Test Benches by Cosse Ronan, Berdjag Denis, Piechowiak Sylvain, Duvivier David, Gaurel Christian
by Koitz Roxane, Wotawa Franz Fault Tolerant Control for a 4-Wheel Skid Steering Mobile Robot by Fourlas George, Karras George, Kyriakopoulos Kostas 105
by Abreu Rui, Bobrow Daniel, Eldardiry Hoda, Feldman Alexander, Hanley John, Honda Tomonori, 193 De Kleer Johan, Perez Alexandre, Archer Dave, Burke David A Structural Model Decomposition Framework for Hybrid Systems Diagnosis by Daigle Matthew, Bregon Anibal, Roychoudhury Indranil Device Health Estimation by Combining Contextual Control Information with Sensor Data by Honda Tomonori, Liao Linxia, Eldardiry Hoda, Saha Bhaskar, Abreu Rui, Pavel Radu, Iverson Jonathan On the Learning of Timing Behavior for Anomaly Detection in Cyber-Physical Production Systems by Maier Alexander, Niggemann Oliver, Eickmeyer Jens The Case for a Hybrid Approach to Diagnosis: A Railway Switch by Matei Ion, Ganguli Anurag, Honda Tomonori, De Kleer Johan Design of PD observer-based fault estimator using a descriptor approach by Krokavec Dusan, Filasova Anna, Liscinsky Pavol, Serbak Vladimir Chronicle based alarm management in startup and shutdown stages by Vasquez John William, Trave-Massuyes Louise, Subias Audine, Jimenez Fernando, Agudelo Carlos
by Mishali Amir, Stern Roni, Kalech Meir Faults isolation and identi cation of Heat-exchanger/ Reactor with parameter uncertainties by Zhang Mei, Dahhou Boutaeb, Cabassud Michel, Li Ze-Tao LPV subspace identi cation for robust fault detection using a set-membership approach: Application to the wind turbine benchmark by Chouiref Houda, Boussaid Boumedyen, Abdelkrim Mohamed Naceur, Puig Vicenc, Aubrun Christophe
by Monrousseau Thomas, Trave-Massuyes Louise, Le Lann Marie-Veronique
by Pencole Yannick HyDiag: extended diagnosis and prognosis for hybrid systems by Chanthery Elodie, Pencole Yannick, Ribot Pauline, Trave-Massuyes Louise 217 225 235 241 247 253 261 269 277 281 Proceedings of the 26th International Workshop on Principles of Diagnosis
Regular papers
1 Proceedings of the 26th International Workshop on Principles of Diagnosis
2 A Divide-And-Conquer-Method for Computing Multiple Conflicts for Diagnosis Kostyantyn Shchekotykhin1 and Dietmar Jannach2 and Thomas Schmitz2 1Alpen-Adria University Klagenfurt, Austria e-mail: kostyantyn.shchekotykhin@aau.at
2TU Dortmund, Germany e-mail: {firstname.lastname}@tu-dortmund.de
In classical hitting set algorithms for ModelBased Diagnosis (MBD) that use on-demand conflict generation, a single conflict is computed whenever needed during tree construction. Since such a strategy leads to a full “restart” of the conflict-generation algorithm on each call, we propose a divide-and-conquer algorithm called MERGEXPLAIN which efficiently searches for multiple conflicts during a single call.
The design of the algorithm aims at scenarios in
which the goal is to find a few leading diagnoses
and the algorithm can – due to its non-intrusive
design – be used in combination with various
underlying reasoners (theorem provers). An
empirical evaluation on different sets of benchmark
problems shows that our proposed algorithm can
lead to significant reductions of the required
diagnosis times when compared to a
“one-conflict-ata-time” strategy.
1
In Model-Based Diagnosis (MBD), the concept of conflicts
describes parts of a system which – given a set of
observations – cannot all work correctly. Besides MBD, the
calculation of minimal conflicts is a central task in a number of
other AI approaches [
Over time, the principle of this MBD approach was used for a number of different diagnosis problems such as electronic circuits, hardware descriptions in VHDL, program specifications, ontologies, and knowledge-based systems[3; 4; 5; 6; 7]. A reason for the broad utilization of hitting set approaches is that its principle does not depend on the underlying knowledge representation and reasoning technique, because only a general Theorem Prover (TP) – a component that returns conflicts – is needed.
The implementation of a TP can be done in different ways. First, the conflict detection can be implemented as a reasoning task, e.g., by modifying a consistency checking algorithm [8; 9]. Second, “non-intrusive” conflict detection techniques can be used with a variety of reasoning approaches, since they require only a very limited reasoning functionality like consistency or entailment checking without knowing the internals of the reasoning algorithm. Such methods can benefit from the newest improvements in reasoning algorithms, such as incremental solving, heuristics, learning strategies, etc., without any modifications.
A non-intrusive conflict detection algorithm which has
shown to be very efficient in different application
scenarios is Junker’s QUICKXPLAIN [
In many classical hitting set based approaches, conflicts
are computed individually with QXP during HS-tree
construction when they are required, as in many domains not
all conflicts are known in advance [
In this paper, we propose MERGEXPLAIN (MXP for
short), a divide-and-conquer algorithm which searches for
multiple conflicts during a single decomposition run. Our
method is built upon QXP and is therefore also
nonintrusive. The basic idea behind MXP is that (a) the early
identification of multiple conflicts can speed up the overall
diagnosis process, e.g., due to better conflict “reuses” [
The paper is organized as follows. After a problem
characterization in Section 2, we present the details of MXP in
Section 3 and discuss the properties of the algorithm.
Section 4 presents the results of an extensive empirical
evaluation using various diagnosis benchmark problems. Previous
work is finally discussed in Section 5.
2
We use the definitions of[
Definition 1 (System). A system is a pair (SD, COMPS) where SD is a system description (a set of logical sentences) and COMPS represents the system’s components (a finite set of constants). A diagnosis problem arises when a set of logical sentences OBS, called observations, is inconsistent with the normal behavior of the system (SD, COMPS). The correct behavior is represented in SD with an “abnormal” predicate AB/1. That is, for any component ci ∈ COMPS the literal ¬AB(ci) represents the assumption that the component ci behaves correctly.
Definition 2 (Diagnosis). Given a diagnosis problem (SD, COMPS, OBS), a diagnosis is a minimal set Δ ⊆ COMPS such that SD ∪ OBS ∪ {AB(c)|c ∈ Δ} ∪ {¬AB(c)|c ∈ COMPS\Δ} is consistent.
A diagnosis therefore corresponds to a minimal subset of the system components which, if assumed to be faulty (and thus behave abnormally) explain the system’s behavior, i.e., are consistent with the observations.
Two general classes of MBD algorithms exist. One relies
on direct problem encodings and the aim is often to find one
diagnosis quickly, see [12; 13; 14]. The other class relies on
the computation of conflicts and their hitting sets (see next
section). Such diagnosis algorithms are often used when the
goal is to findmultiple or all minimal diagnoses. In the
context of our work, techniques of the second class can
immediately profit when the conflict generation process is done
more efficiently.
Finding all minimal diagnoses corresponds to finding all
minimal hitting sets (HS) of all existing conflicts [
Assuming that all components of a conflict work correctly therefore contradicts the observations. A conflict CS is minimal, if no proper subset of CS is also a conflict.
To find the set ofall minimal diagnoses for a given
problem, [
QUICKXPLAIN (QXP)
QXP was developed in the context of inconsistent constraint
satisfaction problems (CSPs) and the computation of
explanations. E.g., in case of an overconstrained CSP, the
problem consists in determining a minimal set of constraints
which causes the CSP to become unsolvable for the given
inputs. A simplified version of QXP [
Algorithm 1: QUICKXPLAIN(B, C) Input: B: background theory, C: the set of possibly faulty constraints
Output: A minimal conflict CS ⊆ C
1 if isConsistent(B ∪ C) then return ‘no conflict’;
2 else if C = ∅ then return ∅;
3 return GETCONFLICT(B, B, C)
function GETCONFLICT (B, D, C)
if D 6= ∅ ∧ ¬ isConsistent(B) then return ∅;
if |C| = 1 then return C;
Split C into disjoint, non-empty sets C1 and C2
D2 ← GETCONFLICT (B ∪ C1, C1, C2)
D1 ← GETCONFLICT (B ∪ D2, D2, C1)
return D1 ∪ D2
Theorem 1 ([
The pseudo-code of MXP, which unlike QXP can return
multiple conflicts at a time, is given in Algorithm 2. MXP,
like QXP, is generally applicable to a variety of problem
domains. The mapping to the terminology used in MBD (SD,
COMPS, OBS) is straightforward as discussed in the previous
section. In the following, we will use the notation and
symbols from [
Note that there are applications of MBD in which the function isConsistent has to be “overwritten” to take the specifics of the underlying knowledge representation and reasoning system into account. The ontology debugging approach presented in [7] for example extends isConsistent with the verification of entailments of a logical theory. MXP can be used in such scenarios after the corresponding adaptation of the implementation of isConsistent.
Furthermore, MXP can be easily extended for cases in which the MBD approach has to support the specification of (multiple) test cases, i.e., sets of formulas that must be consistent or inconsistent with the system description, e.g., [21; 22]. MXP (Algorithm 2) accepts two sets of constraints as inputs, B as the assumed-to-be-correct set of background constraints and C, the possibly faulty components/constraints.
In case C∪B is inconsistent, MXP returns a set of minimal conflicts Γ by calling the recursive function FINDCONFLICTS in line 3. This function again accepts B and C as an input and returns a tuple hC0, Γi, where Γ is a set of minimal conflicts and C0 ⊂ C is a set of constraints that does not contain any conflicts, i.e., B ∪ C0 is consistent.
The logic of FINDCONFLICTS is similar to QXP in that we decompose the problem into two parts in each recursive call (lines 7–9). Differently from QXP, however, we look for conflicts in both splits C1 and C2 independently and then combine the conflicts that are eventually found in the two halves (line 10)1. If there is, e.g., a conflict in the first part and one in the second, FINDCONFLICTS will find them independently from each other. Of course, there might also be conflicts in C whose elements are spread across both C1 and C2, that is, the set C10 ∪ C20 ∪ B is inconsistent. This situation is addressed in lines 11–15. The computation of a minimal conflict is done by two calls to GETCONFLICT (Algorithm 1). In the first call this function returns a minimal set X ⊆ C10 such that X ∪C2∪B is a conflict (line 12). In line 13, we then 0 look for a subset of C20, say Y , such that Y ∪ X corresponds to a minimal conflict CS . The latter is added to Γ (line 15). In order to restore the consistency of C10 ∪ C20 ∪ B we have to remove at least one element α ∈ CS from either C10 or C20. Therefore, in line 14 the algorithm removes α ∈ X ⊆ CS from C10.
Note that MXP allows us to use different split functions in line 7. In our default implementation we use a function that splits the set of constraints C into two equal parts, i.e., split(n) = n/2, where |C| = n. In the worst case this split function results in a perfect binary tree with n leaves. Consequently, the total number of nodes is 2n − 1, which correspond to 2(2n − 1) consistency checks (lines 5 and 11). Other split functions might result in a similar number of consistency checks in the worst case as well, since in any case MXP has to traverse a binary tree with n leaves. For instance, the function split(n) = n − 1 results in a tree with one branch of the depth n − 1 and n leaves, that is, 2n − 1 nodes to traverse. However, while the number of nodes to explore might be comparable, the important point is that the computational costs for the individual consistency checks can be different depending on the splitting strategy. Under the reasonable assumption that consistency checking of smaller sets of constraints requires less time, the function split(n) = n/2 allows MXP to split the set of constraints faster, thus, improving the overall runtime. Consider a CSP consisting of six constraints {c0, ..., c5}. The constraint c0 is considered correct, i.e., B = {c0}. Let {{c0, c1, c3}, {c0, c5}, {c2, c4}} be the set of minimal conflicts. Algorithm 2 proceeds as follows (Figure 1).
Since the input CSP (B ∪ C) is not consistent, the algorithm enters the recursion. In the first step, FINDCONFLICTS partitions the input set (line 7) into the two subsets 1The calls in line 8 and 9 can in fact be executed in parallel.
Algorithm 2: MERGEXPLAIN(B, C) Input: B: background theory, C: the set of possibly faulty constraints
Output: Γ, a set of minimal conflicts 1 if ¬isConsistent (B) then return ‘no solution’; 2 if isConsistent (B ∪ C) then return ∅; 3 h_, Γi ← FINDCONFLICTS(B, C) 4 return Γ; function FINDCONFLICTS (B, C) returns tuple hC0, Γi if isConsistent(B ∪ C) then return hC, ∅i; if |C| = 1 then return h∅, {C}i; Split C into disjoint, non-empty sets C1 and C2 hC10, Γ1i ← FINDCONFLICTS(B, C1) hC20, Γ2i ← FINDCONFLICTS(B, C2) Γ ← Γ1 ∪ Γ2; while ¬isConsistent (C10 ∪ C20 ∪ B) do
X ← GETCONFLICT(B ∪ C20, C20, C10) CS ← X ∪ GETCONFLICT(B ∪ X, X, C20) C10 ← C10 \ {α} where α ∈ X Γ ← Γ ∪ {CS } return hC10 ∪ C20, Γi C1 = {c1,c2,c3} and C2 = {c4,c5} and provides them as input to the recursive calls (lines 8 and 9). In the next level of the recursion – marked with 2 in Figure 1 – the input is found to be inconsistent (line 5) and again partitioned into two sets (line 7). In the subsequent calls, 3 and 4 , the two input sets are found to be consistent (line 5) and, therefore, the set {c1, c2, c3} has to be analyzed using GETCONFLICT (lines 12 and 13) defined in Algorithm 1. GETCONFLICT returns the conflict { c1,c3}, which is added to Γ. Finally, FINDCONFLICTS removes c1 from the set C10 and returns the tuple h{c2,c3}, {{c1,c3}}i to 1 .
Next, the “right-hand” part of the initial input, the set C2 = {c4,c5}, is provided as input to FINDCONFLICTS 5 . Since C2 is inconsistent, it is partitioned into two sets C1 = {c4} and C2 = {c5}. The first recursive call 6 returns h{c4}, ∅i since the input is consistent. The second call 7 , in contrast, finds that the input comprises only one constraint that is inconsistent with the background theory B. Therefore, it returns h∅,{{c5}}i in line 6. Since C10 ∪ C20 = {c4} ∪ ∅ is consistent with B, FINDCONFLICTS 5 returns h{c4}, {{c5}}i to 1 .
Finally, in 1 the set of constraints C10 ∪ C20 = {c2,c3} ∪ {c4} is found to be inconsistent with B (line 11) and GETCONFLICT is called. The method returns the conflict { c2,c4} and c2 is removed from C10. The resulting set {c3,c4} is consistent and MXP returns Γ = {{c1,c3}, {c5}, {c2, c4}}. Theorem 2. Given a background theory B and a set of constraints C, Algorithm 2 always terminates and returns • ‘no solution’, if B is inconsistent, • ∅, if B ∪ C is consistent, and • a set of minimal conflicts Γ, otherwise.
Proof. In the first case, given an inconsistent background theory B, the algorithm terminates in line 1 and returns ‘no solution’. In the second case, if the set B ∪ C is consistent, C1 = {c1, c2, c3} C2 = {c4, c5} h{c2, c3} , {{c1, c3}}i 1 : h{c4} , {{c5}}i Γ = {{c1, c3} , {c5}} ∪ {{c2, c4}} C = {c3, c4} y C1 = {c1, c2} C2 = {c3} h{c1, c2} , ∅i 2 : h{c3} , ∅i Γ = ∅ ∪ {{c1, c3}} C = {c2, c3} %
C1 = {c4} C2 = {c5} 3 : iBsC∪oCns=ist{ecn0t, cX1, c2} 4 : iBsC∪oCns=ist{ecn0t, cX3} 6 : iBsC∪oCns=ist{ecn0t, cX4}
B ∪ C = {c0, c5} 7 : isConsistent |C| = 1 then no subset of C is a conflict. MXP terminates and returns ∅.
Finally, if the set B ∪ C is inconsistent, the algorithm enters the recursion in line 3. The function FINDCONFLICTS in each call partitions the input set C into two sets C1 and C2. The partitioning continues until either the found set of constraints C is consistent or a singleton conflict is detected. Therefore, every recursion branch ends after at most log |C|−1 calls. Consequently, FINDCONFLICTS terminates if the conflict detection loop in lines 11–15 always terminates.
We consider two situations. If the set C10 ∪ C20 is consistent with B, the loop terminates. Otherwise, in each iteration at least one conflict in the set C10 ∪ C20 is resolved. This fact follows from Theorem 1 according to which the function GETCONFLICT in Algorithm 1 always returns a minimal conflict if the input parameter C is inconsistent with B. Since the number of conflicts is finite and in each iteration one of the conflicts in C10 ∪ C20 is resolved in line 14, the loop will terminate after a finite number of iterations. Consequently, Algorithm 2 terminates and returns a set of minimal conflicts Γ.
Corollary 1. Given a consistent background theory B and a set of inconsistent constraints C, Algorithm 2 always returns a set of minimal conflicts Γ such that there exists a diagnosis Δi ⊆ SCSi∈Γ CS i.
The proof follows from the fact that – similar to the HStree algorithm – a conflict is resolved by removing one of its elements from the set of constraints C1 in line 14. The loop in line 11 guarantees that every conflict CS i ∈ C10 ∪ C20 is hit. Consequently, FINDCONFLICTS hits every conflict in the input set C and the set of constraints {α1, . . . , αn} removed in every call of line 14 is a superset or equal to a diagnosis of the problem. The construction of at least one diagnosis from the found conflicts Γ can be done by the HS-tree algorithm.
MXP can in principle use several strategies for the resolution of conflicts in line 14. The strategy used in MXP by default is conservative and allows us to find several conflicts at once. Two additional elimination strategies can be used in line 14: (1) C10 ← C10 \ X or (2) C10 ← C10 \ CS and C2 ← C20 \ CS . These more aggressive strategies result in 0 a smaller number of conflicts returned by MXP in each call but each call returns the results faster. However, for the latter strategies MXP might not return enough minimal conflicts for the HS-tree algorithm to compute at least one diagnosis. For instance, let {{c1, c2} , {c1, c3} , {c2, c4}} be the set of all minimal conflicts. If MXP returns Γ = {{c1, c2}}, which is one of the possible valid outputs, then the HS-tree algorithm fails to find a diagnosis as{c1, c2} must be hit twice. In this case, the HS-tree algorithm must call MXP multiple times or another algorithm for diagnosis computation must be used, e.g., [23].
Corollary 2. Algorithm 2 is sound, i.e., every set CS ∈ Γ is a minimal conflict, and complete, i.e., given a diagnosis problem for which at least one minimal conflict exists, Algorithm 2 returns Γ 6= ∅.
The soundness of the algorithm follows from Theorem 1, since the conflict computation of MXP uses the GETCONFLICT function of QXP. The completeness is shown as follows: Let B be a background theory and C a set of faulty constraints, i.e., B ∪ C is inconsistent. Assume MXP returns Γ = ∅, i.e., no minimal conflicts are found. However, this is impossible, since the loop in line 11 will never end. Consequently, Algorithm 2 will not terminate which contradicts our assumption. Hence, it holds that MXP is complete. 4
We have evaluated the efficiency of computing multiple conflicts at once with MXP using a number of different diagnosis benchmark problems. As a baseline for the comparison, we use QXP as a Theorem Prover, which returns exactly one minimal conflict at a time. Furthermore, we made measurements with a variant of MXP called PMXP in which the lines 8 and 9 are executed in parallel in two threads on a multi-core computer. 4.1 Benchmark Problems We made experiments with different benchmark problems.
First, we used the five first systems of the DX Competition (DXC) 2011 Synthetic Track. For each system, 20 scenarios are specified in which artificial faults were injected. In addition, we made experiments with a number of CSP problems from the CSP solver competition 2008 and several CSP encodings of real-world spreadsheets. The injection of faults was done in the same way as in [17].
In addition to these benchmark problems, we developed a diagnosis problem generator, which can be configured to generate (randomized) diagnosis problems with varying characteristics, e.g., with respect to the number of conflicts, their size, or their position in the system description SD. 4.2
Measurement Method We implemented all algorithms in a Java-based MBD framework, which uses Choco as an underlying constraint solver, see [17]. The experiments were conducted on a laptop computer (Intel i7, 8GB RAM). As a performance indicator we use the time needed (“wall clock”) for computing one or more diagnoses. The reported running time numbers are averages of 100 runs of each problem setting that were done to avoid random effects. We furthermore randomly shuffled the ordering of the constraints in each run to avoid effects that might be caused by a certain positioning of the conflicts in SD. For the evaluation of MXP we used the most aggressive elimination strategy (2) as described in Section 3.4.
Since MXP can return more than one conflict at a time, it is expected to be particularly useful when the problem is to find a set ofn first (leading) diagnoses, e.g., in the context of applying MBD to software debugging [5; 7]. We therefore report the results for the tasks “find-one-diagnosis” (as an extreme case) and “find-n-diagnoses”.
The task of finding a single diagnosis is comparably simple and “direct encodings” or algorithms like INVERSEQUICKXPLAIN [23] are typically more efficient for this task than the HS-tree algorithm. For instance, INVERSEQUICKXPLAIN requires only O(|Δ| log(|C|/|Δ|)) calls to TP.
If TP can check the consistency in polynomial time, then
one diagnosis can also be computed efficiently. The
problem of finding more than one diagnosis is very different and
computationally challenging, because deciding whether an
additional diagnosis exists is NP-complete [24]. In such
settings the application of methods that are highly efficient for
finding one diagnosis is not always advantageous. For
instance, the evaluation presented in [
Results DXC Benchmark Problems Table 1 shows the characteristics of the analyzed and CSP-encoded DXC benchmark problems. Since we consider multiple scenarios per system, the number of faults and the corresponding diagnoses can vary strongly across the experiment runs.
Table 2 shows the observed performance gains when using MXP instead of QXP in terms of absolute numbers (ms) and the relative improvement. For the problem of finding the first 5 diagnoses (QXP-5/MXP-5), the observed improvements range from 15% up to 45%. For the extreme case of finding one single diagnosis, even slightly stronger improvements can be observed. The improvements when searching for, e.g., the first 10 diagnoses are similar for cases in which significantly more than 10 diagnoses actually exist.
System #C #V #F #D #D |D| #Cf |Cf| 74182 21 28 4 - 5 30 - 300 139 4.66 4.9 3.3 74L85 35 44 1 - 3 1 - 215 66.4 3.13 5.9 8.3 74283 38 45 2 - 4 180 - 4,991 1,232.7 4.42 78.8 16.1 74181 67 79 3 - 6 10 - 3,828 877.8 4.53 7.8 10.6 c432 162 196 2 - 5 1 - 6,944 1,069.3 3.38 15.0 19.8
Constraint Problems / Spreadsheets The characteristics for the next set of benchmark problems (six CSP competition instances, five CSP-encoded real-world spreadsheets with injected faults [17]) are shown in Table 3.
Scenario #C #V #F #D |D| #Cf |Cf| c8 523 239 8 4 6.25 7 1.6 costasArray-13 87 88 2 >5 3.6 >565 45.6 domino-100-100 100 100 3 81 2 2 15 graceful–K3-P2 60 15 4 >117 2.94 >12 29.2 mknap-1-5 7 39 1 2 1 1 2 queens-8 28 8 15 9 10.9 15 2.8 hospital payment 38 75 4 40 4 4 3 profit calculation 28 140 5 42 4.25 11 9 course planning 457 583 2 3024 2 2 55.5 preservation model 701 803 1 22 1 1 22 revenue calculation 93 154 4 1452 3 3 15.7
The results for determining the five first minimal diagnoses are shown in Table 42. Again, performance improvements of up to 54% can be observed. The obtained improvements vary quite strongly across the different problem instances: the higher the complexity of the underlying problem, the stronger are the improvements achieved with our new method. Only in the two cases in which only one single conflict exists (see Table 3), the performance can slightly degrade as MXP performs an additional check if further conflicts among the remaining constraints exist.
Systematically Generated MBD Problems To be able to systematically analyze which factors potentially influence the obtained performance improvements, we developed an MBD problem generator in which we could vary (i) the
2The results for finding one diagnosis follow the same trend. Scenario c8 costasArray-13 domino-100-100 graceful–K3-P2 mknap-1-5 queens-8 hospital payment profit calculation course planning preservation model revenue calculation overall number of COMPS, (ii) the number of conflicts and their average size (and as a consequence the number of diagnoses), and (iii) the position of the conflicts in the database.
We considered the last aspect because the performance of QXP and MXP can largely depend on this aspect3. If, e.g., there is only one conflict and the conflict is represented by the two “left-most” elements in SD, QXP’s divide-andconquer strategy will be able to rule out most other elements very fast.
We evaluated the following configurations regarding the position of the conflicts (see Table 5): (a) Random: The elements of each conflict are randomly distributed across SD; (b) Left/Right: All elements of the conflict appear in exactly one half of SD; (c) LaR (Left and Right): Conflicts are both in the left and right half, but not spanning both halves; (d) Neighb.: Conflicts appear randomly across SD, but only involve “neighboring” elements.
One specific rationale of evaluating these constellations individually is that conflicts in some application domains (e.g., when debugging knowledge bases) might represent “local” inconsistencies in SD.
Since the conflicts are known in advance in this experiment, no CSP solver is needed to determine the consistency of a given set of constraints. Because zero computation times are unrealistic, we added simulated consistency checking times in each call to the TP. The value of the simulated time quadratically increases with the number of constraints to be checked and is capped in the experiments at 10 milliseconds. We made additional tests with different consistency checking times to evaluate to which extent the improvements obtained with MXP depend on the complexity of an individual consistency check for the underlying problem. However, these tests did not lead to any significant differences.
Table 5 shows some of the results of this simulation. In this evaluation, we also include the results of the parallelized PMXP variant. The following observations can be made.
(1) The performance of QXP strongly depends on the position of the conflicts. In the probably most realistic Random case, MXP helps to reduce the computation times around 20-30%. In the constellations that are “unfortunate” for QXP, the speedups achieved with MXP can be as high as 75%. When QXP is “lucky” and all conflicts are clustered
3We assume a splitting strategy in which the elements are simply split in half in the middle with no particular ordering of the elements. #Cp #Cf |Cf| in the left part of SD, some improvements or light deteriorations can be observed for MXP. The latter two situations (all conflicts are clustered in one half) are actually quite improbable but help us better understand which factors influence the performance.
(2) When comparing the results of the first two blocks in the table, it can be seen that the improvements achieved with MXP are stronger when there are more components in SD and more time is needed for performing the individual consistency checks. This is in line with the results of the other experiments.
(3) Parallelization can help to obtain modest additional
improvements. The strongest improvements are observed
for the LaR configuration, which is intuitive as PMXP by
design explores the left and right halves independently in
parallel. Note that in the experiments with the DXC and the
CSP benchmark problems, in most cases we could not
observe runtime improvements through parallelization. This is
caused by two facts. First, the consistency checking times
are often on average below 1 ms, which means that the
relative overhead of starting a new thread can be comparably
high. Second, the used CSP solver causes some additional
overheads and thread synchronization when used in multiple
threads in parallel.
5
In [
Technically, Junker proposes to set a choice point whenever a constraint ci is found to be consistent with a partial relaxation during search and thereby look for (a) branches that lead to conflicts not containing ci and (b) branches leading to conflicts in which the removal of ci leads to a solution.
Unfortunately, it is not fully clear from the informal
sketch in [
Processing measure uncertainty into fuzzy classifier Thomas Monrousseau1, Louise Travé-Massuyès1 and Marie-Véronique Le Lann1,2 1CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France 2Univ de Toulouse, INSA, LAAS, F-31400 Toulouse, France e-mails: thomas.monrousseau@laas.fr, louise@laas.fr ,mvlelann@laas.fr
Abstract
Machine learning such as data based classification
is a diagnosis solution useful to monitor complex
systems when designing a model is a long and
expensive process. When used for process
monitoring the processed data are available thanks to
sensors. But in many situations it is hard to get an
exact measure from these sensors. Indeed measure
is done with a lot of noise that can be caused by
the environment, a bad use of the sensor or even
the conversion from analogic to numerical
measure. In this paper we propose a framework based
on a fuzzy logic classifier to model the uncertainty
on the data by the use of crisp (non fuzzy) or fuzzy
intervals. Our objective is to increase the
number of good classification results in the presence
of noisy data. The classifier is named LAMDA
(Learning Algorithm for Multivariate Data
Analysis) and can perform machine learning and
clustering on different kind of data like numerical
values, symbols or interval values.
1
Data classification is the process of dividing pattern space
using hard, fuzzy or probabilistic partitions into a number
of regions [
Most of the time, data are issued from sensor
measurements and are corrupted by noise. This noise can have
different origins, for example environment disturbances, bad
use of the sensor, hysteresis effect or numerical conversion
and representation of the data. Many domains of
application have to deal with noise problems like medical
diagnosis [
Uncertainty can be understood in two ways: the first is the
uncertainty directly present in the data like noise and the
second can be assimilated as the reliability of a feature
inside a class. In this paper we consider only the first case. To
avoid noise problems in classification some solutions have
been provided previously, for example the transformation of
data [
Fuzzy logic is a multi-valued logic framework
introduced by Zadeh [8] that is known to be more efficient for
representating uncertainty and impreciseness than binary
logic. In previous work, a fuzzy classifier named Learning
Algorithm for Multivariate Data Analysis (LAMDA)
has been proposed by Aguilar [9]. This classifier can
originally process simultaneously two different types
of data: quantitative data and qualitative data. A real
number contains an infinite amount of precision whereas
human knowledge is finite and discrete, thus LAMDA is
interesting because there is no solution proposed in the
literature to process in a uniform way heterogeneous data
and to handle in a same problem quantitative data and
qualitative data is often a complex subject. A new type
of data, the interval, has been introduced by Hedjazi [
In the first part of the paper the LAMDA algorithm is shortly presented then in a second time a method to use the algorithm to classify noisy data is introduced. This method is in two parts: the first presents a general solution to model uncertainty on data with crisp intervals based on confidence intervals and the second shows an improvement to model Gaussian noise with fuzzy intervals. In both cases examples of application are introduced to show the improvement of the method compared to the use of the data without transformation. 2
LAMDA algorithm (Learning Algorithm for Multivariate Data Analysis) This section presents the principle of the LAMDA algorithm. LAMDA is a classification algorithm based on fuzzy logic created on an original idea of Aguilar [9] and can achieve machine learning and clustering on large data sets.
The algorithm takes as input a sample x made up of N features. The first step is to compute for each feature of x, an adequacy degree to each class Cj , j = 1..J where J is the total number of class. This is obtained by the use of a fuzzy adequacy function. So J vectors of N adequacy degrees are computed, these vectors are called Marginal Adequacy Degree vectors (MAD). At this point, all the features are in a common space. Then the second step is to take all the MADs and aggregate them into one global adequacy degree (GAD) by means of a fuzzy aggregation function. Thus the J MAD vectors (composed of N MADs) become J scalar GADs, the higher the GAD, the better the adequacy to the class. The simplest way to assign the sample x to a class is to keep as result the class with the biggest GAD.
All the process is summarized in Fig. 1. 2.2 Fuzzy membership computation During the learning step, the algorithm creates prototype data for each class and for each feature. These data are called classe descriptors or prototypes; they can be for example means or variances. We define as Cj,n the class prototype of the n-th feature for the class j.
As previously mentioned the first step of the algorithm is a comparison between the sample vector x and all the Cj,n. This operation is performed with membership functions and gives as result a membership adequacy degree.
Thus M ADj,n is the MAD for the j-th class and the
nth feature. As the framework is based on fuzzy logic, all
memberships are numbers in the [
M ADj,n = f (Cj,n, xn) (1)
The class prototype Cj,n depends on two things: the type of data and the function used. Some functions may require only one data into Cj,n whereas others need a list of parameters.
In the following section, some examples of membership functions are presented.
• Quantitative data:
Many functions are available for this kind of data. For example the Gaussian: or the binomial function: f (xn) = e − (xn − ρj,n)2
2σj2,n f (xn) = ρjx,nn.(1 − ρj,n)1−xn (2) (3)
Where xn is the n-th feature of the sample x, ρj,n is the mean of the n-th feature for the class j and σj,n is the standard deviation of the n-th feature for the class j. • Qualitative data:
Qualitative can take values in a set of modalities. The membership function of qualitative data returns the frequency of modality taken by the feature into the class during the learning phase. We introduce a qualitative variable with K modality {Q1, ..., QK } and the frequency Φjk of the modality Qk for the class j. The membership is described by: f (xn) = (Φj1,n)q1 ∗ ... ∗ (ΦjK,n)qK
(4) with qk = 0 if xn 6= Qk qk = 1 if xn = Qk • Intervals:
The membership function for interval data is a function which tests the similarity between two fuzzy intervals.
In this case similarity is defined by two components: the distance between the intervals and the surface that these intervals have in common. Indeed the class prototype for crisp interval data is a mean interval. The similarity function is:
S(A, B) = 1 ( RV μA∩B(ξ)dξ 2 RV μA∪B(ξ)dξ + 1 − where μX (x) is the value of x in the fuzzy set X, ∂[A, B] is the distance between intervals A = [a−, a+] and B = [b−, b+]and $[X] is the size of a fuzzy set into a V universe. This is described by:
Z $[X] =
μX (ξ)dξ
V In the case of crisp intervals and in a universe between 0 and 1:
(6) S(A, B) = 1 $[A ∩ B]
( 2 $[A ∪ B] + 1 − ∂[A, B])
(7) where $[X] in this case can be replaced by the length of the interval: $[X] = upperbound(X)-lowerbound(X)
(8) and distance ∂[A, B] is defined as: ∂[A, B] = max[0, max(a−, b−)−min(a+, b+)] (9) In the case where an interval feature is used the prototype for a class j is given by [ρjn−, ρjn+] where ρjn−, respectively ρn+ represents the mean value of lower
j bounds (respectively upper bounds) of all the elements belonging to class j for this feature.
Once the MAD are computed whatever the feature type, it is possible to perform any type of processing as described on Fig. 2 Once all the features are grouped into the membership space the next step of the algorithm is to transform the MAD vectors into a set of single value which depicts the global membership of the sample to a class. These values were introduced in section 2.1 and are called GAD. To perform this transformation a fuzzy aggregation function Ψ is used.
The aggregation function is the following: Ψ(M AD) = α.γ(M AD) + (1 − α).β(M AD)
(10) where γ is a fuzzy T-norm and β is a fuzzy T-conorm. α parameter is called exigency indicator. It enables to give more or less significance to the union operation and the intersection operation. Two fuzzy T-norm and T-conorm are currently implemented in the algorithm, the min-max and the probabilistic. For example if min-max is used, (10) becomes: Ψ(M AD) = α.min(M AD)+(1−α).max(M AD) (11)
When all GAD are computed they give the membership of the data x to each class. The final result depends on the application but the simplest way to give a result is to class the sample in the class which has the highest GAD. A limit membership can also be fixed: if no GAD is higher than the limit, the sample is defined as unclassifiable. 3 3.1
Uncertainty modeled with crisp intervals
Method presentation Every data measurement is performed with noise. In some cases noise has enough bad effect to increase the error of classification. Thus the point is to model the imprecision of the data to decrease the number of bad classifications.
A technique used in several fields of application is the
use of intervals to symbolize data uncertainty [
In a situation where the probability law followed by the noise on a variable is unknown, it may be possible to obtain a confidence interval. It is an interval in which the real value of the measure is present with a certain amount of confidence (for example a confidence interval of 95% is an interval in which the exact value of the measure can be found with a probability of 95%). Introducing xˆ the measured value and l the length of a centered on zero confidence interval based on the measurement error, the interval
l ; xˆ + 2l ]. used by the algorithm is calculated: X = [xˆ − 2
The main aim of the transformation is to improve the classification on the transition zones where data is really sensitive to noise and a small change can modify the output of the classifier. The use of intervals to model uncertainty is effective only if the “clean” data is relevant for the classification problem. If it is not the case a better solution is to remove the irrelevant feature. It will in most cases provide better output results. This expresses the fact that if the “clean” data is difficult to classify it is not improved by using confidence intervals. 3.2 A set of data has been created for an application test which can be interpreted as sensors time evolution of a continuous process. This set of data is composed by three quantitative (numerical) features of 101 samples that are shown on the Fig. 3. Three classes are specified and used as targets for the classifier. These classes are chosen arbitrarily to represent different behaviors of a system that could be healthy or failure modes. Nevertheless the classes are built to make all the data relevant for the system monitoring which means the three features do not have a global negative impact on the classification results.
The three features x, y and z are defined by the following time functions: • z = tanh(t − 5)
This example is used to measure the improvement in the classification results in the case of all data are noisy. Artificial noise is added by the following: x is the ideal variable without noise and xˆ the noisy variable, xˆ = x + Y with Y a random variable following a uniform distribution on an interval I.
The experiment has been performed with these conditions: α parameter of (10) is set at 0.8 with the [min,max] functions to compute the fuzzy aggregation and the membership function used for quantitative data is the binomial.[min, max] aggregation is chosen because experiments on the algorithm showed that this kind of aggregation provides better results on noisy data that the probabilistic one.
A first classification without any noise gives a result of 91% of good classification. Then the experiment is repeated a great many times to avoid statistical mistakes. In this case, the experiment has been run fifty thousand times, xˆ is recomputed at each new run. Results are given on table 1.
Interval for random data Mean success percentage with binomial function Mean success percentage with interval function
As it can be seen, this method provides an improvement on the results in the two first cases where noise deteriorates the classification with the quantitative method but when the data is still globally consistent. In these cases, the intervals method gives better results than binomial method 82% of the time. But when noise amplitude is much higher than the data like in the [−2; +2] error interval, the interval method does worse in general than the binomial function. 4.1 Fuzzy interval method presentation Most of the time, noise on physical measure follows a Gaussian distribution centered on the real value. Thus it is interesting to model this specific kind of uncertainty. Nevertheless, it is difficult to handle fuzzy intervals with an exact Gaussian shape. That is why we suggest approximating the Gaussian with a triangular fuzzy interval. This interval is described with a lower boundary x− and an upper boundary x+: X = [x−; x+] which leads to a similar description as crisp intervals. So: μX (x−) = 0 and μX (x+) = 0 and μX ( x++2 x− ) = 1 with μX (x) the fuzzy value of x into the fuzzy set X. As a Gaussian of ρ mean is centered on the true measure value the maximum fuzzy value of the triangle x++x− is equal to
2 ρ. To compute x− and x+ we propose to use the full width at half maximum (FWHM) that can be calculated this way:
F W HM = 2p2ln(2) · σ (12) with σ that is the standard deviation of the measure.
Thus for a Gaussian function that has a mean value ρ and a standard deviation σ the approximated interval X is defined by X = [ρ − 2p2ln(2) · σ; ρ + 2p2ln(2) · σ]. An example of this approximation is given on Fig. 5.
Until now all the implementations of the LAMDA algorithm were using only crisp intervals despite the fact that the general method was introduced. The class prototype is now a triangle interval computed with the means of upper and lower boundaries of the data used to train the algorithm.
Thus the membership function is still a similarity measure
between two fuzzy intervals like in (5) but it is necessary to
redefine the distance function between the intervals. A
solution has been proposed to measure a distance with the center
of gravity of triangular fuzzy intervals [
The intersection A ∩ B needed in (5) is calculated with an analytical solution based on geometry and trigonometry. It avoids numerical integration that could be less precise and longer to compute. As we did previously with the crisp method, a test is performed with a Gaussian noise on the same data set (Fig. 3).
The test is done in the same conditions as in the previous section. The difference is on the construction of the noisy data xˆ = x + Y . Y is now a random variable that follows a normal distribution of standard deviation σ and centered on 0. Results of the simulation are given on the table 2.
σ Mean success percentage with binomial function Mean success percentage with crisp interval function Mean success percentage with fuzzy interval function
Similarly to the previous test, the interval method
increases the rate of good classifications until the standard
deviation σ becomes too high and the binomial function
provides better results. This point is reached here for σ = 0.7
which corresponds to a signal to noise ratio (SNR) of 6 dB
for the signal with the smallest amplitude. Also it is
important to notify that in all cases the fuzzy interval provides
better results than the crisp interval method.
As a second example we use the classical iris dataset[
This dataset contains four features: sepal length in cm, sepal width in cm, petals length in cm and petal width in cm. All these features are measured for three types of flower: iris Setosa, iris Versicolour and iris Virginica which constitute three classes. It is easy to classify without any error the iris dataset by using only the petals information that are in general most relevant that the sepals ones. Thus only the sepal sizes are kept in this test to simulate the noise. The figure 6 shows the repartition of the data in the 2D space of the sepal features.
We assume that the data follow a normal distribution centered on a mean μj,n and with a standard-deviation σj,n.
This hypothesis can be verified by using a statistical test.
The Kolmogorov-Smirnov test has been used for each class with a 5% significance level, it shows that the hypothesis is true for the iris Setosa and the iris Versicolour but not for the iris Virginica. Nevertheless all the data are processed as if they follow a normal distribution.
The classifications are performed using the crossvalidation method. The percentages of well classified data for the two methods are: • using binomial function (scalar): 81.3% • using fuzzy triangular intervals: 94.0%
Once again the classification rate is increased by the use of the fuzzy interval method instead of the binomial one. 5 We presented in this article two methods to model uncertainty for classification applications. An example showed that these methods can improve classification results even when the signal to noise ratio is high. The second method based on fuzzy intervals demonstrated that try to model more precisely the probability law of the noise can provide better results than use confidence intervals modelled by crisp intervals. However this process to model uncertainty reveals limits when the SNR reaches a low level. A future important work is to limit the classification error of the interval method at the level of the numerical method.
These methods will now be tested on data out coming from a real industrial process.
Another way to manage uncertainty on classifiers like
LAMDA could be to use type-2 fuzzy functions [
To provide a better solution to manage uncertainty in the LAMDA classifier it can be useful to extend the problem to the qualitative features. It is often difficult to determine if a qualitative element is close to another, for example the color "orange" is closer to "red" than "blue". But on small training dataset consider this kind of information can improve final classification results. This could be done by using similarity matrix which are already used in some artificial intelligence problems.
LAMDA algorithm can work with a feature selection
algorithm named MEMBAS (Membership Margin Based
Feature Selection) [
Arafat Samer, Dohrmann Mary, and Skubic Marjorie. Classification of coronary artery disease stress ecgs using uncertainty modeling. In Computational Intelligence Methods and Applications, 2005 ICSC Congress, 2005.
Kynan E. Graves and Romesh Nagarajah. Uncertainty estimation using fuzzy measures for multiclass classification. Neural Networks, IEEE Transactions on, Vol.
18:pp. 128–140, 2007. [7] Prabha Verma and R.D.S. Yadava. Fuzzy c-means clustering based uncertainty measure for sample weighting boosts pattern classification efficiency. In Computational Intelligence and Signal Processing (CISP), 2012 2nd National Conference on, pages 31– 35, 2012. [8] L.A. Zadeh. Fuzzy sets. Information and Control, vol.
8:pp. 338–353, June 1965.
Proceedings of the 26th International Workshop on Principles of Diagnosis
Tools/Benchmarks
275 Proceedings of the 26th International Workshop on Principles of Diagnosis
276 Random generator of k-diagnosable discrete event systems
Yannick Pencolé1 2 1CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France 2Univ de Toulouse, LAAS, F-31400 Toulouse, France
e-mail: yannick.pencole@laas.fr
Abstract
This paper presents a random generator of
discrete event systems that are by construction
kdiagnosable. The aim of this generator is to
provide an almost infinite set of diagnosable systems
for creating benchmarks. The goal of such
benchmarks is to provide a solid set of examples to test
and compare algorithms that solve many
problems around diagnosable discrete event systems.
1
For many years, the problem of fault diagnosis in discrete
event systems has been actively addressed by different
scientific communities such as DX (AI-based diagnosis) [1;
2], FDI (Fault Detection and Isolation), DES (Discrete
Event Systems) [
The main problem about these contributions is that they are not really comparable as they are not applied on the same benchmarks. Moreover, used benchmarks may not be always completly defined in a paper due, most of the time, to confidential data that cannot be published so other academic contributors cannot use them for comparison purposes. In order to analyse and boost the effective performance of algorithms addressing the fault diagnosis problem in DES, common and fully available benchmarks become a necessity.
This paper addresses the random generation of kdiagnosable systems. We here propose the possibility to generate (and store on a web page) k-diagnosable systems that have been generated without any kind of bias that would come from a specific diagnosis/diagnosability method. By doing so, we propose to design a random category for benchmarks as the SAT community proposed for SAT problems and to get the same advantages by comparing different diagnosis/diagnosability approaches on the same but random systems. The choice of generating k-diagnosable systems is motivated by the fact that they can be used as examples for: 1. diagnosis algorithms: given a fault f , we know by construction that the most precise algorithm will determine its occurrence with certainty within the next k observations after the occurrence of f ; 2. diagnosability algorithms: the fact that a fault f is kdiagnosable is usually the worst case for this type of algorithms (as they all look for the existence of an ambiguous scenario to conclude the system is not diagnosable).
The paper is organised as follows. After formally recalling the problem that motivates the generation of benchmarks, we describe the fundamental property which is being used for the effective generation of systems where a given fault f is k-diagnosable. Then the description of the algorithm of the generator is provided as well as some details about its effective implementation. 2
Background This paper addresses the random generation of benchmarks for the problem of the fault diagnosis of discrete event system. This problem is briefly recalled in this section. We assume that the reader is familiar with the notations of the language theory (notion of Kleene closure, prefixes,...). We suppose that the system under monitoring behaves as an event generator that can be modelled as an automaton.
Definition 1 (System description). The model (system description) SD of a discrete event system S is a finite state automaton SD = (Q, Σ, T, q0) where: • Q is a finite set of states; • Σ is a finite set of events; • T ⊆ Q × T × Q is a finite set of transitions; • q0 is the initial state of the system.
Σ is the set of events that the system can produce. Among Σ we distinguish events that are observable Σo ⊆ Σ and events that are not observable. When the system operates, its effective behaviour is represented by a trace of the automaton (also called a run).
Definition 2(Trace). A trace τ ∈ Σ∗ of the system is a finite sequence of events associated with a transition path from the initial state q0 to a state q in the model of the system.
The set of traces of the system is the language generated by its model and is denoted L(S) (so the automaton SD generates the language L(S)). Let PΣ0 (τ ) be the classical projection of a sequence τ of Σ∗ on the alphabet Σ0 recursively defined as follows:
1. PΣ0 (ε) = ε; 2. PΣ0 (τ.e) = PΣ0 (τ ) if e 6∈ Σ0;
Definition 3(Observable trace). Let τ be a trace of the system, the observable trace στ is the projection of τ over the set of observable events Σo:
στ = PΣo (τ ).
Diagnosis problem and solution Now we are ready to define the classical Fault diagnosis problem on DES.
Definition 4(Fault). A fault is a non-observable event f ∈ Σ.
A fault is represented as a special type of non-observable
event that can occur on the underlying system. Once the
event has occurred, we say that the fault is active in the
system, otherwise it is inactive. We consider here the problem
of permanent faults as initially introduced in [
Definition 5 (Diagnosis problem). A diagnosis problem is a triple (SD, OBS, FAULTS) where SD is the model of a system, OBS is the sequence of observations of Σo? and FAULTS is the set of fault events defined over SD.
Informally speaking, (SD, OBS, FAULTS) represents the problem of finding the set of active faults fromFAULTS that have occurred relying on the model SD and the sequence of observations OBS.
Definition 6(Diagnosis Candidate). A diagnosis candidate is a couple (q, F ) where q is a state of SD (q ∈ Q) and F is a set of faults.
A diagnosis candidate represents the fact that the underlying system is in state q and the set F of faults has occurred before reaching state q.
Definition 7 (Solution Diagnosis). The solution Δ of the problem (SD, OBS, FAULTS) is the set of diagnosis candidates (q, F ) such that there exists for each of them at least one trace τ of SD such that: 1. the observable trace of τ is exactly the sequence
OBS = o1 . . . om and the last event of τ is om; 2. the set of fault events that has occurred in τ is exactly
F ; 3. the final state of τ is q.
Informally, candidate (q, F ) is part of the solution if it is possible to find out inSD a behaviour of the system satisfying OBS which leads to the state q after the last observation of OBS and in which the faults F have occurred. 2.3
Diagnosability
Diagnosability is a property of the system that asserts
whether a fault f of a system S can be always diagnosed
with certainty after the observation of a finite set of
observations [
Definition 8(Diagnosability). The fault f is diagnosable in a system S if:
∃n ∈ N+, Diagnosable(n) where Diagnosable(n) stands for: ∀τ1.f ∈ L(S), ∀τ2 : τ1.f.τ2 ∈ L(S)
|PΣo (τ2)| ≥ n ⇒ (∀τ ∈ L(S), (PΣo (τ ) = PΣo (τ1.f.τ2) ⇒ f ∈ τ )).
Definition 9 (k-Diagnosability). The fault f is kdiagnosable, k ∈ N+, in a system S if:
Diagnosable(k) ∧ ¬Diagnosable(k − 1).
Diagnosability is a property that relies on the liveness of the observability of the system which means that, to be (k)-diagnosable, a system must not generate unbounded sequences of unobservable events (no cycle of unobservable events in SD). Throughout this paper, we consider that the observability of the system is live. 3 The aim of this section is to present the algorithm that is being used to randomly generate a discrete event systems where a fault f is k-dignosable and that has been implemented inside the Diades software. We focus on the generation of a system with one fault only. (see th conclusion for the generation for n, n > 1 faults). 3.1
Signatures and fault ambiguity The algorithm that generates a k-diagnosable system relies on the notion of signatures. Let f be a faulty event, the signature of f is the set of observable traces resulting from the projection of system traces that contain at least one occurrence of an event f before the last observation of the trace.
Definition 10(Signature). The signature of an event f into a system S is the language Sig(f ) ⊆ Σo? such that
Sig(f ) ={στ |τ = τ1.o.τ2 ∈ L(S),
f ∈ τ1, o ∈ Σo, τ2 ∈ Σ?, στ = PΣo (τ )}.
In the following, we will also denote by Sig(¬f ) the set of observable traces associated with the traces of the system that do not contain any fault f before the last observation. Intuitively speaking, as long as the current observable trace is in Sig(¬f ) ∩ Sig(f ), we know that the system may have produced a faulty trace or a non-faulty trace before the last observation. k-diagnosability ensures that the ambiguity can last at most for k observations. The principle of the generator relies on the following result that formalizes this intuition. Let LARGESTPREFIXES(τ, n) = {τi0 : τ = τi0τi, |τi| = i, i ∈ {0, . . . , n − 1}} be the set of the n largest prefixes ofτ (τ being a prefix of itself).
Theorem 1. In the system S, the event f is k-diagnosable if and only if: 1. For any observable trace σ in Sig(¬f ) ∩ Sig(f ), there exists n < k such that LARGESTPREFIXES(σ, n) ⊆ Sig(¬f ) ∩ Sig(f ) and LARGESTPREFIXES(σ, n + 1) 6⊆ Sig(¬f ) ∩ Sig(f ). 2. There exists at least one observable trace σ in Sig(¬f ) ∩ Sig(f ) such that LARGESTPREFIXES(σ, k − 1) ⊆ Sig(¬f ) ∩ Sig(f ) and an observable o such that σo ∈ Sig(f ).
Proof: (⇒)Let τ1.f be a trace of the system S. As S is k-diagnosable, there exists m ≤ k such that ∀τ2 : τ1.f.τ2 ∈ L(S), |PΣo (τ2)| ≥ m ⇒ (∀τ ∈ L(S), (PΣo (τ ) = PΣo (τ1.f.τ2) ⇒ f ∈ τ )). Consider one of these trace τ1.f.τ2 such that τ2 contains exactly m observations (PΣo (τ2) = o1 . . . om). k-diagnosability implies that there exists a minimal integer n ∈ {1, . . . , m − 1} such that PΣo (τ1.f ).o1 . . . on+1 ⇒ f ∈ τ as soon as τ ∈ L(S) and PΣo (τ ) = PΣo (τ1.f ).o1 . . . on+1, therefore PΣo (τ1.f ).o1 . . . on+1 ∈ Sig(f ) \ Sig(¬f ) and ∀i ∈ {1, . . . , n}, PΣo (τ1.f ).o1 . . . oi ∈ Sig(f ) ∩ Sig(¬f ). So LARGESTPREFIXES(PΣo (τ1.f ).o1 . . . on, n) ⊆ Sig(¬f ) ∩ Sig(f ). So for any τ1.f there exists n < k such that LARGESTPREFIXES(PΣo (τ1.f ).o1 . . . on, n) ⊆ Sig(¬f ) ∩ Sig(f ). Now, remark that for any observable sequence σ that belongs to Sig(¬f ) ∩ Sig(f ), there must exist a trace τ1.f.τ2 of the system, with τ2 containing at least one observable event, such that σ = PΣo (τ1.f.τ2), so there must exist n < k such that σ ∈ LARGESTPREFIXES(PΣo (τ1.f ).o1 . . . on, n) ⊆ Sig(¬f ) ∩ Sig(f ) so, for any σ that belongs to Sig(¬f ) ∩ Sig(f ), there is no set LARGESTPREFIXES(σ, n + 1) that only contains ambiguous signatures.
Finally, as S is k-diagnosable, we know that there exists at least one trace τ.f.τ1.o1, such that τ is a trace of the system that does not contain f , τ1 is a finite continuation ofτ.f that is unobservable and o1 is observable and there is a finite continuation τ2o2τ3o3 . . . τkok with PΣo (τi) = ε such that for any i ∈ {1, . . . , k − 1}, PΣo (τ.f.τ1.o1 . . . τioi) ∈ Sig(¬f ) ∩ Sig(f ) PΣo (τ.f.τ1.o1 . . . τkok) ∈ Sig(f ) \ Sig(¬f ) which implies the condition 2 with σ = PΣo (τ.f.τ1.o1 . . . τk−1ok−1). (⇐) Suppose now that conditions 1 and 2 hold. Consider an observable trace σ that is ambiguous (σ ∈ Sig(f ) ∩ Sig(¬f )). Condition 1 states that there exists n < k such that LARGESTPREFIXES(σ, n) ⊆ Sig(¬f ) ∩ Sig(f ) and LARGESTPREFIXES(σ, n + 1) 6⊆ Sig(¬f ) ∩ Sig(f ). Consider now any largest observable trace σ0 such that |σ0| − |σ| = m and σ ∈ LARGESTPREFIXES(σ0, m) ⊆ Sig(¬f )∩ Sig(f ), it follows that LARGESTPREFIXES(σ0, m + n) ⊆ Sig(¬f ) ∩ Sig(f ) and LARGESTPREFIXES(σ0, m + n + 1) 6⊆ Sig(¬f ) ∩ Sig(f ). As σ0 is one of the largest observable trace holding this condition, any observable trace σ0o, o ∈ Σo, is either in Sig(f ) or in Sig(¬f ) but not in both of them. Condition 1 states that m + n < k, so k observations at least are required to solve the ambiguity. Condition 2 states that there exists at least such an observable trace σ0 with m + n = k − 1 and an observation o so that σ0o is definitively in Sig(f ) so f can be diagnosed with certainty in this case with exactly k observations. Hence the result. 3.2
Algorithm The principle of the random generator is depicted in Algorithm 1. Given a parameter k and a fault event f , the algorithm randomly generates a system S where the event f is k-diagnosable by construction. We also provide another parameter deg which is the maximal number of output transitions that is allowed per state during the generation of the system. Parameter deg is important for the creation of benchmarks as the output degree has a strong influence on the diagnosis/diagnosability computations.
Algorithm 1 General algorithm for the random generation of k-diagnosable systems.
Input: k ∈ N, k ≥ 1 Input: f an event Input: deg maximal output degree (Σo, Σ) ← GENERATEEVENTS() S ← ∅ AmbSig(f ) ← GENERATEAMBSIGNATURE(k,Σo, deg) /* AmbSig(f ) = (Q, Σo, T, q0, A) a deterministic automaton */ MF[q0] ← GENERATESTATES() MNF[q0] ← GENERATESTATES() for all q ∈ Q in Breadth-First Order from q0 do (Σfo , Σo¬f ) ← RANDOMSPLIT(Σo, q) S ← S∪ GENFAULTEXTS∗(MF[q],Σfo ,deg) S ← S∪ GENNOMEXTS∗(MNF[q],Σo¬f ,deg)
o for all q −→ q0 ∈ T do if MF[q0] = ∅ then
MF[q0] ← GENERATESTATES()
MNF[q0] ← GENERATESTATES() end if S ← S∪ GENNOMEXTS(MNF[q],MNF[q0],o,deg) if q0 6∈ A then
S ← S∪ GENNOMEXTS(MF[q],MF[q0],o,deg) else if q ∈ A then
S ← S∪ GENEXTS(MF[q],MF[q0],o,deg) else
S ← S∪
GENFAULTEXTS(MF[q],MF[q0],o,deg) end if end if end for end for Output: S where f is k-diagnosable.
The generation is composed of two steps. The first one is the generation of the ambiguous signature with GENERATEAMBSIGNATURE. The result of this function is a deterministic automaton AmbSig(f ) = (Q, Σo, T, q0, A) that actually generates the language Sig(f )∩Sig(¬f ) (any transition path from state q0 to an accepting state of A represents a sequence of Sig(f ) ∩ Sig(¬f )). The automaton AmbSig(f ) is generated with respect to the conditions 1 and 2 that are defined in Theorem 1 to ensure the kdiagnosability of the resulting system S. The second step of the generation is the effective generation of S based on the ambiguous signature AmbSig(f ). The idea is to map every state q of AmbSig(f ) with two sets of states in S denoted M F [q] and M N F [q]. Given any path σ of AmbSig(f ) that leads to state q with, as a last observation, the event o, any state of M F [q] (resp. M N F [q]) will be reached by at least one transition path τ of S starting from a state of M F [q0] (resp. M N F [q0]) that ends with a transition labelled with o and the observable projection of τ is exactly σ. The difference between M F and M N F is that any underlying path of S leading to a state of M F [q] (resp. M N F [q]) has an observable projection which is a prefix of Sig(f ) (resp. a prefix ofSig(¬f )). To generate S we explore AmbSig(f ) from its initial state in a breadth-first search manner. For a given state q, we have to consider three types of transition generations going out of any state of M F [q], M N F [q]. The first ones are the transition paths that will lead to an observation o that belongs to AmbSig(f ), the second one is the set of transition paths that do not lead to an observation o that belongs to AmbSig(f ) but lead to an observation o0 that belongs to Sig(f ) only and the third one is the set of transition paths that do not lead to an observation o that belongs to AmbSig(f ) but lead to an observation o00 that belongs to Sig(¬f ) only.
The second and third cases are handled by randomly splitting Σo into two subsets (Σfo , Σo¬f ) each of them only containing observable events that are not output event of q in AmbSig(f ) (RANDOMSPLIT(Σo, q)). Then given Σfo , we randomly generate faulty extensions for a subset of Σfo (the selection of the subset is also random and might even be empty if q has no output events in AmbSig(f ), indeed if q has no output events, it must be extended to ensure that the observability of the system is live). An extension is a set of acyclic and unobservable transition paths that lead to a transition labeled with an observable event from Σfo . A faulty extension ensures that an event f has at least occurred on any generated transition path before the observable transition (GENFAULTEXTS). Given Σo¬f , we proceed the same way to generate non-faulty extensions (GENNOMEXTS).
As, in these two cases, the traces generated by these extensions are not associated with observable traces involved in AmbSig(f ) any more, it is sufficient to generate further extensions on these traces and guarantee that the observable language associated with these further extensions is live (this procedure is denoted by the ∗ in GENNOMEXTS∗ and GENFAULTEXTS∗).
The last case to handle now is the case where the observable event o is an output event of q in AmbSig(f ), which o means that there exists one and only one transition q −→ q0 in AmbSig(f ). If q0 has never been visited, the set of states M F [q0] and M N F [q0] are generated first. A nominal extension is generated from M N F [q] to M N F [q0]. Depending on the status of q0, the extension between M F [q] and M F [q0] is different. If q0 6∈ A, it means that any prefix generated by AmbSig(f ) with paths from q0 to q0 are prefixes of sequences inSig(f ) ∩ Sig(¬f ) but they are not in Sig(f ) ∩ Sig(¬f ), they can therefore be only in Sig(¬f ): extensions between M F [q] and M F [q0] are then nominal extensions. Now, if q0 ∈ A, there are two cases. If q 6∈ A, it means the system must become faulty between the states of M F [q] and M F [q0] so that paths of the system that reach any state of M F [q0] is associated with an observable trace that belongs to Sig(f ) (GENFAULTEXTS). If q ∈ A, any path that reaches a state of M F [q] is already faulty (its observable trace is already in Sig(f )), any type of extension from M F [q] to M F [q0] is therefore possible (faulty or not), hence the use of GENEXTS. 3.3
Implementation
Algorithm 1 is implemented with the help of the Diades
library package [
Conclusions
To test and compare diagnosis and/or diagnosability
algorithms, fully detailed and available benchmarks are a
necessity. In order to test how generic is an algorithm, we
propose here an algorithm that randomly generates systems
where a fault f is k-diagnosable. We also propose an
implementation within the DIADES framework. Extension to
generate systems with n k-diagnosable faults is easy, it
requires to repeat the generation of the ambiguous signatures
for the n faults and explore them in parallel to generate the
k-diagnosable system. Our short-term perspective is to
improve the generator to allow a better control of the number
of generated states. A fixed number of generated states
requires to add new constraints in the generation that
propagate during the generation process. Without any control
about this propagation, the generation may just fail as it
could become an over-constrained problem. Our
perspective is to also go one step further by generating diagnosable
systems that are component-based in order to scale up the
size of the generated system. The DIADES framework
already has a tool to generate component-based systems [
References
[
Kasim Sinnamohideen, and Demosthenis Teneketzis.
Diagnosability of discrete-event systems. Transactions
on Automatic Control, 40(9):1555–1575, 9 1995.
[
Thiébaux. A spectrum of symbolic on-line diagnosis approaches. In 17th International Workshop on Principles of Diagnosis, pages 194–201, Nashville, TN USA, 2007.
HYDIAG: extended diagnosis and prognosis for hybrid systems Elodie Chanthery1,2, Yannick Pencolé1, Pauline Ribot1,3, Louise Travé-Massuyès1 1CNRS, LAAS, 7 avenue du colonel Roche, F-31400 Toulouse, France e-mail: [firstname.name]@laas.fr 2Univ de Toulouse, INSA, LAAS, F-31400 Toulouse, France 3Univ de Toulouse, UPS, LAAS, F-31400 Toulouse, France
Abstract HYDIAG is a software developed in Matlab by the DISCO team at LAAS-CNRS. It is currently a software designed to simulate, diagnose and prognose hybrid systems using model-based techniques. An extension to active diagnosis is also provided. This paper aims at presenting the native HYDIAG tool, and its different extensions to prognosis and active diagnosis. Some results on an academic example are given. 1 HYDIAG is a software developed in Matlab, with Simulink.
The development of this software was initiated in the
DISCO team with contributions about diagnosis on hybrid
systems [
An extension to active diagnosis has been also realized [5; 6]. This article aims at presenting the native HyDiag tool and its different extensions to prognosis and active diagnosis.
Section 2 recalls the hybrid formalism used by HYDIAG.
Section 3 presents the native HYDIAG tool that simulates and diagnoses hybrid systems. Section 4 explains how HYDIAG has been extended in HYDIAGPRO to prognose and diagnose hybrid systems. Section 5 presents the extension to active diagnosis. Experimental results of HYDIAG and its extension HYDIAGPRO are finally presented in Section 6. 2
Hybrid Model for Diagnosis HYDIAG deals with hybrid systems defined in a monolithic way. Such a system must be modeled by a hybrid automaton [7]. Formally, a hybrid automaton is defined as a tupleS = (ζ, Q, Σ, T, C, (q0, ζ0)) where: • ζ is a finite set of continuous variables that comprises input variables u(t) ∈ Rnu , state variables x(t) ∈
Rnx , and output variables y(t) ∈ Rny . • Q is a finite set of discrete system states. • Σ is a finite set of events. • T ⊆ Q × Σ → Q is the partial transition function
between states. • C = Sq∈Q Cq is the set of system constraints linking continuous variables. • (ζ0, q0) ∈ ζ × Q, is the initial condition.
Each state q ∈ Q represents a behavioural mode that is characterized by a set of constraints Cq that model the linear continuous dynamics (defined by their representations in the state space as a set of differential and algebraic equations). A behavioural mode can be nominal or faulty (anticipated faults). The unknown mode can be added to model all the non anticipated faulty situations. The discrete part of the hybrid automaton is given by M = (Q, Σ, T, q0), which is called the underlying discrete event system (DES). Σ is the set of events that correspond to discrete control inputs, autonomous mode changes and fault occurrences. The occurrence of an anticipated fault is modelled by a discrete event fi ∈ Σf ⊆ Σuo, where Σuo ⊆ Σ is the set of unobservable events. Σo ⊆ Σ is the set of observable events.
Transitions of T model the instantaneous changes of behavioural modes. The continuous behaviour of the hybrid system is modelled by the so called underlying multimode system Ξ = (ζ, Q, C, ζ0). The set of directly measured variables is denoted by ζOBS ⊆ ζ.
An example of a hybrid system modeled by a hybrid automaton is shown in Figure 1. Each mode qi is characterized by state matrices Ai, Bi, Ci and Di.
Hybrid system u
q1 q2 C1 xY11((nn+)=1C)=1xA11(xn1)(+nD)+1uB(1nu)(n) σ12 C2 xY22((nn+)=1C)=2xA22(xn2)(+nD)+2uB(2nu)(n) σ21
y σ1i
qi Ci xYii((nn+)=1C)=ixAi(inx)i(+nD)+iuB(un()n) σ
…
Overview of the native HYDIAG diagnoser
The method developed in [
There are optional parameters that are helpful to initialize the mode matrices automatically before editing them: the number of entries for the continuous dynamics, the number of outputs for continuous dynamics, the dimensions of each matrix A. The number of entries (resp. outputs) must be the same for all the modes.
The simulator of the edited model has no restrictions on the number of modes or the order of the continuous dynamics, it is generically designed. Online computations are performed using Matlab / Simulink. Results provided by Matlab can be reused if a special need arises. Figure 2 shows an overview of the software interface. Step 2: building the diagnoser HYDIAG automatically computes the analytical redundancy relations (ARRs) by using the parity space approach [9].
Details of this computation can be found in [
The idea of HYDIAG is to capture both the continuous dynamics and the discrete dynamics within the same mathematical object. To do so, the discrete part of the hybrid system M = (Q, Σ, T, q0) is enriched with specific observable events that are generated from continuous information.
The resulting automaton is called the Behaviour Automaton (BA) of the hybrid system. HYDIAG then builds the diagnoser of the Behaviour Automaton (see [8]) by using the DIADES1 software also developed within the DISCO team at LAAS-CNRS (see an example of diagnoser in Figure 7).
Step 3: system simulation and diagnosis Given the built hybrid diagnoser, HYDIAG then loads a set of timed observations produced by the system and it provides at each observation time an update of the diagnosis of the system by triggering the current transition of the hybrid diagnoser that matches the current observation. It is possible to define in HYDIAG a simulation scenario for the modeled system with a duration and a time sample defined by the user.
Software architecture with extensions The general architecture of HYDIAG and its two extensions (see the next sections for their description) is presented on Figure 3. Ellipses represent the objects handled by the software, rectangles with rounded edges depict HYDIAG functions and rectangles with straight edges correspond to external DIADES packages. The behaviour automaton is at the heart of the architecture as HYDIAG and both its extensions rely on it to perform diagnosis, active diagnosis and prognosis.
ActDiades Model display Enriched hybrid model
Specialized Active diagnosers
Additional Signature event ARRs computation
AND/OR Graph
AO* Algorithm
Behaviour
Automaton display
Diades Prognoser prognosis prognosis
ActHyDiag Conditional
plan Conditional plan display
HyDiag Diagnoser display Diagnoser diagnosis
Diagnosis display diagnosis
Prognosis display
HyDiagPro
HYDIAGPRO : an extension for Prognosis
HYDIAG has been extended in order to provide a
prognosis functionality to the software [
In HYDIAGPRO, the initial hybrid model is enriched
by adding for each behavioural mode a set of aging laws:
S+ = (ζ, Q, Σ, T, C, F , (q0, ζ0)) where F = {F q, q ∈ Q}
and F q is a set of aging laws one for each anticipated fault
f ∈ Σf in mode q. The aging modeling framework that
is adopted in HYDIAGPRO is based on the Weibull
probabilistic model [
q
any time the probability that the fault fj ojqcacruersfiixnetdhebysyths-e
tem mode q. Weibull parameters βjq and η
system mode q and characterise the degradation in mode q
that leads to the fault fj . Parameter γjq is set at runtime to
memorize the overall degradation evolution of the system
accumulated in the past modes [
The prognoser uses the aging laws in S+ to predict fault
occurrences (see Figure 3). The prognoser uses the
current diagnosis result to update on-line these aging laws (the
parameters γjq) according to the operation time in each
behavioural mode. For each new result of diagnosis, the
prognosis function computes the most likely sequence of dated
faults that leads to the system failure. From this sequence is
estimated the system RUL [
ACTHYDIAG: Active Diagnosis The second extension of HYDIAG provides an active diagnosis functionality to the software (see Figure 3). The inputs are the same as for HYDIAG but an additional file indicates the events of S that are actions, as well as their respective cost. Based on the behaviour automaton, we compute a set of specialised active diagnosers (one per fault): such a diagnoser is able to predict, based on the behaviour automaton, whether a fault can be diagnosed with certainty by applying an action plan from a given ambiguous situation [6]. From these diagnosers, we also extract a planning domain as a AND/OR graph.
At runtime, when HYDIAG is diagnosing, the diagnosis might be ambiguous. An active diagnosis session can be launched as soon as a specialised active diagnoser can analyse that the current faulty situation is discriminable by applying some actions. If the active diagnosis session is launched, an AO∗ algorithm starts and computes a conditional plan from the AND-OR graph that optimises an action cost criterion. It is important to note that in the case of a system with continuous dynamics, only discrete actions are contained in the active diagnosis plan issued by ACTHYDIAG. In particular, it is assumed that if it is necessary to guide the system towards a value on continuous variables, the synthesis of control laws must be performed elsewhere. 6
HyDiag/HyDiagPro Demonstration Water tank system model
Pump P1 h
Pump P2 hmax h2
h1
HYDIAGPRO has been tested on a water tank system (Figure 4) composed of one tank with two hydraulic pumps (P1, P2). Water flows through a valve at the bottom of the tank depending on the system control. Three sensors (h1, h2, hmax) detect the water level and allow to set the control of the pumps (on/off). It is assumed that the pumps may fail only if they are on. The discrete model of water tank and the controls of pumps are given in Figure 5. Discrete events in Σ = {h1, h2s, h2i, hmax, f1, f2} allow the system to switch into different modes. Observable events are Σo = {h1, h2s, h2i, hmax}. Two faults that correspond to the pump failures are anticipated Σf = {f1, f2} and are not observable.The Weibull parameter values of aging models F = {F qi } are reported in Table 1.
The underlying continuous behaviour of every discrete mode qi for i ∈ {1..8} is represented by the same state
pump mode
Pump1 Pump 2 2 4 6 8
ON ON OFF Fail ON Fail OFF Fail
ON OFF OFF ON Fail OFF Fail
Fail
η 3000 7000 NaN 4000 NaN 7000 NaN
NaN space:
X(k + 1)
Y (k) = =
AX(k) + BU (k) CX(k) + DU (k) where the state variable X is the water level in the tank, continuous inputs U are the flows delivered by the pumps P1, P2 and the flow going through the valve, A = (1), B = eT e/S! eT e/S with T e the sample time, S the tank base area eT e/S and ei = 1 (resp. 0) if the pump is turned on (resp. turned
0! off), C = (1) and D = 0 .
0 HYDIAG results Figure 6 presents the set of results obtained by HYDIAG and HYDIAGPRO on the folllowing scenario. The time horizon is fixed at Tsim = 4000h, the sampling period is Ts = 36s and the filter sensitivity for the diagnosis is set as Tfilter = 3min. The residual threshold is 10−12. The scenario involves a variant use of water (max flow rate = 1200L/h) depending on user needs during 4000h. Pumps are automatically controlled to satisfy the specifications indicated above. Flow rate of P1 and P2 are respectively 750L/h and 500L/h.
The diagnoser computed by HYDIAG is given in Figure 7.
Each state of the diagnoser indicates the belief state in the model enriched by the abstraction of the continuous part of the system, labelled with faults that have occurred on the system. This label is empty in case of nominal mode. In the scenario, fault f1 was injected after 3500h and fault f2 was not injected. )( h e c n e rr u c c o lt u a ff o tse a d d e itc d e r P df2 df1 f1 )( h e ilffse L u U g n ii n a m e R f1 q_32,{} q_75,{f2} q_64,{f1} q3,{} q7,{f2} q6,{f1} q_23,{} q_21,{} q_57,{f2} q8,{f1,f2} q_46,{f1} q2,{} q5,{f2} q4,{f1} q12,{} q1,{}
Left hand side of Figure 6 shows the diagnoser belief state just before and after the fault f1 occurrence. Results are consistent with the scenario: before 3500h, the belief states of the diagnoser are always tagged with a nominal diagnosis.
After 3500h, all the states are tagged with f1.
Middle of Figure 6 illustrates the predicted date of fault occurrence (df1 and df2 ). At the beginning of the process, the prognosis result is: Π0 = ({f1, 4120}, {f2, 5105}). It can be noted that the predicted dates df1 and df2 of f1 and f2 globally increase. Indeed, the system oscillates between stressful modes and less stressful modes. To make it simple, we can consider that in some modes, the system does not degrade, so the predicted dates of f1 and f2 are postponed.
Before 3500h, the predicted date of f1 is lower than the one
of f2. After 3500h, the predicted date of f2 is updated,
knowing that the system is in a degraded mode. Finally, the
prognosis result is Π3501 = ({f2, 5541}). Figure 6 shows
the evolution of the RUL of the system. At t = 3501, as the
fault f2 is estimated to occur at t = 5541, the system RUL
at t = 3501 is 5541 − 3501 = 2040h.
7
HYDIAG is a software developed in Matlab, with Simulink,
by the DISCO team, at LAAS-CNRS. This tool has been
extended into HYDIAGPRO to simulate, diagnose and
prognose hybrid systems using model-based techniques. Some
[
An extension to active diagnosis is also presented. The active diagnosis algorithm is currently tested on a concrete industrial case. HYDIAG and its user manual will be soon available on the LAAS website.
References
M. Bayoudh, L. Travé-Massuyès, and X. Olive. Hybrid systems diagnosis by coupling continuous and discrete event techniques. In IFAC World Congress, 2008.
P. Ribot, Y. Pencolé, and M. Combacau. Diagnosis and prognosis for the maintenance of complex systems. In IEEE International Conf. on Systems, Man, and Cybernetics, 2009.
Elodie Chanthery and Pauline Ribot. An integrated framework for diagnosis and prognosis of hybrid systems. In the 3rd Workshop on Hybrid Autonomous System (HAS), 2013.
S. Zabi, P. Ribot, and E. Chanthery. Health Monitoring and Prognosis of Hybrid Systems. In Annual Conference of the Prognostics and Health Management Society , 2013.
M. Bayoudh, L. Travé-Massuyès, and Xavier Olive. Active diagnosis of hybrid systems guided by diagnosability properties. In the 7th IFAC Symposium on Fault Detection, Supervision and Safety of Technical Processes, 2009.
E. Chanthery, Y. Pencolé, and N. Bussac. An AO*-like algorithm implementation for active diagnosis. In 10th International Symposium on Artificial Intelligence, Robotics and Automation in Space, i-SAIRAS,, 2010.
T. Henzinger. The theory of hybrid automata. In Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, pages 278–292, 1996.
M. Sampath, R. Sengputa, S. Lafortune, K. Sinnamohideen, and D. Teneketsis. Diagnosability of discrete-event systems.
IEEE Trans. on Automatic Control, 40:1555–1575, 1995.
M Staroswiecki and G Comtet-Varga. Analytical redundancy
relations for fault detection and isolation in algebraic
dynamic systems. Automatica, 37(5):687–699, 2001.
[
Author index A B Abdelkrim Mohamed Naceur Abreu Rui Agudelo Carlos Alonso-Gonzalez Carlos Archer Dave Aubrun Christophe Berdjag Denis Biswas Gautam Blesa Joaquim Bobrow Daniel Boussaid Boumedyen Bregon Anibal Bunte Andreas Burke David C Cabassud Michel Carrera Rolando Cayetano Raul Chanthery Elodie Chouiref Houda Christopher Cody Corruble Vincent Cosse Ronan
261 193, 209 241
59 193 261 159 27, 75, 185
67 193 261 59, 201 185 193 253 145 145 281 261 119
35 159
D Eickmeyer Jens El Fallah Seghrouchni Amal Eldardiry Hoda Feldman Alexander Feng Wenquan Filasova Anna Fourlas George G
51 253 201 193, 225
159 43, 217
35 193, 209 127, 193
27 235 177 I J K L Le Gall Francoise Le Lann Marie-Veronique Li Peng Li Shuxing Li Ze-Tao Liao Linxia Liscinsky Pavol 193 137
35 193, 209, 225
51 209
3 67, 83 241
75 113, 247
177 75, 185 185 167 235 177
N O P R Ocampo-Martinez Carlos Pavel Radu Pencole Yannick Perez Alexandre Pethig Florian Piechowiak Sylvain Pons Renaud Provan Gregory Puig Vicenc Pulido Belarmino 209 83, 277, 281 193
43 159
83 127 99, 261
59 83, 281
19 201 Trave-Massuyes Louise Traxler Patrick Wang Jiongqi Wotawa Franz Z 137 167