The Petri nets are one of the most widely used methods for the study of the dynamics that falls within the category of Discrete Event Systems (DES) . The DES is a class of systems that are guided by the occurrence of events asynchronous in time, which are becoming more and more relevant nowadays. The Petri nets are graphically represented as a directed graph, with two classes of nodes, called places and transitions. The places allow capturing the state of a system. They also represent the conditions required by the events to occur, or to execute, in the DES.
The transitions represent the events, or actions, executed in a system. The execution of the transitions may require one or more conditions to be activated. Moreover, it is possible that a transition does not include input places, as in Figure 2 . This class of transitions allows capturing situations in a DES where an event may be random or stochastic, for example, the arrival of an information package in a communication channel. The explanation of the Petri net in Figure 2 will be addressed lather in this section, after the introduction of the system that it represents.
Figure 1 depicts a conceptual diagram of a multitasking manufacturing system . The system is supplied with the raw material from two conveyors, and . A robot arm distributes the raw material to either a mill machine or to a lather machine, depending on the manufacturing recipe. The semi-finished pieces are then moved by transporting bands to the assembly machine.
Figure 2 depicts a Petri net model for this multitasking manufacturing system. The supply of the raw material is represented as two transitions with no inputs. In means the material may arrive at any time that the inventory of raw pieces is able to feed the manufacturing system. The robotic arm moves the raw pieces to the mill machine, by means of , or to the lather machine, by means of . The semi-finished pieces are moved to the assembly station to produce a final product.
Depending on what is the interest of study of the system, for example, the design of control strategies or the evaluation of performance of the assembly recipe, the model in Figure 2 could be refined or extended. Even new sections of the assembly system may be added to the Petri net model.
The manufacturing system and assembly lines, as well as communication protocols, are some of the most popular type of systems that are modeled and studied with Petri net models [8, 9, 10]. However, other types of systems such as workflow management or logistic systems are similarly likely to be modeled and studies by means of Petri nets [15, 16, 17]. Moreover, the design and implementation of complex software systems is as well plausible to be addressed with Petri net models [18, 19, 26].
The addressing of software design with Petri nets is popular because the construction of models for complex structures and control flow is quite intuitive thanks to its graphical nature. Moreover, the techniques developed around the Petri nets allow the construction of models that are usually more compact than the produced by other methods, such as those developed in graph theory. However, Petri nets and graph theory are not antagonist. On the contrary, the theory developed in one of them is usually extended to the other. Thus, they are usually complementary to each other.
Figure 3 depicts a block diagram of a reader and writer problem in computer sciences. The processes share a region of memory where they can read and write. The diagram depicts the process that can read, process that can write, and process that perform both operations, reading and writing to the shared memory region. This situation arises in several cases in the design of monolithic and distributed system, within the area of software design.
Figure 4 depicts a model for the above problem of readers and writers . The net represents a system with readers modeled as . The system allows up to parallel reads from a shared memory region. It is represented by the marking in . However, the writing operation requires tokens on . That is, it requires that no reading operation is currently in execution. Correspondingly, when a writing operation is in execution, no read operation is allowed. This is represented by weighted arc of . Thus, when writing operation is in execution, by the firing of , the tokens in are removed. Once the reading operation is done, the firing of returns tokens to . The Petri net model allows any of the processes to read and to write to the shared place by connecting the place to the reading or writing sections of the net.
Other attractive attribute of the Petri nets is their solid mathematical basis. The incidence matrix that represents the structure of the net in Figure 4 is represented by Eq. (1). The incidence matrix is independent of the initial condition of the net. This structure could be analyzed by methods from the matrix theory, linear algebra, or vector spaces, for example.
The state equation of a Petri net allows a formal definition of its dynamics. The next state of a Petri net can be computed from the current state, and a multiplication of the matrix that represents the structure of the net and a vector that represents the transitions that can fire, as follows:
The vector represents one or more transitions that are allowed to fire. It is known as the Parikh vector, in a clear relationship to the Parikh’s theorem. This theorem relates the strings in a context-free language and the number of the occurrences of the symbols in these strings.
In a similar way, the vector represents the number of times each transition is fired at a given stage in the evolution of the net. In this sense, the Parikh vector behaves like a “functor” in the sense of the category theory , from the strings over the alphabet of events in a DES to vectors that quantifies the occurrence of events in a DES. That is, the Parikh vector “loses” the execution order of the events in a trajectory of a DES to obtain a pure vector which is simpler to operate by a matrix multiplication.
There are different semantics for the execution of the transitions in a Petri net model. First, in a single firing semantics, only one of the enabled transitions can fire at a time. Second, in the multiple firing semantics, all the enabled transitions are allowed to fire at a time. In all the semantic approaches, the conflicting transitions, that is, the ones whose firing disables the firing of others are resolved by priorities, by a probability distribution, or some other conflict resolution mechanism. Depending on the adopted semantics, the ability of the models to capture dynamics of real systems differs. For example, if the analyzed system is of distributed nature, such as a cluster of computers or a cloud service, then the correct semantics is that of multiple firing. The expressiveness of the different semantic mechanisms is a theoretical question that lies around the computer sciences. The next subsections detail some theoretical aspects of the Petri nets and application in science and theory of systems.
2. Petri nets in science
As mentioned, the Petri nets are a very versatile tool that turns it useful in science, as well as in engineering. In the science field, a wide developed aspect is related to the study of Petri nets as a system and their associated abstract properties.
For example, the study of properties of the Petri net models in terms of vectors and matrices is complemented with the linguistic study in terms of strings and formal languages. The well-developed theory of matrices, linear algebra, and vector spaces are well suited to the analysis of properties in the net models, providing efficient solutions. However, other studies such as the reachability analysis, requires the partial expansion of the state space of the models, which turns the investigation in an inverse direction, from a vector space to string over a language. Though, the advantages of the study of the Petri net properties in terms of vectors, matrices, and linear algebra in general are considerable, and many of the theory developed for Petri nets relies on them.
Indeed, by restricting the marking of a Petri net to be non-negative, the state space entirely lies in the positive cone of Z+. Thus, some of the theory of positive linear systems could be applied . Figure 5(a) depicts the state space, in , of the Petri net model in (b) for two different initial conditions and , the two hyperplanes are orthogonal to the unitary vector . Moreover, if the net is conservative (i.e., the number of tokens over all its places remains constant for any evolution trajectory), then it is easy to show that the entire state space of the Petri net lives in one of the hyperplanes orthogonal to a vector in , where is the number of places of the net.
One of the most active areas of the applications of the Petri nets in science is in the field of the modern control theory. The study of control techniques for discrete event system, including Petri net models, covers the range of applications from design of discrete event controller, design of state observers, analysis of fault tolerant systems, analysis of Lyapunov-like stability, detectability analysis, isolation, and failure recovery techniques, among others [4, 5, 6].
In this context, considering a Petri net as an input-output system, as in classical control theory, is useful. Figure 6 depicts the state equation of a Petri net given by a block diagram. The input vector is operated by the matrix to produce a marking increment that is added to the current marking. The sum of these two quantities becomes the new marking reached by the current evolution of the net. A unit delay block allows the new marking becoming the current marking for the next evolution of the net.
Considering the state equation of a Petri net as a block diagram as in Figure 6 allows studying the dynamics of the model as in the control theory . Techniques for the construction of feedback controller or state observers could be addressed . Performance analysis is as well, a usual analysis stage in the design of the class of systems that could be modeled by a Petri net .
Figure 7 depicts a block diagram of a classical control scheme for a DES modeled as a Petri net. The scheme considers two models, one of the system and the other of a reference. The controller receives the difference of the output of the system and the reference in order to compute the control actions. The objective of the control scheme is to achieve zero error, by the actions that the controller can exert over the system. If the system to be controlled is a software, for example, either distributed or monolithic, then the reference is a specification or recipe that the software must meet. Then, the controller is another software responsible for computing the required parameters and configurations in order to adapt the main software system to the required behavior in an autonomous fashion. There is a huge trend in cloud computing and artificial intelligence to transform current software systems, such as database clusters, into autonomous intelligent systems that automatically adapts to user requirements and that are even able to predict future workloads and adapt to them [11, 12].
The next section reviews some illustrative use of Petri net models in engineering applications.
3. Petri nets in engineering
The usability of the Petri nets in engineering applications is as well widely accepted. The stages of the design, the implementation, and the validation of systems are suitable addressed with Petri net models. The covered applications include communication protocols, distributed systems, distributed database, concurrent and parallel programming and systems, industrial control systems, multicore processor platforms, dataflow-computer systems design, workflows and process-driven systems, fault-tolerant systems, and to mention a few. Properties practical interest such as fairness in the execution of tasks, deadlock avoidance, state reachability, process interlocking, among others, are possible to be analyzed within the Petri net framework.
For example, Figure 8 illustrates a very simple and conceptual communication protocol. The communication act is analyzed from the sending process point of view. A sender process sends a message by the output buffer and blocks its activity while waiting for an acknowledgement by the input buffer. A receiver process is blocked while waiting for an input message. Once a message has arrived, the receiving process reads the message and sends an acknowledgment by the input buffer. After the communication act has finished, the process restarts its logic to be ready for the next communication. This model could be extended to include faulty communication channels, which may lose the messages, acknowledge expiration periods, or other characteristics of practical interest. The analysis and design of communications protocols has been widely addressed with the use of Petri net models [9, 10].
There are some extensions to the Petri nets to handle specific aspects of different engineering problems. Some of the extensions add structure and information to the tokens, transitions, and places of a net. These extensions allow the construction of models that are quite compact compared to the models obtained with the traditional approach. These models are called Colored Petri Net (CPN) .
As an illustration, Figure 9 depicts a CPN for a task scheduling problem. The structure of the net represents the different stages of the working processes in a distributed multitasking environment. The left-hand side of the net structure represents the stages that the processes perform to acquire a job. The right-hand side represents the stages that the working processes perform to release the resources and update the state of the overall scheduling problem. The simulation of the model depicted in the figure allows to study the performance of different scheduling policies over different workload conditions. For example, it is possible to approximate the optimal number of process required by the scheduling problem for a fixed number of tasks. Even more, it is possible to study an optimum rate in the increment of the working processes given a rate in the increment of the tasks over discrete interval of times .
Recently, with the increase of the cloud computing and the massive data content in the social networks, the machine learning techniques and the methods related to the data analytics are essential tools in the study and investigation of the big data. There are several proposals to allow the Petri net models learn some kind of fuzzy reasoning and decision making [22, 23, 24]. Similar approaches as that of the supervised and unsupervised learning have been addressed [21, 25].
Figure 10 shows a Petri net representing a workflow pattern for a customer reclaim system. The customer may initiate a request at any time. Two activities are launched in parallel once a request is in the system. First, a ticket check process is executed. Second, an examination of the request is performed. At this point, based on the machine learning, data analytics and/or statistical learning mechanisms, guards for the transitions b and c are constructed. The guards allow deciding when it is more convenient to execute an in-deep examination process or a casual examination process. On the one hand, it saves time by executing a casual examination when the guard determines that it is more likely that the characteristics of the request are that of a genuine customer request. On the other hand, it saves money by executing a thoroughly examination process when the guard determines that the current request is more likely to be a fraudulent request.
Other important area of the engineering where the Petri nets have been successfully used is in the automatic code generation. The exponential growth of the cloud computing and proliferation of solutions based on the Internet of Things have made the design of the system software supporting them become more challenging. The set of requirements that this type of systems must address includes the sensing of signals in soft and hard real-time and the traditional support for media-reach services. This mixture of requirements turns the design of a correct and efficient system of this type a whole challenge. Approaches based on model-based design promise useful solutions for these challenges. The complex behavior and set of conditions that this class of software must address can be well represented with Petri net patterns. Synchronization mechanisms, message passing, rise conditions, critical sections, parallel and concurrent process, task activation conditions, and user interactions, to mention a few, could be easily represented with intuitive Petri net blocks. Then, a simulation process may allow the study of the performance of the solution and the adjustment of parameters for a fine-tuning process.
Figure 11 represents a Petri net model for three parallel processes. The transition launches the execution of the processes in parallel. Each process runs freely until they end its activities. In this design, the transition synchronizes the end of the processes. That is, if one process ends its activities, then it must wait the others to end. Once all the processes have finished, the loop repeats infinitely. The transitions , and represent the activity load of each process. There are different approaches to add an amount of time to these transitions [13, 14, 15]. Within a suitable simulation process, this allows to investigate the performance of the system under different work load conditions, which is a must in the development of real world solutions. Once the parameters of the model have been tuned and its performance evaluated, the next step consists on the synthesis of the code in a target programming language for a specific platform.
For example, Figure 12 shows a section of code in C/C++ implemented from the model in Figure 11 . The code implements a set of joinable posix threads. A for loop launches a number of threads defined by the global constant NUM_THREADS. Other for loop waits for the end of the threads. Once all the threads have finished, the loop repeats indefinitely. The automatic code generation from Petri net models has recently been investigated with promissory results [19, 20].
This chapter aims to briefly review the applications of the Petri nets in science and engineering. It not pretends to be a deep review of the applications with complete detail and mathematical foundation. Rather, the objective is to provide an illustrative introduction to Petri nets and its potential applications, as intuitive as possible, avoiding the use of complex mathematical notation and formulation. The focus of this chapter was in the graphical nature of the Petri nets and the intuition about them, and with some emphasis in its mathematical foundation. Also, the intention is that this chapter serves as an introduction to this book entitled Petri Nets in Science and Engineering. The authors hope you find this book illustrative for your different activities in science and engineering.
R. Campos-Rodriguez, M. Alcaraz-Mejia.
The authors want to thank Jose Valerio, from Oracle Guadalajara Development Center, for his valuable comments in the review of this chapter and for his experience and comments in Machine Learning and Data Analytics.