Modeling, Analysis, and Control with Petri Nets

Abstract

Petri net is a generic term used to designate a broad family of related formalisms for discrete event views of (dynamic) Systems (DES), all sharing some basic relevant features, such as minimality in the number of primitives, locality of the states and actions (with consequences for model construction), or temporal realism. The global state of a system is obtained by the juxtaposition of the different local states. We should initially distinguish between autonomous formalisms and those extended by interpretation. Models in the latter group are obtained by restricting the underlying autonomous behaviors by means of constraints that can be related to different kinds of external events, in particular to time. This article first describes place/transition nets (PT-nets), by default simply called Petri nets (PNs). Other formalisms are then mentioned. As a system theory modeling paradigm for concurrent DES, Petri nets are used in a wide variety of application fields.

Introduction

Petri nets (PNs) are able to model concurrent and distributed DES (Models for Discrete Event Systems: An Overview). They constitute a powerful family of formalisms with different expressive purposes and power. They may be applied to inter alia, modeling, logical analysis, performance evaluation, parametric optimization, dynamic control (minimum makespan, supervisory control, or other kinds), diagnosis, and implementation issues (eventually fault tolerant). Hybrid and continuous PNs are particularly useful when some parts of the system are highly populated. Being multidisciplinary, formalisms belonging to the Petri nets paradigm may cover several phases of the life cycle of complex DES.

A Petri net can be represented as a bipartite directed graph provided with arcs inscriptions; alternatively, this structure can be represented in algebraic form using some matrices. As in the case of differential equations, an initial condition or state should be defined in order to represent a dynamic system. This is done by means of an initial distributed state. The English translation of the Carl Adam Petri’s seminal work, presented in 1962, is Petri (1966).

Untimed Place/Transition Net Systems

A place/transition net (PT-net) can be viewed as $\mathcal{N} =\langle P,T,\mathbf{\mathit{Pre}},\mathbf{\mathit{Post}}\rangle$, where:

• P and T are disjoint and finite nonempty sets of places and transitions, respectively.

• Pre and Post are $\vert P\vert \times \vert T\vert$ sized, natural-valued (zero included), incidence matrices. The net is said to be ordinary if Pre and Post are valued on {0, 1}. Weighted arcs permit the abstract modeling of bulk services and arrivals.

A PT-net is a structure. The Pre(Post) function defines the connections from places to transitions (transitions to places). Those two functions can alternatively be defined as weighted flow relations (nets as graphs). Thus, PT-nets can be represented as bipartite directed graphs with places (p, using circles) and transitions (t, using bars or rectangles) as nodes: $\mathcal{N} =\langle P,T,F,W\rangle$, where $F \subseteq (P \times T) \cup (\mathrm{T} \times P)$ is the flow relation (set of directed arcs, with $\mathit{dom}(F) \cup \mathit{range}(F) = P \cup T$), and $W : \mathit{F} \rightarrow \mathbb{N}^{+}$ assigns a natural weight to each arc.

The net structure represents the static part of the DES model. Furthermore, a “distributed state” is defined over the set of places, known as the marking. This is “numerically quantified” (not in an arbitrary alphabet, as in automata), associating natural values to the local state variables, the places. If a place p has a value υ(m(p) = υ), it is said to have ν tokens (frequently depicted in graphic terms with v black dots or just the number inside the place). The places are “state variables,” while the markings are their “values”; the global state is defined through the concatenation of local states. The net structure, provided with an initial marking, to be denoted as $(\mathcal{N},m_{0})$, is a Petri net system, or marked Petri net.

The last two basic PN constructions in Fig. 1 ( join and fork) do not appear in finite-state machines; moreover, the arcs may be valued with natural numbers. The dynamic behavior of the net system (trajectories with changes in the marking) is produced by the firing of transitions, some “local operations” which follows very simple rules.

Modeling, Analysis, and Control with Petri Nets, Fig. 1

Most basic PN constructions: The logical OR is present around places, in choices (or branches) and attributions (or meets); the logical AND is formed around transitions, in joins (or waits or rendezvous) and forks (or splits)

