《建模与仿真(petri网部分).ppt》由会员分享，可在线阅读，更多相关《建模与仿真(petri网部分).ppt（75页珍藏版）》请在三一办公上搜索。
1、建模与仿真,主 讲 人：许 良,Petri网,经济管理学院工业工程系,一、Petri网起源,1962年联邦德国的卡尔A佩特里在他的博士论文用自动机通信中首次使用网状结构模拟通信系统。这种系统模型后来以Petri网为名流传。现在Petri网一词既指这种模型，又指以这种模型为基础发展起来的理论。有时又把Petri网称为网论(net theory)。,Petri网的发展,五十多年来Petri网的理论和应用都有了长足的进步。其发展过程大体可分为三个阶段。60年代，Petri网的研究以孤立的网系统为对象，以寻求分析技术和应用方法为目标。这些内容统称为特殊网论(special net theory)。此处
2、“特殊”是与“一般”或“通用”比较而言，指的就是孤立的网系统个体。,通用网论的(general net theory)研究始于70年代初。以CAPetri为核心的一批科学家以网系统的全体作为对象，研究其分类及各类网之间的关系，发展了以并发论，同步论，网逻辑和网拓为主要内容的理论体系。80年代开始为Petri网综合发展阶段，以理论与应用的结合及计算机辅助工具的开发为主要内容。发展到现在Petri网已经广泛应用于自动化、机械制造、军事指挥等学科领域。,用简单图形较好的表示并发、同步、因果等关系。以网图的方式简洁、直观的模拟离散事件系统目前已得到广泛应用,有限状态机、通信协议、同步控制、生产系统、形
3、式语言、多处理器系统等建模中,二、Petri网基本概念,Petri网是一种网状信息流模型，包括条件和事件两类节点，在条件和事件为节点的有向二分图基础上添加表示状态信息的托肯（token）分布，并按引发规则使得事件驱动状态演变，从而反映系统动态运行过程。通常情况下，用小矩形表示事件（称作变迁）结点，用小圆形表示条件（称作位置）结点，变迁结点之间、位置结点之间不能有有向弧，变迁结点与位置节点之间连接有向弧，由此构成的有向二分图称作网。网的某些位置结点中标上若干黑点（token），从而构成Petri网。,P1,P2,P3,P10,P4,P5,P8,P6,P7,P9,t5,t1,t2,t4,t8,t3
4、,t7,t6,资源：与系统状态变化有关的因素，如原料、产品、工具、设备等状态元素：资源归类后的抽象库所：一个场所，存放状态元素变迁：资源状态变化事件：引起条件的变迁称为事件容量：库所的最大资源数量,resource,state,place,“S”,transition,event,Capability，“K”,一个Petri网是一个三元组P=p1，p2，pm为库所（place）的集合；T=t1，t2，tn为变迁（transition）的集合；F=（PT）（TP）为输入函数和输出函数集，称为流关系。,Petri网数学定义,一个简单的Petri网,Petri网数学定义,三元组N=（P，T；F）构成
5、网（net）的充分必要条件：PT=，规定了库所和变迁是两类不同的元素；PT，表示网中至少有一个元素；F=（PT）(TP)，建立了从库所到变迁、从变迁到库所的单方向联系，并且规定同类元素之间不能直接联系；,容量和权函数定义,设N=（P，T，F）为有向图K为N上P的容量K:P1,2,3,在网图中用库所中的黑点表示，无黑点的表示无穷大W为N上F的权重W：F 1,2,3,在网图中用有向弧上的数字表示，无数字的表示权重为1。,带权重和库所容量的Petri网,Petri 网描述系统的最基本概念是库所和变迁,库所表示系统的状态。变迁表示资源的消耗、使用及使系统状态产生的变化。变迁的发生受到系统状态的控制，即
6、变迁发生的前置条件必须满足；变迁发生后，某些前置条件不再满足，而某些后置条件则得到满足。,图形化表示：以圆圈表示为库所 以粗实线表示变迁 以联结库所与变迁之间的有向弧表示输入输出函数 用令牌（token）表示库所中拥有的资源数量。黑点或数字表示,库所,变迁,库所中令牌分布决定变迁的使能（enabled）和激发（fire），变迁的激发又将改变令牌的分布。,以变迁激发导致令牌在库所间的流动，Petri网可以用于模拟系 统的动态运行过程，反映系统的动态特性。,网N=（P，T；F）构成了描述系统静态结构框架，但还不能描述系统静态结构的全貌。,网论尊重资源有限的事实。实际上，变迁发生所需的资源是有 限的
7、，库所容量也应是有限的。,完整的网系统应指明资源的初始分布，规定变迁的活动原则，确定库所容量和变迁与资源数量之间的关系。,实例1：工业生产线的Petri网模型,有一工业生产线，要完成两项操作，分别为变迁t1和t2表示，变迁t1 将进入生产线的半成品s1s2用两个部件s3固定在一起，后形成中间件s4。然后第2个变迁t2 将s4 和s5用3个部件s3固定在一起形成中间件s6。完成t1和t2 都需要用到工具s7假设受空间限制s2 s5最多不能超过100件，s4最多不能超过5件，s3最多不能超过1000件。,实例2：基于Petri网的柔性制造系统（FMS）建模举例,板材加工FMS主要由以下三部分组成：
8、数控加工设备，包括：数控冲床、数控剪板机和数控折弯机等及其上下料辅助装置；自动化物料运储装置，如立体仓库、堆垛机及上下料小车等；计算机控制及管理系统。,与金属切削FMS相比，板材FMS具有以下特点：零件的种类、批量及复杂程度存在较大差异；板料和零件的出入库等操作以托盘为单位，加工过程则以托盘 上的单张板料或零件为单位；作业计划制定涉及零件混合排样问题，零件种类、排样方法及 调度策略等对机床的换模形式、换模时间以及FMS效率具有重 要影响；板材零件的加工工序较为简单和固定。从板料到零件需要只经 过冲压、剪切和折弯等三道工序，有些零件则只需冲压和剪切 等两道工序。,具有冲压、剪切和折弯单元的板材加
9、工FMS物理配置图,从系统建模角度，将板材加工FMS中的活动分为三类：以冲压和剪切为特征的冲剪操作；冲剪后零件的折弯操作；板料以及冲剪后零件的出入库操作。,采用Petri网建模的基本步骤：划分和定义系统内所有活动及其相互关系；采用Petri网描述上述活动及其关系，得到系统Petri网模型,其中，“”表示变迁，t1t16为系统中的变迁“”表示普通库所，p0p20为普通库所“”表示决策库所，pd0pd7为决策库所,Petri网是一种图形演绎方法，应用Petri网分析系统故障就是将系统所不希望发生的事件作为顶库所，逐步找出导致这一事件的所有可能因素作为中间库所和底库所。故障树可以看作是系统中故障传播
10、的逻辑关系，一般的单调关联故障树只含有与门和或门。故障树可以很方便地用Petri网表示，如与门采用多输入变迁代替，或门采用两个变迁代替。,案例3 Petri网的应用案例,39,与门,或门,故障树表示,Petri网表示,图2,故障树的Petri网模型表示,应用关联矩阵求割集 在故障树分析中，当一些底事件同时发生时，顶事件必然发生，能使顶事件发生的这些底事件的集合就称为割集。如果割集中的任一底事件不发生时，顶事件也不发生，则这样的割集称为最小割集。,关联矩阵是Petri网的主要分析方法之一。在表示Petri网结构的有向图中，库所以圆表示；变迁以矩形表示(图3)。若从库所P到变迁t的输入函数取值为非
11、负整数w，记为I(P，t)=w，用从P到t的一有向弧并旁注w表示；若从变迁t到库所P的输出函数取值为非负整数w，记为O(P，t)=w，用从t到P的一有向弧并旁注w表示。特别地,若w=1,则不必标注；若I(P，t)=0或O(P，t)=0,则不必画弧。I与O均可表示为nxm非负整数矩阵，O与I之差(AT=O-I)称为关联矩阵。这里我们探讨规范网，所以w=1。,求图3中Petri网模型的关联矩阵：,求图3中Petri网模型的关联矩阵：,(1)找出关联矩阵中只有1和0，没有-1的行，则该 行对应的为顶库所（只有输入库所，没有输出库所），由此库所开始寻找（在此关联矩阵中为最后一行）。(2)由顶库所对应行
12、的1出发按列寻找到-1，此-1所对应行代表的库所为顶库所的一个输入库所，如果该列有多个-1，则说明对应同一变迁有多个输入库所，并且输入的库所为“相与”关系。,割集求解步骤,(3)由步骤（2）中找到的-1按行寻找1，如有1 则说明该库所为中间库所，继续按步骤（2）所述循环查找，直到所在行没有1为止。没有1，则说明该库所是一个底库所即基本事件。如果该行有多个1，则说明由这些1对应的库所对应多个变迁，应为“相或”关系。(4)按步骤（2）、步骤（3）继续查找，直到查找到最底层库所。,(5)按照上面的“相与”“相或”关系将底 库所展开,则得到所有割集。(6)按照布尔吸收律、等幂率或素数法可求得最小割集。
13、注：布尔吸收律A+AB=A A(A+B)=A,四、Petri网的行为特性,与其它建模方法相比，Petri网的优点不仅表现在建模能力上，更主要表现在它所具有的分析能力上。,Petri网具有一些专门的分析手段，对系统活性（liveness）及死锁（deadlock）进行分析，分析系统中的顺序、并发及冲突等复杂事件关系。,采用可达树（reachability tree）理论分析系统的有界性（boundness）与安全性（safety）等,顺序关系,并发关系,1 可达性,是研究任何系统动态特性的基础,决定系统能否到达一个指定的状态.(1)系统按照一定的流程运行，系统是否能够实现一定的状态；或者不期望的
14、状态不出现。比如：生产调度计划的验证（按照一定的生产调度计划进行生产，一定的生产任务是否能够完成）（2）要求到达一定的状态，如何确定系统的运行轨迹（流程）。比如：生产调度，如何安排作业顺序？,死锁关系,2 活性,在系统中用于检测是否存在死锁。一个系统存在的一个潜在问题是死锁，为了避免死锁，系统的Petri网模型必须具有活性。（1）互斥：同时争夺唯一资源（2）占用且等待（3）无抢占（4）循环等待,冲突的实质是竞争资源。,冲突就是指这种两者都有发生权，但在同一时刻只能有一个发 生的关系。,逻辑关系图：冲突（互斥）冲撞关系,冲突双方谁先发生由系统实际运行环境及状态决定，即谁有优 先权是不确定的。,冲
15、突又称为选择（choice）或不确定（nondeterminism），是对系统性能影响最大的事件类型。,3 有界性,是一个非常重要的特性,它保证系统在运行过程中不会需要无限的资源.有界性反映一个库所在系统运行过程中能够获得的最大的令牌数,即所能获得的最大资源数,它与系统的初始令牌有关.在实际系统设计中,必须使网络中的每个库所在任何状态下的令牌数小于库所的容量,这样才能保证系统的正常运行。,4 安全性（是否会溢出）,决定系统中正在执行的操作不会发出请求.若Petri网为1有界,则称此Petri网是安全的.这种网的每一个库所 要么有一个令牌，要么 没有令牌。安全性是有 界性的一种特殊情况。,5 可
16、逆性和回家状态（主宿状态）,在制造业系统和过程控制系统中存在着一个重要的问题：错误复原，即系统能否重新回到原来状态(保证系统的循环特性)。可逆系统可自生初始化主宿（回家）系统经过有限步骤，将回到期望状态,6 守恒性,在一个Petri网系统中,令牌被用来描述系统资源,对这类Petri网,守恒性是一个重要性质,要使代表资源的令牌在Petri网运行中既不会增加也不会减少,最简单的方法就是网中总令牌数保持恒定。,基本逻辑关系表达：顺序、并发、冲突、异或、死锁事例与进程，进程的合成,顺序,并发,异或,冲突,死锁,Petri网性能分析,覆盖树（Coverability tree）可达图不变量（Invari
17、ation）,覆盖树性能分析法,1、标识向量m初始标识m0=(1 1 0 0 0)T标识m1=(0 0 1 0 0)T m2=(0 0 0 1 1)T,覆盖的数学定义,分析步骤,1、m0作为“树根”（可作上new记号）2、对有new记号的标识m做以下事情，否则终止；3、选择某一“new”标识m；（1）若m与树中间已有的其他标识m相同，则将其记为“old”，转向其他“new”标识；（2）若在m下无变迁使能，则将m记为“dead end”；4、对于m下有使能的所有变迁t，做以下事情：（1）激发t，产生标识m；（2）若从树根至m的路径上存在一标识m,使得m覆盖m，但m 不等于m（mm）,则对于那些使
18、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是可逆的。(包含的树无法确定活性),基本性能分析,基本Petr
19、i网：每个库所容量为1，这样库所可称为条件，变迁可称为事件。故又称为条件/事件系统 C/E低级Petri网：库所容量和权重为=1的任意整数，称为库所/变迁网。简作P/T网定时Petri网：将各事件的持续时长标在库所旁边，库所中新产生的标记经过一须时间后才加入到网中，或是标在变迁上，经过时间延迟后发生。高级Petri网：谓词/事件网、染色网、随机网等。,Petri网类型,Petri网模型特点,模拟性：从组织结构的角度，模拟系统的控制和管理，不涉及系统实现所依赖的物理和化学原理；客观性：精确描述事件（变迁）间的依赖（顺序）关系和不依赖（并发）关系。这种关系客观存在，与观察无关；描述性：用统一的语言
20、（网）描述系统结构和系统行为；,流特征：适合描述以有规则的流动为行为特征的系统，包括能量流、物质流和信息流；分析性：网系统具有与应用环境无关的动态行为，是可以独立研究的对象。这样，可按特定方式进行系统性质的分析和验证；基础性：网系统在各个应用领域得到不同的解释，是沟通不同领域的桥梁。网论是这些领域的共同理论基础。,petri网的应用领域,(1)通讯协议的验证 通讯协议的验证是Petri网应用最为成功的领域之一最初应用在70年代初期，由于 Petri网以形式语言作为基础，可形式化地 对通信协议进行正确性验证。(2)计算机通讯网络性能评价及多媒体应用 随着计算机网络技术和信息技术的发展，对网络进行
21、性能分析的需要，不仅出现于企业内部的生产控制的局域总线网，而且出现于光纤局域网或ATM网中。,(3)软件工程 由于产品开发中的竞争和革新需要，导致产品开发者面临巨大压力.在软件工程中Petri网主要用于软件系统的建模和分析，比较成熟的是加色Petri网，可以用于大型软件系统的设计、说明、仿真、确认和实现，在软件开发生命周期的各个阶段，Petri网都可以得到很好的应用。(4)知识处理 Petri网可用于Al中的知识表达和推理的形式化模型的建立，可以表达各个活动之间的各种关系，如顺序关系、与关系、或关系等，并可在模型基础上通过已知的初始状态和初始条件进行逻辑推理。,(5)FMS的建模、分析和控制 柔性制造系统(FMS)对于现代制造业具有重要作用，Petri网由于其自身优点，在制造系统中应用广泛，如带缓冲区的简单生产线、机床加工中心、自动生产线、柔性制造系统和及时加工系统。(6)系统可靠性分析 系统的可靠性不仅包括硬件的可靠性、也包括软件可靠性.利用随机Petri网对系统进行可靠性分析，对软件复用、软件可靠性分析。,建模：结构健壮性 逻辑合理性编程流程图Petri net，活动周期法等仿真：系统重现 效果优化JAVA,C#,C+UG，CAD动态效果Arena，flexsim等,
