470
C. E. Budde et al.
In region S 0 , 2 simulations made it from the initial state to threshold 1 , i.e. they
reached some state with importance 4 before visiting a state . In S 1 , starting
from these two states, 3 simulations reached 2 . Finally, 2 out of 5 simulations
visited states in S 2 . Thus, the estimated rare event probability of this run of
fe 5 is ˆ
p =
2
i=1 ˆ
p i =
2
5
3
5
2
5 = 9.6 × 10
−2 .
RESTART (rst [48, 47]) is another res algorithm, which starts one trace
in γ 0 and monitors the importance of the states visited. If the trace up-crosses
threshold 1 , the first state visited in S 1 is saved and the trace is cloned, aka
split—see Fig. 3b. This mechanism rewards traces that get closer to the rare
event. Each clone then evolves independently, and if one up-crosses threshold 2
the splitting mechanism is repeated. Instead, if a state with importance below
1 is visited, the trace is truncated ( in Fig. 3b). This penalises traces that
move away from the rare event. To avoid truncating all traces, the one that
spawned the clones in region S k can go below importance k . To deploy an
unbiased estimator for p, restart measures how much split was required to
visit a rare state [47]. In particular, restart does not need the rare event
to be defined as γ M [44], and it was devised for steady-state analysis [48] (e.g.
to estimate UNAVA) although it can also been used for transient studies as
depicted in Fig. 3b [45].
4 Importance Splitting for FTA
The effectiveness of isplit crucially relies on the choice of the importance
function I as well as the threshold levels k [30]. Traditionally, these are given
by domain and/or res experts, requiring a lot of domain knowledge. This section
presents a technique to obtain I and the k automatically for an rft.
4.1 Compositional importance functions for Fault Trees
By the core idea behind importance splitting, states that are more likely to lead
to the rare event should have a higher importance. To achieve this, the key lies
in defining an importance function I and thresholds k that are sensitive to both
the state space S and the transition probabilities of the system. For us, S ⊆ N
n
are all possible states of a repairable fault tree (rft). Its top event fails when
certain nodes fail in certain order, and remain failed before certain repairs occur.
To exploit this for isplit, the structure of the tree must be embedded into I.
The strong dependence of the importance function I on the structure of the
tree is easy to see in the following example. Take the rft from Fig. 2 and
let its current state x be s.t. P is failed and HVcab and S are operational. If the
next event is a repair of P, then the new state x
(where all basic elements are
operational) is farther from a failure of the top event. Hence, a good importance
function should satisfy I (x) > I (x
). Oppositely, if the next event had been a
failure of S leading to state x
, then one would want that I (x) < I (x
). The
key observation is that these inequalities depend on the structure of as well
as on the failures/repairs of basic elements.
C. E. Budde et al.
In region S 0 , 2 simulations made it from the initial state to threshold 1 , i.e. they
reached some state with importance 4 before visiting a state . In S 1 , starting
from these two states, 3 simulations reached 2 . Finally, 2 out of 5 simulations
visited states in S 2 . Thus, the estimated rare event probability of this run of
fe 5 is ˆ
p =
2
i=1 ˆ
p i =
2
5
3
5
2
5 = 9.6 × 10
−2 .
RESTART (rst [48, 47]) is another res algorithm, which starts one trace
in γ 0 and monitors the importance of the states visited. If the trace up-crosses
threshold 1 , the first state visited in S 1 is saved and the trace is cloned, aka
split—see Fig. 3b. This mechanism rewards traces that get closer to the rare
event. Each clone then evolves independently, and if one up-crosses threshold 2
the splitting mechanism is repeated. Instead, if a state with importance below
1 is visited, the trace is truncated ( in Fig. 3b). This penalises traces that
move away from the rare event. To avoid truncating all traces, the one that
spawned the clones in region S k can go below importance k . To deploy an
unbiased estimator for p, restart measures how much split was required to
visit a rare state [47]. In particular, restart does not need the rare event
to be defined as γ M [44], and it was devised for steady-state analysis [48] (e.g.
to estimate UNAVA) although it can also been used for transient studies as
depicted in Fig. 3b [45].
4 Importance Splitting for FTA
The effectiveness of isplit crucially relies on the choice of the importance
function I as well as the threshold levels k [30]. Traditionally, these are given
by domain and/or res experts, requiring a lot of domain knowledge. This section
presents a technique to obtain I and the k automatically for an rft.
4.1 Compositional importance functions for Fault Trees
By the core idea behind importance splitting, states that are more likely to lead
to the rare event should have a higher importance. To achieve this, the key lies
in defining an importance function I and thresholds k that are sensitive to both
the state space S and the transition probabilities of the system. For us, S ⊆ N
n
are all possible states of a repairable fault tree (rft). Its top event fails when
certain nodes fail in certain order, and remain failed before certain repairs occur.
To exploit this for isplit, the structure of the tree must be embedded into I.
The strong dependence of the importance function I on the structure of the
tree is easy to see in the following example. Take the rft from Fig. 2 and
let its current state x be s.t. P is failed and HVcab and S are operational. If the
next event is a repair of P, then the new state x
(where all basic elements are
operational) is farther from a failure of the top event. Hence, a good importance
function should satisfy I (x) > I (x
). Oppositely, if the next event had been a
failure of S leading to state x
, then one would want that I (x) < I (x
). The
key observation is that these inequalities depend on the structure of as well
as on the failures/repairs of basic elements.