# Combining Multiple Diagnostic Trouble Codes into a Single Decision Tree

## Combining Multiple Diagnostic Trouble Codes into a Single Decision Tree

Preprints, 8th IFAC International Symposium on Preprints, IFAC Advances in Automotive Control Symposium Preprints, 8th 8th IFAC International Internat...

#### Recommend Documents

Preprints, 8th IFAC International Symposium on Preprints, IFAC Advances in Automotive Control Symposium Preprints, 8th 8th IFAC International International Symposium on on Preprints, 8th IFAC International Symposium on Advances in Automotive Control June 19-23, 2016. Norrköping, Sweden Available online at www.sciencedirect.com Advances in Automotive Control Advances in2016. Automotive Control June 19-23, Norrköping, Sweden June June 19-23, 19-23, 2016. 2016. Norrköping, Norrköping, Sweden Sweden

ScienceDirect

IFAC-PapersOnLine 49-11 (2016) 555–561

Combining Multiple Diagnostic Combining Multiple Diagnostic Combining Multiple Diagnostic Codes into a Single Decision Codes into a Single Codes into a Single Decision Decision

Trouble Trouble Trouble Tree Tree Tree

IFAC AAC 2016 556 June 19-23, 2016. Norrköping, SwedenMarkos F.B.G. Oliveira et al. / IFAC-PapersOnLine 49-11 (2016) 555–561

Definition 6. (Coherent boolean function). A function s is coherent if for any two minterms σ and π such that σ ≼ π, σ ∈ s implies that π ∈ s. In other words, faulty components that cause a system fail must cause fail for all other component conditions.

Fig. 1. Fault tree for Example 1. that can be faulty which generates a system fail s as depicted in Fig. 1. Suppose a system with components c1 , . . . , c6 that can be faulty which generates an observed system fail. A component is set to 1 when it is faulty and 0 otherwise. Similarly s is set to 1 (active) under system fail and 0 otherwise. The relationship between system fail and faulty components is given by the boolean expression (1). s = c 6 c 4 + c5 c 2 + c2 c 3 c 1 (1) A strategy of diagnostic is then a sequence of tests (pass or failed) to identify faulty components causing a system fail.

Given an expression s, s|c1 , . . . , ck is the boolean expression evaluated for c1 = · · · = ck = 1 and c1 = · · · = ck = 0 in s. Proposition 7. (Logical Shannon decomposition). Let s be a boolean expression and c ∈ var(s). Then, s ≡ c · (s|c) + c · (s|c) (2) Proposition 8. (Probabilistic Shannon decomposition). Let s be a boolean expression and c ∈ var(s). Then, Pr{s} = Pr{c} · Pr{s|c} + (1 − Pr{c}) · Pr{s|c} (3) = Pr{c} · (Pr{s|c} − Pr{s|c}) + Pr{s|c} Let π be a positive product of boolean variables of C. The minterm obtained by completing π with negative literals of C that do not appear in π is denoted by ⌊π⌋C . Definition 9. (Minimal cutset). Let s be a boolean function and π be a product of boolean variables of var(s). Then π is a cutset of s if ⌊π⌋var(s) ∈ s. In addition, π is a minimal cutset of s if it is a cutset of s and there is no cutset σ of s such that σ ≺ π. Proposition 10. Let s be a boolean function and MCS(s) be the disjunction of minimal cutsets of s. Then s is coherent iﬀ MCS(s) ≡ s.

2.1 Minimal cutsets

2.2 DIF and CDIF

Boolean variables are denoted by letters c, c1 , c2 , . . . , while s, s1 , s2 , . . . denote boolean expressions. Variables occurring in a boolean expression s are given by var(s). Definition 2. (Boolean expression). A boolean expression over an enumerable set C of variables (components or basic events) is recursively deﬁned by (i) a variable is a boolean expression; (ii) if s1 and s2 are boolean expressions, then s1 + s2 , s1 · s2 and s1 are boolean expressions as well. Definition 3. (Variable assignment). An assignment σ of var(s) ∈ C is a function from var(s) into {0, 1}. Definition 4. (Boolean function). A boolean function of n variables is a mapping f : {0, 1}n → {0, 1}. Definition 5. (Minterm). A minterm is a product of variables c or c (not both) for all c ∈ var(s).

