PETRI网建模理论基础

5.Petri网建模理论基础1962年德国学者CarlA.Petri在其博士论文中提出的描述事件和条件关系的网络用简单图形较好的表示并发、同步、因果等关系。以网图的方式简洁、直观的模拟离散事件系统目前已得到广泛应用,有限状态机、通信协议、同步控制、生产系统、形式语言、多处理器系统等建模中petri网的应用领域(1)通讯协议的验证通讯协议的验证是Petri网应用最为成功的领域之一最初应用在70年代初期，由于Petri网以形式语言作为基础，可形式化地对通信协议进行正确性验证。(2)计算机通讯网络性能评价及多媒体应用随着计算机网络技术和信息技术的发展，对网络进行性能分析的需要，不仅出现于企业内部的生产控制的局域总线网，而且出现于光纤局域网或ATM网中。(3)软件工程由于产品开发中的竞争和革新需要，导致产品开发者面临巨大压力.在软件工程中Petri网主要用于软件系统的建模和分析，比较成熟的是加色Petri网，可以用于大型软件系统的设计、说明、仿真、确认和实现，在软件开发生命周期的各个阶段，Petri网都可以得到很好的应用。(4)知识处理Petri网可用于Al中的知识表达和推理的形式化模型的建立，可以表达各个活动之间的各种关系，如顺序关系、与关系、或关系等，并可在模型基础上通过已知的初始状态和初始条件进行逻辑推理。(5)FMS的建模、分析和控制柔性制造系统(FMS)对于现代制造业具有重要作用，Petri网由于其自身优点，在制造系统中应用广泛，如带缓冲区的简单生产线、机床加工中心、自动生产线、柔性制造系统和及时加工系统。(6)系统可靠性分析系统的可靠性不仅包括硬件的可靠性、也包括软件可靠性.利用随机Petri网对系统进行可靠性分析，对软件复用、软件可靠性分析。5.1基本概念资源：与系统状态变化有关的因素，如原料、产品、工具、设备等状态元素：资源归类后的抽象库所：一个场所，存放状态元素变迁：资源状态变化事件：引起条件的变迁称为事件容量：库所的最大资源数量resourcestateplace,“S”transitioneventCapability，“K”Petri网数学定义一个Petri网是一个三元组P={p1，p2，…，pm}为库所（place）的集合；T={t1，t2，…，tn}为变迁（transition）的集合；F=（P×T）∪（T×P）为输入函数和输出函数集，称为流关系。(,,)NPTF三元组N=（P，T；F）构成网（net）的充分必要条件：①P∩T=ф，规定了库所和变迁是两类不同的元素；②P∪T≠ф，表示网中至少有一个元素；③F=（P×T）∪(T×P)，建立了从库所到变迁、从变迁到库所的单方向联系，并且规定同类元素之间不能直接联系；一个简单的Petri网P1P4P5P3P2t1t3t2Petri网描述系统的最基本概念是库所和变迁变迁的发生受到系统状态的控制，即变迁发生的前置条件必须满足；变迁发生后，某些前置条件不再满足，而某些后置条件则得到满足。库所表示系统的状态。变迁表示资源的消耗、使用及使系统状态产生的变化。图形化表示：以圆圈表示为库所以粗实线表示变迁以联结库所与变迁之间的有向弧表示输入输出函数用令牌（token）表示库所中拥有的资源数量。——黑点或数字表示P1P4P5P3P2t1t3t242库所变迁库所中令牌分布决定变迁的使能（enabled）和激发（fire），变迁的激发又将改变令牌的分布。以变迁激发导致令牌在库所间的流动，Petri网可以用于模拟系统的动态运行过程，反映系统的动态特性。网N=（P，T；F）构成了描述系统静态结构框架，但还不能描述系统静态结构的全貌。网论尊重资源有限的事实。实际上，变迁发生所需的资源是有限的，库所容量也应是有限的。完整的网系统应指明资源的初始分布，规定变迁的活动原则，确定库所容量和变迁与资源数量之间的关系。实例1：工业生产线的Petri网模型有一工业生产线，要完成两项操作，分别为变迁t1和t2表示，变迁t1将进入生产线的半成品s1s2用两个部件s3固定在一起，后形成中间件s4。然后第2个变迁t2将s4和s5用3个部件s3固定在一起形成中间件s6。完成t1和t2都需要用到工具s7假设受空间限制s2s5最多不能超过100件，s4最多不能超过5件，s3最多不能超过1000件。Petri网模型S1S6S7S4t1t2S2S3S5K=100K=1000K=100K=523实例2：基于Petri网的柔性制造系统（FMS）建模举例板材加工FMS主要由以下三部分组成：①数控加工设备，包括：数控冲床、数控剪板机和数控折弯机等及其上下料辅助装置；②自动化物料运储装置，如立体仓库、堆垛机及上下料小车等；③计算机控制及管理系统。与金属切削FMS相比，板材FMS具有以下特点：①零件的种类、批量及复杂程度存在较大差异；②板料和零件的出入库等操作以托盘为单位，加工过程则以托盘上的单张板料或零件为单位；③作业计划制定涉及零件混合排样问题，零件种类、排样方法及调度策略等对机床的换模形式、换模时间以及FMS效率具有重要影响；④板材零件的加工工序较为简单和固定。从板料到零件需要只经过冲压、剪切和折弯等三道工序，有些零件则只需冲压和剪切等两道工序。具有冲压、剪切和折弯单元的板材加工FMS物理配置图Petri网（Petrinet）从系统建模角度，将板材加工FMS中的活动分为三类：①以冲压和剪切为特征的冲剪操作；②冲剪后零件的折弯操作；③板料以及冲剪后零件的出入库操作。采用Petri网建模的基本步骤：①划分和定义系统内所有活动及其相互关系；②采用Petri网描述上述活动及其关系，得到系统Petri网模型板材加工FMS的Petri网模型其中，“▕”表示变迁，t1～t16为系统中的变迁“◯”表示普通库所，p0～p20为普通库所“◎”表示决策库所，pd0～pd7为决策库所Petri网（Petrinet）Petri网（Petrinet）Petri网（Petrinet）5.2Petri网的行为特性：与其它建模方法相比，Petri网的优点不仅表现在建模能力上，更主要表现在它所具有的分析能力上。Petri网具有一些专门的分析手段，对系统活性（liveness）及死锁（deadlock）进行分析，分析系统中的顺序、并发及冲突等复杂事件关系。采用可达树（reachabilitytree）理论分析系统的有界性（boundness）与安全性（safety）等5.2.1顺序关系P1t1P2P3t25.2.2并发关系P1t1P2P3t2P4P5t35.2.3可达性是研究任何系统动态特性的基础,决定系统能否到达一个指定的状态.(1)系统按照一定的流程运行，系统是否能够实现一定的状态；或者不期望的状态不出现。比如：生产调度计划的验证（按照一定的生产调度计划进行生产，一定的生产任务是否能够完成）可达性（2）要求到达一定的状态，如何确定系统的运行轨迹（流程）。比如：生产调度，如何安排作业顺序？死锁关系P1t1P2P3t2P4t3P5P6t45.2.4活性在系统中用于检测是否存在死锁。一个系统存在的一个潜在问题是死锁,为了避免死锁,系统的Petri网模型必须具有活性.（1）互斥：同时争夺唯一资源（2）占用且等待（3）无抢占（4）循环等待逻辑关系图：冲突（互斥）\冲撞关系P1t1P2P3t2P4t3冲突的实质是竞争资源。冲突就是指这种两者都有发生权，但在同一时刻只能有一个发生的关系。冲突双方谁先发生由系统实际运行环境及状态决定，即谁有优先权是不确定的。冲突又称为选择（choice）或不确定（nondeterminism），是对系统性能影响最大的事件类型。5.2.5有界性是一个非常重要的特性,它保证系统在运行过程中不会需要无限的资源.有界性反映一个库所在系统运行过程中能够获得的最大的令牌数,即所能获得的最大资源数,它与系统的初始令牌有关.在实际系统设计中,必须使网络中的每个库所在任何状态下的令牌数小于库所的容量,这样才能保证系统的正常运行。5.2.6安全性（是否会溢出）决定系统中正在执行的操作不会发出请求.若Petri网为1有界,则称此Petri网是安全的.这种网的每一个库所要么有一个令牌,要么没有令牌.安全性是有界性的一种特殊情况.5.2.7可逆性和回家状态（主宿状态）在制造业系统和过程控制系统中存在着一个重要的问题：错误复原，即系统能否重新回到原来状态(保证系统的循环特性)。可逆——系统可自生初始化主宿（回家）——系统经过有限步骤，将回到期望状态5.2.8守恒性在一个Petri网系统中,令牌被用来描述系统资源,对这类Petri网,守恒性是一个重要性质,要使代表资源的令牌在Petri网运行中既不会增加也不会减少,最简单的方法就是网中总令牌数保持恒定.Petri网性能分析：覆盖树（Coverabilitytree）——可达图不变量（Invariation）•1、标识向量m•初始标识m0=(11000)T•标识m1=(00100)T•m2=(00011)T覆盖树性能分析法覆盖的数学定义：kkktokenmmmm),(m)(mp121212；；都有：对于任意正数（令牌，托肯）概念。，表示无穷大的再引入一个特别符号。表示为覆盖则标识：若ppP分析步骤1、m0作为“树根”（可作上new记号）2、对有new记号的标识m做以下事情，否则终止；3、选择某一“new”标识m；（1）若m与树中间已有的其他标识m相同，则将其记为“old”，转向其他“new”标识；（2）若在m下无变迁使能，则将m记为“deadend”；4、对于m下有使能的所有变迁t，做以下事情：（1）激发t，产生标识m’；（2）若从树根至m’的路径上存在一标识m’’,使得m’覆盖m’’，但m’’不等于m’（m’m’’）,则对于那些使m’(p)m’’(p)成立的p：用ω取代m’(p);（3）以m’为一节点，从m到m’画一有向线，将其记为t，并将m’记为“new”5、除去m的“new”标志，回到步骤2举例：建立覆盖树基本性能分析•当且仅当树中所有节点上均不出现ω时，PN网是有界的；（可以在树中找出所有库所中最大的托肯数K，称为PN是K有界的）•当且仅当树中所有的节点上仅包含0或1时，则PN网是安全的。否则没有记为ω的库所是安全的。•在不包含ω的树中，若给定任何2个节点之间，都存在一有向路径，在该路径上所有变迁都出现，则PN是活的。(包含ω的树无法确定活性)•在不包含ω的树中，若从任何节点到根节点之间都存在一有向路径，则PN是可逆的。(包含ω的树无法确定活性)建模工具与仿真工具的区别建模：结构健壮性逻辑合理性编程流程图\结构材料剪应力、拉伸力校核\Petrinet，活动周期法等仿真：系统重现效果优化JAVA,C#,C++\UG，CAD动态效果\Arena，flexsim等作业：写出下面作业流程Petri网的覆盖树，并评价该流程性能如何。（参照前例）Petri网类型基本Petri网：每个库所容量为1，这样库所可称为条件，变迁可称为事件。故又称为条件/事件系统C/E低级Petri网：库所容量和权重为=1的任意整数，称为库所/变迁网。简作P/T网定时Petri网：将各事件的持续时长标在库所旁边，库所中新产生的标记经过一须时间后才加入到网中，或是标在变迁上，经过时间延迟后发生。高级Petri网：谓词/事件网、染色网、随机网等Petri网（Petrinet）作业：撰写一篇本课程论文要求：（1）11周上交，A4纸论文打印稿和电子稿。（2）论文方向：生产、制造领域，或商业服务领域是如何应用仿真建模等技术的。（要有自己的观点）（3）题目自拟。论文页数不少于5页。（4）可以上网查阅资料、文献、书籍，但不许抄袭，如果发现抄袭平时成绩0分。论文格式•必须包括：•题目（宋体，小二，加粗）•姓名、学号（宋体，小四）•摘要（宋体，小四）•引言（宋体，小四）•正文（宋体，小四）•结论（宋体