Open access peer-reviewed chapter

Construction and Application of Learning Petri Net

By Liangbing Feng, Masanao Obayashi, Takashi Kuremoto and Kunikazu Kobayashi

Submitted: November 25th 2011Reviewed: May 7th 2012Published: August 29th 2012

DOI: 10.5772/48398

Downloaded: 2278

1. Introduction

Petri nets are excellent networks which have great characteristics of combining a well-defined mathematical theory with a graphical representation of the dynamic behavior of systems. The theoretical aspect of Petri nets allows precise modeling and analysis of system behavior, at the same time, the graphical representation of Petri nets enable visualization of state changes of the modeled system [32]. Therefore, Petri nets are recognized as one of the most adequate and sound tool for description and analysis of concurrent, asynchronous and distributed dynamical system. However, the traditional Petri nets do not have learning capability. Therefore, all the parameters which describe the characteristics of the system need to be set individually and empirically when the dynamic system is modeled. Fuzzy Petri net (FPN) combined Petri nets approach with fuzzy theory is a powerful modeling tool for fuzzy production rules-based knowledge systems. However, it is lack of learning mechanism. That is the significant weakness while modeling uncertain knowledge systems.

At the same time, intelligent computing is taken to achieve the development and application of artificial intelligence (AI) methods, i.e. tools that exhibit characteristics associated with intelligence in human behaviour. Reinforcement Learning (RL) and artificial neural networks have been widely used in pattern recognition, decision making, data clustering, and so on. Thus, if intelligent computing methods are introduced into Petri nets, this may make Petri nets have the learning capability, and also performance and the applicable areas of Petri nets models will be widely expanded. The dynamic system can be modeled by Petri nets with the learning capability and then the parameters of the system can be adjusted by online (data-driven) learning. At the same way, if the generalized FPNs are expanded by adding neural networks and their leaning capability, then FPNs are able to realize self-adapting and self-learning functions. Consequently, it achieves automatic knowledge reasoning and fuzzy production rules learning.

Recently, there are someresearches for making the Petri net have learning capability and making it optimize itself. The global variables are used to record all state of colored Petri net when it is running [22]. The global variables are optimized and colored Petri net is updated according to these global variables. A learning Petri net model which combines Petri net with a neural network is proposedby Hirasawa et al., andit was applied to nonlinear system control[10]. In our former work [5, 6], a learning Petri net model has been proposed based on reinforcement learning (RL). RL is applied to optimize the parameters of Petri net. And, this learning Petri net model has been applied to robot system control. Konar gave an algorithm to adjust thresholds of a FPN through training instances [1]. In [1], the FPN architecture is built on the connectionism, just like a neural network, and the model provides semantic justification of its hidden layer. It is capable of approximate reasoning and learning from noisy training instances.A generalized FPN model was proposed by Pedrycz et al., which can be transformed into neural networks with OR/AND logic neuron, thus, parameters of the corresponding neural networks can be learned (trained) [24]. Victor and Shen have developed a reinforcement learning algorithm for the high-level fuzzy Petri net models [23].

This chapter focuses on combining the Petri net and fuzzy Petri net with intelligent learning method for construction of learning Petri net andlearning fuzzy Petri net (LFPN), respectively. These are applied to dynamic system controls and a system optimization. The rest of this paper is organized as follow. Section 2 elaborates on the Learning Petri net construction and Learning algorithm. Section 3 describes how to use the Learning Petri net model in the robots systems. Section 4 constructs a LFPN. Section 5 shows the LFPN is used in Web service discovery problem. Section 6 summarizes the models of Petri net described in the chapter and results of their applications and demonstrates the future trends concerned with Learning Petri nets.

2. The learning Petri net model

The Learning Petri net (LPN) model is constructed based on high-level time Petri net (HLTPN). The definition of HLTPN is given firstly.

2.1. Definition of HLTPN

HLTPN is one of expanded Petri nets.

Definition 1: HLTPN has a 5-tuple structure,HLTPN= (NG, C, W, DT, M0) [9], where

  1. NG= (P, Tr, F) is called “net graph” with Pwhich called “Places”.P is a finite set of nodes.ID:PN is a function marking P, N = (1,2,…) is the set of natural number. p1, p2, , pnrepresents the elements of P and n is the cardinality of set P;

Tris a finite set of nodes, called “Transitions”, which disjoints from P, P◠Tr=∅; ID:TrN is a function marking Tr. tr1, tr2, …, trmrepresents the elements of Tr, m is the cardinality of set Tr;

F(P×Tr)∪(Tr×P)is a finite set of directional arcs, known as the flow relation;
  1. C is a finite and non-empty color set for describing different type of data;

  2. W: F C is a weight function on F. If F(P×Tr), the weight function W is Winthat decides which colored Token can go through the arc and enable T fire. This color tokens will be consumed when transition is fired. If F(Tr×P), the weight function W is Woutthat decides whichcolored Token will be generated by T and be input to P.

  3. DT: TrR is a delay time function of a transition which has a Time delay for an enable transition fired or the fire of a transition lasting time.

  4. M0: PUp∈P μC(p)such that ∀ pP, M0(p) ∈ μC(p) is the initial marking function which associates a multi-set of tokens of correct type with each place.

2.2. Definition of LPN

In HLTPN, the weight functions of input and output arc for a transition decide the input and output token of a transition. These weight functions express the input-output mapping of transitions. If these weight functions are able to be updated according to the change of system, modeling ability of Petri net will be expanded. The delay time of HLTPN expresses the pre-state lasting time. If the delay time is able to be learnt while system is running, representing ability of Petri net will be enhanced. RL is a learning method interacting with a complex, uncertain environment to achieve an optimal policy for the selection of actions of the learner. RL suits to update dynamic system parameters through interaction with environment [18]. Hence, we consider using the RL to update the weight function and transition’s delay time of Petri net for constructing the LPN. In another word, LPN is an expanded HLTPN, in which some transition’s input arc weight function and transition delay time have a value item which records the reward from the environment.

Definition 2: LPN has a 3-tuple structure, LPN= (HLTPN, VW, VT), where

  1. HLTPN= (NG, C, W, DT, M0) is a High-Level Time Petri Net and NG= (P, Tr, F).

  2. VW (value of weight function): WinR, is a function marking on Win. An arc F(P×Tr) has a set of weight function Win and each Win has a reward value item VW ∈real number.

  3. VT (value of delay time): DTR, is a function marking on DT. A transition has a set of DT and each DT has a reward value item VT ∈real number.

Figure 1.

An example of LPN model

An example ofLPNmodel is shown in Figure 1 Using LPN, a mapping of input-output tokens is gotten. For example, in Figure 1,colored tokens Cij(i=1;j=1,2, …, n) are input toP1 by Trinput. There are n weight functions W(<C1j>, VWC1j,1,j) on a same arc F1,j. it is according to the value VWCij,i,jthat token C1j obeys what weight functions inW(<Cij>, VWCij,i,j)to fire a transition. After token C1j passed through arc Fi,j (i=1;j=1,2, …, n), one of Tri,j(i=1; j=1,2, …, n) fires and generates Tokens Cij(i=2; j=1,2, …, n)in P2. After P2 has color Token Cij(i=2; j=1,2, …, n),Tri,j(i=2; j=1,2, …, n) fires and different colored Token Cij(i=3; j=1,2, …, n)is generated. Then, a mapping of C1jC3j is gotten. At the same time, a reward will be gotten from environment according to whether it accords with system rulethat C3j generated by C1j. These rewards are propagated to every VWCij,i,j and adjust the VWCij,i,j.After training, the LPN is able to express a correct mapping of input-output tokens.

Using LPN to model a dynamic system, the system state is modeled as Petri net marking which is marked for a set of colored token in all places of Petri net, and the change of the system state (i.e. the system action) is modeled as fired of transitions. Some parameters of system can be expressed as token number and color, arc weight function, transition delay time, and so on. For example, different system signals are expressed as different colored of token. When the system is modeled, some parameters are unknown or uncertain. So, these parameters are set randomly. When system runs, the system parameters are gotten gradually and appropriately through system acting with environment and the effect of RL.

2.3. Learning algorithm for LPN