Markings in net systems evolve according to the following firing (or occurrence) rules (see, Fig. 2):

• A transition is said to be enabled at a given marking if each input place has at least as many tokens as the weight of the arc joining them.

• The firing or occurrence of an enabled transition is an instantaneous operation that removes from (adds to) each input (output) place a number of tokens equal to the weight of the arc joining the place (transition) to the transition (place).

Modeling, Analysis, and Control with Petri Nets, Fig. 2

Only transitions b and c are initially enabled. The results of firing b or c are shown subsequently

The precondition of a transition can be seen as the resources required for the transition to be fired. The weight of the arc from a place to a transition represents the number of resources to be consumed. The post-condition defines the number resources produced by the firing of the transition. This is made explicit by the weights of the arcs from the transition to the places. Three important observations should be taken into account:

• The underlying logic in the firing of a transition is non-monotonic! It is a consumption/production logic.

• Enabled transitions are never forced to fire: This is a form of non-determinism.

• An occurrence sequence is a sequence of fired transitions σ = t₁… t _k . In the evolution from m₀, the reached marking m can be easily computed as:

  $$\displaystyle{ \mathbf{\mathit{m}} = \mathbf{\mathit{m}}_{0} + \mathbf{\mathit{C}}\cdot \boldsymbol{\sigma }, }$$

  (1)

  where C = Post – Pre is the token flow matrix (incidence matrix if $\mathcal{N}$ is self-loop free) and $\boldsymbol{\sigma }$ the firing count vector corresponding to $\boldsymbol{\sigma }$. Thus m and $\boldsymbol{\sigma }$ are vectors of natural numbers.

The previous equation is the state-transition equation (frequently known as the fundamental or, simply, state equation). Nevertheless, two important remarks should be made:

• It represents a necessary but not sufficient condition for reachability; the problem is that the existence of a $\boldsymbol{\sigma }$ does not guarantee that a corresponding sequence σ is firable from m₀; thus, certain solutions – called spurious (Silva et al. 1998) – are not reachable. This implies that – except in certain net system subclasses – only semi-decision algorithms can usually be derived.

• All variables are natural numbers, which imply computational complexity.

It should be pointed out that in finite-state machines, the state is a single variable taking values in a symbolic unstructured set, while in PT-net systems, it is structured as a vector of nonnegative integers. This allows analysis techniques that do not require the enumeration of the state space.

At a structural level, observe that the negation is missing in Fig. 1; its inclusion leads to the so-called inhibitor arcs, an extension in expressive power. In its most basic form, if the place at the origin of an inhibitor arc is marked, it “inhibits” the enabling of the target transition. PT-net systems can model infinite-state systems, but not Turing machines. PT-net systems provided with inhibitor arcs (or priorities on the firing of transitions) can do it.

With this conceptually simple formalism, it is not difficult to express basic synchronization schemas (Fig. 3). All the illustrated examples use joins. When weights are allowed in the arcs, another kind of synchronization appears: Several copies of the same resource are needed (or produced) in a single operation. Being able to express concurrency and synchronization, when viewing the system at a higher level, it is possible to build cooperation and competition relationships.

Modeling, Analysis, and Control with Petri Nets, Fig. 3

Basic synchronization schemes: (1) Join or rendezvous, RV ; (2) Semaphore, S; (3) Mutual exclusion semaphore (mutex), R, representing a shared resource; (4) Symmetric RV built with two semaphores; (5) Asymmetric RV built with two semaphores (master/slave); (6) Fork-join (or par-begin/par-end); (7) Non-recursive subprogram (places i and j cannot be simultaneously marked – must be in mutex – to remember the returning point; for simplicity, it is assumed that the subprogram is single input/single output); (8) Guard (a self-loop from a place through a transition); its role is like a traffic light: If at least one token is present at the place, it allows the evolution, but it is not consumed. Synchronizations can also be modeled by the weights associated to the arcs going to transitions

Analysis and Control of Untimed PT Models