DIF measures the importance of a component for diagnostic, i.e. it is the probability of a particular component is faulty given the system is faulty. Definition 11. (DIF). Given a boolean function s and a component c ∈ C, the diagnostic importance factor DIF(s, c) is given by Pr{c · s} . DIF(s, c) = Pr{c|s} = (4) Pr{s}

There is a one-to-one mapping between variable assignments and minterms. Given an assignment σ and a minterm π, c ∈ var(π) if σ(c) = 1 and c ∈ var(π) if σ(c) = 0. Therefore, σ or π are used interchangeable to denote variable assignments or minterms. Similarly, there is a unique boolean function corresponding to a given boolean expression (not the opposite). Therefore, we refer interchangeable to s as a boolean expression or function according to convenience. A partial order is deﬁned in the set of minterms built over C (and consequently in the set of variable assignments of C). Given two minterms σ and π and c ∈ C, σ ≼ π iﬀ c ∈ σ then c ∈ π. 566

It measures the risk of system fail due to a particular component fault c. It can be approximated by (5) and (6) according to Dutuit and Rauzy (2013).

with Pr{s|c} ≈

Pr{c} · Pr{s|c} DIF(s, c) ≈ ∑ π∈MCS(s) Pr{π} ∑

c·π∈MCS(s)

Pr{π} +

(5)

Pr{π}

(6)

π∈MCS(s),c∈π /

Assaf and Dugan (2008) have introduced CDIF. It includes a cost for component test as, for instance, time required for testing or test complexity. Definition 12. (CDIF). Given a boolean function s and a component c ∈ C whose cost of testing is tc , the cost of importance factor CDIF(s, c) is given by DIF(s, c) CDIF(s, c) = (7) tc

IFAC AAC 2016 June 19-23, 2016. Norrköping, SwedenMarkos F.B.G. Oliveira et al. / IFAC-PapersOnLine 49-11 (2016) 555–561

557

is the unreliability of component c ∈ C. Given a system s with n cutsets, the system unreliability Qs is given by n ∏ Qs = 1 − (1 − qcutseti ) (9) i=1

where qcutseti is a product of unreliability values of c in the cutset i. 2.5 Diagnostic Cost (DC) Assaf and Dugan (2008) have introduced a formula to evaluate the cost of a particular BDD. Given a system s with n cutsets the diagnostic cost DC(s) is given by n 1 ∑ · qcutseti · cpi (10) DC(s) = Qs i=1

Fig. 2. BDD for Example 1.

j=1

CDIF is a tradeoﬀ between test importance and cost. It is used here to provide the ordering of components to be tested. A component with high CDIF should be tested ﬁrst either because it is important for diagnostic (high DIF) or because it is an inexpensive test (low cost). 2.3 Binary Decision Diagram (BDD) We assume the reader is familiar with most details of BDDs. A comprehensive introduction and algorithms are presented in Rauzy (1993). Definition 13. (BDD). A BDD is a directed acyclic graph with leaves ONE and ZERO encoding the constant boolean functions 1 and 0, respectively. Internal nodes are labeled by components c ∈ C with 1- and 0-outedges. It encodes a boolean function s = c · s1 + c · s0 where s1 and s0 are boolean functions encoded by nodes pointed by 1and 0-outedges of c, respectively. A BDD is built from a boolean expression by encoding its minimal cutsets. The corresponding BDD of Example 1 is given by Fig. 2. It encodes (1) by sharing common subtrees. Each path starting from the root to the leaves ONE or ZERO corresponds to a diagnostic sequence of tests. For example, a system fail caused by faulty components c6 , c5 and c2 is diagnosed by testing c6 , c4 , c5 , and c2 in Fig. 2. 2.4 Failure rate and unreliability The failure rate λ(t) of a component is the expected number of failures per hour. The unreliability F(t) is the probability that a system (or component) fails in a time interval [0, t]. Considering a constant failure rate λ, the unreliability F(t) is given by F(t) = 1 − e−λt

