Petri网及其应用.

Presentation on theme: "Petri网及其应用."— Presentation transcript:

1 Petri网及其应用

2 一、Petri网的起源与发展 二、基本Petri网 Petri网的定义 Petri网的结构 Petri网的运行规则 三、基本PN的性能 四、PN的基本分析方法 五、Petri网的特点 六、PN的应用及难点

3 Petri网的起源与发展 Petri网最早是由卡尔·A·佩特里于1962年在他的博士论文提出的，用来描述计算机系统事件之间的因果关系。早期Petri网主要应用于计算机与信息处理领域，后来具有工程背景的研究人员将Petri网方法用在工程系统尤其是自动制造系统的研究。40多年来， Petri网不断的充实和发展，日臻完善，在计算机、自动化、通信、交通、电力与电子、服务以及制造等领域得到广泛的应用。

4 系统的状态随离散事件发生而瞬时改变,不能用通常的动态方程来描述,一般称这类系统为离散事件动态系统。
Petri网采用可视化图形描述，用形式化的数学方法支持，表达离散事件动态系统（Discrete Event Dynamic System，DEDS）的静态结构和动态变化；它是一种结构化的DEDS描述工具，可以描述系统异步、同步、并行逻辑关系；既能够分析系统运行性能（如制造系统设备利用率、生产率、可靠性等），又可以用于检查与防止诸如自动系统的锁死、堆栈溢出、资源冲突等不期望的系统行为性能；能够直接从可视化的Petri网模型产生DEDS监控控制编码；还可以用于DEDS的仿真，从而通过结构变化描述系统的变化。

5 Petri网的结构 库所（Place）圆形节点 变迁（Transition）方形节点
有向弧（Connection）是库所 和变迁之间的有向弧 令牌（Token）是库所中的动态对象（用库所p中圆点表示），可以从一个库所移动到另一个库所 经典Petri网

6 注意！ 有向弧是有方向的 两个库所或变迁之间不允许有弧 库所可以拥有任意数量的令牌 有两个变迁都被允许的可能，但是一次只能发生一个变迁

7 Petri网的定义 定义2.1 PN的结构是由4要元描述的一有向图： PNS=（P，T，I，O） 此处：
（1）P={p1，…，pn}是库所的有限集合，n>0为库所的个数； （2）T={t1，…，tm}是变迁的有限集合，m>0为库所的个数； P∩Ｔ=⊙（空集） （3）I：P×T→N是输入函数，它定义了从P到T的有向弧的重复数或权（Weight）的集合，这里N={0，1…}为非负整数集； （4）O：T×P→N是输出函数，它定义了从T到P的有向弧的重复数或权的集合。

8 Petri网的运行规则 在PN中，我们以变迁t表示一事件，用变迁的使能（enabling）表示事件因前提条件得以满足而能够发生。我们还用t的输入库所（通过指向t的弧连接的库所）表示该事件的发生所需要的前提局部状态，用由输入库所至t的输入函数定义这些要求局部前提状态实现的次数，而局部状态的实现情况由库所中所包含的令牌（token）数目来表示。 如果一个变迁的每个输入库所（input place）都拥有令牌，该变迁即为被允许(enable)。一个变迁被允许时，变迁将发生(fire)，输入库所(input place)的令牌被消耗，同时为输出库所(output place)产生令牌。

9

10 基本Petri网的性能 有界性与安全性 活性 可逆性与主宿状态 守衡性 ……
作为数学工具，PN具有一些性质。系统的特性可分为行为（Behavioral）特性与结构（Structural）特性。 可达性 有界性与安全性 活性 可逆性与主宿状态 守衡性 ……

11 （2）要求到达一定的状态，如何确定系统的运行轨迹，典型的问题是生产调度问题。
1.可达性(Reachability)。若从初始标识m0开始激发一个变迁序列mr，则称mr是从m0可达的。 可达性用以描述制造系统这样的2个问题。 （1）系统按照一定的轨迹运行，系统是否能够实现一定的状态或者不期望的状态不出现，典型的问题是生产调度计划的验证。即按照一定的生产调度计划进行生产，一定的生产任务是否能够完成； （2）要求到达一定的状态，如何确定系统的运行轨迹，典型的问题是生产调度问题。

12 2.有界性(Boundedness)和安全性（safty）。
在一个Petri网中的每一个位置中,令牌数不超过一个有限整数k,即 p∈P, M(p)≤k，称Petri网是k有界的,k=1时称为安全的。 通常，库所用于表示制造系统中的工件、工具、托盘以及AGV的存放区，还用于表示资源的可利用情况。确认这些存放区是否溢出或资源的容量是否溢出是非常重要的。PN的有界性是检验被描述的系统是否存在溢出的有效尺度。