The behavior of a concurrent (eventually distributed) system is frequently difficult to understand and control. Thus, misunderstandings and mistakes are frequent during the design cycle. A way of cutting down the cost and duration of the design process is to express in a formalized way properties that the system should enjoy and to use formal proof techniques. Errors can be eventually detected close to the moment they are introduced, reducing their propagation to subsequent stages. The goal in verification is to ensure that a given system is correct with respect to its specification (perhaps expressed in temporal-logic terms) or to a certain set of predetermined properties.

Among the most basic qualitative properties of “net systems” are the following: (1) reachability of a marking from a given one; (2) boundedness, characterizing finiteness of the state space; (3) liveness, related to potential fireability of all transitions starting on an arbitrary reachable marking (deadlock-freeness is a weaker condition in which only global infinite fireability of the net system model is guaranteed, even if some transitions no longer fire); (4) reversibility, characterizing recoverability of the initial marking from any reachable one; and (5) mutual exclusion of two places, dealing with the impossibility of reaching markings in which both places are simultaneously marked.

All the above are behavioral properties, which depend on the net system $(\mathcal{N},\mathbf{\mathit{m}}_{0})$. In practice, sometimes problems with a net model are rooted in the net structure; thus, the study of the structural counterpart of certain behavioral properties may be of interest. For example, a “net” is structurally bounded if it is bounded for any initial marking; a “net” is structurally live if an initial marking exists that make the net system live (otherwise stated, it reflect non-liveness for arbitrary initial markings, a pathology of the net).

Basic techniques to analyze net systems include: (1) enumeration, in its most basic form based on the construction of a reachability graph (a sequentialized view of the behavior). If the net system is not bounded, losing some information, a finite coverability graph can be constructed; (2) transformation, based on an iterative rewriting process in which a net system enjoys a certain property if and only if a transformed (“simpler” to analyze) one also does. If the new system is easier to analyze, and the transformation is computationally cheap, the process may be extremely interesting; (3) structural, based on graph properties, or in mathematical programming techniques rooted on the state equation; (4) simulation, particularly interesting for gaining certain confidence about the absence of certain pathological behaviors. Analysis strategies combining all these kinds of techniques are extremely useful in practice.

Reachability techniques provide sequentialized views for a particular initial marking. Moreover they suffer from the so-called state explosion problem. The reduction of this computational issue leads to techniques such as stubborn set methods (smaller, equally informative reachability graphs), also to non-sequentialized views such as those based on unfoldings. Transformation techniques are extremely useful, but not complete (i.e., not all net systems can be reduced in a practical way). In most cases, structural techniques only provide necessary or sufficient conditions (e.g., a sufficient condition for deadlock-freeness, a necessary condition for reversibility, etc.), but not a full characterization. As already pointed out, a limitation of methods based on the state equation for analyzing net systems is the existence of non reachable solutions (the so-called spurious solutions). In this context, three kinds of related notions that must be differentiated are the following: (1) some natural vectors (left and right annullers of the token flow matrix, C: P-semiflows and T-semiflows), (2) some invariant laws (token conservation and repetitive behaviors), and (3) some peculiar subnets (conservative and consistent components, generated by the subsets of nodes in the P- and T-semiflows, respectively).

More than analysis, control leads to synthesis problems. The idea is to enforce the given system in order to fulfill a specification (e.g., to enforce certain mutual exclusion properties). Technically speaking, the idea is to “add” some elements in order to constrain the behavior in such a way that a correct execution is obtained. Questions related to control, observation, diagnosis, or identification are all areas of ongoing research.

