petri网理论

1Petri网理论280年代开始为Petri网综合发展阶段，以理论与应用的结合及计算机辅助工具的开发为主要内容。1986年的第二届夏季培训斑是又一次阶段性总结，讲稿集结为LNCS254和255两1962年联邦德国的卡尔·A·佩特里在他的博士论文《用自动机通信》中首次使用网状结构模拟通信系统。这种系统模型后来以Petri网为名流传。现在Petri网一词既指这种模型，又指以这种模型为基础发展起来的理论。有时又把Petri网称为网论(nettheory)。Petri网起源3五十多年来Petri网的理论和应用都有了长足的进步。其发展过程大体可分为三个阶段。60年代，Petri网的研究以孤立的网系统为对象，以寻求分析技术和应用方法为目标。这些内容统称为特殊网论(specialnettheory)。此处“特殊”是与“一般”或“通用”比较而言，指的就是孤立的网系统个体。Petri网的发展4通用网论的(generalnettheory)研究始于70年代初。以C．A．Petri为核心的一批科学家以网系统的全体作为对象，研究其分类及各类网之间的关系，发展了以并发论，同步论，网逻辑和网拓为主要内容的理论体系。80年代开始为Petri网综合发展阶段，以理论与应用的结合及计算机辅助工具的开发为主要内容。发展到现在Petri网已经广泛应用于自动化、机械制造、军事指挥等学科领域。Petri网的发展5Petri网基本概念Petri网是一种网状信息流模型，包括条件和事件两类节点，在条件和事件为节点的有向二分图基础上添加表示状态信息的托肯（token）分布，并按引发规则使得事件驱动状态演变，从而反映系统动态运行过程。通常情况下，用小矩形表示事件（称作变迁）结点，用小圆形表示条件（称作位置）结点，变迁结点之间、位置结点之间不能有有向弧，变迁结点与位置节点之间连接有向弧，由此构成的有向二分图称作网。网的某些位置结点中标上若干黑点（token），从而构成Petri网。6P1P2P3P10P4P5P8P6P7P9t5t1t2t4t8t3t7t6网系统演示：图17模拟性：从组织结构的角度，模拟系统的控制和管理，不涉及系统实现所依赖的物理和化学原理；客观性：精确描述事件（变迁）间的依赖（顺序）关系和不依赖（并发）关系。这种关系客观存在，与观察无关；描述性：用统一的语言（网）描述系统结构和系统行为；Petri网模型特点8流特征：适合描述以有规则的流动为行为特征的系统，包括能量流、物质流和信息流；分析性：网系统具有与应用环境无关的动态行为，是可以独立研究的对象。这样，可按特定方式进行系统性质的分析和验证；基础性：网系统在各个应用领域得到不同的解释，是沟通不同领域的桥梁。网论是这些领域的共同理论基础。Petri网模型特点9Petri网是一种图形演绎方法，应用Petri网分析系统故障就是将系统所不希望发生的事件作为顶库所，逐步找出导致这一事件的所有可能因素作为中间库所和底库所。故障树可以看作是系统中故障传播的逻辑关系，一般的单调关联故障树只含有与门和或门。故障树可以很方便地用Petri网表示，如与门采用多输入变迁代替，或门采用两个变迁代替。Petri网的应用10与门或门故障树表示Petri网表示故障树的Petri网模型表示图211Petri网的图形表示方法更为形象、直观，可以表达故障的动态传递过程。从图2中可以看出，用Petri网的基本元素—库所和变迁的不同连接可以表示故障树模型的不同逻辑关系，可以充分利用图论的方法来解决故障模型的诊断推理问题。12P3t1P5P1P2P4t2t3图3故障树模型和其对应的Petri网模型举例：13应用关联矩阵求割集在故障树分析中，当一些底事件同时发生时，顶事件必然发生，能使顶事件发生的这些底事件的集合就称为割集。如果割集中的任一底事件不发生时，顶事件也不发生，则这样的割集称为最小割集。14关联矩阵是Petri网的主要分析方法之一。在表示Petri网结构的有向图中，库所以圆表示；变迁以矩形表示(图3)。若从库所P到变迁t的输入函数取值为非负整数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网模型的关联矩阵：P3t1P5P1P2P4t2t3求图3中Petri网模型的关联矩阵：17(1)找出关联矩阵中只有1和0，没有-1的行，则该行对应的为顶库所（只有输入库所，没有输出库所），由此库所开始寻找（在此关联矩阵中为最后一行）。(2)由顶库所对应行的1出发按列寻找到-1，此-1所对应行代表的库所为顶库所的一个输入库所，如果该列有多个-1，则说明对应同一变迁有多个输入库所，并且输入的库所为“相与”关系。割集求解步骤18(3)由步骤（2）中找到的-1按行寻找1，如有1则说明该库所为中间库所，继续按步骤（2）所述循环查找，直到所在行没有1为止。没有1，则说明该库所是一个底库所即基本事件。如果该行有多个1，则说明由这些1对应的库所对应多个变迁，应为“相或”关系。(4)按步骤（2）、步骤（3）继续查找，直到查找到最底层库所。割集求解步骤19(5)按照上面的“相与”“相或”关系将底库所展开,则得到所有割集。(6)按照布尔吸收律、等幂率或素数法可求得最小割集。注：布尔吸收律A+AB=AA(A+B)=A割集求解步骤20开始找到只有0和1的行，并记下值为1的列数Ai(i=1,2,3,…,m),i=0找到Ai列中值为-1的行数Bj(j=1,2,3,…,n),j=0找到Bj中值为1的列数Ck(i=1,2,3,…,P),k=0利用布尔吸收率、等幂率得到最小割集i++;i≤m?k++;k≤P?j++;j≤n?YYNNNAi各列对应库所为“相或”关系Bj各列对应库所为“相或”关系Ck各列对应库所为“相或”关系结束程序流程图21P5t1P1P2t2P4P3图4（a）故障树模型（b）Petri网模型求含重复事件的Petri网模型的最小割集在故障树建模过程中会出现重复事件,即树中的两个图元代表同一事件。这样的重复事件应用Petri网模型可以用同一个库所表示,如图下图所示。t322由图4a中可以看出B1为重复事件，在对应的Petri网模型中P1为与B1相对应的重复事件，可见用Petri网模型表达不但图形简单明了，而且算法简便，没有相同序号的图形出现。图4b中Petri网模型的关联矩阵如下：10001311100201011154321tttpppppAT23应用关联矩阵法按前述步骤查找，可得：顶库所为P5，由第5行中的1向上查找可知P3、P4为“相与”事件，两者同时与P1“相或”。而P4又为P1、P2的“相与”事件。所以P5=P1+P3P4=P1+P1P2P3，从而最小割集为P1。24应用上面提出的算法求解一个简单的舰艇防空系统故障的最小割集，其故障树模型及Petri网模型如图5所示。实例分析图(5-1)防空系统故障树25P13P1P4P7P3t1t2P6P8P5t3t4P10P9t7t8P12P11t9t10t6t5P2图(5-2)防空系统故障树对应Petri网模型26由图5可以写出关联矩阵如下:27(1)搜索此关联矩阵,找出没有-1即顶库所在行为第13行，记录下每个1所在的列分别为第7、8、9、10列。(2)从第7列出发，搜索此列记录下这一列中-1所在的行为第9行。(3)继续搜索第9行，记录下这一行中1所在的列为5,并且第5列中对应有两个-1，则说明这两个-1所对应的库所P1、P2同为P9的输入库所，则P1、P2为“相与”关系，即P9=P1P2。28(4)再从第8列出发即搜索第10行,只有一个底库所为P10。(5)从第9列出发，搜索第11行，重复步骤(2)、(3),可得P11=P7P8=(P3+P4)(P5+P6)。(6)搜索第12行只有一个底库所为P12。(7)根据上述步骤,即有:P13=P9+P10+P11+P12=P1P2+P10+(P3+P4)(P5+P6)+P12。29(8)再应用布尔吸收率即可求得最小割集为{P1,P2}、{P10}、{P12}、{P3,P5}、{P4,P5}、{P3,P6}、{P4,P6}。上述方法充分利用了Petri网的理论,使Petri网的图形方法与其关联矩阵有效结合,更易于最小割集的求取。31故障树将系统所不希望发生的事件(故障事件)作为分析的目标，逐级找出导致这一事件发生的所有可能因素。故障树采用相应的符号表示这些事件,再用描述事件间逻辑因果关系的逻辑门符号把顶事件、中间事件与底事件连接成倒立的树状图形，用以表示系统特定顶事件与其各子系统或各元件的故障事件及其他有关因素之间的逻辑关系。故障树