A new heuristics for the event ordering in binary decision diagram applied in fault tree analysis

Abstract

Fault tree is a common approach in probabilistic risk assessment of complex engineering systems. Since their introduction, binary decision diagrams proved to be a valuable tool for complete quantification of hard fault tree models. As is known, the size of the binary decision diagram representation is mainly determined by the quality of the selected fault tree event ordering scheme. Finding the optimal event ordering for binary decision diagram representation is a computationally intractable problem, for which reason heuristic approaches are applied to find reasonable good ordering schemes. The existing method for finding optimal ordering schemes related to special types of fan-in 2 read-once formulas is employed in our research to develop a new heuristic for fault tree. Various fault tree simplification methods are used for the sake of reducing fault tree model discrepancy from fan-in 2 read-once formulas. The reduced fault tree is traversed in a depth-first manner, as for every gate, the best ordering scheme is chosen from selected sets of input permutations. The quality of the final event ordering scheme is compared to orderings produced with depth-first left most heuristic on a set of fault tree models addressed in the literature as well as on a set of our hard models. Our method proves to be a useful heuristic for finding good static event ordering, and it compares favourably to the known heuristic based on a depth-first left most assignment approach.

Keywords

Binary decision diagrams event ordering fault tree analysis probabilistic risk assessment reliability engineering

Introduction

The fault tree (FT) is frequently used to analyse safety and reliability requirements of complex engineering systems. At the beginning of the 1960s, FT was introduced by Bell Laboratories for the purposes of evaluating the Minuteman I launch control system. Afterwards it was further developed by numerous civil and military contributors in order to utilize computer-based probabilistic risk assessment (PRA) tools.¹ Usually, FT models are depicted graphically in form of a tree structure which represents a logical connection between possible events during the deductive analysis of the undesired top event.

Figure 1 presents a simple model where the top event (gate G1) shows logical connections between basic events (E1–E6) leading to G1 gate. This kind of logical connection can be written in form of logical functions. The graphical view below shows the logical function G1 = E6 ∨ (2, (E1 ∨ E2), E5, (E3 ∧ E4)) where G3 operation (tagged) represents ‘2-out-of-3’ voting OR logical expressions, meaning that it happens, if at least two of three inputs have occurred.

Figure 1.

Example of a simple fault tree.

In general, FTs are used to investigate potential faults, modes and causes as well as to quantify their contribution to a system’s unreliability or to find importance factors for the components’ unavailability.² Traditionally, FT models are initially analysed qualitatively and then quantitatively. The qualitative analysis aims to find component failure lists which are essential and sufficient to cause the top event. These lists are often referred to as minimal cut sets and are widely employed in quantitative analysis of FT models. The typical quantitative assessment is performed on minimal cut sets to find the probability of occurrences of a top event and to compute the importance measures for various contributing events.

Binary decision diagram (BDD) structures were introduced by Lee³ and Akers,⁴ although the representation of logical functions with two-terminal graphs had been developed earlier by several mathematicians.⁵ Akers systematically introduced BDDs and the basic terminology, though, the true popularity of the latter was achieved through Bryant’s⁶ thesis, where the author developed modern graph-based algorithms to be worked with. Moreover, BDD variants optimized for specific areas of application were developed and analysed in the Wegener⁷ paper. Since their introduction, it has become clear that the size of BDD representations of every logical function depends on the selection of a variable ordering scheme. BDDs in which this variable ordering scheme is kept equal at all paths from the top node are denoted as ordered BDD (OBDD). Whereas, OBDD representation reduced by the Bryant reduction algorithm is defined as the reduced OBDD (ROBDD). In this article, it is assumed that the ROBDD representation is used whenever the term BDD representation is mentioned.

A BDD approach to FT analysis (FTA) has been developed (Rauzy⁸) as an alternative to conventional methods which are based on Boolean algebra rewriting rules. Since BDDs uniquely encode Shannon decomposition of logical functions by means of shared subtrees, BDDs are usually built from FT models in a bottom-up approach. The bottom-up approach is carried out conveniently by means of the ite connectivity defined with ite(F, G, H) = (F ∧ G)∨(¬F ∧ H) as shown in the Rauzy⁸ paper.

For clarity sake of the bottom-up approach, let us illustrate how to build BDD for the logical expression (G4 ∧ G8) from the FT example (Figure 1), assuming that the variable ordering is defined as E3 < E1 < E6 < E4 < E2 < E5.

Then

\begin{matrix} G 4 = ite (E 3, ite (E 4, 1, 0), 0) \\ G 8 = ite (E 1, 1, ite (E 2, 1, 0)) \\ \begin{matrix} G 4 \land G 8 = ite (E 3, ite (E 4, 1, 0), 0) \land ite (E 1, 1, ite (E 2, 1, 0)), 0) \\ = ite (E 3, ite (E 4, 1, 0) \land ite (E 1, 1, ite (E 2, 1, 0)), 0) \\ = ite (E 3, ite (E 1, ite (E 4, 1, 0), ite (E 4, 1, 0) \land ite (E 2, 1, 0)), 0) \\ = ite (E 3, ite (E 1, ite (E 4, 1, 0), ite (E 4, ite (E 2, 1, 0), 0)), 0) \end{matrix} \end{matrix}