With respect to classical control theory, there are two main differences: Models are DES and untimed (autonomous, fully nondeterministic, eventually labeling the transitions in order to be able to consider the PNs languages). Let us remark that for control purposes, the transitions should be partitioned into controllable (when enabled, you can either force or block the firing) and uncontrollable (if enabled, the firing is nondeterministic). A natural approach to synthesize a control is to start modeling the plant dynamics (by means of a PN, P) and adopting a specification for the desired closed-loop system (S). The goal is to compute a controller (L) such that S equals the parallel-composition of P and L; in other words, controllers (called “supervisors”) are designed to ensure that only behaviors consistent with the specification may occur. The previous equality is not always possible, and the goal is usually relaxed to minimally limit the behavior within the specified legality (i.e., to compute maximally permissive controllers). For an approach in the framework of finite-state machines and regular languages, see Supervisory Control of Discrete-Event Systems. The synthesis in the framework of Petri nets and having goals as enforcing some generalized mutual exclusions constraints in markings or avoiding deadlocks, for example, can be efficiently approached by means of the so named structure theory, based on the direct exploitation of the structure of the net model (using graph or mathematical programming theories and algorithms, where the initial marking is a parameter).

Similarly, transitions (or places) can be partitioned into observable and unobservable. Many observability problems may be of interest; for example, observing the firing of a subset of transitions to compute the subset of markings in which the system may be. Related to observability, diagnosis is the process of detecting a failure (any deviation of a system from its intended behavior) and identifying the cause of the abnormality. Diagnosability, like observability or controllability, is a logical criterion. If a model is diagnosable with respect to a certain subset of possible faults (i.e., it is possible to detect the occurrence of those faults in finite time), a diagnoser can be constructed (see section “Diagnosis and Diagnosability Analysis of Petri Nets” in Diagnosis of Discrete Event Systems). Identification of DES is also a question that has required attention in recent years. In general, the starting point is a behavioral observation, the goal being to construct a PN model that generates the observed behavior, either from examples/counterexamples of its language or from the structure of a reachability graph. So the results are derived models, not human-made models (i.e., not made by designers).

The Petri Nets Modeling Paradigm

Along the life cycle of DES, designers may deal with basic modeling, analysis, and synthesis from different perspectives together with implementation and operation issues. Thus, the designer may be interested in expressing the basic structure, understanding untimed possible behaviors, checking logic properties on the model when provided with some timing (e.g., in order to guarantee if a certain reaction is possible before 3 ms; something relevant in real-time systems), computing some performance indices on timed models (related to the throughput in the firing of a given transition, or to the length of a waiting line, expressed as the number of tokens in a place), computing a schedule or control that optimizes a certain objective function, decomposing the model in order to prepare an efficient implementation, efficiently determining redundancies in order to increase the degree of fault tolerance, etc. For these different tasks, different formalisms may be used. Nevertheless, it seems desirable to have a family of related formalisms rather than a collection of “unrelated” or weakly related formalisms. The expected advantages would include coherence among models usable in different phases, economy in the transformations and synergy in the development of models and theories.

Other Untimed PN Formalisms: Levels of Expressive Power

PT-net systems are more powerful than condition/event (CE) systems, roughly speaking the basic seminal formalism of Carl Adam Petri in which places can be marked only with zero or one token (Boolean marking). CE-systems can model only finite-state systems. As already said, “extensions” of the expressive power of untimed PT-net systems to the level of Turing machines are obtained by adding inhibitor arcs or priorities to the firing of transitions.

An important idea is adding the notion of individuals to tokens (e.g., from anonymous to labeled or colored tokens). Information in tokens allows the objects to be named (they are no longer indistinguishable) and dynamic associations to be created. Moving from PT-nets to so-called high-level PNs (HLPNs) is something like “moving from assembler to high-level programming languages,” or, at the computational level, like “moving from pure numerical to a symbolic level.” There are many proposals in this respect, the more important being predicate/transition nets and colored PNs. Sometimes, this type of abstraction has the same theoretical expressiveness as PT-net systems (e.g., colored PNs if the number of colors is finite); in other words, high-level views may lead to more compact and structured models, while keeping the same theoretical expressive power of PT-nets (i.e., we can speak of “abbreviations,” not of “extensions”). In other cases, object-oriented concepts from computer programming are included in certain HLPNs. The analysis techniques of HLPNs can be approached with techniques based on enumeration, transformation, or structural considerations and simulation, generalizing those developed for PT-net systems.

