The aim of this paper is to present a new class of Petri nets called generalised fuzzy Petri nets. The new class extends the existing fuzzy Petri nets by introducing two operators: triangular norms (t-norms) and t-conorms (s-norms), which are supposed to function as substitute for the min and max operators. To demonstrate the power and the usefulness of this model, an application of the generalised fuzzy Petri nets in the domain of train trac control is provided. The new model is more exible than the classical one as in the former class the user has the chance to dene the input/output operators. The proposed approach can be used for knowledge representation and reasoning in decision support systems.
Petri nets serve as a graphical and mathematical modelling tool applicable to
many systems. Their graphical aspect allows representation of various
interactions between discrete events more easily. However, the mathematical aspect
allows formal modelling of these interactions and analysis of the modelled
system properties [
The concept of a Petri net has its origin in C.A. Petri’s dissertation [
The aim of this paper is to further improve the fuzzy Petri net model for
knowledge representation and reasoning and to overcome some deciencies of
former FPN approaches [
In the paper, we propose a new class of Petri nets called " Generalised F uzzy P etri N ets (GFPNs )" for knowledge representation and reasoning in decision support systems. This model is a natural extension of fuzzy Petri nets. The tnorms and s-norms are introduced to the model as substitutes of min and max operators. The latter ones generalize naturally AND and OR logical operators with the Boolean values 0 and 1. The proposed model is not only more comfortable in terms of knowledge representation, but most of all it is more eective in the modelling process of approximate reasoning as in the new class of fuzzy Petri nets the user has the chance to dene the input/output operators. The preliminary results of real-life data experiments using this model are promising. In order to demonstrate the modelling aspects of GFPNs, an application of generalised fuzzy Petri nets in the domain of train trac control is provided.
The structure of this paper is as follows. Sect. 2 gives a brief introduction to fuzzy Petri nets. In Sect. 3 generalised fuzzy Petri nets formalism is presented. Sect. 4 describes an application of this class of FPN in the domain of train trac control. In Sect. 5 conclusions are made. 2
One of the most known and applicable class of Petri nets in the domain of
Articial Intelligence are fuzzy Petri nets [
In this paper we view a fuzzy Petri net as a decision support system based on specic rules of the form: IF condition THEN action, for which the condition is consumed and the action is produced each time the rule is used. In a decision support system, the knowledge representation is based on a collection of rules. In a fuzzy Petri net, each transition may be seen as a rule which depicts a possible state change.
Denition 1. A fuzzy Petri net (FP-net) is a tuple N = (P; T; S; I; O; ; ; ; M 0), where: - P = fp1; p2; : : : ; png is a nite set of places, n > 0; - T = ft1; t2; : : : ; tmg is a nite set of transitions, m > 0; - S = fs1; s2; : : : ; sng is a nite set of statements; - the sets P , T , S are pairwise disjoint, i.e., P \ T = P \ S = T \ S = ; and card(P ) = card(S); - I : T ! 2P is the input function; - O : T ! 2P is the output function; - : P ! S is the statement binding function; - : T ! [0; 1] is the truth degree function; - : T ! [0; 1] is the threshold function; - M 0 : P ! [0; 1] is the initial marking, and 2P denotes a family of all subsets of the set P .
As for the graphical interpretation, places are denoted by circles and transitions by rectangles. The places are the nodes describing states (a place is a partial state) and the transitions depict the state changes. The function I describes the oriented arcs connecting places with transitions. It represents, for each transition t, the fragments of the state in which the system has to be, before the state change corresponding to t can occur. The function O describes the oriented arcs connecting transitions with places. It represents, for each transition t, fragments of the state in which the system will be after the occurrence of the state change corresponding to t. If I(t) = fpg then a place p is called an input place of a transition t. Moreover, if O(t) = fp0g, then a place p0 is called an output place of t. The initial marking M 0 is an initial distribution of tokens in the places. It can be represented by a vector of dimension n of real numbers from the closed interval [0; 1]. For p 2 P , M 0(p) is the token load of place p and represents a partial state of the system described by the fuzzy Petri net. This value can be interpreted as a truth value of a statement s bound with a given place p by means of the statement binding function , i.e., (p) = s. Pictorially, the tokens are represented by means of grey "dots" together with the suitable real numbers placed inside the circles corresponding to appropriate places. We assume that if a truth value of a statement attached to a given place is equal to 0 then the token does not exist in the place. The number (t) is placed in a net picture under a transition t. Usually, this number is interpreted as a truth degree of an implication corresponding to a given transition t. The meaning of the threshold function is explained below.
Let N be a FP -net. A marking of N is a function M : P ! [0; 1].
The fuzzy Petri net dynamics denes how new markings are computed from the current marking when transitions are red (the corresponding state change occurs). It describes the state changes of the decision support system modeled by the fuzzy Petri net.
Let N be a FP -net, t 2 T , I(t) = fpi1; pi2; : : : ; pikg be a set of input places for a transition t, and M - a marking of N .
A transition t is enabled for marking M if the minimum min for all input places of the transition t by M is positive and greater than or equal to the value of the threshold function to t, i.e., min(M (pi1); M (pi2); : : : ; M (pik))
Only enabled transitions can be red. Informally, ring the enabled transition t consists of removing (or not) dependently on the ring mode (it will be further discussed in detail) the token load of its input places by I(t) (as the transition is enabled no negative token load will be obtained), and increasing the token load of all its output places by O(t) without any alteration of the token loads of other places.
This informal denition points out the fact that ring the transition t is local in the sense that it only involves the tokens captured by I(t) and O(t) independently from the other remaining tokens of the current marking. Firing is based on two invisible primitives: removal of the tokens from input places and insertion of the tokens in output places. Transitions which do not share any places can be red independently. This is why fuzzy Petri nets are a mathematical tool that can capture true concurrency.
There are two operating modes of the fuzzy Petri nets. In the rst mode, each ring of an enabled transition t removes tokens from its input places and adds a token to each of its output place (if the token does not exist in the place yet). If in a given output place the token already exists then the red transition does not place a new token. In the rst case, a new value related to the generated token is computed as follows. After computing the minimum value from all values corresponding to input places of a red transition, the computed value is timed by the value of function corresponding to a red transition. A new value is placed in all output places of a red transition. In the second case, we assume that ring enabled transition does not remove tokens from its input places (copies of the tokens are only transmitted to output places of a red transition). A nal value of tokens is computed in an analogous way to the rst case. In both cases, if in a given output place the token already exists then the red transition computes a new value of the token as follows. The nal value of a given output place of a red transition is computed as maximum value from the one residing in the output place and the computed value of the red transition.
Let N = (P; T; S; I; O; ; ; ; M 0) be a FP -net, t 2 T , I(t) = fpi1; pi2; : : : ; pikg be a set of input places for a transition t, (t) be a value of the truth degree function corresponding to t and (t) 2 (0; 1] (0 is not included), (t) be a value of threshold function corresponding to t, and M be a marking of N . Moreover, let min, , max denote the minimum, the algebraic product and the maximum, respectively.
Mode 1. If M is a marking of N enabling transition t and M 0 the marking derived from M by the ring transition t, then for each p 2 P :
M 0(p) = 8 0 if p 2 I(t); <
max(min(M (pi1); M (pi2); : : : ; M (pik)) : M (p) otherwise. (t); M (p)) if p 2 O(t);
In this mode, a procedure for computing the marking M 0 is as follows: (1) Tokens from all input places of the transition t are removed (the rst condition from M 0 denition). (2) Tokens in all output places of t are modied in the following way: at rst the value of minimum min for all input places of t is computed, then the product of the computed minimum for all input places of t and the value of truth degree function (t) is determined, and nally, a value corresponding to M 0(p) for each p 2 O(p) is obtained as a result of maximum for the computed product value and the current marking M (p) (the second condition from M 0 denition). (3) Tokens in the remaining places of net N are not changed (the third condition from M 0 denition).
Mode 2. If M is a marking of N enabling transition t and M 0 the marking derived from M by the ring transition t, then for each p 2 P :
M 0(p) = max(min(M (pi1); M (pi2); : : : ; M (pik)) M (p) otherwise. (t); M (p)) if p 2 O(t);
The dierence in the denition of a marking M 0 presented above ( Mode 2 ) concerns input places of the red transition t. In Mode 1 tokens from all input places of the red transition t are removed (cf . the rst denition condition of Mode 1 ), whereas in Mode 2 all tokens from input places of the red transition t are copied (the second denition condition of Mode 2 ). Example 1. Let us consider a fuzzy Petri net in Figure 1. For the net we have: the set of places P = fp1; p2; p3; p4; p5g, the set of transitions T = ft1; t2g, the input function I and the output function O in the form: I(t1) = fp1; p2g, I(t2) = fp2; p3g, O(t1) = fp4g, O(t2) = fp5g. Moreover, there are: the set of statements S = fs1; s2; s3; s4; s5g, the statement binding function : (p1) = s1, (p2) = s2, (p3) = s3, (p4) = s4, (p5) = s5, the truth degree function : (t1) = 0:7, (t2) = 0:8, the threshold function : (t1) = 0:4, (t2) = 0:3 and the initial marking M 0 = (0:6; 0:4; 0:7; 0; 0).
(a) (b)
Transitions t1 and t2 are enabled by the initial marking M 0. Firing transition t1 by the marking M 0 according to Mode 1 transforms M 0 to the marking M 1 = (0; 0; 0:7; 0:28; 0) (Figure 2(a)), and ring transition t2 by the initial marking M 0 according to Mode 2 results in the marking M 2 = (0:6; 0:4; 0:7; 0; 0:32) (Figure 2(b)). 3
Now we are ready to dene a new class of Petri net model called a generalised fuzzy Petri net. Before giving a formal denition of this model we remind some notions used later on. This section presents the main contribution to the paper.
A t-norm is dened as t : [0; 1] [0; 1] ! [0; 1] such that, for each a; b; c 2 [0; 1]: (1) it has 1 as the unit element, i.e., t(a; 1) = a; (2) it is monotone, i.e., if a b then t(a; c) t(b; c); (3) it is commutative, i.e., t(a; b) = t(b; a); (4) it is associative, i.e., t(t(a; b); c) = t(a; t(b; c)).
More relevant examples of t-norms are: the minimum t(a; b) = min(a; b) which is the most widely used, the algebraic product t(a; b) = a b, the ukasiewicz t-norm t(a; b) = max(0; a + b 1).
An s-norm (or a t-conorm) is dened as s : [0; 1] [0; 1] ! [0; 1] such that, for each a; b; c 2 [0; 1]: (1) it has 0 as the unit element, i.e., s(a; 0) = a, (2) it is monotone, i.e., if a b then s(a; c) s(b; c), (3) it is commutative, i.e., s(a; b) = s(b; a), and (4) it is associative, i.e., s(s(a; b); c) = s(a; s(b; c)).
More relevant examples of s-norms are: the maximum s(a; b) = max(a; b) which is the most widely used, the probabilistic sum s(a; b) = a + b a b, the ukasiewicz s-norm s(a; b) = min(a + b; 1).
Using the notions of t- and s-norms we formulate the denition a generalised fuzzy Petri nets as follows: Denition 2. A generalised fuzzy Petri net (GFP-net) is a tuple N 0 = (P; T; S; I; O; ; ; ; Op; ; M 0), where: - P; T; S; I; O; ; ; ; M 0 have the same meaning as in Denition 1; - Op is a nite set of t-norms and s-norms called the set of operators; - : T ! Op Op Op is the operator binding function.
The operator binding function connects transitions with triples of operators
(opIn; opOut1; opOut2). The rst operator appearing in the triple is called the
input operator, and two remaining ones are the output operators. The input
operator opIn concerns the way in which all input places are connected with
a given transition t (more precisely, statements corresponding to those places).
However, the output operators opOut1 and opOut2 concern the way in which
the next marking is computed after ring the transition t. In the case of input
operator we assume that it can belong to one of two classes, i.e., t- or s-norm.
This issue is more precisely discussed further on. In fuzzy Petri nets the operators
minimum, algebraic product and maximum are usually used. As we know, the
rst two belong to the class of t-norms whereas the third belongs to the class
of s-norms. In the new net model the input/output operators can be dened
by a user of the model dependently on her/his needs. In general, selecting rule
operators and parameters (if we consider so called parameterised families of
t- and s-norms [
Let N 0 be a GFP -net. A marking of N 0 is a function M : P ! [0; 1].
A transition t 2 T is enabled for marking M if the value of input operator opIn for all input places of the transition t by M is positive and greater than or equal to the value of threshold function corresponding to the transition t, i.e., opIn(M (pi1); M (pi2); : : : ; M (pik))
(t) > 0 for each pij 2 I(t); j = 1; : : : ; k:
Let N 0 = (P; T; S; I; O; ; ; ; Op; ; M 0) be a GFP -net, t 2 T , I(t) = fpi1; pi2; : : : ; pikg be a set of input places for a transition t and (t) 2 (0; 1]. Moreover, let opIn be an input operator and opOut1, opOut2 be output operators for the transition t.
Mode 1. If M is a marking of N 0 enabling transition t and M 0 the marking derived from M by ring transition t, then for each p 2 P :
8 0 if p 2 I(t); M 0(p) = >< opOut2(opOut1(opIn(M (pi1); M (pi2); : : : ; M (pik)); (t)); M (p)) > if p 2 O(t); : M (p) otherwise.
In this mode, a procedure for computing the marking M 0 is similar to appropriate procedure corresponding to fuzzy Petri nets and Mode 1 presented above. The dierence is that present procedure needs to set operators: opIn, opOut1, opOut2 at rst. Remaining stages of the procedure are analogous to the previous procedure concerning Mode 1.
Mode 2. If M is a marking of N 0 enabling transition t and M 0 the marking derived from M by ring transition t, then for each p 2 P :
8 opOut2(opOut1(opIn(M (pi1); M (pi2); : : : ; M (pik)); (t)); M (p)) M 0(p) = < if p 2 O(t);
: M (p) otherwise.
(Mode 2 ) and Mode 1 is analogous to the fuzzy Petri nets.
Example 2. Let us consider a generalised fuzzy Petri net in Figure 3. For the net we have: the set of places P , the set of transitions T , the set of statements S, the input function I, the output function O, the statement binding function , the truth degree function , the threshold function , and and the initial marking M 0 are described analogously to Example 1. Moreover, there are: the set of operators Op = fmax; min; g and the operator binding function dened as follows: (t1) = (max; ; max), (t2) = (min; ; max).
(a) (b)
Transitions t1 and t2 are enabled by the initial marking M 0. Firing transition t1 by the marking M 0 according to Mode 1 transforms M 0 to the marking M 1 = (0; 0; 0:7; 0:42; 0) (Figure 4(a)), and ring transition t2 by the initial marking M 0 according to Mode 2 results in the marking M 2 = (0:6; 0:4; 0:7; 0; 0:32) (Figure 4(b)). 4
This section presents an application of GFPN in the domain of train trac
control [
In this situation, the following alternatives can be taken into consideration: Train B waits for train A to arrive. In this case, train B will depart with delay.
Train B departs in time. In this case, passengers disembarking train A have to wait for a later train.
Train B departs in time, and an additional train is employed for late train A0s passengers.
To make a decision, several inner conditions have to be taken into account such as the delay period, the number of passengers changing trains, etc. The discussion regarding an optimal solution to the problem of divergent aims such as: minimization of delays throughout the trac network, warranty of connections for the customer satisfaction, ecient use of expensive resources, etc. is disregarded at this point.
In order to describe the trac conict, we propose to consider the following three rules:
IF s1 AND s4 AND s6 THEN s7;
IF s4 AND s5 THEN s8, where: s1 = "Train B is the last train in this direction today", s2 = "The delay of train A is huge", s3 = "There is an urgent need for the track of train B", s4 = "Many passengers would like to change for train B", s5 = "The delay of train A is short", s6 = "(Let) train B depart according to schedule", s7 = "Employ an additional train C (in the same direction as train B)", and s8 = "Let train B wait for train A".
In Figure 5 the GFPN model corresponding to these rules, where the logical operators OR, AND are interpreted as max and min, respectively, is shown. Note that the places p1; p2; p3 and p4 include the fuzzy values 0.6, 0.4, 0.7 and 0.5 corresponding to the statements s1; s2; s3 and s4, respectively. In this example, the statement s5 attached to the place p5 is the only crisp and its value is equal to 1. By means of evaluation of the statements attached to the places from p1 up to p5, we observe that the transitions t1 and t3 can be red. Firing these transitions according to the ring rules for the GFPN model allows the computation of the support for the alternatives in question. In this way, the possible alternatives are ordered with regard to the preference they achieve from the knowledge base. This order forms the basis for further examinations and simulations and, in the end, for the dispatching proposal. If one chooses a sequence of transitions t1t2 then they obtain the nal value, corresponding to the statement s7, equal to 0.35. In the second possible case (i.e., for the transition t3 only), the nal value, corresponding now to the statement s8, equals 0.45. 5
The GFPN model combining the graphical power of Petri nets, possibilities of fuzzy sets and the theory of t -norms to model rule-based expert knowledge in a decision support system have been described in the paper. Having discussed basic notions from the fuzzy Petri net theory, GFPN formalism has been presented. Using a simple real-life example the suitability and the usefulness of the proposed approach for the design and implementation of decision support systems have been proved. Success of the elaborated approach looks promising with regard to alike application problems that could be solved similarly.
An experimental application called PNES on IBM PC, in Java, consisting of an editor and a simulator have been developed. The editor allows the inputting and editing of generalised fuzzy Petri nets, while the simulator that starts with a given initial marking and executes enabled transitions visualising reached markings. All gures and simulation results presented in the paper were produced by the application.
Acknowledgment. The author is grateful to anonymous referees for their helpful comments.