In LPN, there are two kinds of parameters. One is discrete parameter −− the arc’s weight function which describes the input and output colored tokens for transition. The other is continuous parameter −− the delay time for the transition firing. Now, we will discuss two kinds of parameters which are learnt using RL.

2.3.1. Discrete parameter learning

In LPN, RL is used to adjust VW and VT through interacting with environment. RL could learn the optimal policy of the dynamic system through environment state observation and improvement of its behavior through trial and error with the environment. RL agent senses the environment and takes actions. It receives numeric award and punishments from some reward function. The agent learns to choose actions to maximize a long term sum or average of the future reward it will receive.

The arc weight function learning algorithm is based on Q-learning – a kind of RL[18]. In arc weight function learning algorithm, VWCij,i,j is randomly set firstly. So, the weight function on the arc is arbitrary. When the system runs, formula (1) is used to update VWCij,i,j.

VWCij,i,j=VWCij,i,jj+α[r+γ(VWci+1j,i+1,j¯)VWCij,i,j]E1
(1)

where,

  1. áis the step-size,is a discount rate.

  2. ris reward which W(<Cij>, VWCij,i,j) gets when Tri,j isfired by <Cij>. Here, because environment gives system reward at only last step, so a feedback learning method is used. If W(<Cij>, VWCij,i,j) through Tri,j generates Token <Ci+1,j> and W(<Ci+1j>, VWCi+1j,i+1,j) through Tri+1,j generates Token <Ci+2,j>, VWCi+1j,i+1,j gets an update value, and this value is feedback as W(<Cij>, VWCij,i,j) next time reward r.

  3. (VWci+1j,i+1,j¯)WCi+1jVWCi+1j,i+1,j
(VWci+1j,i+1,j¯)t=γ(VWci+1j,i+1,j¯)t1+rtE2

where t is time for that <Ci+1j> is generated by W(<Cij>, VWCij,i,j).

When everyweight function of input arc of the transition has gotten the value, each transition has a value of its action. The policy of the action selection needs to be considered. The simplest action selection rule is to select the service with the highest estimated state-action value, i.e. the transition corresponding to the maximum VWCij,i,j. This action is called a greedy action. If a greedy action is selected, the learner (agent) exploits the current knowledge. If selecting one of the non-greedy actions instead, agent intends to explore to improve its policy. Exploitation is to do the right thing to maximize the expected reward on the one play; meanwhile exploration may produce the greater total reward in the long run. Here, a method using near-greedy selection rule calledε-greedy method is used in action selection; i.e., the action is randomly selected at a small probability ε and selected the action which has the biggest VWcij,i,j at probability 1−ε.Now, we show the algorithm of LPN which is listed in Table 1.

Algorithm 1. Weight function learning algorithm
Initialization: Set all VWijand r of all input arc’s weight function to zero.
Initialize the learning Petri net. i.e. make the Petri net state as M0.
Repeat i) and ii) until system becomes end state.
When a place gets a colored Token Cij, there is a choice that which arc weight function is obeyed if the functions include this Token. This choice is according to selection policy which isε greedy (εis set according to execution environment by user, usually 0<ε<<1).
A: Select the function which has the biggest VWcij,i,j at probability1-ε;
B: Select the function randomly at probability ε.
The transition which the function correlates fires and reward is observed. Adjust the weight function valueusing VWCij,i,j = VWCij,i,jj+α[r+- VWCij,i,j]. At the same time, α[r+- VWCij,i,j] is fed back to the weight function with generatedCij as its reward for next time.

Table 1.

Weight function learning algorithm in LPN

2.3.2. Continuous parameter learning

The delay time of transition is a continuous variable. So, the delay time learning is a problem of RL in continuous action spaces. Now, there are several methods of RL in continuous spaces: discretization method, function approximation method, and so on [4]. Here, discretization method and function approximation method are used in the delay time learning in LPN.

Discretization method

As shown in Figure 2 (i), the transition tr1 has a delay time t1. When p1 has a token <tokenn>, the system is at a state that p1 has a Token. This time transition tr1 is enabled. Becausetr1 has a delay timet1, tr1 doesn’t fire immediately. After passing time t1 andtr1 fires, the token in p1 is taken outand this state is terminated. Then, during the delay time of tr1,the state that p1has a token continues.

Because the delay time is a continuous variable, the different delay time is discretized for using RL to optimize the delay time. For example, tr1 in Figure 2(i) has an undefined delay time t1. Tr1is discretized into several different transitions which have different delay times (shown in Figure 2(ii)) and every delay time has a value item Q. After Tr1 fired at delay time t1i, it gets a reward r immediately or after its subsequence gets rewards. The value of Q is updated by formula (3).

γ(VWci+1j,i+1,j¯)E3

where, Q(P, Tr) is value of transition Tr at Petri net state P. Q(P',Tr' ) is value of transition T' atnext state P'of P. αisa step-size, γ is a discount rate.

Figure 2.

Transformation form from high-level Petri net to the learning model

After renewing of Q, the optimal delay time will be selected. In Figure 2 (ii), when tr11,…,tr1n get value Q11,…,Q1n,respectively, the transition is selected by the soft-max method according to a probability of Gibbs distribution.

γ(VWci+1j,i+1,j¯)E4

where, Pr{tt=t|pt=p} is a probability selecting of transition t at state p, â is a positive inverse temperature constant and A is a set of available transitions.

Now, we found the learning algorithm of delay time of LPN using the discretization method. And it is listed in Table 2.

Transition’s delay time learning algorithm 1 (Discretization method):
Initialization: discretize the delay time and set Q(p,t) of every transition’s delay time to zero.
Initialize Petri net, i.e. make the Petri net state as P1.
Repeat(i) and (ii) until system becomes end state.
Select a transition using formula (4).
After transition fired and reward is observed, value of Q(p,t) is adjusted using formula (3).
Step 3. Repeat Step2 until t is optimal as required.

Table 2.

Delay time learning algorithm using the discretization method

Function approximation method

First, the transition delay time is selected randomly and executed. The value of the delay time is obtained using formula (3). When the system is executed m times, the data (ti, Qi(p,ti)) (i = 1, 2, …, m) is yielded.The relation of value of delay time Q and delay time t is supposed as Q = F(t). Using the least squares method, F(t) will be obtained as follows.It is supposed that F is a function class which is constituted by a polynomial. And it is supposed that formula (5) hold.

Q(P,Tr)Q(P,Tr)+α[r+ γQ(P',Tr')Q(P,Tr)]E5

The data (ti, Qi(p,ti)) are substituted in formula (5). Then:

Pr{tt=t|pt=p} =eβQ(p,t)bAeβQ(p,b)E6

Here, the degree m of data (ti, Qi(p,ti)) is not less than data number n of formula (5). According to the least squares method, we have (2.7).

f(t) =k=0naktkFE7

In fact, (7) is a problem which evaluates the minimum solution of function (8).

f(ti) =k=0naktik(i= 1, 2, ,m;mn)E8

So, function (9), (10) are gotten from (8).

||δ||2=i=1mδi2=i=1m[k=0naktikQi]2minE9
||δ||2=i=1m[k=0naktikQi]2E10

Solution of Equation (10) a0, a1,…, ancan be deduced and Q= f(t) is attained. The solution t*opt of Q= f(t) which makes maximum Q is the expected optimal delay time.

||δ||2aj=2i=1mk=0n(aktikQi)tij=0  (j=0, 1, ,n) E11

The multi-solution of (11) t = topt(opt = 1, 2, …, n-1) is checked by function (5) and a t*opttoptwhich makes f(t*opt)= max f(topt) (opt= 1, 2, …,n-1)is the expected optimal delay time. t*optis used as delay time and the system is executed and new Q(p, t*opt)is gotten. This (t*opt,Q(p, t*opt)) is used as the new and the least squares method can be used again to acquire more precise delay time.

After the values of actions are gotten, the soft-max method is selected as the actions selection policy.And then, we found the learning algorithm of delay time of Learning Petri net using the function approximation method. And it is listed in Table 3.