13 3.活性(Liveness)。 对于一变迁t∊T，在任一标识m∊R下、，若存在某一变迁序列sr，该变迁序列的激发使得此变迁t使能，则称该变迁是活的。若一个PN的所有变迁都是活的，则该PN是活的。 死变迁（Dead transition）和锁死（Deadlock）从反面描述PN的活性。 出现锁死的原因是不合理的资源分配策略或某些或全部资源的耗尽。下列4个情况可能同时满足，从而导致锁死： （1）互斥 （2）占用且等待 （3）无抢占 （4）循环等待

14 4.可逆性和主宿状态(Reversibility and homestate)。
可逆性表明了一个物理系统可以由当前状态返回到初始状态。在自动制造系统中常用于系统故障的修复以使系统从故障状态回到初始状态。 如果对于任意的M∈R(M0),M′是从M可达的,就称M′为主宿状态。这种情况对应于一个实际的物理系统可以从当前某个状态返回到一个指定状态,而不是初始状态。 5.可覆盖性(Coverability)。如果对于M∈R(M0)和M′∈R(M0)有M′(p)≥M(p)，就称M是可覆盖的。

15 Petri网基本分析方法 (1)　代数分析技术 代数分析技术主要以关联矩阵的形式对一个网系统的结构给与刻划，然后建立状态可达的线性系统关系(状态方程),这种分析途径最早由Ｐｅｔｅｒｓｏｎ提出, 国内吴哲辉教授等也在这方面进行了出色的研究,其优点在于可以借助线性代数的有关结果,简洁的展现Ｐｅｔｒｉ网的一些性质,尤其是结构性质,但对动态性质的刻划作用有限,比如对可达性的刻划仅仅有一个必要而非充分条件. (2)　图分析技术图 分析技术是以一个有限的有向图(树),直接展现一个网系统的运行机制,如可达图与可覆盖树,类似于一个状态机,其优点是能够反映一个网系统的动态行为和特征,特别是对于有界网系统,它是一个准确的刻划,并且对应一个有限状态机,而对于无界网却只能部分反映.

16 (3)　归纳分析技术 归纳分析技术主要是针对Ｐｅｔｒｉ网的状态复杂性提出的,因为即便对一个规模不大的系统,也可能出现状态组合爆炸的问题,所以考虑对Ｐｅｔｒｉ网的简化,主要是在保证一些性质不变的情况下进行化简和分解操作。

17 Petri网的特点 Petri网系统与其他一些系统模型在本质上存在不同，具有自身鲜明的特点。 1、模型语义规范，表达能力强。Petri网兼顾了严格语义和图形语言两个方面：经典Petri网以及高级网的所有元素都是经过严格定义，具有规范的模型语义。Petri网具有足够丰富的表达能力，完全支持现实中基本的过程逻辑(如图所示)。 2、模型基于状态，形式直观。许多建模的方法(如GRASP、PERT)均是基于事件的，缺乏对系统状态的明确体现。而Petri网是一种基于状态的建模方法，它明确定义了模型元素的状态，并且其演进过程也受状态驱动，从而不但严格区分了活动的授权和活动的执行，而且使过程定义具有更丰富的表达能力；能够动态地修改过程实例，使建模过程具有了更多的柔性特征。

18

19 3、分析能力强。Petri网建立在严格的数学基础上，具有强有力的分析技术与手段，可以用来分析模型的各种特性，如有界性(安全性)、活性、不变量等；还可计算模型中的各种性能指标，如响应时间、等待时间、资源占有率等。这些分析技术同样可用从理论与仿真两个方面对业务过程的一些基本要求和性质进行验证。通过分析，还可以对模型进行优化，获取性能最优的来运行。 4、可扩充性好。Petri网仍在纵横两个方向不断发展：纵向扩展表现为由基本的EN系统到P/T系统，发展到高级网(如谓词/变迁系统、染色网)。横向扩展表现为从传统Petri网，发展到时间Petri网和随机Petri网；从一般有向弧发展到抑制弧和可变弧；从自然数标记个数到概率标记个数。Petri网的描述能力仍在不断增强，同时相应的系统性能分析方法也不断地得到完善。