Extending Net Systems with External Events and Time: Nonautonomous Formalisms

When dealing with net systems that interact with some specific environment, the marking evolution rule must be slightly modified. This can be done in an enormous number of ways, considering external events and logical conditions as inputs to the net model, in particular some depending on time. The same interpretation given to a graph in order to define a finite-state diagram can be used to define a marking diagram, a formalism in which the key point is to recognize that the state is now numerical (for PT-net systems) and distributed. For example, drawing a parallel with Moore automata, the transitions should be labeled with logical conditions and events, while unconditional actions are associated to the places. If a place is marked, the associated actions are emitted.

Even if only time-based interpretations are considered, there are a large number of successful proposals for formalisms. For example, it should be specified if time is associated to the firing of transitions (T-timing may be atomic or in three phases), to the residence of tokens in places (P-timed), to the arcs of the net, as tags to the tokens, etc. Moreover, even for T-timed models, there are many ways of defining the timing: time intervals, stochastic or possibilistic forms, and the deterministic case as a particular one. If the firing of transitions follows exponential pdfs, and the conflict resolution follows the race policy (i.e., fire in conflicts the first that ends the task, not a preselection policy), the underlying Markov chain described is isomorphic to the reachability graph (due to the Markovian “memoryless” property). Moreover, the addition of immediate transitions (whose firing is instantaneous) enriches the practical modeling possibilities, eventually complicating the analysis techniques. Timed models are used to compute minimum and maximum time delays (when time intervals are provided, in real-time problems) or performance figures (throughput, utilization rate of resources, average number of tokens – clients – in services, etc.). For performance evaluation, there is an array of techniques to compute bounds, approximated values, or exact values, sometimes generalizing those that are used in certain queueing network classes of models. Simulation techniques are frequently very helpful in practice to produce an educated guess about the expected performance.

Time constraints on Petri nets may change logical properties of models (e.g., mutual exclusion constraints, deadlock-freeness, etc.), calling for new analysis techniques. For example, certain timings on transitions can transform a live system into a non-live one (if to the net system in Fig. 2 are associated deterministic times to transitions and a race policy with the time associated to transition c smaller than that of transition a, transition b cannot be fired, after firing transition d; thus it is non-live, while the untimed model was live). By the addition of some time constraints, the transformation of a non-live model into a live one is also possible. So additional analysis techniques need to be considered, redefining the state, now depending also on time, more than just on the marking.

Finally, as in any DES, the optimal control of timed Petri net models (scheduling, sequencing, etc.) may be approached by techniques as dynamic programming or perturbation analysis (presented in the context of queueing networks and Markov chains, see Perturbation Analysis of Discrete Event Systems). In practice, those problems are frequently approached by means of some partially heuristic strategies. About the diagnosis of timed Petri nets, see Diagnosis of Discrete Event Systems. Of course, all these tasks can be done with HLPNs.

Fluid and Hybrid PN Models

Different ideas may lead to different kinds of hybrid PNs. One is to fluidize (here to relax the natural numbers of discrete markings into the nonnegative reals) the firing of transitions that are “most time” enabled. Then the relaxed model has discrete and continuous transitions, thus also discrete and continuous places. If all transitions are fluidized, the PN system is said to be fluid or continuous, even if technically it is a hybrid one. In this approach, the main goal is to try to overcome the state explosion problem inherent to enumeration techniques. Proceeding in that way, some computationally NP-hard problems may become much easier to solve, eventually in polynomial time. In other words, fluidization is an abstraction that tries to make tractable certain real-scale DES problems (Discrete Event Systems and Hybrid Systems, Connections Between).

When transitions are timed with the so-called infinite server semantics, the PN system can be observed as a time differentiable piecewise affine system. Thus, even if the relaxation “simplifies” computations, it should be taken into account that continuous PNs with infinite server semantics are able to simulate Turing machines. From a different perspective, the steady-state throughput of a given transition may be non-monotonic with respect to the firing rates or the initial marking (e.g., if faster or more machines are used, the uncontrolled system may be slower); moreover, due to the important expressive power, discontinuities may even appear with respect to continuous design parameters as firing rates, for example.