Immediately after the Bryant seminal work, Friedman and Supowit⁹ created an algorithm of exponential complexity for finding the optimal variable ordering. Several other algorithms were created afterwards, yet they are applicable only for small sized problems, typically up to 50 variables. Computing an optimal variable ordering, and by this the event ordering for FT analysis, happens to be a non-deterministic polynomial-time (NP)-hard problem;¹⁰ however, the decision problem of improving variable ordering is NP-complete.¹¹ Therefore, the hardness of the problem justifies the use of heuristic approaches for finding a good initial event ordering scheme for FTA^12,13 or an event tree analysis (ETA).¹⁴

The following section briefly explains an optimal ordering algorithm for a special kind of fan-in 2 read-once formulas. The remainder of the article is structured in the following order: section three explains the new heuristic approach along with FT simplification techniques, section four presents the used benchmarks and results achieved, providing an explanation of the advantages of the new approach. Finally, the last section brings the conclusion, encouraging further research.

Related work

Fan-in 2 read-once formulas on n logical variables {x₁, …, x_n} are represented by a binary tree having exactly n leaf nodes labelled with variables and internal nodes denoting one of the binary logical operations (AND, OR, XOR, …) on two children nodes. For example, the following binary tree (Figure 2) represents the formula ((x₁ ∧ x₂) ∨ (x₃ ∧ x₄)) ∧ ((x₅ ∨ x₆) ∧ x₇).

Figure 2.

Example of fan-in 2 read-once formula: ((x₁ ∧ x₂) ∨ (x₃ ∧ x₄)) ∧ ((x₅ ∨ x₆) ∧ x₇).

The optimal variable ordering scheme for fan-in 2 read-once formulas can be computed with an algorithm developed by Sauerhoff et al.¹⁵ Their algorithm is based on recursive equations for binary operations {and, or, xor}. At each gate, two numbers are calculated for optimal sizes of the BDDs with or without complemented edges. From these two numbers, the recursive equations define the rules for the computation of the optimal BDD size. As pointed out in Sauerhoff et al.,¹⁵ the optimal BDD size for a single variable requires one BDD node with complemented edges, or two without. Recursively, following the single variable case upwards to the final formula, the authors presented a way to construct an optimal ordering by using only two sets of recursive equations, one set for {and, or } operations and another set for xor operation. In addition, they proved upper and lower bounds on an optimal BDD size for an arbitrary logical function on the restricted class of fan-in 2 read-once formulas. Since their algorithm is not directly applicable to FT models, it can be used in case where no overlapping between inputs to FT gate occurs, that is, in case where no formula sharing between gate inputs exists. Basically, it means that we can apply the respective algorithm with gates having only basic events as inputs or with gates having inputs from other gates without shared basic events. In addition, FT models considered in this article are models built with AND/OR gate operations, thereby enabling us to use a single set of recursive equations from their work.

Method

In this section, we are going to detail our newly developed heuristic approach to the variable ordering scheme throughout these subsections ‘FT simplification’ techniques arising from common logical equivalence rules; ‘New ordering heuristic’, which is the most important part of the new approach and ‘An outline of the algorithm’ with an optional BDD size reduction step.

FT simplification

Before the application of an ordering method, the FT structure has been simplified as much as possible. One of the approaches is to split complex FT models into simpler FTs by means of the functional decomposition with respect to a small subset of basic events.¹⁶ In this article, we perform a simpler approach based on logically equivalent formula rewriting rules¹⁷ which may be applied iteratively as long as any changes are made in the FT, that is:

The associativity rule – elimination of all equivalence gates by exchanging the references into gates they represent

The K-of-N expansion rule – elimination of all K-of-N operators by rewriting them into equivalent AND/OR combinations according to the following rule of the gate expansion: $(k, F_{1}, \dots, F_{n}) = (F_{1} \land (k - 1, F_{2}, \dots, F_{n})) \lor (k, F_{2}, \dots, F_{n})$ The K-of-N (voting OR) gate can be decomposed by more complex rules¹⁸ which we left for future implementations.

Application of the idempotent law rules on the FT to eliminate the terms with multiple equal gate inputs: X∧X≡X, X∨X≡X.

By applying the law of absorption rule to the AND/OR gates, the inputs are simplified by absorbing like terms: (X∧Y)∨X≡X, (X∨Y)∧X≡X.

From the given example, we show that the simple FT model has been modified by the application of K-of-N expansion rule (see Figure 3). The gate G3 operation is rewritten to the equivalent combination of the AND/OR operations (tagged) as follows

\begin{matrix} G 3 = (2, G 8, E 5, G 4) = G 31 \lor G 32 \lor G 33 \\ = (G 8 \land E 5) \lor (G 8 \land G 4) \lor (E 5 \land G 4) \end{matrix}

Figure 3.

The G3 gate operation expanded to equivalent formula.