Transition’s delay time learning algorithm 2 ( Function approximation method):
Step 1. Initialization: Set Q(p,t) of every transition’s delay time to zero.
Step 2. Initialize Petri net, i.e. make the Petri net state as P1.
Repeat(i) and (ii) until system becomes end state.
Randomly select the transition delay time t.
After transition fires and reward is observed, the value of Q(p, t)is adjusted using formula (3).
Step 3. RepeatStep 2 until adequacy data are gotten. Then, evaluate the optimal t using the function approximation method.

Table 3.

Delay time learning algorithm using the function approximation method

3. Applying LPN to robotic system control

3.1. Application for discrete event dynamic robotic system control

A discrete event dynamic system is a discrete-state, event-driven system in which the state evolution depends entirely on the occurrence of asynchronous discrete events over time [2]. Petri nets have been used to model various kinds of dynamic event-driven systems like computers networks, communication systems, and so on. In this Section, it is used to model Sony AIBO learning control system for the purpose of certification of the effectiveness of the proposed LPN.

AIBO voice command recognition system

AIBO (Artificial Intelligence roBOt) is a type of robotic pets designed and manufactured by Sony Co., Inc. AIBO is able to execute different actions, such as go ahead, move back, sit down, stand up and cry, and so on. And it can "listens" voice via microphone. A command and control system will be constructed for making AIBO understand several human voice commands by Japanese and English and take corresponding action. The simulation system is developed on Sony AIBO’s OPEN-R (Open Architecture for Entertainment Robot) [19]. The architecture of the simulation system is showed in Figure 3. Because there are English and Japanese voice commands for same AIBO action, the partnerships of voice and action are established in part (4). The lasted time of an AIBO action is learning in part (5). After an AIBO action finished, the rewards for correctness of action and action lasted time are given by the touch of different AIBO’s sensors.

Figure 3.

System architecture of voice command recognition

LPN model for AIBO voice command recognition system

In the LPN model for AIBO voice command recognition system, AIBO action change, action time are modeled as transition, transition delay, respectively. The human voice command is modeled by the different color Token. The LPN model is showed in Figure4. The meaning of every transition is listed below:Tr input changes voice signal as colored Token which describe the voice characteristic.Tr11, Tr12and Tr13can analyzethe voice signal. Tr1generates 35 different Token VL1….VL35 according to the voice length. Tr2 generates 8 different Token E21…E28 according to the front twenty voice sample energy characteristic. Tr3 generates 8 different Token E41…E48according to the front forty voice sample energy characteristic [8]. These three types of the token are compounded into a compound Token <VLl>+<VE2m>+ <VE4n> in p2[12].

Tr2jgenerates the different voice Token. The input arc’s weight function is ((<VLl>+<VE2m>+ <VE4n>), VWVlmn,2j) and the output arc’s weight function is different voice Token. And voice Token will generate different action Token through Tr3j.When Pr4Pr8 has Token, AIBO’s action will last. Tr4j takes Token out from p4p8, and makes corresponding AIBO action terminates. Tr4j has a delay time DT4i, and every DT4i has a value VT4i. Transition adopts which delay time DT4i according to VT4i.

Results of simulation

When the system begins running, it can’t recognize the voice commands. A voice command comes and it is changed into a compound Token in p2. This compound Token will randomly generate a voice Token and puts into p3. This voice Token randomly arouses an action Token. A reward for action correctness is gotten, then, VW and VT are updated. For example, a compound colored Token (<VLl>+ <VE2m> + <VE4n>) fired Tr21and colored Token VC1 is put into p3. VC1 firesT32and AIBO acts "go". A reward is gotten according to correctness of action. VWVC1,32 is updated by this reward and VWVC1,32 updated value is fed back to p2 as next time reward value of (<VLl>+ <VE2m> + <VE4n>) fired Tr21. After an action finished, a reward for correctness of action time is gotten and VT is updated.

Figure 4.

LPN model of voice command recognition

Figure 5.

Relation between training times and recognition probability

Figure 5 shows the relation between training times and voice command recognition probability. Probability 1 shows the successful probability of recently 20 times training. Probability 2 shows the successful probability of total training times. From the result of simulation, we confirmed that LPN is correct and effective using the AIBO voice command control system.

3.2. Application for continuous parameter optimization

The proposed system is applied to guide dog robot system which uses RFID (Radio-frequency identification) to construct experiment environment. The RFID is used as navigation equipment for robot motion. The performance of the proposed system is evaluated through computer simulation and real robot experiment.

RFID environment construction

RFID tagsare used to construct a blind road which showed in Figure 6. There are forthright roads, corners and traffic light signal areas. The forthright roads have two group tags which have two lines RFID tags. Every tag is stored with the information about the road. The guide dog robot moves, turns or stops on the road according to the information of tags. For example, if the guide dog robot reads corner RFID tag, then it will turn on the corner. If the guide dog robot reads either outer or inner side RFID tags, it implies that the robot will deviate from the path and robot motion direction needs adjusting. If the guide dog robot reads traffic control RFID tags, then it will stop or run unceasingly according tothe traffic light signal which is dynamically written to RFID.

Figure 6.

The real experimental environment

LPN model for the guide dog

The extended LPN control model for guide dog robot system is presented in Figure 7. The meaning of place and transition in Figure 7 is listed below:

Figure 7.

The LPN model for the guide dog robot

When the system begins running, it firstly reads RFID environment and gets the information, Token puts into P2. These Tokens fire one of transition from Tr2 to Tr6according to weight function on P2to Tr2,…,Tr6. Then, the guide dog enters stop, running, turning corner, left adjustingor right adjusting states. Here, at P3, P4, P5states, the guide dog turns at a specific speed. The delay time of Tr7-Tr9 decide the correction of guide dog adjustingits motion direction.

Reward getting from environment

When Tr7, Tr8or Tr9 fires, it will get reward r as formula (12-b) when the guide dog doesn’t get Token <Left> and <Right> until getting Token <corner> i.e. the robot runs according correct direction until arriving corner. It will get reward r as formula (12-a), where t is time from transition fire to get Token <Left> and <Right>. On the contrary, it will get punishment -1 as (12-c) if robot runs out the road.

i=1m(k=0ntij+k)ak=i=1mtijQi (j= 0, 1, ,n). E12
Computer simulation and real robot experiment

When robot reads the <Left>, <Right> and <corner> information, it must adjust the direction of the motion. The amount of adjusting is decided by the continuing time of the robot at the state of P3, P4and P5. So, the delay time of Tr7, Tr8 and Tr9 need to learn.

Figure 8.

Direction adjustment of the guide dog robot motion

Before the simulation, some robot motion parameter symbols are given as:

v velocity of the robot

ω angular velocity of the robot

tpre continuous time of the former state

t adjusting time

tpost last time of the state after adjusting

v, ω, tpre, tpost can be measured by system when the robot is running. The delay time of Tr7, Tr8 and Tr9, i.e. the robot motion adjusting time, is simulated in two cases.

  1. As shown in Figure8(i), when the robot is running on the forthright road and meets inside RFID line, its deviation angleθ is:

f(t)t=0E13

where d1 and l1 are width of area between two inside lines and moving distance between two times reading of the RFID,respectively (See Figure8).

Robot’s adjusting time (transition delay time) is t.

If ωt -θ≥0, then

