library(zddr)

Currently, the zddr package only works using integer variables corresponding to variable rank. An additional layer of abstraction is needed for the user to enter real life fault tree problems, which can be converted to the integer variable form for solving.

The purpose of this vignette is to use the existing zddr package for a fault tree problem to discover the design of functions that will do this automatically. This vignette will be retired once the zddr package exposes the new symbolic functions. Easy enough.

Define a problem

Imagine a system with four trains: A, B, C, and D. The fault tree of the first train is essentially an OR gate of the following subtrees:

  • Failures of Train A that have no dependencies to the other trains: IND_A
  • Failures of Train A that have dependencies with one other train: CCF_AB, CCF_AC, CCF_AD
  • Failures of Train A that have dependencies with two other trains: CCF_ABC, CCF_ABD, CCF_ACD
  • Failures of Train A that have dependencies with all trains: CCF_ABCD

Set up variables

For a complete description of the problem, the entire range of possible variables are assigned integers. (Remember: doing this the long way right now to help discover what the clever functions will be. This will be necessarily painful.)

# independent failures
IND_A    <-  1;   IND_B    <-  2;   IND_C    <-  3;   IND_D    <-  4
# dependencies between two trains
CCF_AB   <-  5;   CCF_AC   <-  6;   CCF_AD   <-  7
CCF_BC   <-  8;   CCF_BD   <-  9;   CCF_CD   <- 10
# dependencies between three trains
CCF_ABC  <- 11;   CCF_ABD  <- 12;   CCF_ACD  <- 13;   CCF_BCD  <- 14
# dependencies between all trains
CCF_ABCD <- 15

Use zddr to create simple system trees

With the variables defined, the train failure cutsets can be given by the following OR gates for each train.

A <- zdd_or(IND_A, CCF_AB, CCF_AC, CCF_AD, CCF_ABC, CCF_ABD, CCF_ACD, CCF_ABCD)
B <- zdd_or(IND_B, CCF_AB, CCF_BC, CCF_BD, CCF_ABC, CCF_ABD, CCF_BCD, CCF_ABCD)
C <- zdd_or(IND_C, CCF_AC, CCF_BC, CCF_CD, CCF_ABC, CCF_ACD, CCF_BCD, CCF_ABCD)
D <- zdd_or(IND_D, CCF_AD, CCF_BD, CCF_CD, CCF_ABD, CCF_ACD, CCF_BCD, CCF_ABCD)
A
#> Memory of ZDD Store:     0.051 MB, item count: 45 ( 1.13 KB/item)
#> Memory of ZDD Functions: 0.018 MB, item count: 85 ( 0.21 KB/item)
#> 3baf4f09be7b5c11f86c09bdd140a496 : 8 cutsets, min order: 1 max order: 1 
#> 1-order 
#>       8 
#> {1}, {5}, {6}, {7}, {11}, {12}, {13}, {15}

Admittedly, the zddr package still needs a good way to translate the results back to the original variable names for better readability. The best way to accomplish that translation is part of what this vignette is trying to discover. Be patient, okay?

Manipulate the trees

Some examples of tree manipulation follow. Remember, there are four “trees” defined above, one for each train. The examples below explore

Multiply two trees

What are the cutsets associated with failure of trains A and B?

A*B
#> Memory of ZDD Store:     0.069 MB, item count: 61 ( 1.13 KB/item)
#> Memory of ZDD Functions: 0.032 MB, item count: 157 ( 0.2 KB/item)
#> 442e4c2c7cbfb7b11856378445d32358 : 20 cutsets, min order: 1 max order: 2 
#> 1-order 2-order 
#>       4      16 
#> {1,2}, {5}, {2,6}, {2,7}, {1,8}, {6,8}, {7,8}, {1,9}, {6,9}, {7,9}, {11}, {12},
#> {2,13}, {8,13}, {9,13}, {1,14}, {6,14}, {7,14}, {13,14}, {15}

Note that there were common events between A and B. For this reason the crossproduct of A and B has only 20 cutsets. If this problem were to be solved by brute force cross multiplication, the solution would have to look at all 64 combinations of A and B’s trees and then filter out the non-minimal cutsets. The full cross multiplication is trivial for a small problem, but would quickly get unmanageable for a problem with many AND operations.