After the simplification steps, the FT has been traversed to find blocks of gates which behave like a single entity, that is, modularization.¹⁹ Generally, two module finding algorithms are widely used to reduce the computational costs of BDD operations on the FT. The first one, derived by Kohda et al.,²⁰ is based on formula rewriting rules to detect and define modules on the FTs composed from the gates with logical AND/OR operation only. The second method developed by Dutuit and Rauzy²¹ uses a variation of the Tarjan algorithm for finding strongly connected graph components, thus being more universal since it does not depend on the gate operation. Both algorithms perform equally well on the common FT models with only AND/OR gates, consequently we employ the latter method as it does not depend on the gate operation. For instance, the simple FT model presented here entails the following module top gates: G8, G4, G3 and G1.

New ordering heuristic

Based on the algorithm for fan-in 2 read-once formulas, we developed an ordering approach to sequentially combine the orders from the gate inputs. The idea is to utilize, as frequently as possible, the fan-in 2 read-once order combination technique on non-overlapping gate inputs. To be more specific, when orders from two gate inputs do not share events, the Sauerhoff, Wegener and Wercher algorithm is applied. However, if they do share events, they are combined according to the number of BDD nodes generated for each event in these orders. For implementation, each event in order is assigned two numbers (nodes₁ and nodes₂) entailing the estimated number of BDD nodes, whereby nodes₁ holds the count of the BDD nodes with complemented edges, while nodes₂ holds the count of the BDD nodes without complemented edges. Our new order combining approach is defined by the following algorithm.

CombineOrders( g, A, π_F)
1 g – the gate for which we build an order 2 A – array of orders for the gates adjacent to g 3 π– the final order for g 4 $π \leftarrow π_{F}$ 5 For each order $π_{i}$ from the array A do 6 if $(π_{i} \cap π) \neq Ø$ then 7 $π_{n} \leftarrow Ø$ 8 $node s_{1, 2} (π_{n}) \leftarrow 0$ 9 For each event in orders $(π, π_{i})$ 10 Let e₁ be next event from $π$ not present in $π_{n}$ 11 Let e₂ be next event from $π_{i}$ not present in $π_{n}$ 12 $s_{1} \leftarrow 2 * node s_{1} (e_{1}) + node s_{2} (e_{2})$ 13 $s_{2} \leftarrow 2 * node s_{1} (e_{2}) + node s_{2} (e_{1})$ 14 if $s_{1} < s_{2}$ then 15 append $e_{1}$ to order $π_{n}$ 16 $node s_{1} (e_{1}) \leftarrow node s_{1} (e_{1}) + node s_{1} (e_{2})$ 17 $node s_{2} (e_{1}) \leftarrow s_{1}$ 18 else 19 append $e_{2}$ to order $π_{n}$ 20 $node s_{1} (e_{2}) \leftarrow node s_{1} (e_{1}) + node s_{1} (e_{2})$ 21 $node s_{2} (e_{2}) \leftarrow s_{2}$ 22 end if 23 end for 24 $π \leftarrow π_{n}$ 25 else 26 $s_{1} \leftarrow 2 * node s_{1} (π) + node s_{2} (π_{i})$ 27 $s_{2} \leftarrow 2 * node s_{1} (π_{i}) + node s_{2} (π)$ 28 $node s_{1} (π) \leftarrow node s_{1} (π) + node s_{1} (π_{i})$ 29 if $s_{1} < s_{2}$ then 30 append to π events from $π_{i}$ after the events from π 31 $node s_{2} (π) \leftarrow s_{1}$ 32 else 33 append to π events from $π_{i}$ before the events from π 34 $node s_{2} (π) \leftarrow s_{2}$ 35 end if 36 end if 37 end for 38 return π

CombineOrders( g, A, π_F)

1 g – the gate for which we build an order
2 A – array of orders for the gates adjacent to g
3 π– the final order for g
4

π \leftarrow π_{F}

5 For each order

π_{i}

from the array A do
6 if

(π_{i} \cap π) \neq Ø

then
7

π_{n} \leftarrow Ø

node s_{1, 2} (π_{n}) \leftarrow 0

9 For each event in orders

(π, π_{i})

10 Let e₁ be next event from

π

not present in

π_{n}

11 Let e₂ be next event from

π_{i}

not present in

π_{n}

s_{1} \leftarrow 2 * node s_{1} (e_{1}) + node s_{2} (e_{2})

s_{2} \leftarrow 2 * node s_{1} (e_{2}) + node s_{2} (e_{1})

14 if

s_{1} < s_{2}

then
15 append

e_{1}

to order

π_{n}

node s_{1} (e_{1}) \leftarrow node s_{1} (e_{1}) + node s_{1} (e_{2})

node s_{2} (e_{1}) \leftarrow s_{1}

18 else
19 append

e_{2}

to order

π_{n}

node s_{1} (e_{2}) \leftarrow node s_{1} (e_{1}) + node s_{1} (e_{2})

node s_{2} (e_{2}) \leftarrow s_{2}

22 end if
23 end for
24

π \leftarrow π_{n}

25 else
26

s_{1} \leftarrow 2 * node s_{1} (π) + node s_{2} (π_{i})

s_{2} \leftarrow 2 * node s_{1} (π_{i}) + node s_{2} (π)

node s_{1} (π) \leftarrow node s_{1} (π) + node s_{1} (π_{i})

29 if

s_{1} < s_{2}

then
30 append to π events from

