We introduce an automated approach for applying rare event simulation to stochastic Petri net (SPN) models of highly reliable Markovian systems (HRMS). In particular, we are interested in the event of reaching a rare set of goal states (e.g., system failure) before reaching a specific set of typical states (e.g., all components working). The state space of an HRMS model of a realistic system will typically be very large, but we assume that it is specified using the high-level modelling formalism of SPNs. This allows us to perform Monte Carlo simulation at the SPN-level. However, since our event of interest is rare we would need to use a prohibitively large number of samples using standard simulation. Hence, we use the efficient simulation technique of importance sampling. The main idea of importance sampling is to use a different probability measure than the original one such that transitions towards the goal set are made more likely. To do this, we need a notion of distance to the goal set. To formalise this distance, we assume that all transition rates in the HRMS are polynomial functions of a rarity parameter . The parameter signifies the fact that in an HRMS, the rates of different types of transitions tend to differ greatly (e.g., the rates of failure transitions are much lower than those of repair transitions). We assume that when ↓ 0, the probability of the event of interest vanishes. The distance between a state and the goal set can then be expressed in terms of the smallest polynomial order of among the probabilities of the paths between them. The distance between each state and the goal set is unclear a priori. Determining the shortest path to the goal set for each state individually using Dijkstra's algorithm would be computationally expensive. Hence, we want to exploit the structure of the system such that we can determine the shortest path to the goal set for groups of states simultaneously. The structure of the SPN allows this: transitions in an SPN are described using a fixed number of transition types, each of which has the same effect on the state vector (through the same vector addition). We assume that for each transition type, the rates of all transitions of this type are of the same polynomial -order. This allows us to partition the state space into zones such that for each zone, the shortest path from each state in that zone will be such that a single other zone is reached through repeatedly taking transitions of the same transition type. This zone partitioning is constructed iteratively, starting from the goal set. It turns out that due to the structure of the SPN, all zone boundaries and all path lengths within zones can be expressed using linear inequalities. An example of the output of the algorithm is given in Figure 1 ; the underlying model for this figure is an SPN model of a two-node tandem queue where the goal set equals those states for which there are at least n customers in the second queue, for a given n > 1. The state space is twodimensional, with each dimension representing the number of customers in one of the two queues. There are three transition types: arrivals to the first queue (which occur at rate λ), movements from the first to the second queue (with rate µ) and departures from the second queue (with rate ν). We assume that there are sizeable differences between the rates of the three transition types: in particular, we assume that λ = Θ( 2 ), µ = Θ( ) and ν = Θ(1). 1 As can be seen in Figure 1 , for some states the structure of the shortest path to the goal set is such that the second queue is emptied before n customers arrive to the first queue (this occurs in zone z 320 ). 1 Using Landau notation, we write f ( ) = Θ(g( )) if 0 < lim ↓0 f ( )/g( ) < ∞. If the HRMS model satisfies certain conditions (no high-probability cycles, all states being assigned an integer-valued distance), then the distances can be used to construct an importance sampling estimator that has the desirable property of bounded relative error, and this can be done in an automated manner. See [1] or [2] for a more detailed discussion of the algorithm. 2 In the future, we hope to relax the method's assumptions and extend it to queueing/population models (e.g., models in which the event of interest is rare due to a large number of failure transitions that needs to be taken).
Another interesting approach is that of REF , which is geared to simulating rare events, although restricted to Stochastic Petri Nets.
Automated rare event simulation for stochastic petri nets
QEST
Computer Science