1、2 1 Petri Net概述概述 2. 经典经典Petri Net 3. 高阶高阶Petri网网 4. 一个一个Petri网建模实例网建模实例 5.小结小结3 经典的经典的Petri net是由是由 Carl Adam Petri在在 1962年的博士论文年的博士论文中提出的。中提出的。 是离散事件动态系统(是离散事件动态系统(Discrete Event Dynamic System, DEDS)的描述工具,可描述异步、同步、并行逻辑关系,)的描述工具,可描述异步、同步、并行逻辑关系,是描述、分析和控制是描述、分析和控制DEDS的最有效和应用最广泛的方法;的最有效和应用最广泛的方法; 大量
2、研究大量研究(10.000 publications),至,至1985年,它主要被用于年,它主要被用于理论界;自从理论界;自从80年中期后,实际的应用越来越多,这主要年中期后,实际的应用越来越多,这主要是由于引入高阶是由于引入高阶 Petri nets和许多工具;和许多工具; 最早是应用于计算机信息处理、然后工程方面(自动制造最早是应用于计算机信息处理、然后工程方面(自动制造系统)、目前在计算机、自动化、通信、交通、电力与电系统)、目前在计算机、自动化、通信、交通、电力与电子、服务与制造都得到广泛应用。子、服务与制造都得到广泛应用。4PetriPetri网观点可简单的归纳到两个基本概念网观点可
3、简单的归纳到两个基本概念: : 事件事件和条件和条件, ,许多系统均可从事件与条件的观点去建模;许多系统均可从事件与条件的观点去建模; 事件是系统中的动作事件是系统中的动作, , 事件的出现是由系统状态控制的事件的出现是由系统状态控制的; ; 系统状态可描述为一组条件系统状态可描述为一组条件, , 条件就是系统状态的谓词条件就是系统状态的谓词或逻辑描述或逻辑描述; ; 前条件前条件:由于事件是动作:由于事件是动作, , 所以它可以发生。为了使事所以它可以发生。为了使事件发生件发生, , 必须使某些条件成立必须使某些条件成立, ,这种条件称为事件的前条这种条件称为事件的前条件件; ; 后条件后条
4、件:事件的发生可能破坏前条件而使另外的条件成:事件的发生可能破坏前条件而使另外的条件成立立, , 这种条件称为事件的后条件。这种条件称为事件的后条件。5 因此因此(一组条件)和(一组条件)和(事件事件)是Petri nets的最基本单元。的最基本单元。 基本Petri网包含库所(状态)、转移、以及它们的关系。 高阶高阶Petri nets 是对是对Petri nets的扩展:的扩展: 颜色颜色 (for the modelling of attributes) 时间时间 (for performance analysis) 层次层次 (for the structuring of models
5、, DFDs)6Petri网的特点网的特点 从控制和管理的角度模拟系统从控制和管理的角度模拟系统, , 不涉及系统所依不涉及系统所依赖的物理化学原理赖的物理化学原理, ,这样可以简化某些细节这样可以简化某些细节, , 易于易于理解。理解。 精确描述系统中事件的依赖关系和不依赖关系精确描述系统中事件的依赖关系和不依赖关系, ,这这是事件之间存在的、不依赖于观察的关系。是事件之间存在的、不依赖于观察的关系。 具有统一的语言描述系统结构和行为具有统一的语言描述系统结构和行为, , 方便建模方便建模仿真仿真, ,从而起到沟通不同子系统间桥梁的作用。从而起到沟通不同子系统间桥梁的作用。 与顺序模型不同与
6、顺序模型不同, Petri, Petri网系统比其他图形建模工网系统比其他图形建模工具更适于描述并发和冲突。具更适于描述并发和冲突。7冲突冲突并发并发8Petri net主要用途:主要用途: 系统性能分析:如制造系统设备使用率、生产率、系统性能分析:如制造系统设备使用率、生产率、可靠性等。可靠性等。 系统控制:直接从可视化模型中产生系统控制:直接从可视化模型中产生DEDS监控监控编码,进行系统实施控制。编码,进行系统实施控制。 系统仿真:系统分析与评估的系统仿真。系统仿真:系统分析与评估的系统仿真。 数字分析:可通过结构变化描述系统的变化,支数字分析:可通过结构变化描述系统的变化,支持持DED
7、S形式的数学描述与分析;形式的数学描述与分析; 还可以转化为其它的还可以转化为其它的DEDS模型,如马可夫链等。模型,如马可夫链等。9利用利用PetriPetri网建模具有以下优点。网建模具有以下优点。 (1) Petri(1) Petri网建立在严格的数学基础上,精确描述系统中事网建立在严格的数学基础上,精确描述系统中事件的依赖关系和不依赖关系件的依赖关系和不依赖关系, ,这是事件之间存在的、不依赖这是事件之间存在的、不依赖于观察的关系,已有了许多成熟的分析方法和工具。于观察的关系,已有了许多成熟的分析方法和工具。 (2) (2) 兼顾了严格语义与图形表示两方面,具有统一的语言描兼顾了严格语
8、义与图形表示两方面,具有统一的语言描述系统结构和行为述系统结构和行为, , 方便建模仿真方便建模仿真, ,从而起到沟通不同子系从而起到沟通不同子系统间桥梁的作用统间桥梁的作用; ; (3) Petri(3) Petri网是一种基于状态的建模方法,与基于事件的过网是一种基于状态的建模方法,与基于事件的过程建模方法不同程建模方法不同, Petri, Petri网系统比其他图形建模工具更适于网系统比其他图形建模工具更适于确定触发方式、描述同步并发系统,并具有更多的柔性。确定触发方式、描述同步并发系统,并具有更多的柔性。 从建模角度从建模角度可视化图形描述却被形式化数学方可视化图形描述却被形式化数学方
9、法支持;法支持;10PetriPetri网建模的缺点:网建模的缺点: PetriPetri网的优点实际上是在模型构成上增加了模型的组成网的优点实际上是在模型构成上增加了模型的组成元素,因此往往导致组成模型的元素数量过多;元素,因此往往导致组成模型的元素数量过多; PetriPetri网不如基于活动网络容易理解;网不如基于活动网络容易理解; PetriPetri网的建模中不能在网中体现数据流,尽管基于状态网的建模中不能在网中体现数据流,尽管基于状态建模的建模的PetriPetri网能够精确、方便地对过程的控制逻辑进行网能够精确、方便地对过程的控制逻辑进行定义,在这种情况下,数据流就与控制流完全混
10、合,当两定义,在这种情况下,数据流就与控制流完全混合,当两者不一样的时候,者不一样的时候, PetriPetri网就无法显式地表示这种独立于网就无法显式地表示这种独立于控制流之外的控制流;控制流之外的控制流;11 1 Petri Net概述概述 2. 经典经典Petri Net 3. 高阶高阶Petri网网 4. 一个一个Petri网建模实例网建模实例 5.小结小结12 经典的经典的Petri网是一个由库所网是一个由库所 places ( ) 和和转移转移transitions ( )构成的网络构成的网络t2p1p2p3p4t3t1连接连接具有方向,并在库所和转换之间。具有方向,并在库所和转换
11、之间。托肯托肯Token 是动态对象。是动态对象。Petri网的网的状态状态由分布在库所中的托肯决定由分布在库所中的托肯决定13Petri网的网的组成元素组成元素 库所库所(Place)小圆圈)小圆圈 P 转移转移(Transition)小方块)小方块 T 连接连接(Connection)是库所和转移之间的有向边,)是库所和转移之间的有向边,流关系流关系 F,K 托肯托肯(Token)是库所中的动态对象,可以从一)是库所中的动态对象,可以从一个库所移动到另一个库所个库所移动到另一个库所 14Petri网的网的规则规则 连接是有方向的,其上可以标出权重连接是有方向的,其上可以标出权重 两个库所或
12、转移之间不允许有边,且不应该有孤两个库所或转移之间不允许有边,且不应该有孤立节点立节点 库所可以拥有任意数量的托肯库所可以拥有任意数量的托肯 15顺序流程迭代(循环)流程并发流程选择流程16 转移转移t1具有三个输入库所具有三个输入库所 (p1, p2 and p3) 和两个和两个输出库所输出库所 (p3 and p4). 库所库所p3 既是既是t1的输入库所又是它的输出库所的输入库所又是它的输出库所.p1p2p3p4t1输入库所输入库所/输出库所输出库所17 转移是主动元素,而库所和托肯是被动元素转移是主动元素,而库所和托肯是被动元素 如果输入库所都包含了托肯,那么转移就被激活如果输入库所都
13、包含了托肯,那么转移就被激活t1t2Transition t1 is not enabled, transition t2 is enabled.18 激活的转移可以被点火激活的转移可以被点火 点火将消耗输入库所的托肯,并为输出库所产生托肯点火将消耗输入库所的托肯,并为输出库所产生托肯t2t2Firing is atomic.1920 两个转移竞争同一个托肯:冲突两个转移竞争同一个托肯:冲突 即使有两个托肯,依然存在冲突即使有两个托肯,依然存在冲突t1t221 库所库所代表缓存,渠道,地理位置,条件或者状态代表缓存,渠道,地理位置,条件或者状态 转移转移代表时间,传输或者转换代表时间,传输或者
14、转换 托肯托肯表示对象表示对象 (humans, goods, machines), 信息信息或者对象的状态或者对象的状态 过程的状态用位于过程的状态用位于库所库所的的托肯托肯来表示,状态之间来表示,状态之间的变换用的变换用转移转移来表示来表示22一般Petri网定义为五元组 = ( P , T ,F , K , M0 ) 其中其中, P , P 为位置的集合为位置的集合, , 用圆圈代表用圆圈代表, , 表示系统的状态表示系统的状态; T ; T 为转移的集合为转移的集合, , 用空心矩形代表用空心矩形代表, , 表示系统中的事件表示系统中的事件; ; F F 称为称为P-TP-T的流关系的
15、流关系, , 其规定资源的输出流其规定资源的输出流; ; K K 称为称为T-PT-P的流关系的流关系, , 其规定资源的输入流其规定资源的输入流; ; M0 M0 称为称为PetriPetri网网的初始标识。的初始标识。 Token表示工作对象,转移是网络中的控制点。表示工作对象,转移是网络中的控制点。Petri网进网进行算法扩展行算法扩展, 可以使它具有处理模型求解系统运行的能力。可以使它具有处理模型求解系统运行的能力。23rgredyellowgreenyrgy24rg1red1yellow1green1yr1gy1rg2red2yellow2green2yr2gy225rg1red1y
16、ellow1green1yr1gy1rg2red2yellow2green2yr2gy2safe26单身汉孩童已婚青春期结婚离婚死亡已故27 拿到拿到2黑或黑或2红放回红放回1黑;黑; 拿到黑红各拿到黑红各1放回放回1红;红;blackredbbrrbr每次拿两个球但放回一个球:28 当前状态当前状态库所中托肯的分布情况库所中托肯的分布情况. 可达状态可达状态通过一系列激活的转移的点火,从当前状态可以达到的状通过一系列激活的转移的点火,从当前状态可以达到的状态态. 死状态(死状态(dead state)没有转移能够激活的状态没有转移能够激活的状态 blackredbbrrbr29 拿到拿到2黑
17、或黑或2红放回红放回1黑;黑; 拿到黑红各拿到黑红各1放回放回1红;红; 7 7 可达状态可达状态, 1 , 1 死状态死状态. .blackredbbrrbr(3,2)(1,3)(3,1)(1,2)(3,0)(1,1)(1,0)rrrrrrbrbrbbbrbbbrbbbr30 多少可达状态多少可达状态? ? 是否有死状态是否有死状态? ?deadsleepingactivestartstopdie(2,0,0)(1,1,0)start(1,0,1)diestopstart(0,2,0)(0,1,1)(0,0,2)stopstartdiedie31 交通灯的可达图交通灯的可达图rg1red1y
18、ellow1green1yr1gy1rg2red2yellow2green2yr2gy2safe32rg1red1yellow1green1yr1gy1rg2red2yellow2green2yr2gy2safe2safe133 画出可达图画出可达图 多少个可达状态多少个可达状态? 有无死状态有无死状态? 两个作者和三个读者的情况是怎样的两个作者和三个读者的情况是怎样的?restmail_boxreceive_mailtype_mailreadyrestbeginsend_mailread_mail34 1 Petri Net概述概述 2. 经典经典Petri Net 3. 高阶高阶Petri
19、网网 4. 一个一个Petri网建模实例网建模实例 5.小结小结35 在实际中经典的在实际中经典的Petri网并不是非常有用网并不是非常有用: Petri网变得规模太大,太复杂网变得规模太大,太复杂. 建模可能要花太多的时间建模可能要花太多的时间. 不能处理时间和数据信息不能处理时间和数据信息. 因此我们需要使用高阶因此我们需要使用高阶Petri网,也就是说采用网,也就是说采用以下方式来扩展以下方式来扩展Petri网网: 颜色颜色属性描述属性描述 时间时间性能分析性能分析 层次层次结构分解结构分解36 理发厅的例子理发厅的例子startwaitingfinishbusyfreereadycli
20、ent waitinghairdresser ready to begin注意:如何简化了对多个理发师的建模注意:如何简化了对多个理发师的建模37 某一某一托肯托肯经常代表了具有经常代表了具有某种属性某种属性的对象的对象 因此,每一托肯具有因此,每一托肯具有值(颜色)值(颜色)以表示由托肯以表示由托肯建模的对象的建模的对象的特定属性特定属性startwaitingfinishbusyfreereadyname: Harryage: 28experience: 2name: Sallyage: 28hairtype: BL38 每一个每一个转移转移可以有正式的(非正式的)描述可以有正式的(非正式
21、的)描述: :产生的托肯数目产生的托肯数目这些托肯的值这些托肯的值和和( (可选可选) ) 的一个前提条件的一个前提条件 复杂性被分解到网络和托肯的值上复杂性被分解到网络和托肯的值上 这种处理产生了紧凑、可管理和自然的过程描述。这种处理产生了紧凑、可管理和自然的过程描述。 例子:汽车装配过程例子:汽车装配过程39 为了进行为了进行性能分析性能分析,需要对,需要对持续时间持续时间,延迟延迟等等的时间概念进行建模的时间概念进行建模 因此,每一个因此,每一个托肯托肯都有一个都有一个时间戳时间戳,而,而转移转移确确定了定了产生一个托肯产生一个托肯的延迟的延迟startwaitingfinishbusy
22、freeready0139D=3D=0D=040包含时间属性的交通灯包含时间属性的交通灯41 对复杂的对复杂的Petri网添加网添加结构信息结构信息的方法,与的方法,与DFD类似类似 一个子网是对库所,转一个子网是对库所,转移和子网的扩展移和子网的扩展startfinishbusyfreewaitingreadyh1h2h342waitingreadyh1h2h3startfinishbusyfreebeginendpendingbeginendpending43 1 Petri Net概述概述 2. 经典经典Petri Net 3. 高阶高阶Petri网网 4. 一个一个Petri网建模实例
23、网建模实例 5.小结小结44Petri网建立步骤:网建立步骤: 根据状态与事件的定义,确定系统的状态集和事件集。根据状态与事件的定义,确定系统的状态集和事件集。 确定系统中状态与事件的关系。确定系统中状态与事件的关系。 将将库所库所和和转移转移对应起来,建立对应起来,建立Petri网模型图。网模型图。 根据系统情况,决定根据系统情况,决定Petri网模型图的初始状态,确定初始网模型图的初始状态,确定初始状态的下个状态的状态的下个状态的Token数。数。 基于初始状态判断那些事件可被激发,当模型激活后,模基于初始状态判断那些事件可被激发,当模型激活后,模型状态图将发生变化,又引起一些事件被触发。
24、型状态图将发生变化,又引起一些事件被触发。45电子商务的交易流程可用语言描述为电子商务的交易流程可用语言描述为: : 客户通过浏览信息向商家提交订单意向,商家接到提交的订单意向后, 通过查看库存信息形成可供订单; 对可供订单确认后,客户输入用于电子支付的信用卡号和密码; 得到银行的支付确认后, 商家将可供订单转为有效订单,同时产生库存信息变更; 商家按有效订单配送货物, 并修改库存信息。接着商家进行下次交易的处理。46 这个系统的状态这个系统的状态 ( (库所库所) ) 可概括为可概括为: :P P1 1: :客户客户; P; P2 2: :可供订单可供订单;P;P3 3 : :有效订单和库存
25、信息有效订单和库存信息; P; P4 4: :商家商家事件事件( ( 转移转移) ) 可概括为可概括为: :T T1 1 : :支付确认支付确认; T; T2 2 : :查看库存查看库存; T; T3 3 : :配送货物配送货物。47 不妨认为这个场景有不妨认为这个场景有2个个Token,通过这两个,通过这两个Token流转完成流程运作:流转完成流程运作: (商品)库存(商品)库存 (客户)订单(客户)订单P1P2T1T2P4P3T348Token Token (商品)库存的流动过程;(商品)库存的流动过程; P4P2P1P3P4 事件:事件: T2,T1,T3P1P2T1T2P4P3T349
26、Token Token (客户)订单的流动过程;(客户)订单的流动过程; P1P3P4 事件:事件: T1,T3P1P2T1T2P4P3T350 1 Petri Net概述概述 2. 经典经典Petri Net 3. 高阶高阶Petri网网 4. 一个一个Petri网建模实例网建模实例 5.小结小结51例例 描述:描述: 1 参考下面的参考流程(要求库所不少于参考下面的参考流程(要求库所不少于8,转移,转移9,要求,要求有并发及选择流程)。有并发及选择流程)。 在公司接到客户投诉时,对事件内容进行登记,然后向客在公司接到客户投诉时,对事件内容进行登记,然后向客户寄出调查表收集具体细节,同时联系
27、办公室对对该事件户寄出调查表收集具体细节,同时联系办公室对对该事件进行调查。如果客户和办公室都在两周内返回了调查表格,进行调查。如果客户和办公室都在两周内返回了调查表格,那么该投诉事件的相关材料就被受理,如果超过这一期限,那么该投诉事件的相关材料就被受理,如果超过这一期限,则该项投诉事件就被放弃,不进入受理流程;则该项投诉事件就被放弃,不进入受理流程; 在对投诉事件进行评估的基础上,根据评估意见决定是否在对投诉事件进行评估的基础上,根据评估意见决定是否对投诉进行处理。如果决定处理投诉,根据收集到的材料对投诉进行处理。如果决定处理投诉,根据收集到的材料决定对客户投诉给出补偿或拒绝的决定,根据处理
28、决定由决定对客户投诉给出补偿或拒绝的决定,根据处理决定由相关人员执行具体处理过程,并通知客户,如客户有异议相关人员执行具体处理过程,并通知客户,如客户有异议则再进入评估处理流程,无异议则并把相应的投诉记录归则再进入评估处理流程,无异议则并把相应的投诉记录归档保存,整个投诉过程结束。档保存,整个投诉过程结束。52 事件和条件是事件和条件是PetriPetri网的基础,能精确且严格地描网的基础,能精确且严格地描述;述; 高阶高阶PetriPetri网网扩展了颜色、时间、层次以描述复杂扩展了颜色、时间、层次以描述复杂过程;过程; PetriPetri网建模是基于网建模是基于状态状态的过程建模方法,对描述的过程建模方法,对描述并发系统非常有用;并发系统非常有用; PetriPetri网最大的优点是可视化图形描述却被形式化网最大的优点是可视化图形描述却被形式化数学方法支持。数学方法支持。