π_{i}

after the events from π
31

node s_{2} (π) \leftarrow s_{1}

32 else
33 append to π events from

π_{i}

before the events from π
34

node s_{2} (π) \leftarrow s_{2}

35 end if
36 end if
37 end for
38 return π

Considering the above algorithm, the order for each gate is computed from the orders associated with the adjacent gates, which are considered from left to right (Line 5). In Line 6, we check the existence of shared events between orders; in case of their non-existence we proceed with the Sauerhoff algorithm (Lines 26–35). However, if we establish the existence of shared events the algorithm (Lines 7–24) alternatively proceeds with the implementation of our approach. For example, let us combine orders for gate G3 from intermediate gates after the simplification of the FT model. We assume that the orders

\begin{matrix} π_{1} = {(3, 6) {E 5 : (1, 2), E 1 : (1, 2), E 2 : (1, 2)}} \\ π_{2} = {(4, 8) {E 3 : (1, 2), E 4 : (1, 2), E 1 : (1, 2), E 2 : (1, 2)}} \\ π_{3} = {(3, 6) {E 5 : (1, 2), E 3 : (1, 2), E 4 : (1, 2)}} \end{matrix}

are computed for gates G31, G32 and G33, respectively. On the first pass, through our approach the order $π$ is initialized with π₁. Since each order entails a pair of nodes_1,2 values followed by a list of basic events carrying their associated pair of nodes_1,2 values, the loop iteration proceeds as follows:

0:π={(3,6) {E5:(1,2), E1:(1,2), E2:(1,2)}}, π₂ ={(4,8) {E3:(1,2), E4:(1,2), E1:(1,2), E2:(1,2)}}

1:e₁ = E5:(1,2), e₂ = E3:(1,2), π_n ={(2,4) {E3:(2,4)}}

2:e₁ = E5:(1,2), e₂= E4:(1,2), π_n ={(4,8) {E3:(2,4), E4:(2,4)}}

3:e₁ = E5:(1,2), e₂ = E1:(1,2), π_n ={(6,12) {E3:(2,4), E4:(2,4), E1(2,4)}}

4:e₁ = E5:(1,2), e₂ ={E2:(1,2)}, π_n ={(8,16) {E3:(2,4), E4:(2,4), E1(2,4), E2:(2,4)}}

5:e₁ = E5:(1,2), e₂ ={}, π_n ={(9,17) {E3:(2,4), E4:(2,4), E1(2,4), E2:(2,4), E5:(1,2)}}

6:π_n ={(9,17) {E3:(2,4), E4:(2,4), E1(2,4), E2:(2,4), E5:(1,2)}}

7:π = {(9,17) {E3:(2,4), E4:(2,4), E1(2,4), E2:(2,4), E5:(1,2)}}, π₃ ={(3,6) {E5:(1,2), E3:(1,2), E4:(1,2)}}

8:e₁=E3:(2,4), e₂=E5:(1,2), π_n ={(2,4) {E5:(2,4)}}

9: e₁ = E3:(2,4), e₂ = E3:(1,2), π_n ={(5,10) {E5:(2,4), E3:(3,6)}}

10: e₁ = E4:(2,4), e₂ = E4:(1,2), π_n ={(8,16) {E5:(2,4), E3:(3,6), E4(3,6)}}

11: e₁ = E1:(2,4), e₂ ={}, π_n ={(10,20) {E5:(2,4), E3:(3,6), E4(3,6), E1:(2,4)}}

12: e₁ = E2:(2,4), e₂ ={}, π_n ={(12,24) {E5:(2,4), E3:(3,6), E4(3,6), E1:(2,4), E2:(2,4)}}

13: π = π_n ={(12,24) {E5:(2,4), E3:(3,6), E4(3,6), E1:(2,4), E2:(2,4)}}

By this a new order from gate inputs is computed, which herein becomes the actual order for gate G3.

An outline of the algorithm

As it is known, in the conventional approach to FTA the model is traversed in a depth-first manner, whereby actions are performed on each encountered gate. In our approach we are going to apply the FindBestOrder procedure to compute the proposed order for the observed gate. For instance, the order for G1 gate from the FT example is built by means of the FindBestOrder procedure on the following gates: G8, G4, G31, G32, G33, G3 and G1. By applying the FindBestOrder procedure we intend to generate different permutations of adjacent gate inputs and employ the new heuristic to combine the orders from them. Among all generated orderings for the specific gate, the order with the smallest BDD in size will be selected.

FindBestOrder( g, A, π)
1 g – the gate for which we build an order 2 A – array of orders for the gates adjacent to g 3 F – array of orders which are fixed for all generated permutations of A 4 <Move basic events from A to F which are directly adjacent to g> 5 <Move orders from A to F which are module tops> 6 $π_{F} \leftarrow CombineOrders (g, F, Ø)$ 7 <Initialize calculations> 8 For each new permutation A_p from A do 9 $π_{n} \leftarrow CombineOrders (g, A_{p}, π_{F})$ 10 <Build BDD of g with order $π_{n}$ > 11 size ← number of BDD nodes for gate g with order $π_{n}$ 12 if size<best_so_far_size then 13 $π \leftarrow π_{n}$ 14 best_so_far_size ← size 15 end if 16 if number of generated permutations greater than some limit then 17 Exit For 18 end if 19 end for 20 <Apply optional dynamic reordering step to the order $π$ > 21 return π