Such that cpi is the accumulated cost of testing all m components in the cutset i as in (11) m ∑ tj (11) cpi =

(8)

In this work, evaluations are done considering a time interval of 1 year (8760 hours): Qs is the unreliability of system s; qcutseti is the unreliability of cutset i; and Pr{c} 567

However, DC does not consider the ordering of components in BDD. Hence, BDDs with same boolean expression will return the same DC. In order to capture the diﬀerent orders a change is proposed to compute BDD cost. Given a BDD b with n paths from the root to a leaf ONE and m components in path i, the diagnostic cost DC’(b) is given by [m(i) ] n 1 ∑ ∏ DC’(b) =

Qs

·

i=1

j=1

[wj · P r{cj } + (1 − wj ) · (1 − P r{cj })] ·cpi

(12)

where wj = 1 if component cj comes from a 1-edge and wj = 0 otherwise. DC’ is similar to DC in (10), but it is computed over all BDD paths ending in a leaf ONE. 3. PROBLEM DESCRIPTION Modern vehicles have lots of electronic devices performing diﬀerent tasks such as active control, safety, comfort and entertainment. These tasks are executed by several Electronic Control Units (ECU) which are microprocessor units that take care of a particular vehicles’ subsystem. Moreover, they monitor operating conditions which can be used to alert malfunctioning. In digital systems, a fault is an anomalous physical condition of a component. An error is a manifestation of a fault in the system (Nelson, 1990). Based on observed conditions (errors), vehicles’ ECUs are able to generate online alerts to the driver as well as store numerical fault codes (DTCs) to be used in oﬃne vehicle diagnostic. These DTCs are designed to consider several components and subsystems of diﬀerent manufacturers built for diﬀerent vehicles’ models and conﬁgurations. In automotive systems a particular DTC can be considered as root of both FT and BDD trees. For FT tree, it maps a system fault (DTC) into a combination of its possible causes. For BDD tree, it represents a sequence of tests

IFAC AAC 2016 558 June 19-23, 2016. Norrköping, SwedenMarkos F.B.G. Oliveira et al. / IFAC-PapersOnLine 49-11 (2016) 555–561

Fig. 4. Merging strategy for diagnostic. Fig. 3. Diagnostic in automotive systems. that must be performed in order to identify the faulty components which caused the observed condition (DTC). The automotive diagnostic is guided by BDD information. It is important to understand the relation between FTs and BDDs, as BDDs are usually built from corresponding fault trees by a previous fault analysis during vehicle development cycles. Fault analysis and algorithms for generating BDDs from fault trees can be found in Rauzy (1993); Dutuit and Rauzy (2013). The general framework of diagnostic in automotive systems is depicted in Fig. 3. Firstly, a fault generates an observed error in the system. The error is caught by an ECU that trigger a corresponding DTC. However, mainly due to the great complexity of vehicle electronics, the observed error could have several causes. Hence, a diagnostic procedure is necessary. The diagnostic consists of ﬁnding the root cause of an error (DTC) by performing tests on possible faulty components. The test sequence is encoded into a corresponding BDD and carried out by specialized technicians using tools and diagnostic data during maintenance. Thus, the diagnostic task determines the fault component(s) of the system to be repaired or replaced. Definition 14. (Root cause). When multiple DTCs are triggered, the root cause of a system fail is the set of components that caused the active DTCs, i. e., it is the set of faulty components. Replacing or repairing those components, the system should resume to normal (nonfault) operation. A diagnostic procedure with one active DTC is straightforward. The technician executes a sequence of tests presented in a single BDD. However, a strategy of diagnostic in presence of several active DTCs is not easy, particularly when there are BDDs with common components which could cause multiple activations. In this case, the technician has no clue (besides his/her own experience) to decide which sequence of BDDs has to be taken. In addition, 568