Multiply three trees

What are the cutsets associated with failure of trains A and B and D?

A*B*D
#> Memory of ZDD Store:     0.089 MB, item count: 79 ( 1.13 KB/item)
#> Memory of ZDD Functions: 0.062 MB, item count: 318 ( 0.19 KB/item)
#> 5cb3e88f1c6a857b514e223ea50dfe1c : 34 cutsets, min order: 1 max order: 3 
#> 1-order 2-order 3-order 
#>       2      24       8 
#> {1,2,4}, {4,5}, {2,4,6}, {2,7}, {5,7}, {1,4,8}, {4,6,8}, {7,8}, {1,9}, {5,9},
#> {6,9}, {7,9}, {1,2,10}, {5,10}, {2,6,10}, {1,8,10}, {6,8,10}, {4,11}, {7,11},
#> {9,11}, {10,11}, {12}, {2,13}, {5,13}, {8,13}, {9,13}, {11,13}, {1,14}, {5,14},
#> {6,14}, {7,14}, {11,14}, {13,14}, {15}

As above, there were common events between A, B, and D, resulting in only 34 cutsets. This is far fewer than the maximum possible number of cutsets by brute force cross multiplication, 512.

Multiply all four trees

What about failure of all four?

A*B*C*D
#> Memory of ZDD Store:     0.148 MB, item count: 130 ( 1.14 KB/item)
#> Memory of ZDD Functions: 0.137 MB, item count: 719 ( 0.19 KB/item)
#> bf6462db079af2b05a202b13e29b550b : 49 cutsets, min order: 1 max order: 4 
#> 1-order 2-order 3-order 4-order 
#>       1      25      22       1 
#> {1,2,3,4}, {3,4,5}, {2,4,6}, {4,5,6}, {2,3,7}, {3,5,7}, {2,6,7}, {5,6,7},
#> {1,4,8}, {4,5,8}, {4,6,8}, {7,8}, {1,3,9}, {3,5,9}, {6,9}, {3,7,9}, {1,8,9},
#> {5,8,9}, {1,2,10}, {5,10}, {2,6,10}, {2,7,10}, {1,8,10}, {6,8,10}, {1,9,10},
#> {7,9,10}, {4,11}, {7,11}, {9,11}, {10,11}, {3,12}, {6,12}, {8,12}, {10,12},
#> {11,12}, {2,13}, {5,13}, {8,13}, {9,13}, {11,13}, {12,13}, {1,14}, {5,14},
#> {6,14}, {7,14}, {11,14}, {12,14}, {13,14}, {15}

Again, the cross multiplication using zddr directly identifies the 49 nonminimal cutsets, without having to first generate the 4096 possible cutsets by brute force. Huzzah!

k of n train failures

For now, k of n failures is done manually. If we were interested in the list of cutsets that represents failure of at least 2 trains, it would be the logical OR of the AND of all possible pairs of trains. Note how compact the results actually are: there are 384 possible combinations of cutsets for the problem defined, but the ZDD method quickly filters down to the 17 that match the criteria without evaluating all permutations.

(A*B) | (A*C) | (A*D) | (B*C) | (B*D) | (C*D)
#> Memory of ZDD Store:     0.287 MB, item count: 253 ( 1.13 KB/item)
#> Memory of ZDD Functions: 0.226 MB, item count: 1157 ( 0.2 KB/item)
#> 2274d75e4c80d65c83db6c3db7d0637d : 17 cutsets, min order: 1 max order: 2 
#> 1-order 2-order 
#>      11       6 
#> {1,2}, {1,3}, {2,3}, {1,4}, {2,4}, {3,4}, {5}, {6}, {7}, {8}, {9}, {10}, {11},
#> {12}, {13}, {14}, {15}

Repeating the same exercise, except with failure of at least 3 trains. Again, instead of evaluating 1536 combinations, the ZDD method quickly identifies the 36 cutsets that meet the criteria.