r={1/et11.(12a)(12b)(12c)E14
else
θ=arcsin(d1/l1) =arcsin(d1/(tprev)).E15

Here, tpost is used to calculate reward r using formula (12). In the same way, the reward r can be calculated when the robot meets outside RFID line.

When the robot is running on the forthright road and meets the outside RFID line, the deviation angle θ is

tpost=d1vsin(ωtθ),E16

Robot’s adjusting time (transition delay time) is t.

If ωt -θ≥0, then

tpost=d2vsin(ωtθ).E17

else the robot will runs out the road. And the reward r is calculated using formula (12).

  1. As shown in Figure8(ii), when the robot is running at the corner, it must adjustθ=90°. Ifθ≠90°, the robot will read <Left>, <Right> after it turns corner. Now, the case which the robot will read inner line <Left>, <Right> will be considered. If robot’s adjusting time is t. If ωt -θ≥0, then

θ=arcsin(d2/(vtpre)),E18
else
tpost=d2vsin(ωtθ),E19

Same to case (1), tpost is used to calculate reward r using formula (12). In the same way, the reward r can calculate when the robot meets outside RFID line.The calculation of reward, which is calculated from t, for other cases of direction adjustment of the robot is considered as the above two cases.

In this simulation, the value of the delay time has only a maximum at optimal delay time point. The graph of relation for the delay time and its value is parabola. So, when transition’s delay time learning by function approximation method which states in section 2.2.3, the relation of the delay time and its value is assumed as:

tpost=d12vsin(ωtθ),E20

Computer simulations of Transition’s delay time learning algorithms were executed in the all cases of the robot direction adjusting. In the simulation of algorithm of discretization, the positive inverse temperature constant β is set as 10.0. After the delay time of different cases was learnt, it is recorded in a delay time table. Then, the real robot experiment was carried out using the delay time table which was obtainedby simulation process.

Result of simulation and experiment

The simulation result of transition’s delay time learning algorithm in two cases is shown in Figure 9.

Figure 9.

Result of simulation for the guide dog robot

The simulation result of θ=5° for the robot moving adjustment on forthright road is shown in Figure 9 (i). The simulation result of robot moving adjustment at the corner is shown in Figure 9(ii). From the result, it is found that the function approximation method can quickly approach optimal delay time than the discretization method, but the discretization method can approach more near optimal delay time through long time learning.

4. Construction of the learning fuzzy Petri net model

Petri net (PN) has ability to represent and analyze concurrency and synchronization phenomena in an easy way. PN approach can also be easily combined with other techniques and theories such as object-oriented programming, fuzzy theory, neural networks, etc. These modified PNs are widely used in the fields of manufacturing, robotics, knowledge based systems, process control, as well as other kinds of engineering applications [15]. Fuzzy Petri net (FPN), which combines PN and fuzzy theory, has been used for knowledge representation and reasoning in the presence of inexact data and knowledge based systems. But traditionalFPN lacks of learning mechanism, it is the main weakness while modeling uncertain knowledge systems [25]. In this section, we propose a new learning model tool — learning fuzzy Petri net (LFPN) [7]. Contrasting with the existing FPN, there are three extensions in the new model: 1) the place can possess different tokens which represent different propositions; 2) these propositions have different degrees of truth toward different transitions; 3) the truth degree of proposition can be learned through the arc’s weight function adjusting. The LFPN model obtains the capability of fuzzy production rules learning through truth degree updating. The artificial neural network is gotten learning ability through weight adjusting. The LFPN learning algorithm which introduces network learning method into Petri net update is proposed and the convergence of algorithm is analyzed.

4.1. The learning fuzzy Petri net model

Petri net is a directed, weighted, bipartite graph consisting of two kinds of nodes, called places and transitions, where arcs are either from a place to a transition or from a transition to a place. Tokens exist at different places. The use of the standard Petri net is inappropriate in situations where systems are difficult to be described precisely. Consequently, fuzzy Petri net is designed to deal with these situations where transitions, places, tokens or arcs are fuzzified.

The definition of fuzzy Petri net

A fuzzy place associates with a predicate or property. A token in the fuzzy place is characterized by a predicate or property belongs to the place, and this predicate or property has a level of belonging to the place. In this way, we may get a fuzzy proposition or conclusion, for example, speed is low. A fuzzy transition may correspond to an if-then fuzzy production rule for instance and is realized by truth values such as fuzzy inference algorithms [11, 20, 26].

Definition 1 FPN is a8-tuple, given byFPN=<P,Tr,F, D,I,O,α, β>

where:

P = {p1, p2, …, pn} isafinite set of places;

Tr = {tr1, tr2, …, trm} is a finite set of transitions;

F tpost=d22vsin(ωtθ)(P×Tr)∪(Tr×P)is a finite set of directional arcs;

D = {d1, d2, …, dn} is a finite set of propositions, where proposition di corresponds to place pi; PTrD = ; cardinality of (P) = cardinality of (D);

I: trP∞ is the input function, representing a mapping from transitions to bags of (their input) places, noting as *tr;

O: trP∞ is the output function, representing a mapping from transitions to bags of (their output) places, noting as tr*;

α: P → [0, 1] and β: PD. A token value in place piP is denoted by α(pi)∈ [0, 1]. If α(pi)=yi, yi∈[0, 1] and β(pi)= di,, then this states that the degree of truth of proposition di is yi.

A transition trkis enabled if for all piI(trk), α(pi)≥th, where th is a threshold value in the unit interval. If this transition is fired, then tokens are moved from their input place and tokens are deposited to each of its output places. The truth values of the output tokens are yiuk, where uk is the confidence level value of trk. FPN has capability of modeling fuzzy production rules. For example, the fuzzy production rule (21) can be modeled as shown in Figure 10.

Q=a2t2+a1t+a0.E21

Figure 10.

A fuzzy Petri net model (FPN)

The definition of LFPN

In a FPN, a token in a place represents a proposition and a proposition has a degree of truth. Now, three aspects of extension are done at the FPN and learning fuzzy Petri net (LFPN) is constructed. First, a place may have different tokens (Tokensare distinguished with numbers or colors) and the different tokens represent different propositions, i.e. a place has a set of propositions. Second, a place has a special token, i.e. there is a specified proposition. This proposition may have different degrees of truth toward different transitions tr which regard this place as input place *tr. Third, the weight of each arc is adjustable and used to record transition’s input and output information.

Definition 3 LFPN is a10-tuple, given byLFPN=<P,Tr,F, D,I,O,Th,W, α, β> (A LFPN model is shown in Figure 11).

where: Tr, F,I, Oare same with definition of FPN.

P={ p1, p2,…, pi,…, pn,…, p′1, p′2,…, p′i,…, p′r} is a finite set of places, where pi is input place and p′i is output places.

D = {d11, …, d1N; d21,…, d2N; …, dij, …; dn1,…, dnN; d′11, …, d′1N; d′21,…, d′2N; …, d′ij, …; d′r1,…, d′rN} is a finite set of propositions, where proposition dijis j-thproposition forinput place piand proposition d′ijis j-thproposition foroutput place p′i.

W ={w11, w12, …, w1k, …, w1m; …; wi1, wi2, …, wik, …, wim; …;wn1, wn2, …, wnm; w′11, w′12, …, w′1r; …; w′k1, w′k2, …, w′kj,…, w′kr; …;w′m1, w′m2, …, w′mr} is the set of weights on the arcs, where wikis a weight from i-th input placeto k-th transition and w′kj is a weight from k-th transition to j-th output place.

W ={w11, w12, …, w1k, …, w1m; …; wi1, wi2, …, wik, …, wim; …;wn1, wn2, …, wnm; w′11, w′12, …, w′1r; …; w′k1, w′k2, …, w′kj,…, w′kr; …;w′m1, w′m2, …, w′mr} is the set of weights on the arcs, where wikis a weight from i-th input placeto k-th transition and w′kj is a weight from k-th transition to j-th output place.

α(dij, trk)→ [0, 1] and β: P D. When pi∈P has a specialtokenij and β(tokenij, pi)=dij, the degree of truth of proposition dij in place pitoward to transition trk is denoted by α(dij, trk ) ∈ [0, 1]. When trk fires, the probability of proposition dij in pi is α(dij, trk ).

Figure 11.

The model of learning fuzzy Petri net (LFPN)

α(dij, trk)→ [0, 1] and β: P D. When pi∈P has a specialtokenij and β(tokenij, pi)=dij, the degree of truth of proposition dij in place pitoward to transition trk is denoted by α(dij, trk ) ∈ [0, 1]. When trk fires, the probability of proposition dij in pi is α(dij, trk ).

Figure 12.

A LFPN model with one transition

Th = {th1, th2, …, thk, …, thm}representsa set of threshold values in the interval [0, 1] associated with transitions (tr1, tr2, …, trk, …, trm), respectively; If all piI(trk) and α(dij, trk )≥thk, trk is enable.

As showed in Figure 12, when pi has a tokenij, there is propositiondij in pi. This proposition dij has different truth to tr1, tr2, …, trk, …, trm. When a transition trk fired, tokens are put into p′1, …, p′r according to weight w′k1, …, w′kr and each of p′1, …, p′r gets a proposition.