depending on which sequence of BDDs is chosen, several tests can be made unnecessarily. Our work presents a strategy for combining multiple BDDs into a single one in order to improve the diagnostic procedure in presence of multiple triggered DTCs. 4. COMBINING MULTIPLE DTCS We propose a merging approach based on the current active and non-active BDDs when multiple DTCs are triggered. Definition 15. (Diagnostic scenario). A diagnostic scenario is deﬁned by two disjoint sets of active (ACT ) and nonactive (ACT ) DTCs. The merging strategy considers the information of which DTCs are active and which ones are not to create a new BDD structure. For example, an automotive system with n predeﬁned DTCs (each one corresponding to a particular BDD) has 2n possible diﬀerent combinations of active and nonactive DTCs, or 2n possible diagnostic scenarios. Although each scenario could be stored for diagnostic, they grow exponentially and thus impose limits to the available memory. Our strategy builds a new sequence of tests dynamically for each particular diagnostic scenario. In this case, only n BDDs have to be stored. The proposed merging strategy is depicted in Fig. 4. Shadow blocks represent procedure blocks in which an operation is done. Standard blocks represent procedure outputs. The algorithm starts by traversing recursively each BDD and evaluating its solutions. The recursive approach is based on an algorithm presented in Rauzy (1993) that utilizes the Shannon decomposition representation of BDDs.

IFAC AAC 2016 June 19-23, 2016. Norrköping, SwedenMarkos F.B.G. Oliveira et al. / IFAC-PapersOnLine 49-11 (2016) 555–561

559

Each individual cutset in a single BDD is a possible root cause of a single DTC. It is represented by a minterm in a boolean expression in disjunctive normal form (DNF). Hence, the set of all cutsets is a complete description of DNF. As the automotive industry encodes sequences of tests using BDDs, they are our basic input data for diagnostic.

There are approaches in the literature that compute the minimal BDD (with the minimum number of nodes). But they do not take into account the importance or cost of each test. Our approach on the other hand attempts to minimize the size of the ﬁnal BDD using a measure of test importance and cost represented by CDIF to deﬁne a variable ordering.

Given a DNF representation for each BDD, the second step is to compute the logical conjunction on these boolean expressions in a particular manner. This evaluation is done using an approach introduced by Assaf and Dugan (2008). It deﬁnes two types of information used to construct the model from which the ﬁnal BDD will be built. The ﬁrst type is collected from sensors that monitors conditions and states of the system. The information of several sensors is combined to construct such model. However, additional system information may be available through further sources. This second type of information, known as evidences, is used to reduce the number of suspected root causes on consideration. This information is used to reﬁne the previous model.

The choice of CDIF is based on its meaning for diagnostic. DIF is a measure associated with a component that quantiﬁes its probability of failure considering a diagnostic scenario. In other words, given a particular set of active DTCs (encoded by the minimal model), it is possible to infer from DIF values which causes (faulty components) are more likely to occur given the current diagnostic scenario. CDIF is derived from DIF, but test costs are also taken into account. Therefore, CDIF is a tradeoﬀ between DIF and test cost.