(A*B*C) | (A*B*D) | (A*C*D) | (B*C*D) 
#> Memory of ZDD Store:     0.377 MB, item count: 333 ( 1.13 KB/item)
#> Memory of ZDD Functions: 0.311 MB, item count: 1599 ( 0.19 KB/item)
#> 39b214ae4432e10f195ac9a5f92fed0a : 36 cutsets, min order: 1 max order: 3 
#> 1-order 2-order 3-order 
#>       5      27       4 
#> {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {3,5}, {4,5}, {2,6}, {4,6}, {5,6}, {2,7},
#> {3,7}, {5,7}, {6,7}, {1,8}, {4,8}, {5,8}, {6,8}, {7,8}, {1,9}, {3,9}, {5,9},
#> {6,9}, {7,9}, {8,9}, {1,10}, {2,10}, {5,10}, {6,10}, {7,10}, {8,10}, {9,10},
#> {11}, {12}, {13}, {14}, {15}

What about exactly 3 failed trains? EASY.

( (A*B*C) | (A*B*D) | (A*C*D) | (B*C*D) ) %% (A*B*C*D)
#> Memory of ZDD Store:     0.392 MB, item count: 346 ( 1.13 KB/item)
#> Memory of ZDD Functions: 0.326 MB, item count: 1680 ( 0.19 KB/item)
#> 40c41a7d25bf17cd61e9a3d642346abc : 32 cutsets, min order: 1 max order: 3 
#> 1-order 2-order 3-order 
#>       4      24       4 
#> {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {3,5}, {4,5}, {2,6}, {4,6}, {5,6}, {2,7},
#> {3,7}, {5,7}, {6,7}, {1,8}, {4,8}, {5,8}, {6,8}, {1,9}, {3,9}, {5,9}, {7,9},
#> {8,9}, {1,10}, {2,10}, {6,10}, {7,10}, {8,10}, {9,10}, {11}, {12}, {13}, {14}

Experiment with interfaces

So listen, this isn’t a perfect solution, BUT we finally have a prototype that proves that it’s doable to convert the ZDD-based solution easily to the string variables that were used in defining the original fault tree. Enjoy this demonstration and stay tuned!

reset_zdd_store()
#> Resetting zdd_store.
v <- structure(
  1:15,
  names = c(
    # independent failures
    'IND_A', 'IND_B', 'IND_C', 'IND_D', 
    # dependencies between two trains
    'CCF_AB', 'CCF_AC', 'CCF_AD', 'CCF_BC', 'CCF_BD', 'CCF_CD', 
    # dependencies between three trains
    'CCF_ABC', 'CCF_ABD', 'CCF_ACD', 'CCF_BCD', 
    # dependencies between all trains
    'CCF_ABCD'
  ) 
)
A <- zdd_or(v['IND_A'   ], v['CCF_AB'  ], v['CCF_AC'  ], v['CCF_AD'  ], 
            v['CCF_ABC' ], v['CCF_ABD' ], v['CCF_ACD' ], v['CCF_ABCD'] )
B <- zdd_or(v['IND_B'   ], v['CCF_AB'  ], v['CCF_BC'  ], v['CCF_BD'  ], 
            v['CCF_ABC' ], v['CCF_ABD' ], v['CCF_BCD' ], v['CCF_ABCD'] )
C <- zdd_or(v['IND_C'   ], v['CCF_AC'  ], v['CCF_BC'  ], v['CCF_CD'  ], 
            v['CCF_ABC' ], v['CCF_ACD' ], v['CCF_BCD' ], v['CCF_ABCD'] )
D <- zdd_or(v['IND_D'   ], v['CCF_AD'  ], v['CCF_BD'  ], v['CCF_CD'  ], 
            v['CCF_ABD' ], v['CCF_ACD' ], v['CCF_BCD' ], v['CCF_ABCD'] )

# define a function that can convert zdd results to cutsets
convert_zdd_result_to_cutsets <- function(zdd, variables) {
  reslist <- cutsets(zdd)
  relist( names(variables[unlist(reslist)]) , reslist)
}