FindBestOrder( g, A, π)

1 g – the gate for which we build an order
2 A – array of orders for the gates adjacent to g
3 F – array of orders which are fixed for all generated permutations of A
4 <Move basic events from A to F which are directly adjacent to g>
5 <Move orders from A to F which are module tops>
6

π_{F} \leftarrow CombineOrders (g, F, Ø)

7 <Initialize calculations>
8 For each new permutation A_p from A do
9

π_{n} \leftarrow CombineOrders (g, A_{p}, π_{F})

10 <Build BDD of g with order

π_{n}

>
11 size ← number of BDD nodes for gate g with order

π_{n}

12 if size<best_so_far_size then
13

π \leftarrow π_{n}

14 best_so_far_size ← size
15 end if
16 if number of generated permutations greater than some limit then
17 Exit For
18 end if
19 end for
20 <Apply optional dynamic reordering step to the order

π

>
21 return π

As presented in the above algorithm, the initialization is performed at the beginning of the procedure (Lines 4–6). The result of this initialization (denoted as $π_{F}$ ) is achieved by employing our heuristic to combine directly connected adjacent events with orders from adjacent gates which are module top gates. Following that, we set the two limits for the underlying BDD engine, that is, the time limit and the maximum number of nodes allowed. The purpose of this is to reject orders which are inefficient in terms of time or nodes to be finished. The remaining adjacent gates are permuted and, by applying our heuristic, combined with π_F to create a complete order for the gate; subsequently, it is checked and best in size selected (Lines 8–19). The permutation loop is limited to 120 repetitions, which makes good trade-offs between the quality of the generated order and time to find it.

For further understanding of this procedure, let us study an example with G3 inputs {G31, G32, G33}, which are entailed in the array of orders A from adjacent gates. Within the loop we use all possible permutations of this array

\begin{matrix} {G 31, G 32, G 33}, {G 31, G 33, G 32}, {G 32, G 31, G 33}, \\ {G 32, G 33, G 31}, {G 33, G 31, G 32}, {G 33, G 32, G 31} \end{matrix}

as the input to our heuristic. With the intention to build the order for top gate G1 we must combine the order for gate G3 with event E6. In the earlier presented example for CombineOrders heuristic we created the order for G3 gate, which is

π_{G 3} = {(12, 24) {E 5 : (2, 4), E 3 : (3, 6), E 4 (3, 6), E 1 : (2, 4), E 2 : (2, 4)}}

Both, E6 as the directly connected adjacent event and G3 as module top gate are combined with our heuristic (Lines 4–6) to the final order for G1 gate

π = {(13, 26) {E 6 : (1, 2), E 5 : (2, 4), E 3 : (3, 6), E 4 (3, 6), E 1 : (2, 4), E 2 : (2, 4)}}

An interesting fact arising from the upper order of our example is that, actually we expected 13 BDD nodes for the FT model, however, once it was built it eventually resulted in 10 nodes.

The generally used method for the reduction of BDD size is the dynamic reordering following the construction step, which in this case is optional (Line 20). There are various dynamic reordering schemes based on the swap of two adjacent variables in an algorithm developed by Rudell.²² Commonly used methods are group sifting²³ and minimization by exploiting of strong symmetries between variables.^24,25 For this paper we selected the group sifting method as an optional BDD size reduction step (Line 20). For instance, the generated order from the algorithm is reduced from 10 to 9 BDD nodes for the FT model in our example, which is an optimal number of nodes for such a small example. As the results will show, the optional dynamic reordering step proves to be useful, and more importantly, being the key step for a successful construction of BDDs for large FT models.

Results and discussion

This section presents the test results obtained from applying the new ordering heuristic to a selected set of FT models from the literature^26,27 and to a set of own large FTs from industry applications. The proposed ordering heuristic is compared to the best results obtained from depth-first left most (DFLM). The Colorado University Decision Diagram (CUDD) BDD package is used to implement DFLM as well as the new algorithm presented in this article. Since it is clear that there is no benefit from selecting gate inputs in any order,²⁸ we decided to perform tests with DFLM and our heuristic for 100 times with a randomized ordering of inputs at each gate. For a better assessment of the results gained with the new method, the following statistics for top gate BDD size of each FT model were collected: minimum number of nodes, average number of nodes and maximum number of nodes out of 100 runs.

Comparison on small-to-medium FT models

In the first set of tests from the literature, we used 41 small-to-medium sized FTs from the Aralia benchmark test,^26,27 that is, tests with less than 1000 events and gates aggregative. These FTs originate from different sources and have different characteristics in terms of size, structure, and number of internal connections among the gates and basic events. The results of the tests are summarized in Table 1, both for the DFLM and for the herein presented new approach. It is important to mention that all runs (for DFLM and the new heuristic) give variable orderings with which the BDD from the FT model was constructed within the given limits (up to 100M nodes) on the CUDD package. The results are also presented graphically in Figure 4.

Table 1.