An alternative way to define hybrid Petri nets is a generalization of hybrid automata: The net system is a DES, but sets of differential equations are associated to the marking of places. If a place is marked, the corresponding differential equations contribute to define its evolution.

Summary and Future Directions

Petri nets designate a broad family of related DES formalisms (a modeling paradigm) each one specifically tailored to approach certain problems. Conceptual simplicity coexists with powerful modeling, analysis, and synthesis capabilities. From a control theory perspective, much work remains to be done for both untimed and timed formalisms (remember, there are many different ways of timing), particularly when dealing with optimal control of timed models. In engineering practice, approaches to the latter class of problems frequently use heuristic strategies. From a broader perspective, future research directions include improvements required to deal with controllability and the design of controllers, with observability and the design of observers, with diagnosability and the design of diagnosers, and with identification. This work is not limited to the strict DES framework, but also applies to analogous problems relating to relaxations into hybrid or fluid approximations (particularly useful when high populations are considered). The distributed nature of system is more and more frequent and is introducing new constraints, a subject requiring serious attention. In all cases, different from firing languages approaches, the so named structure theory of Petri nets should gain more interest.

Cross-References

• Applications of Discrete-Event Systems

• Diagnosis of Discrete Event Systems

• Discrete Event Systems and Hybrid Systems, Connections Between

• Models for Discrete Event Systems: An Overview

• Perturbation Analysis of Discrete Event Systems

• Supervisory Control of Discrete-Event Systems

Recommended Reading

Topics related to PNs are considered in well over a hundred thousand papers and reports. The first generation of books concerning this field is Brauer (1980), immediately followed by Starke (1980), Peterson (1981), Brams (1983), Reisig (1985), and Silva (1985). The fact that they are written in English, French, German, and Spanish is proof of the rapid dissemination of this knowledge. Most of these books deal essentially with PT-net systems. Complementary surveys are Murata (1989), Silva (1993), and David and Alla (1994), the latter also considering some continuous and hybrid models. Concerning high-level PNs, Jensen and Rozenberg (1991) is a selection of papers covering the main developments during the 1980s. Jensen and Kristensen (2009) focuses on state space methods and simulation where elements of timed models are taken into account, but performance evaluation of stochastic systems is not covered. Approaching the present day, relevant works written with complementary perspectives include inter alia, Girault and Valk (2003), Diaz (2009), David and Alla (2010), and Seatzu et al. (2013). The consideration of time in nets with an emphasis on performance and performability evaluation is addressed in monographs such as Ajmone Marsan et al. (1995), Bause and Kritzinger (1996), Balbo and Silva (1998), and Haas (2002), while timed models under different fuzzy interpretations are the subject of Cardoso and Camargo (1999). Structure-based approaches to controlling PN models is the main subject in Iordache and Antsaklis (2006) or Chen and Li (2013). Different kinds of hybrid PN models are studied in Di Febbraro et al. (2001), Villani et al. (2007), and David and Alla (2010), while a broad perspective about modeling, analysis, and control of continuous (untimed and timed) PNs is provided by Silva et al. (2011).

DiCesare et al. (1993) and Desrochers and Al-Jaar (1995) are devoted to the applications of PNs to manufacturing systems. A comprehensive updated introduction to business process systems and PNs can be found in van der Aalst and Stahl (2011). Special volumes dealing with other monographic topics are, for example, Billington et al. (1999), Agha et al. (2001), and Cortadella et al. (2002). An application domain for Petri nets emerging over the last two decades is systems biology, a model-based approach devoted to the analysis of biological systems (Koch et al. 2011; Wingender 2011). Furthermore, it should be pointed out that Petri nets have also been employed in many other application domains (e.g., from logistics to musical systems).

For an overall perspective of the field over the five decades that have elapsed since the publication of Carl Adam Petri’s PhD thesis, including historical, epistemological, and technical aspects, see Silva (2013).