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