Results for the comparison of DFLM and new heuristic on small to medium FT models from the Aralia benchmark set.

Fault tree model			DFLM heuristic BDD size			New heuristic BDD size
Name	Events	Gates	Min.	Avg.	Max.	Min.	Avg.	Max.
baobab1	61	84	1615	5194	16,162	2025	2207	2439
baobab2	32	40	197	346	494	226	259	290
baobab3	80	107	2992	11,461	26,509	3582	3995	4341
cea9601	186	201	11,415	215,573	1.5M	5400	8185	10,042
chinese	25	36	73	105	143	66	68	71
das9201	122	82	569	775	898	191	230	273
das9202	49	36	108	236	347	50	79	108
das9203	51	30	60	111	179	55	59	62
das9204	53	30	61	89	122	53	53	53
das9205	51	20	52	52	52	52	52	52
das9206	121	112	449	1388	2340	474	546	636
das9207	276	324	2934	13,375	47,178	3143	5395	13,229
das9208	103	145	1186	2131	5240	1270	1357	1516
das9209	109	73	110	137	191	111	156	200
das9601	122	288	1277	2343	4140	1109	1444	1843
edf9201	183	132	1706	2094	2910	1302	1391	1446
edf9202	458	435	471	689	1841	440	488	577
edf9203	362	475	8381	20,892	74,845	8338	38,372	55,828
edf9204	323	375	6864	30,958	89,934	22,544	25,458	54,402
edf9205	165	142	448	1011	2037	471	505	554
edf9206	240	362	733	4095	17,880	907	1477	1849
edfpa14b	311	290	6616	21,735	63,683	7890	22,916	52,043
edfpa14o	311	173	6829	21,805	60,925	9563	17,506	38,646
edfpa14p	124	101	2855	10,401	35,887	6579	15,526	39,259
edfpa14q	311	194	7638	23,304	79,589	4990	7108	12,336
edfpa14r	106	132	2817	9982	38,363	2714	13,951	51,827
edfpa15b	283	249	2400	7542	18,808	2322	3700	11,820
edfpa15o	283	138	2356	7910	20,817	4111	6170	9567
edfpa15p	100	80	914	4326	14,906	1703	2522	7715
edfpa15q	289	151	2175	7677	25,879	1698	2013	2333
edfpa15r	88	110	861	3543	9990	1005	1521	3227
elf9601	145	242	962	3114	7620	638	652	665
ftr10	175	94	289	1144	1928	181	220	297
isp9601	143	104	383	853	2193	238	283	346
isp9602	116	122	529	1302	2313	444	452	459
isp9603	91	95	440	1464	3203	443	481	522
isp9604	215	132	701	1103	1930	487	518	525
isp9605	32	40	185	439	748	244	244	244
isp9606	89	41	142	283	550	108	137	184
isp9607	74	65	274	469	643	122	130	140
jbd-001	533	315	5248	50,328	321,132	8569	12,191	24,280
Average BDD size ratio DFLM/new heuristic			1.1	2.8	7.6

DFLM: depth-first left most; BDD: binary decision diagram.

Figure 4.

Graphical view of results for the comparison of DFLM (left bar/black) and the new heuristic (right bar/orange) on small-to-medium FT models from the Aralia benchmark set.

The comparison shows that the best results for the new method are nearly the same as the best results achieved with the DFLM method (column Min. in Table 1). Comparing average ratios of BDD results, the new heuristic performs better than the DFLM to an average of almost three times (precisely 2.8). What is more important, in most cases the new heuristic outperforms the average DFLM results by several times, even 26 times in one case (cea9601). In addition to that, the new method appears rather stable in producing good orderings for the analysed FTs, since the average ratio between the maximum and minimum size is less than three, while for the DFLM approach it is more than 11 (more than eight if cea9601 is thrown). This proves equally the stability of the approach as well as the quality of the orders obtained by our heuristic approach.

In addition to that, a single run was made with the new heuristic to check the correlation between the estimated size and built size without sifting (Table 3 in Appendix 1). On average, the estimated size is approximately 4.5 times bigger than the BDD built size and it is achieved in a reasonable time. The longest running time for the heuristic was approximately 5 min on the edf9202 model, which is still acceptable. It is worthwhile mentioning that in one test (das9207), the estimated size from our heuristic proved to be extremely overestimated, approximately 100 times more than the built size. Apart from that extreme result, the estimated size from our heuristic is on average two times bigger than the built size. After the optional reordering method was applied on built BDDs, the size further lowered on average by a factor of 1.85, that is, approximately 46% less BDD nodes are needed to represent a selected benchmark set.

Comparison on large FT models

In addition to tests performed on the Aralia benchmark set, we selected some of own larger FT models from nuclear industry, that is, FT models in which the sum of gates and events exceed 1000. The largest selected model (i.e. cored2) reaches the limits of the CUDD engine, while others happen to be too large for a plain DFLM heuristic. Therefore, we decide to implement the DFLM heuristic with an automatic dynamic reordering (the group sifting method) during the BDD construction phase which is a common approach in constructing BDDs for large models. For such an extensive test, we employ the optional dynamic reordering step in FindBestOrder procedure on gate orders expecting a number of BDD nodes within the range from 1M up to 10M nodes. The tests were run for 10 times with an increased limit on the CUDD package to 1000M nodes.

