Quantitative Analysis of Complex Fault Trees Using Importance Sampling With Monte Carlo Tree Search

Fault tree analysis is widely used in reliability engineering. However, it is a challenging task to be performed accurately and fast with limited computational resources when the fault tree becomes large and the top event probability becomes small. A novel algorithm is introduced that uses importance sampling with Monte Carlo tree search to tackle this challenge, with focus on static fault trees. Importance sampling uses proposal probabilities to bias the sampling of the basic events' states towards those the combination of which would cause the top event to happen, and Monte Carlo tree search is used to iteratively improve the proposal probabilities of the basic events' states. A case study is performed to analyze the accuracy, and the computational efficiency measured by the runtime and the memory usage of the new algorithm. Well established deterministic and stochastic algorithms are used as benchmarks, and a wide range of fault trees are used: ranging from simple to complex fault trees, and fault trees with both high and low top event probabilities. The new algorithm is shown to be significantly faster (on average one order of magnitude) than the other algorithms for fault trees that are complex (with more than one million minimal cut sets) and with low top event probabilities (less than 0.01), as well as having similar performance for other classes of fault trees while maintaining low error.