基于Petri网的建模技术

基于Petri网的建模技术2agenda1PetriNet概述2.经典PetriNet3.高阶Petri网4.一个Petri网建模实例5.小结31PetriNet概述•经典的Petrinet是由CarlAdamPetri在1962年的博士论文中提出的。•是离散事件动态系统（DiscreteEventDynamicSystem,DEDS）的描述工具，可描述异步、同步、并行逻辑关系，是描述、分析和控制DEDS的最有效和应用最广泛的方法；•大量研究(10.000publications)，至1985年，它主要被用于理论界；自从80年中期后，实际的应用越来越多，这主要是由于引入高阶Petrinets和许多工具；•最早是应用于计算机信息处理、然后工程方面（自动制造系统）、目前在计算机、自动化、通信、交通、电力与电子、服务与制造都得到广泛应用。4Petri网观点可简单的归纳到两个基本概念:•事件和条件,许多系统均可从事件与条件的观点去建模；•事件是系统中的动作,事件的出现是由系统状态控制的;•系统状态可描述为一组条件,条件就是系统状态的谓词或逻辑描述;•前条件：由于事件是动作,所以它可以发生。为了使事件发生,必须使某些条件成立,这种条件称为事件的前条件;•后条件：事件的发生可能破坏前条件而使另外的条件成立,这种条件称为事件的后条件。5•因此状态（一组条件）和转移（事件）是Petrinets的最基本单元。•基本Petri网包含库所（状态）、转移、以及它们的关系。•高阶Petrinets是对Petrinets的扩展：–颜色(forthemodellingofattributes)–时间(forperformanceanalysis)–层次(forthestructuringofmodels,DFD's)6Petri网的特点•从控制和管理的角度模拟系统,不涉及系统所依赖的物理化学原理,这样可以简化某些细节,易于理解。•精确描述系统中事件的依赖关系和不依赖关系,这是事件之间存在的、不依赖于观察的关系。•具有统一的语言描述系统结构和行为,方便建模仿真,从而起到沟通不同子系统间桥梁的作用。•与顺序模型不同,Petri网系统比其他图形建模工具更适于描述并发和冲突。7冲突并发8Petrinet主要用途：•系统性能分析：如制造系统设备使用率、生产率、可靠性等。•系统控制：直接从可视化模型中产生DEDS监控编码，进行系统实施控制。•系统仿真：系统分析与评估的系统仿真。•数字分析：可通过结构变化描述系统的变化，支持DEDS形式的数学描述与分析；•还可以转化为其它的DEDS模型，如马可夫链等。9利用Petri网建模具有以下优点。•(1)Petri网建立在严格的数学基础上，精确描述系统中事件的依赖关系和不依赖关系,这是事件之间存在的、不依赖于观察的关系，已有了许多成熟的分析方法和工具。•(2)兼顾了严格语义与图形表示两方面，具有统一的语言描述系统结构和行为,方便建模仿真,从而起到沟通不同子系统间桥梁的作用;•(3)Petri网是一种基于状态的建模方法，与基于事件的过程建模方法不同,Petri网系统比其他图形建模工具更适于确定触发方式、描述同步并发系统，并具有更多的柔性。•从建模角度——可视化图形描述却被形式化数学方法支持；10Petri网建模的缺点：•Petri网的优点实际上是在模型构成上增加了模型的组成元素，因此往往导致组成模型的元素数量过多；•Petri网不如基于活动网络容易理解；•Petri网的建模中不能在网中体现数据流，尽管基于状态建模的Petri网能够精确、方便地对过程的控制逻辑进行定义，在这种情况下，数据流就与控制流完全混合，当两者不一样的时候，Petri网就无法显式地表示这种独立于控制流之外的控制流；11agenda1PetriNet概述2.经典PetriNet3.高阶Petri网4.一个Petri网建模实例5.小结122经典PetriNet•经典的Petri网是一个由库所places()和转移transitions()构成的网络t2p1p2p3p4t3t1连接具有方向，并在库所和转换之间。托肯Token是动态对象。Petri网的状态由分布在库所中的托肯决定13Petri网的组成元素Petri网简称PNG(PetriNetGraph)，它有库所和转移两种结点•库所（Place）小圆圈P•转移（Transition）小方块T•连接（Connection）是库所和转移之间的有向边，流关系F,K•托肯（Token）是库所中的动态对象，可以从一个库所移动到另一个库所•14Petri网的规则•连接是有方向的，其上可以标出权重•两个库所或转移之间不允许有边，且不应该有孤立节点•库所可以拥有任意数量的托肯15顺序流程迭代（循环）流程并发流程选择流程16•转移t1具有三个输入库所(p1,p2andp3)和两个输出库所(p3andp4).•库所p3既是t1的输入库所又是它的输出库所.p1p2p3p4t1输入库所/输出库所17•转移是主动元素，而库所和托肯是被动元素•如果输入库所都包含了托肯，那么转移就被激活t1t2Transitiont1isnotenabled,transitiont2isenabled.使能条件18•激活的转移可以被点火•点火将消耗输入库所的托肯，并为输出库所产生托肯t2t2Firingisatomic.点火19托肯迁移的例子20•两个转移竞争同一个托肯：冲突•即使有两个托肯，依然存在冲突t1t2不确定性21•库所代表缓存，渠道，地理位置，条件或者状态•转移代表时间，传输或者转换•托肯表示对象(humans,goods,machines),信息或者对象的状态•过程的状态用位于库所的托肯来表示，状态之间的变换用转移来表示基于PetriNet的流程建模22形式化表达一般Petri网定义为五元组∑=(P,T，F,K,M0)•其中,P为位置的集合,用圆圈代表,表示系统的状态;T为转移的集合,用空心矩形代表,表示系统中的事件;•F称为P-T的流关系,其规定资源的输出流;•K称为T-P的流关系,其规定资源的输入流;•M0称为Petri网∑的初始标识。•Token表示工作对象，转移是网络中的控制点。Petri网进行算法扩展,可以使它具有处理模型求解系统运行的能力。23rgredyellowgreenyrgy例子：交通灯24rg1red1yellow1green1yr1gy1rg2red2yellow2green2yr2gy2两个交通灯25rg1red1yellow1green1yr1gy1rg2red2yellow2green2yr2gy2safe两个安全的交通灯26单身汉孩童已婚青春期结婚离婚死亡已故人的一生27Ballgame•拿到2黑或2红放回1黑；•拿到黑红各1放回1红；blackredbbrrbr每次拿两个球但放回一个球：28•当前状态库所中托肯的分布情况.•可达状态通过一系列激活的转移的点火，从当前状态可以达到的状态.•死状态（deadstate）没有转移能够激活的状态blackredbbrrbr某些定义29•拿到2黑或2红放回1黑；•拿到黑红各1放回1红；•7可达状态,1死状态.blackredbbrrbr(3,2)(1,3)(3,1)(1,2)(3,0)(1,1)(1,0)rrrrrrbrbrbb\brbb\brbb\br30•多少可达状态?•是否有死状态?deadsleepingactivestartstopdie练习：你的一生(2,0,0)(1,1,0)start(1,0,1)diestopstart(0,2,0)(0,1,1)(0,0,2)stopstartdiedie31练习•交通灯的可达图rg1red1yellow1green1yr1gy1rg2red2yellow2green2yr2gy2safe32rg1red1yellow1green1yr1gy1rg2red2yellow2green2yr2gy2safe2safe1安全而公平的交通灯33•画出可达图•多少个可达状态?•有无死状态?•两个作者和三个读者的情况是怎样的?restmail_boxreceive_mailtype_mailreadyrestbeginsend_mailread_mail课后练习34agenda1PetriNet概述2.经典PetriNet3.高阶Petri网4.一个Petri网建模实例5.小结35•在实际中经典的Petri网并不是非常有用:–Petri网变得规模太大，太复杂.–建模可能要花太多的时间.–不能处理时间和数据信息.•因此我们需要使用高阶Petri网，也就是说采用以下方式来扩展Petri网:–颜色——属性描述–时间——性能分析–层次——结构分解3高阶Petri网36•理发厅的例子startwaitingfinishbusyfreereadyclientwaitinghairdresserreadytobegin注意：如何简化了对多个理发师的建模例子37•某一托肯经常代表了具有某种属性的对象•因此，每一托肯具有值（颜色）以表示由托肯建模的对象的特定属性startwaitingfinishbusyfreereadyname:Harryage:28experience:2name:Sallyage:28hairtype:BL采用颜色进行扩展38•每一个转移可以有正式的（非正式的）描述:–产生的托肯数目–这些托肯的值–和(可选)的一个前提条件•复杂性被分解到网络和托肯的值上•这种处理产生了紧凑、可管理和自然的过程描述。•例子：汽车装配过程39•为了进行性能分析，需要对持续时间，延迟等的时间概念进行建模•因此，每一个托肯都有一个时间戳，而转移确定了产生一个托肯的延迟startwaitingfinishbusyfreeready0139D=3D=0D=0时间的扩展40包含时间属性的交通灯rg1red1yellow1green1yr1gy1rg2red2yellow2green2yr2gy2safe25300552530000041•对复杂的Petri网添加结构信息的方法，与DFD类似•一个子网是对库所，转移和子网的扩展startfinishbusyfreewaitingreadyh1h2h3层次的扩展42waitingreadyh1h2h3startfinishbusyfreebeginendpendingbeginendpending练习：把层次去掉43agenda1PetriNet概述2.经典PetriNet3.高阶Petri网4.一个Petri网建模实例5.小结444一个Petri网建模实例Petri网建立步骤：•根据状态与事件的定义，确定系统的状态集和事件集。•确定系统中状态与事件的关系。•将库所和转移对应起来，建立Petri网模型图。•根据系统情况，决定Petri网模型图的初始状态，确定初始状态的下个状态的Token数。•基于初始状态判断那些事件可被激发，当模型激活后，模型状态图将发生变化，又引起一些事件被触发。45Asimpleexample电子商务的交易流程可用语言描述为:•客户通过浏览信息向商家提交订单意向,商家接到提交的订单意向后,通过查看库存信息形成可供订单;•对可供订单确认后，客户输入用于电子支付的信用卡号和密码;•得到银行的支付确认后,商家将可供订单转为有效订单，同时产生库存信息变更;•商家按有效订单配送货物,并修改库存信息。接着商家进行下次交易的处理。46Petri网建立的模型这个系统的状态(库所)可概括为:P1:客户;P2:可供订单;P3:有效订单和库存信息;P4:商家事件(转移)可概括为:T1:支付确认;T2:查看库存;T3:配送货物。47•不妨认为这个场景有2个Token，通过这两个Token流转完成流程运作：•①（商品）库存•②（客户）订单P1P2T1T2P4P3T348Token①（商品）库存的流动过程；•P4——〉P2——〉P1——〉P3——〉P4•事件：