8.4.1-Petri网基本知识简介

8.4.1Petri网基本知识简介Petri网库所place变迁transistionPetri网由两类元素组成：库所（place）和变迁（transistion），前者表示状态，后者反映状态的变化。变迁的作用是改变系统的状态，库所的作用则是决定变化能否发生。两者的这种相互依赖关系用有向弧（流关系）表示。网是系统的静态结构。图8-22给出了一个Petri网和网系统的例子。图中用圆圈表示库所，用短横表示变迁（也有用方框表示的）。库所中的黑点称为托肯（token），用以表示某类资源，反映了系统的局部状态，托肯在库所中的分布，给出了各状态元素的初态，称为初始标识（initialmarking），反映出系统初始情况下的全局状态。如果库所中的托肯数不多于一个，与布尔型变量类似的库所只有两种状态：有托肯（成真）和无托肯（成假）。我们把这样的网系统称为条件（condition）/事件（event）系统，简称C/E系统。当网系统中的托肯在网中流动时，就反映了网的动态行为。托肯是沿有向弧指示的方向流动的。图8-22中，对于变迁e3来说，从库所b1有一条指向它的有向弧，用（b1，e3）表示，称为输入弧；同时还有另外两条输出弧，用（e3，b3）、（e3，b4）表示。网论中将b1称为e3的输入库所，b3、b4称为它的输出库所，由输入库所组成的集合叫输入库所集，又称为前集，记为*e3={b1}；由输出库所组成的集合叫做输出库所集，又称后集，记为e3*={b3，b4}。同理，对于库所b1，它的输入变迁集（前集）为*b1={e2}，输出变迁集（后集）为b1*={e1，e3}。一个变迁，如果它的每一个输入库所都包含至少一个托肯时，则这个变迁有发生权，当这个变迁发生时，将导致在其每个输入库所中减少一个托肯，而在每个输出库所中增加一个托肯。图8-22中，变迁e3的发生将“消耗”b1中的一个资源，同时产生b3类和b4类各一个资源，这就是变迁规则。变迁的发生，改变了系统的状态，同时又使其它一些变迁具有发生权。值得注意的是，有发生权的变迁并不意味着立即发生，只是说明有发生的可能性而已。以上初步了解了Petri网的组成，下面给出Petri网的形式化定义。=（S，T；F，K，W，M0）构成P/T系统的条件是：六元组的基网，S和T分别称为N的库所集和变迁集，F为流关系；（1）N=（S，T；F）是一个网，称为表示无穷大；}，是库所集上的容量函数，N+={1，2，3…}，（2）K：S→N+∪{（3）W：F→N+，是弧集上的权函数；的标识，M0称为初始标识；S：M（s）≤K（s），M称为s（4）M：S→N0，并满足中变迁发生的条件以及发生的结果如下：P/T系统。t*：M（s）≤K（s）-W（t，s），则称t在标识M下有发生权，记为M[s*t：M（s）≥W（s，t），且sT，如果（1）对于tS：s（2）如果t在标识M下发生，得到新的标识M’，M'。从M发生t得到M’记为M[对于P/T系统而言，当变迁的输入库所中的托肯数大于等于该变迁输入弧的权，且发生后不致使输出库所中的托肯数超过它的容量时，变迁有发生权。变迁的发生使它的输入库所中的托肯数减少，输出库所中的托肯数增加，减少或增加的托肯数由相应的弧的权决定，但库所是有容量限制的，库所中托肯的数量不能超过它的容量。当库所的容量和弧的权都为1时，这就成为C/E系统；当权为1而容量无限时，这就是狭义的Petri网。理论证明，P/T系统可以改造成为这样的Petri网系统。=（S，T；F，M0），其中S={s1，s2，…，sm}，T={t1，t2，…，tm}，称Petri网可以用线性代数的方法来表示。设n]m[Cijn=[Cij+]mCC=C+为的关联矩阵，其中）到达M，M可用状态方程当用m维列向量来表示标识M时，即M=[M(s1)，M(s2)，…，M(sm)]T，这样，Petri网从M0经过一系列的变迁发生（发生序列M=M0+CX中出现的次数。推导出来。其中X是一个n维列向量，它的第j个分量是变迁tj在发生序列现在我们给出几个基本概念：1．冲突图8-22中，在给定的初始标识下，e1和e3都能发生，但不能同时发生，它们共享b1中的一个资源。这种现象称为冲突。冲突的引起本质上是由系统的结构决定的，因此存在结构冲突。但如果b1中有两个托肯，则不会发生冲突。因此，冲突的外部条件是由于资源缺乏，在资源缺乏的情况下，结构冲突变成了实际的冲突。网论认为，解决冲突需要从环境中得到“指示”，这也正是环境可以对系统控制的地方。2．冲撞图8-22中，如果b3中也有一个托肯，如果它又是一个C/E系统，即库所的容量为1。这时e3不能发生，因为e3如果发生，将超过b3的容量，这种现象称为冲撞：在b3处有（可能的）冲撞。一个网系统在所有可达标识下都不可能有冲撞，则称该系统是无冲撞系统。3．并发在图8-22中，如果e3发生，则b1失去托肯，而b3、b4中各得一个托肯。这时，e4、e5都可发生，它们的发生是相互独立的，网论中称它们为并发。网论并不规定它们发生的顺序，它们是异步的。4．可达性，则称标识M是可达的，记为M0[在一个Petri网中，如果存在一个从M0到M的发生序列M。所有从M0可达的标识组成的集合，叫做可达标识集，记为R（M0）。5．有界性S，都有M（s）≤K，则称这一Petri网K有界或简称有界。sR（M0），M对于一个Petri网，如果存在一个正整数K，使得M0的任一可达标识的每个库所中的托肯数都不超过K，即6．活性一个Petri网，如果从M0可达的任一标识出发，对于任一变迁，都可以通过一变迁发生序列而最终使该变迁发生，则称这一Petri网是活的。7．死锁R（M0），在M下所有的变迁都没有发生权，则称M是一个死锁（有作者称之为死标识）。如果对于M8．不变量如果一个Petri网系统中有一些库所，这些库所中的托肯数的总和在任何可达标识下均为常数，则这些库所就是系统的S-不变量。如果Petri网系统中有一些变迁，它们的发生会使网系统的标识回到它们开始发生时的状态，则称这些变迁就是网系统的一个T-不变量。S-不变量和T-不变量是由网的结构性质所决定的，与初始标识无关。在图8-22中，b1、b2、b3、b5组成一个S-不变量，b1、b2、b4、b6也是一个S-不变量。e3、e4、e5、e6组成一个T-不变量，e1、e2也组成一个T-不变量。前面已经提到，一个变迁有发生权并不一定发生，只是有发生的可能性。对于实际系统而言，发生通常是有条件的，为此，人们引出了同步Petri网。图8-23是一个同步Petri网的例子，它表示状态重复变化的系统。例如一台电动机，首先处于停止状态，然后起动，再停止等等。图中t1有发生权但不能发生，只有当外界事件（即起动命令）发生时，t1才能发生。图8-24是受控离散系统的一部分。图中有三个盛放液体的罐子V1、V2和V3，其中V1、V2是用来测量的，M是搅拌系统的驱动电机。系统停止时，指示灯Y0亮。当起动按钮按下时（X0=1），阀Y1、Y2打开，两种不同的液体F1、F2分别注入V1、V2。V1中的液体到达X1位置时，Y1关闭，阀Y3打开；V2中的液体到达X3时Y2关闭，Y4打开。当V3中液体到达X5时，Y5=1，M起动，搅拌液体使其充分混合；V1中的液体低于X2时，Y3关闭；V2中的液体低于X4时，Y4关闭；V1、V2两罐液体均到达下限位置时，阀Y6打开；V3中液体低于X6时，Y6关闭，指示灯亮，重新回到原来状态。图8-25是该系统的控制解释Petri网模型，库所与动作关联。