Figure 11 shows a LFPN which has n-input places, m-transitions and r-output places. To explain the truth computing, transition fire rule, token transfer rule and fuzzy production rules expression more clearly, a transition and its relation arcs, places are drawn-out from Figure 11 and shown in Figure 12.

Truth computing As shown in Figure 12, wik is the perfectvalue for tokenij when trk fires. When a set of tokens= (token1j, token2j, …, tokenij, …, tokennj) are input to all places of *trk,β(token1j, p1)= d1j,…, β(tokennj, pn)= dnj. α(dij, trk ) is computed using the degree of similarity between tokenij and wik and calculation formula is shown in formula (22).

E22

According to LFPN modelsfor different systems, the token and weight value may have different data types. There are different methods for computing α(dij, trk ) according to data type. If value types of token and weight are real number, α(dij, trk ) is computed as formula (2). In Section 4, α(dij, trk ) will be discussed for a LFPN model which has the textual type token and weight.

Transition fire rule As shown in Figure 12, when a set of tokens=(token1j, token2j,…, tokennj) are input to all places of *trk, and β(token1j, p1)= d1j,…, β(tokennj, pn)= dnj. If all α(dij, trk ) (i=1, 2, …, n) ≥thkis held, trk is enabled. Maybe, several transitions are enabled at same time. If formula (23) is held, trk is fired.

IFdiTHENdj(with Certainty Factor (CF)uk)E23
(23)

Token transfer rule As shown in Figure 12, after trk fired, token will be taken out from p1~pn. The token take rule is:

If tokenijwik is held, tokenij in pi will be taken out.

If tokenijwik is held, token which equates tokenijwik will be left in pi.

Thus, after a transition trk fired, maybe theenabletransitions still exist in LFPN. An enable transition will be selected and fired according to formula (23) until there isn’t any enable transition.

After trk fired, the token according w′ki will be put into p′i. For example, if the weight function of arc trk to p′i is w′ki, then token which equates w′ki will be put into p′i.

Fuzzy production rules expression A LFPN is capable of modeling for fuzzy production rules just as a FPN. For example, as a case which states in Transition fire rule and Token transfer rule, when trk is fired, the below production rule is expressed:

IF d1j AND d2j AND … AND dnj THEN d′1k AND d′2k AND … AND d′rk

α(dij,trk)=1|wiktokenij|max(|wik|,|tokenij|)E24
The mathematical model of LFPN

In this section, the mathematical model of LFPN will be elaborated. Firstly, some conceptions are defined. When a tokenij is input to a place pi, it is defined event pij occurs, i.e. the proposition dijis generated and probability of event pijis Pr(pij). The fired trkis defined as event trk and probability of event trk occurrence is Pr(trk). Secondly, we assume that each transition tr1, tr2, …, trk, …, trm has the same fire probability in whole event space, then

α(d1j,trk)α(d2j,trk)...α(dnj,trk)=max(α(d1j,trh)α(d2j,trh)...α(dnj,trh)1hm)E25

And when event trk occurs, the conditionalprobability of pij occurrence is defined asPr(pij |trk), i.e. á(dij, trk ) which is the probability of proposition dijgeneration when trkfires.

When p1,p2, …, pn have token1j, token2jtokennj and eventsp1j, p2j, …, pnjoccur. Then, Pr(trk| p1j, p2j, …, pnj) is:

(CF=α(d1i,trk )α(d2i,trk )α(dni,trk ))E26

When events p1j, p2j, …, pnj occurred, there is one of transitionstr1, tr2, …, trk, …, trm which will be fired, therefore

Pr(trk)=1mE27

From (25), (26)and (27), (28′) is gotten by the formula of full probability and Bayesian formula.

Pr(trk|p1j,p2j,...,pnj)=Pr(p1j,p2j,...,pnj|trk)Pr(trk)h=1mPr(trh)Pr(p1jp2j,...,pnj)E28

The transformation from (28′) to (28) is according to definition of α(dij, trk). As shown in Figure 11, when p1,p2, …, pn have token1j, token2jtokennj, the occurring probability of transition tr1, …, trk, …, trm are α(d1j, tr1) •α(d2j, tr1) •…•α(dnj, tr1)/m, …, α(d1j, trk) •α(d2j, trk) •…•α(dnj, trk)/m, …, α(d1j, trm) •α(d2j, trm) •…•α(dnj, trm)/m. Thus, the transition trk, which has maximum of α(d1j, trk) •α(d2j, trk) •…•α(dnj, trk), is selected and fired according to formula (23).

4.2. Learning algorithm for learning fuzzy Petri net

Learning algorithm

The learning fuzzy Petri net (LFPN) can be trained and made it learn fuzzy production rules. When a set of data input LFPN, a set of propositions are produced in each input place. For example, when token vectors (token1j, token2j, …, tokennj) (j=1, 2, …, N) input to p1~pn, propositions d1j, d2j, …, dnj (j=1, 2, …, N) are produced. To train a fuzzy production rule which is IF d1j AND d2j AND … AND dnj THEN d′1kAND d′2kAND … AND d′nk, there are two tasks:

  1. α(d1j, trk )•α(d2j, trk )•…•α(dnj, trk ) (k∈{1,2,…m}) need to be updated to hold formula (23);

  2. 2) The output weight function of trk need to be updated for putting correct token to p′1~p′r. Then, β(p′1) = d′1k, β(p′2) = d′2k, …, β(p′r) = d′rk.

To accomplish these two tasks, the weightsw1k, w2k, …, wnkand w′k1, w′k2, …, w′krare modified by a learning algorithm of LFPN. Firstly, we define the training data set as {(X1, Y1), (X2, Y2), …, (XN, YN)}, where X is input token vector, Y is output token vector and Xj, Yj is defined as Xj=( x1j, x2j, …, xnj)T, Yj=( y1j, y2j, …,yrj)T,respectively. Thus,

X=(X1, X2,…, Xj, …, XN,),Y=( Y1, Y2, …, Yj, …, YN), i.e.

h=1mPr(trh)Pr(p1j,p2j,...,pnj)=1

Secondly, the weight Wk=(w1k, w2k, …, wnk)T is the weight on arcs from *trk to trk and Wk=( w′k1, w′k2, …, w′kr)T is the weight on arcs from trk to trk*. W1, …, Wk, …, Wm and W′1, …, W′k, …, W′m are the input and output arcs weight for tr1, …, trk, …, trm. Thus,

W=(W1, W2,…, Wk, …, Wm), W′=(W′1, W′2,…, W′k, …, W′m), i.e.

Pr(trk|p1j,p2j,...,pnj)=1mPr(p1j,p2j,...,pnj|trk)=1mPr(p1j|trk)×Pr(p2j|trk)×...×Pr(pnj|trk)=1mα(d1j,trk)α(d2j,trk)...α(dnj,trk)

Lastly, in the learning algorithm, when trk is fired, the truth of d′1j, d′2j, …, d′rjto trk are defined as α(d′1j, trk )=1−|y1jw′k1|/max (|w′k1|, |y1j|), α(d′2j, trk )=1−|y2jw′k2|/ max (|w′k2|, |y2j|), …, α(d′rj, trk )=1−|yrjw′kr|/ max(|w′kr|, |yrj|) according to definition 3.The learning algorithm of learning fuzzy Petri net is shown in Table 4.