The results are summarized in Table 2 and graphically presented in Figure 5. As shown in Table 2, the DFLM heuristic fails to produce the ordering within the limits on ‘cored1’ and ‘cored2’ FTs, while in other tests the DFLM heuristic, compared to our approach, performs consistently worse. In terms of the stability for the new method, the model complexity has moderate impact, since the average ratio between maximum and minimum results is less than three, similar to small-to-medium models. In the last row, it is possible to compare averaging ratios, excluding the ‘cored1’ and ‘cored2’ tests. Here, even for the best results, the new approach is consistently, nearly two times, better compared to the DFLM with automatic dynamic orderings applied during the construction phase. The average results prove that our approach performs far better yielding a ratio over five, while in one case the ratio surges convincingly higher (to 11.7 for ‘chrgr’).

Table 2.

Results for the comparison of DFLM and new heuristic for large FT models.

Fault tree model			DFLM heuristic BDD size			New heuristic BDD size
Name	Events	Gates	Min.	Avg.	Max.	Min.	Avg.	Max.
acp	409	674	3092	15,705	31,972	3047	3270	3584
chrgr	438	695	67,032	348,155	1.2M	25,305	29,626	31,505
cored1	1319	1279	n/a	n/a	n/a	19M	23M	39M
cored2	1377	1633	n/a	n/a	n/a	337M	499M	541M
dcp	447	706	43,835	265,403	1.1M	26,660	49,013	83,504
efw	692	957	350,408	2.5M	7.5M	349,251	490,275	1M
hpsi	674	940	70,827	153,712	480,635	21,369	29,370	41,164
lpsi	525	760	18,863	44,505	82,147	9516	18,962	60,552
sw	444	720	32,210	103,408	379,953	19,421	31,422	39,385
Average size ratio DFLM/new			1.9	5.4	13.0

DFLM: depth-first left most; BDD: binary decision diagram.

Figure 5.

Results (BDD size) for the comparison of DFLM (left bar/black) and new (right bar/orange) heuristic for larger FT models.

Discussion

Considering small-to-medium sized models, both heuristics produce orderings with which the BDD representation for every FT model was built. The results on tests with small-to-medium sized models show that on the average, our heuristic produces better event ordering than the DFLM heuristic. Moreover, it can be noticed that the optional dynamic reordering proves to be helpful for both approaches. However, when applied in our heuristic it gives better results than an ordinary application of reordering at the end of the BDD creation step. The results are somewhat better for the DFLM heuristic on minimum sizes in a respectful number of cases (18 from 41). This is assumingly the result of a random selection of gate inputs in both approaches.

Finally, in the analysis of larger FT models (Table 2) the new ordering heuristic is able to produce an order with which we build the BDD representation, even in the case of the largest considered models, where DFLM heuristic failed. This indicates that our approach does not only bring better results but also has a higher capability of beneficial order finding. Additional tests on large FT models prove that dynamic reordering during the build phase is not in all cases helpful for DFLM heuristic, yet it is useful in the new heuristic. It is far better to perform dynamic reordering after the BDD has been constructed and to refrain from automatic reordering during the build phase. The cause may be that automatic reordering within the BDD build phase simply does not sufficiently dispose over information on the event dependency as they appear to be available after the BDD has been constructed.

Conclusion

The new heuristic emerges from the known approach for fan-in 2 read-once formulas which has been further extended to a mixed case. Combining the heuristics with the simple exhaustive search, the new complete ordering algorithm is developed and verified on test models with different structural characteristics. The results from tests performed with the new algorithm show a clear improvement over the widely used DFLM heuristic.

Also, some important positive facts as well as some important issues have been discovered. The DFLM heuristic is very sensitive to the order of gate inputs. Our ordering approach based on the fan-in 2 read-once formulas algorithm appears useful even when applied on large FT models. However, during the BDD construction phase on large FT models with more than 1000 events and gates, the automatic reordering is of no help.

The presented approach proves to be promising for the application on industry FT models and indicates that further research may show potential in direction of: simplification of FT models to be more like fan-in k read-once formulas; application of search strategies other than exhaustive search at the gate level when orders from adjacent gate inputs are combined; investigation of different combining techniques (weight-based, greedy, AI search, …) on overlapping orders from adjacent gate inputs; application of dynamic reordering at different points during the order construction.

Apart from the presentation of the innovative heuristic, this article also reveals inspiring ideas for further research and development of an improved event ordering heuristic for the BDD-based analysis of FT models.

Footnotes

Appendix 1

Table 3 contains the statistics from a single run of the new heuristic on a complete set of 41 FT, small to medium sized, from the Aralia benchmark set. The statistics were collected without optional dynamic variable ordering in the procedure FindBestOrder. The first column shows the estimated number of BDD nodes resulting from the order produced with our heuristic, while the next column shows the number of BDD nodes used when it was built with CUDD engine. The third column brings the number of nodes after the group sifting method was applied on built BDD. The fourth column presents the CUDD engine report showing the peak number of BDD nodes used during the built process with that order. Eventually, the last column shows the time needed by the new heuristic to find that order.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship and/or publication of this article.

