In jordagaman/zddr: A zero-suppressed binary decision diagram implementation for R

knitr::opts_chunk$set(
  collapse = TRUE,
  comment = "#>"
)

library(zddr)

as_zdd(F)

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)

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

Note that there were common events between A and B. For this reason the crossproduct of A and B has only r length(cutsets(A*B)) cutsets. If this problem were to be solved by brute force cross multiplication, the solution would have to look at all r length(cutsets(A))*length(cutsets(B)) 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

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

Multiply all four trees

What about failure of all four?

A*B*C*D

Again, the cross multiplication using zddr directly identifies the r length(cutsets(A*B*C*D)) nonminimal cutsets, without having to first generate the r length(cutsets(A))*length(cutsets(B))*length(cutsets(C))*length(cutsets(D)) 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 r 6*8*8 possible combinations of cutsets for the problem defined, but the ZDD method quickly filters down to the r length(cutsets((A*B) | (A*C) | (A*D) | (B*C) | (B*D) | (C*D))) that match the criteria without evaluating all permutations.

(A*B) | (A*C) | (A*D) | (B*C) | (B*D) | (C*D)

Repeating the same exercise, except with failure of at least 3 trains. Again, instead of evaluating r 3*8*8*8 combinations, the ZDD method quickly identifies the r length(cutsets((A*B*C) | (A*B*D) | (A*C*D) | (B*C*D))) cutsets that meet the criteria.

(A*B*C) | (A*B*D) | (A*C*D) | (B*C*D)

What about exactly 3 failed trains? EASY.

( (A*B*C) | (A*B*D) | (A*C*D) | (B*C*D) ) %% (A*B*C*D)

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()
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)
(A*B*C)            %>% convert_zdd_result_to_cutsets(v)
((A*B*C) %% D)     %>% convert_zdd_result_to_cutsets(v)

(( (A*B*C) | (A*B*D) | (A*C*D) | (B*C*D) ) %% (A*B*C*D) ) %>% 
  convert_zdd_result_to_cutsets(v)