Learning Algorithm of LFPN:
Step 1.Wand W′ are selected randomly.
Step 2.For every training data set (Xj, Yj)(j=1, 2, …, N), subject propositions d1j, d2j, …, dnj in p1~pn and propositions d′1j, d′2j, …, d′rjin p′1~p′r are produced. Then do step 3 to step 7;
Step 3.For i=1 to n
For h=1to m do
Compute α(dij, trh ) according to formula (2);
Step 4.Compute maximum truth of transition
4.1 Max=α(d1j, tr1 ) •α(d2j, tr1 ) •…• α(dnj, tr1 ); k=1;
4.2 For h=1 to m do
If α(d1j, trh ) •α(d2j, trh ) •…• α(dnj, trh )"/>Max
Then { Max=α(d1j, trh ) •α(d2j, trh ) •…• α(dnj, trh );
k=h; }
Step 5. Firetrk;
Step 6.Maked1j, d2j, …, dnj have bigger truth to trk,
Wk(new) = Wk (old) + γ(XjWk (old)) (29)
(Wk (new) is the vector Wk after update and Wk (old) is the vector Wk before updated. γ∈ QUOTE QUOTE (0,1) is learning rate.)
Step 7.Maked′1j, d′2j, …, d′rj have bigger truth to trk,
W′k(new) = W′k(old) +γ(YjW′k(old) )(30)
(W′k(new) is the vector W′k after update and W′k(old) is the vector W′k before updated. γ∈ (0,1) is learning rate.)
Step 8. Repeat step 2-7, until the truth of α(d1j, trk ), α(d2j, trk ), …, α(dnj, trk ) meet the requirement.

Table 4.

Learning algorithm of learning fuzzy Petri net

X=[x11x12...x1j...x1Nx21x22...x2j...x2N::::::::::::xn1xn2...xnj...xnN]Y=[y11y12...y1j...y1Ny21y22...y2j...y2N::::::::::::yr1yr2...yrj...yrN]E29
[w11w12...w1k...w1mw21w22...w2k...w2m::::::::::::wn1wn2...wnk...wnm]E30

Some details in the algorithm need to be elaborated further.

  1. About the net construction: The number of input and output places can be easily set according to a real problem. It is difficult to decide anumber of transitions when the net is initialized. When LFPN is used to solve a special issue, the number of transitions is initially set according to practical situation experientially. Then, transitions can be dynamically appended and deleted during the training. If an input data Xj has a maximal truth to trk but one or several α(dij, trk)(1≤in) are less than thk (threshold of trk), transition trk cannot fire according to definition 3. Thus, data Xjcannot fire any existed transition. This case means that W1, W2, …, Wk, …, Wm cannot describe the vector characteristic of Xj. Then, a new transition trm+1 and the arcs which connect trm+1 with input and output place are constructed. Xjcan be set as weight Wm+1 directly. Second, during a training episode, if there is no data in X1, X2, …, XNthat can fire transition trd, it means that Wd cannot describe the vector characteristic of any data X1, X2, …, XN. Then, the transition trd and the arcs which connect trd with input and output place will be deleted.

  2. About WandW′ initialization: for promoting training efficiency at the first stage of training, W and W′ are set randomly in [Xmin, Xmax], [Ymin, Ymax] (Xmin is a vector which every components is minimal component of vector set X1, X2, …, XN; Xmax is a vector which every components is maximal component of vector set X1, X2, …, XN; Ymin, Ymax are same meaning with Xmin, Xmax).

  3. Training stop condition of the learning algorithm: According to application case, th1, th2, …, thk, … thm are generally set a same value th. Whentraining begins, the threshold th is set low (for example 0.2), th increases as training time increasing. A threshold value thlast (for example 0.9) is set as training stop condition and algorithm is run until α(d1j, trk )> thlast, α(d2j, trk ) > thlastα(dnj, trk ) > thlast. From transition appending analysis, we understand that number of transitions will near to the number of training data if the threshold of transition sets near to 1. In this case, results will be obtained more correctly but the training time and LFPN running time will increase.

Analysis for convergence of LFPN learning algorithm

In this section, the convergence of the proposed algorithm will be analyzed. In step 6 of the LFPN learning algorithm, the formula (29) is used for making Wk (new) approach Xj than Wk (old) when Xj fired a transition trk. It is proved as follows.

Wk(new)=Wk(old)+γ(XjWk(old))

Formula (11′) is rewritten as a scalar type and the scalar type of (XjWk (old)) is used to divide both sides of formula (11′). We get formula (11).

Wk(new)=Wk(old)+γ(YjWk(old))
Wk(new)=Wk(old)+γ(XjWk(old))=Wk(old)+γXjγWk(old)XjWk(new)=Xj[Wk(old)+γ(XjWk(old))]=XjWk(old)γXj+γWk(old)=(1γ) (XjWk(old))E31

Hence, Wkwill converge to Xj after enough training times.

In LFPN learning algorithm, there may be a class of training data Xj which are able to fire same transition trk. In this case, Wkapproaches to a class of data Xj and converges to a point in the class of data Xj according to formula (31).

Now, we will discuss the point in the class of data Xj where Wkconverges to. Supposing,there are b1 data which are in X1, X2,…, Xj, …, XN and fire a certain transition trkat the first training episode. At the second training episode, there are b2 data which fire trk, and so on. If the total training times is ep and the total number of data which fire trk is t, t =(xijwkj(new)xijwkj(old))0in. According to the order of the data fired trk, these t data are rewritten as Xk1, Xk2, …, Xkt. The average of training data Xk1, Xk2, …, Xkt is noted as =((1−γ)⋅(xij−wkj(old))xij−wkj(old))0≤i≤n=1−γk. To record the updated process of Wk simply, the updated order of Wk is recorded as Wk1,Wk2….Wkt.

The learning rate γ (0<γ<1) will decrease according to training time increasing, and it approaches to 0 at last because every training data cannot effectWk too much in the last stage of training, else Wk will shake at the last stage of training. If learning rate γ is set as 1/(q+1) (q>0) when training begin, 1/(q+2), 1/(q+3), …, 1/(q+t) are set as learning rate γ when trk is fired at 2, 3, …, t time. Here, the initial values of Wkis set as Wk0=W(0)×1/q, every component of W(0)×1/q is a random value in [Xmin, Xmax]. According to formula (29), we get

i=1epbiE32

When the training time increases, the training data set Xk1, Xk2, …, Xkt can be looked as very large, i.e. t is large.

X¯E33

Generally, q is a small positive constant and t is large. Then,

Wk0=1qW(0)Wk1=Wk0+1q+1(Xk1Wk0)=1qW(0)1q+1×1qW(0)+1q+1Xk1=1q+1(W(0)+Xk1)Wk2=Wk1+1q+2(Xk2Wk1)=1q+1W(0)+1q+1Xk11q+1×1q+2W(0)1q+1×1q+2Xk1+1q+2Xk2=1q+2(W(0)+Xk1+Xk2)Wkt=Wk,t1+1q+t(XktWk,t1)=1q+t1W(0)1q+t×1q+t1W(0)+1q+t1Xk11q+t×1q+t1Xk1+...+1q+t1Xk,t11q+t×1q+t1Xk,t1+1q+tXkt=1q+t(W(0)+Xk1+...+Xk,t1+Xkt)E34

From formula (14) will be gotten:

limtWkt=limt1q+t(W(0)+Xk1+...+Xk,t1+Xkt)E35

In the same way, WklimtWktlimt1t(W(0)+Xk1+...+Xk,t1+Xkt)=limt1tW(0)+limt1t(Xk1+...+Xk,t1+Xkt)limt1t(Xk1+...+Xk,t1+Xkt)=Xk¯(k=1, 2, …, m) andW′kWkX¯k(k=1, 2, …, m) can be proved. Consequently, the learning algorithm of LFPN converges.

Now, we will analyze the convergence process and signification of convergence.

  1. Xk1, Xk2, …, Xkt fire a certain transition trk at training time. As the training time increase, there are almost same data which fire the transition trk in every training time. These data belong to a class k. We suppose that these data are Xk1, Xk2, …, Xks. When training begins, supposing, there is data Xuwhich does not belong to Xk1, Xk2, …, Xks but fires trk. But, when training times increase, Wk will approach to Xk1, Xk2, …, Xks and the probability which Xufires trk will decrease. Hence, this type data Xu is very small part of Xk1, Xk2, …, Xkt. Xulittle affects to Wk. On the other hand, when training begins, there is Xke which belongs to Xk1, Xk2, …, Xks but doesn’t fire transition trk. But, when training times increase, the probability which Xke fires trk increases, then,Xk1, Xk2, …, Xks can be approximately looked firing trkaccording tothe training. X¯kis denoted as the average of training data Xk1, Xk2, …, Xks.

  2. In the convergence demonstration, we use a special series of learning rate γ.Form the analysis in 1), Xk1, Xk2, …, Xks can be looked as a class data which fires one transition trk. The data series Xk1, Xk2, …, Xkt can be looked as iterations of Xk1, Xk2, …, Xks. Wk can converge to a point near Y¯kwith any damping learning rate series γ.

  3. After training, Wk=(w1k, w2k, …, wnk) comes near to the average of data which belong to class k, i.e.,WkX¯k=(X¯k1k,X¯k2k,…,x¯nk). When a data Xkj belong to class k comes, Xkj will have same vector characteristic with Xk1, Xk2, …, Xks, i.e. x1,kj, x2,kj, …, xn,kj are near to w1k, w2k, …, wnk. Then, each component xi, kj (1≤in) of this data Xkj will have bigger similarity to wik (1≤in) than i-th components of other weight W according to formula (2). Xkj will have biggest truth to trk according to formula (2). Thus, when data Xkj which belongs to class of Xk1, Xk2, …, Xks inputs to LFPN, it will fire trk correctly and product correct output.

5. Web service discovery based on learning fuzzy Petri net model

Web services are used for developing and integrating highly distributed and heterogeneous systems in various domains. They are described by Web Services Description Language (WSDL). Web services discovery is a key to dynamically locating desired Web services across the Internet [16]. It immediately raises an issue, i.e. to evaluate the accuracy of the mapping in a heterogeneous environment when user wants to invoke a service. There are two aspects which need to evaluate. One is functional evaluation. The service providing function should be completely matched with user’s request; another aspect is non-functional evaluation, i.e. Quality of Service (QoS) meets user’s requirement. UDDI (Universal Description, Discovery and Integration) is widely used as a kind of discovery approach for functional evaluation. But, as the number of published Web services increases, discovering proper services using the limited description provided by the UDDI standard becomes difficult [17]. And UDDI cannot provide the QoS information of service. To discover the most appropriate service, there are necessary to focus on developing feasible discovery mechanisms from different service description methods and service execution context. Segev proposed a service function selection method [21]. A two-step, context based semantic approach to the problem of matching and ranking Web services for possible service composition is elaborated. The two steps for service function selection are Context extraction and Evaluation for Proximity degree of Service. Cai proposed service performance selection method [3]. The authors used a novel Artificial Neural Network-based service selection algorithm according to the information of the cooperation between the devices and the context information. In this paper, we aim at analyzing different context of services and constructing a services discovery model based on the LFPN. Firstly, different service functional descriptions are used to evaluate service function and an appropriate service is selected. Secondly, context of QoS is used to predict QoS and a more efficient service is selected. Data of QoS is real number and LFPN learning algorithm is directly used. But service function description is literal. Therefore, a Learning Fuzzy Petri Net for service discovery model is proposed for keyword learning based on LFPN.

5.1. Web services discovery model based on LFPN

To map a service’s function accurately, free textual service description, WSDL description, Web service’s operation and port parameters which are drawn from WSDL are used as input data here. Because the input data type is keyword, the proposed LFPN cannot deal with this type of data. Consequently, a Learning Fuzzy Petri Net for Web Services Discovery model (LFPNSD) is proposed. LFPNSD is a 10-tuple, given by LFPNSD =<P,Tr,F, W, D,I, O, Th, α, β > (as shown in Figure 13.)

where: Tr, I, O, Th, β are same with definition of LFPN.

P= {Pinput}∪{Poutput}={P11, P12, P13}∪{P21, P22, P23, P24}

Fx¯(Pinput×Tr)∪(Tr×Poutput)

W=FKeywords+, where weight function on Pinput×Trare different keywords of service description and weight function on Tr×Poutput are different service invoking information.

D = {d11,a, d12,b, d13,c}∪{d21,e, d22,f, d23,g, d24,h } is a finite set of propositions, where proposition d11, a is that P11 has a service description tokens; proposition d12, b is that P12 has a free textual description tokens; proposition d13, c is that P13 has a service operation and port parameters tokens. And the propositions d21, e, d22, f, d23, g, d24, h are that P21, P22, P23, P24have different invoking information tokens of services.

Figure 13.

The learning fuzzy Petri net for Web service discovery (LFPNSD)

α(dij, trk )→ [0, 1]. α(dij, trk)=yi∈ [0, 1] is the degree of truth of proposition dij to trk. α(dij, trk) is computed by bellow rules: if input description has n keywords and the wik on arc Pi to trk has s same keywords, the degree of similarity between weight keywords and input description keywords is expressed as:

x¯E36

The fire rule of transition: if α(d11,a, trk) •α(d12,b, trk) •α(d13,c, trk) =max((α(d11,a, tri) •α(d12,b, tri) •α(d13,c, tri))1≤im) and all of α(d11,a, trk), α(d12,b, trk), α(d13,c, trk) are bigger than a threshold value th, then trk fires, the tokens in P11~P13 are taken out and tokens which according to wk,21, wk,22, wk,23,wk,24 are put into P21~P24.

As shown in Figure 13, service free textual description, WSDL description and operation and port information are used as input vector in the learning algorithm. And, service classification, WSDL address, all of service operation names and service SOAP messages are used as output vector. Because the training data type is the keyword, the learning algorithm of LFPN isdeveloped into a learning algorithm of LFPNSD. The learning algorithm of learning fuzzy Petri net for Web service discovery is shown in the table 5.

Learning Algorithm of LFPNSD:
Step 1. Make all weights on arcsbe ∅;
Step 2. For every service in training data set,
Repeat:
Get free textual description; Draw out WSDL description and operation and port name from WSDL;
Set service textual description, WSDL description, operation and port information as input vector;
Compare the input with the keywords on the weight of input arc:
If every keyword in weight is in the input data, then compute α(dij, trk) according to formula (16), else set α(dij, trk) =0.
If each of α(dij, tr1), α(dij, tr2), …, α(dij, trm-1) equates 0 and the weight of trm is ∅, then set α(dij, trm) =1.
If each of α(dij, tr1), α(dij, tr2), …, α(dij, trm-1) equates 0 and trm doesn’t exist, a new transition trm and the arcs which connect trm with input and output place are constituted, set weight of arcs to be ∅ and α(dij, trm) =1.
If α(d11,a, trk) •α(d12,b, trk) •α(d13,c, trk) =max((α(d11,a, tri) •α(d12,b, tri) •α(d13,c, tri)) 1≤i≤m), then trk fires.
If the trk fired, get a keyword in service description but not in the weight, and add it into the weight.
If training time is t and the weight is ∅, t keywords in service description are gotten and they are added into the weight.
If the trk fired, compare out training data (service classification, WSDL address, service operation and message) with the weight of wk,21, wk,22, wk,23, wk,24, and calculate and record the correct rate of output.
Update wk,21, wk,22, wk,23, wk,24 according to output of training data.
Step 3. Repeat step 2, until each α(d11,a, trk), α(d12,b, trk), α(d13,c, trk) meets the requirement value thk.

Table 5.

Learning algorithm of learning fuzzy Petri net for Web service discovery

Discussion:

  1. We discuss about the learning rate γ in the learning algorithm of LFPNSD. In the algorithm, the keyword is learned and added into weights one by one. Hereby,XjWk (new) =1 and XjW(old) equates the difference between the number of input data keywords and the number of keywords on arc weight. Because XjW(old) is not constant, the learning rate γ is different at each learning episode. For example, when input data has 10 keywords and arc weight has 6 keywords firstly, one keyword is learnt from input data and added into weight. In this case, the learning rate is 1/(10-6)=0.25.

  2. If keyword isn’t learning one by one, the keywords on W1, W2, …, Wk, …, Wm will do not balance at beginning stage of training. Then, the similar but different description services have unbalance probability to fire transition at beginning stage of training. This makes the similar but different description services improperly fire a transition which has more keywords on its weight. It makes training efficiency lower.

  3. In step 2.3 of algorithm, when each of α(dij, tr1), α(dij, tr2), …, α(dij, trm-1) equates 0, it means all weights on transition tr1~ trm-1 cannot describe this service. Therefore, it is a new type service. If there is a transition which has weight arc, it is used to record the new type service; else a new transition needsto be constructed.

5.2. The result of simulation

The two simulations are carried out. One is a more efficient service selection through QoS prediction using LFPN. The other is a service selection for appropriate function using LFPNSD.

Simulation for more efficient Web service selection

During the process of Web services discovery, there are maybe several services which have same function. One service which has the best QoS needs to be select. Hereby, the service performance context is used to predict the QoS value for next execution of service. If the prediction is precise enough, an appropriate service maybe selected.

In this simulation, LFPN is used as learning model for predicting service execution time which is main part of QoS. There are 11 inputs and 1 output in this model. 11 inputs include 10 data which are last 10 times execution time of a service and one data which is reliability of the service. The output is a prediction for execution time of service’s next execution. 10 transitions of LFPN is set when initialization.

A Web service performance dataset is employed for simulation. This dataset includes 100 publicly available Web services located in more than 20 countries. 150 service users executed about 100 invocations on each Web service. Each service user recorded execution time and invocation failures in dataset [27]. We selected one use’s invocation data as training data. Last 10 times execution time and reliability of each service was set as input and next time execution time was set as output. 20 sets of training data were selected for each of 100 services.

The initial threshold is selected as 0.2 and the threshold is increased 0.001 at every training episode. The initial learning rate is set as 1/1.1 for every transition. The learning rate is 1/(0.1+t) when a transition fired t times. Prediction result and training output data are noted as Outputpredict and Outputtraining. Prediction precision probability Prepro is used to evaluate the precision result. And the precision probability is computed using:

Prepro =1-(|Outputpredict−Outputtraining|/ Outputtraining).

Three different training stop conditionsare set as that three threshold values equal to 0.7, 0.8, and 0.9. The simulation result is listed in Table 6. Here, the number of service, which their execution time is precisely predicted, increased with the training threshold value increasing.

In the paper [3], the authors improved the traditional BP algorithm based on three-term method consisting of a learning rate, a momentum factor and a proportional factor for predicting service performance according to service context information. In this paper, this model is used to predict service execution time. The training data is same to LFPN’s. And the learning rate is 0.6, momentum factor 0.9, proportional factor 1 and training times is 10,000. We compared the simulation result of the method of [3], i.e. the conventional method, with that of LFPN in Table 7. From Table 7, it is shown that Web service number of high precision in LFPN’s prediction is bigger than the number of BP algorithm’s prediction and Web service number of low precision in LFPN’s prediction is smaller that BP algorithm’s prediction. Hereby, the result of LFPN is better than result of three term’s BP algorithm.

Precision0.99~10.98~0.990.95~
0.98
0.9~0.950.8~0.90.7~0.80.6~0.70~0.6
Number of Web services (th= 0.9)2114171510896
Numberof Web services (th= 0.8)1712141110121014
Number of Web services (th= 0.7)10101688111918

Table 6.

Prediction ability of LFPN

Precision0.99~10.98~0.990.95~0.980.9~0.950.8~0.90.7~0.80.6~0.70~0.6
Number of Web services using the LFPN(th=0.9)2114171510896
Number of Web services using the
conventional method
67151820121012

Table 7.

Prediction ability compares for two methods

Simulation for selection of Web service’s function

In this simulation, LFPNSD is used as leaning model. The benchmark Web services which listed at www.xmethods.net are used as training data. Each service of these 260 services has a textual description and its WSDL address. And, we can get WSDL description, operation and port parameters from the WSDL. We want to classify the Web service into four classes: 1) business, 2) finance, 3) nets and 4) life services. After training, Web services are invoked by natural language request [14]. The natural language is decompounded into three inputs of this model. For example, we want to get a short message service (SMS) for sending a message to a mobile phone. The nature language of this discovery is input and decomposed into three parts: 1) WSDL description: send a message to a mobile phone; 2) free textual service description: sending a message to a mobile phone through the Internet; 3) operation and port parameters maybe have operation names: send messages, send message multiple recipients, and so on; port names send serviceSOAP, and so on.

In this simulation, we firstly set 100 transitions for LFPNSD model. The training stop condition is thk (1≤km) ≥ 0.6. The service selection precision is recorded after every time of training. As shown in Figure 14 and 15, using LFPNSD model and its learning algorithm described in Section 5.1, every service class precision probability raised to more than 0.9when the training time reaches to 10.

Figure 14.

The results of simulation using LFPNSD and its learning algorithm− Discovery Precision Probability for total services

Figure 15.

The results of simulation using LFPNSD and its learning algorithm − Discovery Precision Probability for classification services

A method for evaluating the proximity of services is proposed [21]. In the method, WSDL document is represented as Dwsdl={t1, t2, …, twsdl} and Ddesc={t1, t2, …, tdesc} represents the textual description of the service. Because there is another descriptor of operation and port parameters in LFPNSD model, we add this descriptor as Dop&port={t1, t2, …, top&port} in order to compare two methods. Here, twsdl, tdesc and top&port are last keyword of WSDL, textural description and operation and port parameters. In the proximity of services method, the descriptor of natural language request which is provided by a user is Duser and descriptor of invoked service is Dinv. The three Context Overlaps (CO) are defined as same keywords between Dwsdluser, Ddescuser, Dop&portuser and Dwadlinv, Ddescinv, Dop&portinv. The proximity of user requested service and invoked service is defined as a root of sum of three CO’s squares. When a user invoking comes, it is compared with all services in services repository. Then, one service in Dinv, which has the biggest proximity value with Duser, was selected. We compared the discovery precision probability of this method (conventional method) withthe proposed LFPNSD.The simulation resultsare shown in Figure 16. The LFPNSD method yielded higher precision probabilities than theconventional method proposed in [21]. Especially when the service number of Web services’repository becomes more than 88, the difference is much more significant.Here, a correct service is selected in 14 services, 24 services, 37 services, 54 services, 88 services, 151 services just as they were used in [21].

Figure 16.

Comparison of two discovery methods

6. Conclusion

In this chapter, Learning Petri net (LPN) was constructed based on High-level Time Petri net and reinforcement learning (RL). The RL was used for adjusting the parameter of Petri net. Two kinds of learning algorithm were proposed for Petri net’s discrete and continuous parameter learning. And verification for LPN was shown. LPN model was applied to dynamical system control. We had used the LPN in three robot systems control - the AIBO, Guide Dog. The LPN models were found and controlled for these robot systems. These robot systems could adjust their parameters while system was running. And the correctness and effectiveness of our proposed model were confirmed in these experiments. LPN model was improved to the hierarchical LPN model and this improved hierarchical LPN model was applied to QoS optimization of Web service composition. The hierarchical LPN model was constructed based on stochastic Petri net and RL. When the model was used, the Web service composition was modeled with stochastic Petri net. A Web service dynamical composing framework is proposed for optimizing QoS of web service composition. The neural network learning method was used to Fuzzy Petri net. Learning fuzzy Petri net (LFPN) was proposed. Contrasting with the existing FPN, there are three extensions in the new model: the place can possess different tokens which represent different propositions; these propositions have different degrees of truth toward different transitions; the truth degree of proposition can be learnt through adjusting of the arc’s weight function. The LFPN model obtains the capability of fuzzy production rules learning through truth degree updating. The LFPN learning algorithm which introduced network learning method into Petri net update was proposed and the convergence of the algorithm was analyzed. The LFPN model was used into discovery of Web service. Using the LFPN model, different service functional descriptions are used to evaluate service function and an appropriate service is selected firstly, Secondly, context of QoS is used to predict QoS and a more efficient service is selected.

In the future, the different intelligent computing methods will be used into Petri net for constructing different type of LPN. The efficient different types of LPN used in different special area will be compared and an efficient LPN model for solving various problems will be founded.

© 2012 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Liangbing Feng, Masanao Obayashi, Takashi Kuremoto and Kunikazu Kobayashi (August 29th 2012). Construction and Application of Learning Petri Net, Petri Nets - Manufacturing and Computer Science, Pawel Pawlewski, IntechOpen, DOI: 10.5772/48398. Available from:

chapter statistics

2278total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Control Interpreted Petri Nets - Model Checking and Synthesis

By Iwona Grobelna

Related Book

First chapter

An Application of GSPN for Modeling and Evaluating Local Area Computer Networks

By Masahiro Tsunoyama and Hiroei Imai

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us