20 Petri网的应用 PN(Petri Nets)在计划调度领域的研究最早是在20世纪80年代提出来的，一般仅是分析计划调度问题的可行性与可达性。在现代企业生产中，获取最大利润是每个生产经营者的最大目标，合理优化的计划调度策略是保证企业取得上述目标的关键。当一个企业确立了其发展规划和长期计划后，就按照预先设定计划方案发展。然而，在实际生产环境中，制造系统经常受外部随机事件的干扰，如设备故障、缺货、更换交货日程等。如何及时调整计划，制定合理优化调度策略，使企业尽快按照预先的计划调度策略完成任务，是当前企业界迫需解决的课题。

21 Petri网应用于柔性制造系统 Petri网在FMS系统中的应用比较典型。一般采用随机Petri网为柔性制造系统建模。Petri网有一个重要的优点，它可以从设计的第一步到系统的实现提供统一的模型工具。Petri网模型提供: 1) 图形的、准确的形式描述，这可以使设计者、拥有者和用户之间进行关于系统行为的深入对话； 2) 良好定义的理论，它可进行模型性质(活性、公平、有界等)的验证； 3) 性能评价的理论和方法(指随机网) ； 4) 系统实现技术，包括实时控制软件的代码产生技术。

22 1) 有效性，也就是说，测试工作流是否按照涉及的要求来运转； 2) 正确性，即工作流模型应该是没有错误的；
Petri 网应用于工作流、物流等建模 工作流是一类能够完全或者部分自动执行的业务过程，根据一系列过程规则,文档、信息或任务能够在不同的执行者之间传递、执行。一般来说，对工作流的分析主要有以下3 个方面: 1) 有效性，也就是说，测试工作流是否按照涉及的要求来运转； 2) 正确性，即工作流模型应该是没有错误的； 3) 性能分析，即评估在吞吐量、响应时间、资源利用等方面是否能达到设计的要求。

23 图9 软件物流仿真过程

24 Petri网作为离散时间系统建模技术具有以下优点:
用于离散系统的建模和仿真 Petri网作为离散时间系统建模技术具有以下优点: 1) 提供了统一的图形表示方法来描述系统的各个特性，对于非专业人员来说在直觉上容易理解和应用，而对于专业人员来说又提供了强大而又形式化的描述能力； 2) 高级Petri网可以方便地进行层次化的建模，这适合于自顶向下的建模及各个阶段的独立验证和确认； 3) Petri网有见地的理论基础和比较成熟的分析方法，如可达树、可达图、系统的p不变量、t不变量、安全性、死锁等特性分析，而随机Pet ri 网则可转化为马尔可夫链进行分析，这些分析可以使系统的特性在运行前被检查从而避免错误。 即某事件轨迹的某点事件发生所产生的下一状态仅与当前状态有关，而与过去的状态轨迹无关。

25 应用于计算机科学的有关领域 Petri网应用于网络通讯中协议的描述、验证和设计

26 Petri 网应用于计算机系统和软件系统模型
在计算机系统和计算机网络中，系统的资源(如缓冲器,信道等) 经常要被多个用户所共享。围绕这些资源所进行的管理、控制以及管理策略是系统管理、控制的核心问题，这些策略和方案对系统的性能有很大的影响。 在实现软件系统并行开发的时候，一般要控制系统的并发性，所以基于Petri网的并行控制器的研究比较热门。

27 Petri 网应用于数据库系统 由于Internet的飞速发展，基于Web的数据库技术已渗透到各个领域。随着信息量的增加，静态的Web网页越来越不能满足用户对信息服务的动态性、实时性和交互性的要求。将Web技术与数据库技术相融合，实现Web数据库的交互式应用已成为必然。Petri网作为一种数学图形工具能从组织结构、控制和管理的角度，精确描述系统中事件之间的依赖和不依赖关系，所以可以将Petri网应用于数据库的系统容错、并发控制以及死锁监测等方面。

28 Petri网的应用难点 当前国际上应用的热点和难点主要表现在以下两个方面：
1) 基于抑制弧Petri网在离散事件系统监控理论中的应用。利用抑制弧监控离散事件系统的理论有一个共同的特点和优点:控制概念清晰，易被控制工程师所理解和接受。所以如何来综合离散事件系统的Petri网控制器是一个发展方向。难点在于如何高效地求取临界状态，如何确定一个抑制弧的合适的权值并借以控制哪些变迁。这有待于Petri网理论本身的发展。

29 2) 如何将离散随机的模型转化成连续确定的近似模型，从而更好地用于对离散事件动态系统建模。提出了一种新的发展观点，即可以将离散Petri网的属性与相对应的连续近似模型的属性相比较。

30 Thank you!