Petri Nets: An Alternative to Markov Chains

By: Captain Richard V. Melnyk, United States Army

Introduction

In the Third Quarter, 2003 issue of the RAC Journal, an article by Norm Fuqua discussed the application of Markov Chain analysis to reliability and maintainability analysis. In addition to Markov Chain analysis, other methods are available for stochastic modeling. This article provides one of these alternative methods for stochastic modeling known as Stochastic Petri Nets (SPNs). Petri Nets were presented in the 1960's in a PhD thesis by Carl Petri in Germany (Reference 1). Designed to model dynamic systems, Petri Nets have been used for numerous applications to include software reliability, network reliability, and queuing theory.

The use of Petri Nets avoids two of the basic drawbacks of Markov Chain analysis. First, the model does not grow in size as the number of components in the model increase. Because Petri Nets model local states instead of global ones, they do not grow out of control as the model increases in complexity. This concept will be discussed later in more detail. Second, Markov Chain analysis is typically limited to modeling the probability of changes in the system with the exponential distribution (Reference 2). However, processes pertaining to reliability, availability, maintainability, and safety (RAMS) do not necessarily conform to an exponential distribution.

The author used a Petri Net to model and analyze the phase maintenance process for the U.S. Army's AH-64 Apache helicopter. The phase inspection is a large inspection conducted every 250 flight hours. It is performed by phase teams made up of maintenance personnel from within the aviation unit, or by contractor phase teams. The purpose of the Petri Net analysis was to determine how reducing the duration of phase inspections or introducing Operational Readiness Floats (ORFs) to units would affect Operational Availability (Ao).



Elements of a Petri Net

Petri Nets consist of four basic elements: places, transitions, tokens and arcs (Reference 3). Places represent a condition in the process. For example, in the phase inspection model, a place can represent the condition of availability or the condition associated with being in the process of a phase inspection. Transitions represent the stochastic, or time-based nature of changes in the model. Transitions can be immediate, deterministically time-delayed, or time-delayed based on a probability distribution defined by the user. A transition could represent the interval between phase inspections or the amount of time an aircraft spends in phase.

Tokens represent objects in the model. For instance, an aircraft or aircraft component could be modeled as a token. A token graphically appears as a small, solid circle. In basic applications the token is black but in more sophisticated tools, tokens can take on various colors to signify the various `ages' of components. When too many tokens appear in one place, most applications revert to placing a number inside the place.

When a transition allows the movement of a token it is like a door that opens in the model. The transition is said to have `fired' when this happens. Lastly, arcs determine the path that tokens take throughout the model. Arcs can either enable or inhibit movement in the model, depending on their use. A graphical representation of these Petri Net components appears in Figure 1.

Figure 1. Petri Net Components (Click to Zoom)


Global vs. Local Models

As stated earlier, a Petri Net model employs local places, while a Markov Chain features global states. In a Markov Chain, the circles or states represent all the components in that model. On the other hand, in a Petri Net, each circle or place represents only a condition in that model. The difference is more easily illustrated with a basic example.

In this example, a system has three identical components. Each of these components is repairable and fails with the same probability. To build a Markov Chain, the analyst has to understand all the combinations possible for the system. Starting with operational components up, the user has to define all of the combinations of operational and failed components and label the combinations as states. Therefore, each state represents the entire system in a particular combination of conditions. Figure 2 depicts an example of a Markov Chain.

Figure 2. Markov Chain Example (Click to Zoom)
For the same application, the equivalent Petri Net is shown in Figure 3. For this application, the user only has to define the conditions the components can be found in; operational or failed. Then the user also assigns values to the failure and repair probabilities. However, the system can consist of 3 or 100 components; the construction of the model will not change.

Figure 3. Petri Net Example (Click to Zoom)


Petri Net Application

To understand the simple way in which Petri Nets can be constructed, it is best to view an example. As stated earlier, the author used a basic SPN to model the phase maintenance program for a U.S. Army attack battalion. An explanation of the model, depicted in Figure 4 follows.

Figure 4. SPN for Phase Maintenance (Click to Zoom)
The process begins in the upper left corner in the `Operate'place. In this place, aircraft are considered to be out of phase maintenance. For this model, 19 aircraft are currently in this place. To the right of this place is a transition, referred to as Interval. This transition `fires' approximately every 19 days to allow a token, or aircraft, to move from the Operate place to the next place, or `Prephase'. The 19-day metric is representative of how often an aircraft must enter phase maintenance, based on a typical attack battalion's annual flying hour program. This value can easily be changed if a unit increases or decreases their operational tempo and can be approximated by a deterministic value, normal distribution, uniform distribution, etc.

