Petri nets
IRIS Wiki - Computational Models - Petri nets
Contents
Background
Petri nets is a mathematical model suited for modeling process control and resource sharing. It has mainly been used to model and validate network protocols and systems in production. In such systems Petri nets are used to perform real-time control and supervision, but they can also model path finding (mainly scheduling problems).
Description
Intuitive representation
The following figures gives an intuitive presentation of Petri nets and its dynamics.
Petri Nets - Figure 1
Petri Nets - Figure 2
Petri Nets - Figure 3
Petri Nets - Figure 4
Petri Nets - Figure 5
Petri Nets - Figure 6
Petri Nets - Figure 7
Petri Nets - Figure 8
Petri Nets - Figure 9
Petri Nets - Figure 10
Petri Nets - Figure 11
Formal description
A Petri net is a four-uple R = < P, T, Pre, Post > where:
- P is a set of places
- T is a set of transitions
- Pre: P x T -> N is a set of arcs (input arcs, the point of view is the one of transitions)
- Post: P x T -> N is a set of arcs (output arcs)
W = Post - Pre is also used and call weighted function.
Petri net with marking
N = < R, M > where:
- R is a Petri net
- M is the initial marking (M(p) is the number of tokens in place p.
Enabling and firing transitions
A transition t is enabled iff \forall p \in P M(p) \geq Pre(p, t)
A transition is enabled iff all its input places got a token count greater than 1 (as a simplification).
A transition enabled means that this transition can be fired.
The transition firing consumes one token in each input place (decrease the token count by one) and produce a token in each input place (increase the token count by one). These operations (consume and produce) are atomic.
<math>\forall p \in P M'(p) = M(p) - Pre(p,t) + Post(p,t)</math>
Conflict
Structural conflict: two transitions a1 and a3 are said to be in structural conflict iff they share at least one input place.
Effective conflict: two transitions a1 and a3 are in effective conflict for a marking M iff they are in structural conflict and they are enabled.
The set of accessible marking
The set of accessible marking is an oriented graph (coverability tree) defined by the set of all the making that can be reach for a given initial marking.
A node represents a marking and an arc the transition firing that changes the making from the initial node to the ending one.
Remark: the accessible marking can be unbounded.
Rule system
A Petri nets may have various point of view:
- a graph with two kind of nodes and a dynamics behaviour
- a set of matrix
It can also be considered as knowledge rule system (If then rules).
Properties analysis
Properties have been split into two:
- initial marking dependent properties. The proof is generally based on the accessible marking graph.
- structural properties. The proof is generally based on the matrix analysis
Representing time in Petri nets
A Petri net is a discrete event model meaning that time increases with each event (transition firing).
In Petri nets time is represented by the ordered sequence of transitions firing.
It has been extended to take time into account (mainly for scheduling problems).
Time is considered either as a delay (time Petri nets) or as intervals of dates (timed Petri nets). In both cases time annotation can be attached to places or transitions.
A p-time Petri net is a Petri net whose token has to wait a delay before being used to enable a transition.
In a t-time Petri net, the time can be considered as the duration of the firing transition.
Timed Petri nets were introduced to model watchdog problems. A t-timed Petri net has a time interval attached to transitions. These intervals are the ones where the transition can be fired.
A p-timed Petri net has intervals attached to places and corresponds to the period where the token is valid and can be used to fire transitions.
Stochastics Petri nets
A stochastic Petri net is a Petri net where each transition is associated with an exponentially distributed random variable that expresses the delay imposed on firing transition.
Application to Interactive Storytelling
PN have been used as a model for interactive plot by C. Brom. A sequence of transitions gives the sequence of actions in a narrative. The authors underline the possibility of having a model made up of modules (a set of Petri nets with each one giving a partial view of the system) and also exploits the hierarchical representation.
The interactivity comes from the fact that the actions are modelled by transitions and these can be bound either by the "internal narrator" as well as by the user input.
The drawback of using petri nets for IS is that the PN has to be completely specified a priori. It is similar to a tree structure for the narrative base, except that the graph covering a Petri net may not be finite.
Examples
- Hussein Karam Hussein Abd El-Sattar (2008). A New Framework for Plot-Based Interactive Storytelling Generation, Proceedings of the 2008 Fifth International Conference on Computer Graphics, Imaging and Visualisation, Pages 317-322.
- Brom, C., Sisler, V., Holan, T. (2007). Story Manager in 'Europe 2045' Uses Petri Nets, ICVS 2007: Saint-Malo, France, 38-50.
References
- Murata, T. Proceedings of the IEEE, Vol. 77, No. 4, pages 541-580. April 1989
(http://embedded.eecs.berkeley.edu/research/hsc/class/papers/PetriNets.pdf)