(A*B)              %>% convert_zdd_result_to_cutsets(v)
#> [[1]]
#> [1] "IND_A" "IND_B"
#> 
#> [[2]]
#> [1] "CCF_AB"
#> 
#> [[3]]
#> [1] "IND_B"  "CCF_AC"
#> 
#> [[4]]
#> [1] "IND_B"  "CCF_AD"
#> 
#> [[5]]
#> [1] "IND_A"  "CCF_BC"
#> 
#> [[6]]
#> [1] "CCF_AC" "CCF_BC"
#> 
#> [[7]]
#> [1] "CCF_AD" "CCF_BC"
#> 
#> [[8]]
#> [1] "IND_A"  "CCF_BD"
#> 
#> [[9]]
#> [1] "CCF_AC" "CCF_BD"
#> 
#> [[10]]
#> [1] "CCF_AD" "CCF_BD"
#> 
#> [[11]]
#> [1] "CCF_ABC"
#> 
#> [[12]]
#> [1] "CCF_ABD"
#> 
#> [[13]]
#> [1] "IND_B"   "CCF_ACD"
#> 
#> [[14]]
#> [1] "CCF_BC"  "CCF_ACD"
#> 
#> [[15]]
#> [1] "CCF_BD"  "CCF_ACD"
#> 
#> [[16]]
#> [1] "IND_A"   "CCF_BCD"
#> 
#> [[17]]
#> [1] "CCF_AC"  "CCF_BCD"
#> 
#> [[18]]
#> [1] "CCF_AD"  "CCF_BCD"
#> 
#> [[19]]
#> [1] "CCF_ACD" "CCF_BCD"
#> 
#> [[20]]
#> [1] "CCF_ABCD"
(A*B*C)            %>% convert_zdd_result_to_cutsets(v)
#> [[1]]
#> [1] "IND_A" "IND_B" "IND_C"
#> 
#> [[2]]
#> [1] "IND_C"  "CCF_AB"
#> 
#> [[3]]
#> [1] "IND_B"  "CCF_AC"
#> 
#> [[4]]
#> [1] "CCF_AB" "CCF_AC"
#> 
#> [[5]]
#> [1] "IND_B"  "IND_C"  "CCF_AD"
#> 
#> [[6]]
#> [1] "IND_A"  "CCF_BC"
#> 
#> [[7]]
#> [1] "CCF_AB" "CCF_BC"
#> 
#> [[8]]
#> [1] "CCF_AC" "CCF_BC"
#> 
#> [[9]]
#> [1] "CCF_AD" "CCF_BC"
#> 
#> [[10]]
#> [1] "IND_A"  "IND_C"  "CCF_BD"
#> 
#> [[11]]
#> [1] "CCF_AC" "CCF_BD"
#> 
#> [[12]]
#> [1] "IND_C"  "CCF_AD" "CCF_BD"
#> 
#> [[13]]
#> [1] "IND_A"  "IND_B"  "CCF_CD"
#> 
#> [[14]]
#> [1] "CCF_AB" "CCF_CD"
#> 
#> [[15]]
#> [1] "IND_B"  "CCF_AD" "CCF_CD"
#> 
#> [[16]]
#> [1] "IND_A"  "CCF_BD" "CCF_CD"
#> 
#> [[17]]
#> [1] "CCF_AD" "CCF_BD" "CCF_CD"
#> 
#> [[18]]
#> [1] "CCF_ABC"
#> 
#> [[19]]
#> [1] "IND_C"   "CCF_ABD"
#> 
#> [[20]]
#> [1] "CCF_AC"  "CCF_ABD"
#> 
#> [[21]]
#> [1] "CCF_BC"  "CCF_ABD"
#> 
#> [[22]]
#> [1] "CCF_CD"  "CCF_ABD"
#> 
#> [[23]]
#> [1] "IND_B"   "CCF_ACD"
#> 
#> [[24]]
#> [1] "CCF_AB"  "CCF_ACD"
#> 
#> [[25]]
#> [1] "CCF_BC"  "CCF_ACD"
#> 
#> [[26]]
#> [1] "CCF_BD"  "CCF_ACD"
#> 
#> [[27]]
#> [1] "CCF_ABD" "CCF_ACD"
#> 
#> [[28]]
#> [1] "IND_A"   "CCF_BCD"
#> 
#> [[29]]
#> [1] "CCF_AB"  "CCF_BCD"
#> 
#> [[30]]
#> [1] "CCF_AC"  "CCF_BCD"
#> 
#> [[31]]
#> [1] "CCF_AD"  "CCF_BCD"
#> 
#> [[32]]
#> [1] "CCF_ABD" "CCF_BCD"
#> 
#> [[33]]
#> [1] "CCF_ACD" "CCF_BCD"
#> 
#> [[34]]
#> [1] "CCF_ABCD"
((A*B*C) %% D)     %>% convert_zdd_result_to_cutsets(v)
#> [[1]]
#> [1] "IND_A" "IND_B" "IND_C"
#> 
#> [[2]]
#> [1] "IND_C"  "CCF_AB"
#> 
#> [[3]]
#> [1] "IND_B"  "CCF_AC"
#> 
#> [[4]]
#> [1] "CCF_AB" "CCF_AC"
#> 
#> [[5]]
#> [1] "IND_A"  "CCF_BC"
#> 
#> [[6]]
#> [1] "CCF_AB" "CCF_BC"
#> 
#> [[7]]
#> [1] "CCF_AC" "CCF_BC"
#> 
#> [[8]]
#> [1] "CCF_ABC"

