Coloured Petri Nets
In event condition nets and place transition nets it is impossible to distinguish
tokens from one another. This shortcoming in simple types of Petri nets is
addressed by the colour feature, which allows tokens to have values.
Like variables in programming languages, tokens have typed values. The
data type of a token defines the domain of values and the operations that are valid on the data. In the context of coloured Petri nets, data types are
also called colour sets, with the understanding that a colour set of a token
represents the set of values that the token can possibly have.
In coloured Petri nets, the enabling of a transition is determined the not
by only number of tokens in the input places of the transition, but also by
the values of these tokens. Whether the precondition of a transition is met or
not depends on the presence and values of the tokens to be consumed. This
behaviour is realized by attaching expressions to transitions that are evaluated
to decide whether a transition is enabled.
Similarly, the values of the tokens produced by a transition firing may
depend on values of the tokens consumed. This also means that not all of
the output places receive tokens upon the firing of a transition, realizing a
choice of branches of the net based on the values of the token consumed and
the conditions attached to the transition. The specific firing behaviour of a
transition is specified in the postcondition of the transition.
As a result, the graphical representation of coloured Petri nets is not complete,
since expressions that denote preconditions and postconditions, as well
as values of tokens, are not shown.
While there are several variants of coloured Petri nets, the reminder of
this section introduces them as developed by Kurt Jensen. The behaviour
of transitions is guided by tokens in the input places, in guards attached to
transitions, and in expressions attached to arcs, the arc expressions.
Arc expressions are used to determine whether a transition is enabled.
Arc expressions evaluate to multi-sets, where multi-sets can contain multiple
identical elements. These multi-sets determine the tokens removed from the
input places and added to the output places of a transition when it fires.
Definition 4.6 A coloured Petri net is a tuple (, P, T, A,N,C, G,E, I) such
that
• is a finite set of nonempty types, called colour sets
• P is a finite set of places
• T is a finite set of transitions
• A is a finite set of arc identifiers, such that P \ T = P \ A = T \ A = ;
• N : A ! (P ×T)[(T ×P) is a node function that maps each arc identifier
to a pair (start node, end node) of the arc
• C : P ! is a colour function that associates each place with a colour
set
• G : T ! BooleanExpr is a guard function that maps each transition to a
predicate
• E : A ! Expr is an arc expression that evaluates to a multi-set over the
colour set of the place
• I is an initial marking of the coloured Petri net
Bindings are used to associate data values to variables, i.e., colours to tokens.
For instance, the value “Paula” can be bound to a variable “name.” In coloured
Petri nets, the enabling of a transition depends on a binding. A transition t
is enabled in a binding b if its input places contain tokens that satisfy the
arc expressions under binding b and if in addition, the guard function of the
transition evaluates to true.
If a transition is enabled, it can fire. Depending on the evaluation of the arc
expressions, the respective tokens are removed from the input places. Guided
by the arc expressions of the outgoing edges, the respective tokens are added
to the output places. For a formal treatment of coloured Petri nets, the reader
is referred to the bibliographical notes at the end of this chapter.
The coloured Petri net has associated a colour set consisting of [Customer,
Amount] pairs of values, where Customer is a string and Amount is an integer
value. Coloured tokens represent specific [Customer, Amount] value pairs.
Initially, there are three tokens in the Credit Request place p1, representing
the credit requests by Paula, Mary, and Peter and their respective credit
amounts. The AssessRisk transition is enabled, because there is a token in
its input place and there is no additional guard function associated with that
transition.
The AssessRisk transition is enabled under binding c = Paula, and a =
15000, because there is a token [Paula,15000 ] at p1 that satisfies the arc
expression. Since there is no additional guard expression associated with that
transition, it is enabled, and it can fire.
The assess risk transition decides on which of its output places a token
should be put when it fires. The respective arcs are labelled postcon ditions that define the firing behaviour. Assuming a token carrying the value
[Paula,15000 ] is consumed, so that amount is below 20000, the AssessRisk
transition puts a token on p3 and not on p2, enabling the SimpleRiskAssessment
transition.
This behaviour of the coloured Petri net is due to the arc expressions
associated with the outgoing edges of the transition. When the transition fires,
the arc expressions of both outgoing edges are evaluated. Since the requested
amount is below 20000, only the arc expression if a <=20000 (c,a) is evaluated
to true, so that a token is put on p3, and no token is put on p2.
When the SimpleRiskAssessment transition fires, a token is put on p4.
The token also includes a value assessing the risk of the credit requested,
indicated by the arc expression (c, a, r), where r stands for a variable that
carries the assessed risk. Assuming there are two risk levels—represented by
values l for low and h for high—and Paula gets a low risk assessment, the
token [Paula, 15000, l] is put on p4.
Depending on the first letter of the credit requester’s name, the respective
inform customer transition is enabled. This decision is ruled by guard functions,
which are represented by functions placed on top of transitions. In the
example, the BeginsWith(name, interval) returns true if and only if name
begins with a letter in interval. Since the token for Paula is in p4, the transition
Inform Customer I-Z is enabled. After the customer is informed, the
process completes.
To summarize, the behaviour of a transition in a coloured Petri net is
defined by a guard function, by the tokens that reside in its input places, and
by arc expressions. Hence, transition firing in coloured Petri nets exhibits a
complex and highly customizable behaviour.
Therefore, it is valid to say that each transition in a coloured Petri net
has its own transition behaviour, which provides a high expressive power for
this class of Petri nets. At the same time, the graphical representation is no
longer sufficient to capture and understand the semantics of the Petri net.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment