1、Petri網(wǎng)網(wǎng)-基本概念基本概念 軟軟 件件 學(xué)學(xué) 院院2An informal introduction3Strong point of Petri nets4A glimpse of history1962researchPhD thesisC.A. Petri19701980Focus mainlyon theoryFocus now alsoon tooling andapplications“Hidden” in manydiagrammingtechniques, e.g., BPMN,EPCs, UML, etc.1990200020105Elements of a Petri

2、net 庫所庫所 變遷變遷 弧弧 托肯托肯67Syntactic rules Directed graph with two types of nodes: places and transitions Places may hold zero or more tokens State (marking) is distribution of tokens over places8Transition enabling A transition is enabled if each of its input places contains at least one token.enabledn

3、otenablednotenabled9Transition firing An enabled transition can fire When it fires it consumes a token from each input place and produces a token into each output place.fired10Playing “Token Game” In the new state, T1 is enabled It will fire, etc.1112Remarks正確！正確！錯誤！錯誤！13Non-determinismtwo transitio

4、ns are enabled but only one can fire14concurrencytwo transitions are enabled, they can fire concurrentlythe first case15First T1 then T2the second case16First T2 then T1the third case17Example: Single traffic light1819內(nèi)容內(nèi)容 1、 Petri網(wǎng)的靜態(tài)部分-網(wǎng) 2、 Petri網(wǎng)的動態(tài)部分-標識 3、網(wǎng)系統(tǒng)分類 4、基本網(wǎng)系統(tǒng)（系統(tǒng)）201、Petri網(wǎng)的靜態(tài)部分網(wǎng)的靜態(tài)部分-網(wǎng)

5、（網(wǎng)（1/2） 滿足下列條件的三元組N=(S, T; F)稱作一個網(wǎng)：1) ST 2) ST 3)()()FSTTS4)()()dom Fcod FSTN至少含一個元素至少含一個元素二類不同的元素二類不同的元素有序偶的集合有序偶的集合不能有孤立元素不能有孤立元素()|: ( ,)()|: (,)dom FxSTySTx yFcod FxSTySTy xF其 中 ，21 S=P0, P1, P2 T=T0 F=(P0, T0), (P1, T0), (T0, P2)Any diagram can be mapped onto such a triple and vice versa22網(wǎng)（網(wǎng)（2

6、/2） 通常，習(xí)慣稱：通常，習(xí)慣稱： 1）S中的元素為庫所（中的元素為庫所（place）; 2）T中的元素為變遷（中的元素為變遷（transition）; 3）F為網(wǎng)的流關(guān)系（為網(wǎng)的流關(guān)系（flow relation）。）。 圖形化的，習(xí)慣用：圖形化的，習(xí)慣用： 1）用圓圈表示）用圓圈表示S中的元素；中的元素； 2）用矩形表示）用矩形表示T中的元素；中的元素； 3）對）對x, y S T，若（若（ x, y ） F，則從，則從x到到y(tǒng)畫一條有向邊。畫一條有向邊。23例子例子，（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），（，），

7、（，）2425x的前集和后集的前集和后集 設(shè)xX=ST為網(wǎng)N=(S, T; F)任一元素x=y| yST(y, x)F，x的前集(輸入集) x =y| yST(x, y)F，x的后集(輸出集)26簡單網(wǎng)簡單網(wǎng) 若x, yST， （ x= y） （ x = y ）x=y，則稱N為一個簡單網(wǎng)。非簡單網(wǎng)示例：非簡單網(wǎng)示例：27純網(wǎng)純網(wǎng) 若x, yST， x x = ，則稱N為一個純網(wǎng)。任何元素不能同時是任何元素不能同時是另一元素的輸入和輸出另一元素的輸入和輸出xy282、Petri網(wǎng)的動態(tài)部分網(wǎng)的動態(tài)部分-標識標識 設(shè)N=(S, T; F)為一個網(wǎng)。映射 M：S0,1,2,稱為網(wǎng)N的一個標識或狀態(tài)（

8、marking）。二元組（N, M）即四元組（S, T; F, M）稱為一個標識網(wǎng)。 用圖形表示時，對sS，若M(s)=k，則在表示庫所s的小圓圈內(nèi)加上k個小黑點。此小黑點稱為托肯(token)或標記。29網(wǎng)系統(tǒng)（網(wǎng)系統(tǒng)（net system） 一個網(wǎng)系統(tǒng)是一個標識網(wǎng)= (S, T; F, M)，并具有下面的變遷發(fā)生規(guī)則： 1）對于變遷tT，如果sS: stM(s)1，則說變遷t在標識M有發(fā)生權(quán)（enabled），記為Mt； 2）若Mt ，則在標識M下，變遷t可以發(fā)生或點火（fire），從標識M發(fā)生變遷t得到一個新的標識M，記為Mt M ，對sS，有：( )1( )1( )( )MssttMs

9、sttMsMs，若，若，其他30網(wǎng)系統(tǒng)網(wǎng)系統(tǒng) 一個網(wǎng)系統(tǒng)有一個初始標識（initial marking），記為M0。 在M0下，一個網(wǎng)系統(tǒng)中可能有若干變遷有發(fā)生權(quán)，其中一個變遷發(fā)生，就得到一個新的標識M1（不同的變遷發(fā)生，所得到的新標識一般也不相同）。 在M1下又可能有若干變遷有發(fā)生權(quán)，其中一個發(fā)生，又得到一個新的標識。這樣繼續(xù)下去，變遷的連續(xù)發(fā)生和標識的不斷變化，就是網(wǎng)系統(tǒng)的運行。31例子例子s1t1t2t3s2s3s4t4M0: M0(s1)=1, M0(s2)=M0(s3)=M0(s4)=00=(N, M0)N=(S, T; F)S=S1, S2,S3 ,S4T=t1, t2,t3 ,t

10、4F=(t1, s1), .M0=(1, 0, 0, 0)32變遷變遷t2發(fā)生發(fā)生s1t1t2t3s2s3s41=(N, M1)M1: M1(s1)=0, M0(s2)=M0(s3)=1, M0(s4)=0M1=(0, 1, 1, 0)t433變遷變遷t1發(fā)生發(fā)生s1t1t2t3s2s3s42=(N, M2)M2: M1(s1)=1, M0(s2)=M0(s4)=0, M0(s3)=1M2=(1, 0, 1, 0)t434變遷變遷t4發(fā)生發(fā)生s1t1t2t3s2s3s43=(N, M3)M3: M1(s1)=0, M0(s2)=M0(s3)=0, M0(s4)=1M3=(0, 0, 0, 1)

11、t435問題問題 當網(wǎng)系統(tǒng)運行到標識M1時，變遷t1和t4都可以發(fā)生點火。網(wǎng)系統(tǒng)根據(jù)什么原則，選取變遷呢？ 當網(wǎng)系統(tǒng)運行到標識M2時，還可以繼續(xù)運行下去嗎？ 當網(wǎng)系統(tǒng)運行到標識M3時，還可以繼續(xù)運行下去嗎？不確定性不確定性停止停止363、網(wǎng)系統(tǒng)分類、網(wǎng)系統(tǒng)分類(1/2) 容量函數(shù) K: SN N是自然數(shù)集， 是無窮 標識 M: SN0為一個標識的充要條件，sS有M(s)K(s)。 權(quán)函數(shù)W: FN+。用W(x, y)表示值。我們前面學(xué)習(xí)的網(wǎng)系統(tǒng)：K(s)=, W(x, y)=137網(wǎng)系統(tǒng)分類網(wǎng)系統(tǒng)分類(2/2) 根據(jù)及分成四類： 基本網(wǎng)系統(tǒng)（系統(tǒng)）:K1, W 1 庫所變遷網(wǎng)（網(wǎng)） :K, W

12、 1 庫所變遷系統(tǒng)（系統(tǒng)）:K和W為任意容量函數(shù)和權(quán)函數(shù) 高級Petri網(wǎng)：謂詞Petri網(wǎng)和有色Petri網(wǎng)38基本網(wǎng)系統(tǒng)（系統(tǒng)）基本網(wǎng)系統(tǒng)（系統(tǒng)） K1, W 1； 四元組N= (B, E; F, Cin)，0( )=,1Ms兩 種 狀 態(tài) ： 有 托 肯 和 無 托 肯 庫所條件：真或假；B表示條件集； 變遷事件 E表示事件集； 由于庫所為條件，即()或，可以不用向量表示，而用的子集表示: c=bB|M(b)=1，稱為情態(tài) cin=bB|M0(b)=1，稱為初始情態(tài)39例子例子c1c2c4c3c5c6c7a1a2a3M0=(1, 1, 0, 1, 1, 0, 0)M0=(c1, c2,

13、c4, c5)40P/T網(wǎng)網(wǎng) K, W 1 1962年，聯(lián)邦德國的Carl Adam Petri在他的博士論文用自動機通信中提出的Petri網(wǎng)。 基本網(wǎng)系統(tǒng)是P/T網(wǎng)的特例，P/T網(wǎng)是P/T系統(tǒng)的特例。41案例：四季系統(tǒng)案例：四季系統(tǒng)(1/3) 用EN系統(tǒng)建模四級的變化?42四季系統(tǒng)四季系統(tǒng)(2/3)春暖花開春暖花開赤日炎炎赤日炎炎秋風(fēng)落葉秋風(fēng)落葉寒風(fēng)刺骨寒風(fēng)刺骨春暖花開春暖花開43四季系統(tǒng)四季系統(tǒng)(3/3)春暖花開春暖花開赤日炎炎赤日炎炎秋風(fēng)落葉秋風(fēng)落葉事件事件t1（變化）（變化）t2t3t4條件條件s1（狀態(tài)）（狀態(tài)）s2s3寒風(fēng)刺骨寒風(fēng)刺骨s4春暖花開春暖花開s144a1c1c2a2c3

14、a3c4a445案例：生產(chǎn)流水線（案例：生產(chǎn)流水線（P/T系統(tǒng)）系統(tǒng)） 生產(chǎn)流水線：半成品在流水線上移動，每個生產(chǎn)環(huán)節(jié)再組裝上一兩個部件，直到產(chǎn)生產(chǎn)品。t1:半成品半成品s1部件部件s2二個螺絲二個螺絲s3t2:工具工具s7半成品半成品s4部件部件s5四個螺絲四個螺絲s3工具工具s7半成半成s半成品半成品s6s64647說明說明 變遷變遷t1的產(chǎn)生：用工具的產(chǎn)生：用工具(s7)，兩個螺絲釘，兩個螺絲釘(s3)把一個部件把一個部件(s2)裝配到半成品裝配到半成品(s1)，產(chǎn)，產(chǎn)生一個新的半成品生一個新的半成品(s4)，并退換工具。，并退換工具。 變遷變遷t2的產(chǎn)生：用四個螺絲釘?shù)漠a(chǎn)生：用四個螺絲

15、釘(s3)把一個把一個部件部件(s5)裝配到半成品裝配到半成品(s4)，產(chǎn)生一個新的，產(chǎn)生一個新的半成品半成品(s6)，并退換工具。，并退換工具。48問題問題 變遷變遷t1和和t2的關(guān)系的關(guān)系? t2會不會永遠不執(zhí)行？會不會永遠不執(zhí)行？494、基本網(wǎng)系統(tǒng)（系統(tǒng)）、基本網(wǎng)系統(tǒng)（系統(tǒng)）( )1110( )1, 011( )( ),( )M bbeeM bbeeMbM bbeeM b，若，若，50局部確定性局部確定性ee.c一個變遷是否發(fā)生，一個變遷是否發(fā)生，取決于變遷的外延，取決于變遷的外延，與全局狀態(tài)無關(guān)。與全局狀態(tài)無關(guān)。51事件間的基本關(guān)系事件間的基本關(guān)系 設(shè)c為E/N系統(tǒng)EN=(B, E; F, cin)的情態(tài)，e1, e2E為EN的任意兩個事件。 1、順序關(guān)系（sequential relation） 如果ce1, 但ce2，而ce2，其中c是c的后繼； ce1 c, 就說e1和 e2在c有順序關(guān)系。c1c2c3e1e252 2、沖突關(guān)系（in conflict） 若ce1ce2，但 ce1, e2，則e1和 e2在c有互相沖突。c1c2e1e253 3、沖撞關(guān)系（contact） 若有bB和eE使得ec，又bc且b e，則說在情態(tài)c條件b處有沖