(( (A*B*C) | (A*B*D) | (A*C*D) | (B*C*D) ) %% (A*B*C*D) ) %>% 
  convert_zdd_result_to_cutsets(v)
#> [[1]]
#> [1] "IND_A" "IND_B" "IND_C"
#> 
#> [[2]]
#> [1] "IND_A" "IND_B" "IND_D"
#> 
#> [[3]]
#> [1] "IND_A" "IND_C" "IND_D"
#> 
#> [[4]]
#> [1] "IND_B" "IND_C" "IND_D"
#> 
#> [[5]]
#> [1] "IND_C"  "CCF_AB"
#> 
#> [[6]]
#> [1] "IND_D"  "CCF_AB"
#> 
#> [[7]]
#> [1] "IND_B"  "CCF_AC"
#> 
#> [[8]]
#> [1] "IND_D"  "CCF_AC"
#> 
#> [[9]]
#> [1] "CCF_AB" "CCF_AC"
#> 
#> [[10]]
#> [1] "IND_B"  "CCF_AD"
#> 
#> [[11]]
#> [1] "IND_C"  "CCF_AD"
#> 
#> [[12]]
#> [1] "CCF_AB" "CCF_AD"
#> 
#> [[13]]
#> [1] "CCF_AC" "CCF_AD"
#> 
#> [[14]]
#> [1] "IND_A"  "CCF_BC"
#> 
#> [[15]]
#> [1] "IND_D"  "CCF_BC"
#> 
#> [[16]]
#> [1] "CCF_AB" "CCF_BC"
#> 
#> [[17]]
#> [1] "CCF_AC" "CCF_BC"
#> 
#> [[18]]
#> [1] "IND_A"  "CCF_BD"
#> 
#> [[19]]
#> [1] "IND_C"  "CCF_BD"
#> 
#> [[20]]
#> [1] "CCF_AB" "CCF_BD"
#> 
#> [[21]]
#> [1] "CCF_AD" "CCF_BD"
#> 
#> [[22]]
#> [1] "CCF_BC" "CCF_BD"
#> 
#> [[23]]
#> [1] "IND_A"  "CCF_CD"
#> 
#> [[24]]
#> [1] "IND_B"  "CCF_CD"
#> 
#> [[25]]
#> [1] "CCF_AC" "CCF_CD"
#> 
#> [[26]]
#> [1] "CCF_AD" "CCF_CD"
#> 
#> [[27]]
#> [1] "CCF_BC" "CCF_CD"
#> 
#> [[28]]
#> [1] "CCF_BD" "CCF_CD"
#> 
#> [[29]]
#> [1] "CCF_ABC"
#> 
#> [[30]]
#> [1] "CCF_ABD"
#> 
#> [[31]]
#> [1] "CCF_ACD"
#> 
#> [[32]]
#> [1] "CCF_BCD"