DTCs in the ACT set are those who actually were triggered and hold some faulty condition through its cutsets. The conjunction of DTCs in ACT yields to a model of the current diagnostic scenario named ACT-model. This model contains the boolean expressions of the BDDs of only active DTCs. A BDD is then built from ACT-model. In addition, this model can be further simpliﬁed by using the ACT set information. This information reduces the number of possible root causes, cutting down the number of cutsets examined in diagnostic. In our proposal, this information is considered as the evidences. The getCUE algorithm presented by Assaf and Dugan (2008) is used to combine the ACT-model with evidences, or ACT and ACT sets respectively. The evidences are included in the ACT-model one by one increasing the knowledge of diagnosis and reducing both the possible causes and the necessary tests. Essentially it performs the conjunction of the boolean expressions of each DTC maintaining its state (active or non-active). This step with further logical minimization results in a set of (minimal) candidates for the root cause of system fail, since any of its members is capable of generate all active DTCs. This set can be viewed as the boolean expression that represents (models) the current diagnostic scenario, in which both ACT and ACT information were used. In this work, this boolean expression is called Minimal model. Definition 16. (Minimal model). The minimal model is the boolean expression that encodes the minimal cutsets of the ﬁnal BDD. These cutsets trigger all active DTCs and do not trigger any non-active DTC. The minimal model represents the diagnostic scenario, from which the ﬁnal BDD is synthesized. However, a variable ordering should be deﬁned to build a BDD from its corresponding boolean expression. In general, the chosen variable ordering has a signiﬁcant impact on the BDD size and thus in the number of diagnostic testes performed.

569

By gathering the minimal model and the variable ordering provided by CDIF, the ﬁnal BDD is built such that components with higher CDIF have priority to be tested. Rauzy (1993) presents an algorithm that creates a BDD from its minimal cutsets using a preﬁxed ordering. Thus the ﬁnal BDD encodes the minimal model to be used for diagnostic when multiple faults occur. Algorithm 1 presents the proposed merging algorithm to deal with multiple faults by computing the ﬁnal BDD. This BDD contains components that cause the active DTCs and do not contain any component that could activate nonactive DTCs. Algorithm 1 Combining multiple faults into a single BDD Require: ACT BDDs: DTC(1), DTC(2), ... , DTC(n); ACT BDDs: DT C(1), DT C(2), ... , DT C(m) Ensure: ﬁnal BDD: DTCm function createACT-model(ACT) for i = 1 to n do Compute minimal cutsets MC(i) for DTC(i) ∈ ACT end for ACT-model ← MC(1) for i = 2 to n do ACT-model ← ACT-model ∧ MC(i) end for end function function getCUE(ACT-model, ACT ) // (see Assaf and Dugan (2008)) Minimal model ← ACT-model for i = 1 to m do Minimal model ← Minimal model ∧ DT C(i) end for end function Compute CDIF for all c ∈ var(Minimal model) Built DTCm by ordering variables according to CDIF

However, an interactive procedure is made in a practical diagnostic as shown in Fig. 5. After each iteration, input BDDs are updated to take into account ﬁxed components (replaced or repaired). This is done by setting the corresponding variable to ZERO in the boolean expressions.

IFAC AAC 2016 560 June 19-23, 2016. Norrköping, SwedenMarkos F.B.G. Oliveira et al. / IFAC-PapersOnLine 49-11 (2016) 555–561

Fig. 5. The proposed diagnostic approach using a merging strategy for several root causes. Hence, the number of DTCs should decrease as faulty components are identified and fixed. The diagnostic ends by clearing all DTCs which means that all faulty components were fixed. This means that all components are good and no more tests are necessary.

Fig. 6. BDDs for example 17. Table 2. Diagnostic cost for each BDD. BDD DT C2 DT C3 DT C4 Total

5. ILLUSTRATIVE EXAMPLE Example 17. Suppose a system composed by seven components c1 , . . . , c7 and four diagnostic trouble codes DT C1 , . . . , DT C4 which are diagnosed by means of four boolean expressions s1 , s2 , . . . , s4 whose BDDs are depicted in Fig. 6. Probabilities of fail and test costs of components are given in Table 1. Also suppose that three DTCs are triggered: DT C2 , DT C3 and DT C4 . The diagnostic scenario is then defined by ACT = {DT C2 , DT C3 , DT C4 } and ACT = {DT C1 }. Table 1. Probabilities of fail and test costs of components. Component Pr{c} tc (\$)

c1 0.002 200

c2 0.1 1000

c3 0.05 300

c4 0.2 250