ORCID iDs

Reni Banov

Zdenko Šimić

References

Nusbaumer

Rauzy

. Fault tree linking versus event tree linking approaches: a reasoned comparison. P I Mech Eng O-J Ris 2013; 227(3): 315–326.

Dutuit

Rauzy

. Importance factors of coherent systems: a review. P I Mech Eng O-J Ris 2014; 228(3): 313–323.

Lee

. Representation of switching circuits by binary-decision programs. Bell Syst Tech J 1959; 38: 985–999.

Akers

. Binary Decision Diagrams. IEEE T Compt 1978; 27(6): 509–516.

Adam

. Truth functions and the problem of their realization by two-terminal graphs. Budapest: Akademia Kiado, 1969.

Bryant

. Graph-based algorithms for Boolean function manipulation. IEEE T Comput 1986; C-35(8): 677–691.

Wegener

. BDDs-design, analysis, complexity, and applications. Discrete Appl Math 2004; 138(1–2): 229–251.

Rauzy

. New algorithms for fault tree analysis. Reliab Eng Syst Safe 1993; 40(3): 203–211.

Friedman

Supowit

. Finding the optimal variable ordering for Binary Decision Diagrams. IEEE T Comput 1990; C-39(5): 710–713.

10.

Bolling

. On the complexity of some ordering problems. In: Csuhaj-Varjú

Dietzfelbinger

Ésik

(eds) Mathematical foundations of computer science 2014 (Lecture notes in computer science), vol. 8635. Berlin; Heidelberg: Springer, 2014, pp.118–129.

11.

Bolling

Wegener

. Improving the variable ordering of OBDDs is NP-complete. IEEE T Comput 1996;C-45(9): 993–1002.

12.

Yuchang

Farong

Huawen

, et al. Depth-first event ordering in BDD-based fault tree analysis. Comput Inform 2013; 31(6): 1401–1416.

13.

Yuchang

Farong

Huawen

, et al. Efficient ordering heuristics in Binary Decision Diagram-based fault tree analysis. Qual Reliab Eng Int 2013; 29(3): 307–315.

14.

Ibanez-Llano

Melendez

Nieto

. Variable ordering schemes to apply to the Binary Decision Diagram methodology for event tree sequences assessment. P I Mech Eng O-J Ris 2008; 222(1): 7–16.

15.

Sauerhoff

Wegener

Werchner

. Optimal ordered Binary Decision Diagrams for read-once formulas. Discrete Appl Math 2000; 103(1–3): 237–258.

16.

Matuzas

Contini

. On the efficiency of functional decomposition in fault tree analysis. P I Mech Eng O-J Ris 2012; 226(6): 635–645.

17.

Mordechai

. Mathematical logic for computer science. 2nd ed. London: Springer-Verlag, 2001.

18.

Wang

Chen

Wang

, et al. A new decomposition algorithm for complex voting gates processing in qualitative fault tree analysis. P I Mech Eng O-J Ris 2015; 229(6): 568–575.

19.

Remenyte

Andrews

. Qualitative analysis of complex modularized fault trees using Binary Decision Diagrams. P I Mech Eng O-J Ris 2006; 220(1): 45–53.

20.

Kohda

Henley

Inoue

. Finding modules in fault trees. IEEE T Reliab 1989; 38(1): 165–176.

21.

Dutuit

Rauzy

. A linear-time algorithm to find modules of fault trees. IEEE T Reliab 1996; 45(3): 422–425.

22.

Rudell

. Dynamic variable ordering for ordered Binary Decision Diagrams. In: Proceedings of the 1993 IEEE/ACM international conference on computer aided design, San Jose, CA, 7–11 November 1993, pp.42–47. New York: IEEE.

23.

Panda

Somenzi

. Who are the variables in your neighborhood. In: Proceedings of the 1995 IEEE/ACM international conference on computer aided design (ICCAD1995), San Jose, CA, 5–9 November 1995, pp.74–77. New York: IEEE.

24.

Panda

Somenzi

Plessier

. Symmetry detection and dynamic variable ordering of decision diagrams. In: Proceedings of the 1994 IEEE/ACM international conference on computer aided design, San Jose, CA, 6–10 November 1994, pp.628–631. New York: IEEE.

25.

Scholl

Melchior

Hotz

, et al. Minimizing ROBDD sizes of incompletely specified Boolean functions by exploiting strong symmetries. In: Proceedings European design and test conference, Paris, 17–20 March 1997, pp.229–234. New York: IEEE.

26.

Rauzy

. Some disturbing facts about depth-first left-most variable ordering heuristics for Binary Decision Diagrams. P I Mech Eng O-J Ris 2008; 222(4): 573–582.

27.

Groupe Aralia. Computation of prime implicants of a fault tree within Aralia. In: Proceedings of the European safety and reliability association conference (ESREL 1995), Bournemouth, 26–28 June 1995, pp.190–202. London: ESRA

28.

Yuchang

Liudong

Farong

, et al. Choosing a heuristic and root node for edge ordering in BDD-based network reliability analysis. Reliab Eng Syst Safe 2014; 131: 83–93.