In the `Prephase'place, an aircraft is ready to enter phase. In this model, two immediate transitions allow movement from `Prephase' to either of two phase teams labeled `Tm1' and `Tm2'. Inhibitor arcs from the phase teams to the immediate transitions prevent the transitions from firing if a token is already present in the phase team. When the token reaches a phase team the `Duration' transitions are enabled. In the current model, these transitions reflect the 26-day average phase inspection duration. However, these transitions can also be modeled with different values or distributions, depending on the application. Once the inspection is complete, the `Duration' transition fires, allowing the aircraft to move to the `Spares' place.

If a unit has an ORF aircraft available the model can start with a token or tokens in the `Spare' place. Regardless, once a token moves to the `Spares' place, the `Admin Delay' transition is enabled. This transition simply delays the aircraft's return to operation to account for paperwork, test flights, etc. An inhibitor arc from the `Operate' to `Admin Delay' also prevents more than 21 aircraft from entering the `Operate' place, in this case. This arc is used in the event of ORF analysis to prevent more aircraft from entering the `Operate' place than the unit technically has.

An analyst can use this model to study several issues related to Operational Availability. The user can add or subtract phase teams to study the effects. The duration of phase inspections can also be altered to reflect the effects of increasing the availability of maintainers on the phase team or spare parts. In addition, ORF aircraft can be added or subtracted to the model to determine the impact on overall availability.



Advantages and Disadvantages

The application of an SPN to the phase inspection process is only one example of how this form of stochastic modeling can be used in analyzing RAMS processes. However, the example clearly illustrates the advantages of Petri Nets.

First, the size of the model is easily manageable, regardless of the amount of tokens present. Once the model is constructed, the user can change the number of aircraft, without affecting the places and transitions. Conversely, a Markov Chain used to model a unit consisting of 21 aircraft would be larger than one for 18 aircraft. Both models would be extremely large.

Second, Petri Nets allow the analyst to model dynamic events using something other than the exponential distribution. This distribution, widely regarded as appropriate for electronic components, is usually inappropriate for mechanical components and real world processes. Petri Nets give the user more flexibility in creating a model.

Third, Petri Nets, used in a simulation, allow the user to actually observe the stochastic processes. The user can develop a model, and then observe the tokens as they move throughout the model in real or simulated time. This feature gives the user insight into the actual flow of the model and any potential conflicts.

Finally, Petri Nets are easy to modify. Since the model itself is very simple, it is easy to change the values of transitions or the number of tokens without having to change the entire model itself. This characteristic is useful when the user needs to analyze several different cases.

Currently, the major drawback of Petri Nets is the lack of readily available software packages. While Markov Chain analysis appears in most of the major reliability software tools such as those from Relex Software and Item Software, Petri Net software applications are obscure and difficult to integrate with existing software tools. However, the relative strengths of Petri Nets to model stochastic processes could be easily harnessed by software developers and incorporated into their reliability packages. This disadvantage will be discussed in greater detail in the next section.



Implementing an SPN

The underlying structure of all Petri Net software is a code-based architecture. Different programmers use different languages for each software package and the learning curve associated with each package can be steep.

Alternatively, more advanced software packages feature a graphical user interface (GUI) that allows a user to graphically build the Petri Net and implement it. The result would be similar to Figure 4. This approach is obviously easier for a new user to learn and implement.

The main purpose of building a Petri Net in either type of application is performing a simulation with the model. All of the applications the author reviewed gave the user a way to simulate the dynamic nature of the model for a pre-determined amount of time with pre-set time intervals. With applications featuring a GUI, the user can actually observe the transitions activating and note the movement of tokens throughout the model. One of the main obstacles to effectively implementing a Petri Net simulation and analysis, with some current applications, is the lack of tools for output analysis. Since the early uses of Petri Nets mainly involved software analysis, network analysis and queuing theory, simply watching the simulation take place was sufficient. The goal was to graphically determine if a token or tokens reached a certain place in the model.

However, for RAMS applications, typically it is important to track and measure a particular value. That value can include Operational Availability, MTTF, or MTTR of a component or system. Therefore, it is important to use an application that provides some way to measure indices within the model. Some applications provide an output window that graphically displays the number of tokens in a selected place over the duration of the simulation. Other more advanced applications include tools to measure specified metrics in the model. The relative strength of any software packages for RAMS usage depends on the ability to easily capture and display data from the simulation.



Summary

No matter the discipline, there is no perfect tool for every situation. RAMS analysis requires that various tools be used, sometimes in an integrated fashion, to accomplish the job. Petri Nets offer an analyst another powerful tool to simply, and effectively model stochastic processes. If the lack of software tools for implementing Petri Nets can be overcome, the advantages that Petri Nets present over Markov Chains could make them the tool of choice for dynamic models.



References

1. Petri Nets World Online Homepage, www.daimi.au.dk/PetriNets
2. Fuqua, Norman B., "Markov Analysis," The Journal of the RAC, Third Quarter 2003.
3. Volovoi, Vitali, "System Reliability and Availability Modeling," Georgia Institute of Technology Class Lecture, April 2003.