c5 0.04 500

c6 0.05 750

Cost (\$) 1336.2 560.00 1551.7 3447.9

c2 c4 c6 . Furthermore, the evidences are included in the model by using ACT . The resulting boolean expression is then sm = c2 c3 c4 + c2 c4 c6 . Such model is a more compact representation of the diagnostic scenario because it encodes both ACT and ACT sets. CDIF values for each variable in sm are necessary to define the sequence of tests to be applied in possible fault components. They are shown in Table 3. Table 3. CDIF for possible fault components.

c7 0.01 500

Component CDIF

The corresponding boolean expressions are s1 = c1 + c3 c7 + c2 c5 c6 , s2 = c1 + c2 c4 , s3 = c3 + c4 + c5 , and s4 = c1 + c2 c3 + c2 c6 . The standard approach used in industry is to consider each BDD of Fig. 6 independently. The diagnostic cost of active DTCs according to (12) is shown in Table 2. The logical conjunction and minimization of the individual minimal cuts results in sact = c1 c3 + c1 c4 + c1 c5 + c2 c3 c4 + 570

c2 1 · 10−3

c3 1.75 · 10−3

c4 4 · 10−3

c6 7 · 10−4

A test with higher CDIF appear first in the final BDD as shown in Fig. 7. Note that component c1 is not in sm as it is not faulty for sure (otherwise, DT C1 would be active too). By using the standard diagnostic approach, c1 might be unnecessarily tested. The diagnostic cost for the BDD of Fig. 7 is \$1868.4 which corresponds to 54% of the cost using the standard diagnostic approach.

IFAC AAC 2016 June 19-23, 2016. Norrköping, SwedenMarkos F.B.G. Oliveira et al. / IFAC-PapersOnLine 49-11 (2016) 555–561

561

Yuan, K. and Hu, S. (2009). Multiple-fault diagnosis based on binary decision diagram. In Proc. of the Int. Conf. on Industrial Eng. and Eng. Management, 1658–1662.

Fig. 7. Resultant BDD. 6. CONCLUSION Guided diagnostic tools in automotive industry usually recovery hundreds of DTCs logged into electronic devices due to active system fails. Each DTC has a corresponding BDD with possible common faulty components which makes diagnostics a diﬃcult task. This work has proposed a strategy for combining multiple BDDs into a single one by considering active and non-active DTCs. The results have been evaluated in terms of the total diagnostic cost using a slightly diﬀerent metric found in the literature. They have shown that a signiﬁcant decrease in cost is obtained by avoiding tests of components that do not aﬀect a particular diagnostic scenario. Future work considers to implement this approach in a guided diagnostic tool. ACKNOWLEDGEMENTS The authors thank F. Mori from Volvo do Brasil for his helpful technical support. REFERENCES Assaf, T. and Dugan, J.B. (2008). Diagnosis based on reliability analysis using monitors and sensors. Reliability Engineering and System Safety, 93, 509–521. Dutuit, Y. and Rauzy, A. (2013). Importance factors of coherent systems: a review. Proc. of the Inst. of Mechanical Engineers, Part O: Journal of Risk and Reliability, 228(3), 313–323. Nelson, V.P. (1990). Fault-tolerant computing: fundamental concepts. Computer, 23(7), 19–25. Rauzy, A. (1993). New algorithms for fault trees analysis. Reliability Engineering and System Safety, 40(3), 203– 211. Reay, K.A. and Andrews, J.D. (2002). A fault tree analysis strategy using binary decision diagrams. Reliability Engineering and System Safety, 78, 45–56. Remenyte, R. and Andrews, J.D. (2006). A simple component connection approach for fault tree conversion to binary decision diagram. In Proc. of the First Int. Conf. on Availability, Reliability and Security, 1–6. Suwatthikul, J. (2010). Fault detection and diagnosis for in-vehicle networks. In W. Zhang (ed.), Fault Detection, chapter 13, 283–306. InTech. 571