red black
rr
bb
28
br
red black
(1,3)
(3,2) rr bb\br (3,1) rr bb\br br (3,0)
rr
bb
(1,2)
rr
bb\br (1,1)
• 拿到2黑或2红放回1黑； • 拿到黑红各1放回1红； • 7 可达状态, 1 死状态.
br
(1,0)
29
练习：你的一生
基于Petri网的建模技术
agenda
1 Petri Net概述 2. 经典Petri Net 3. 高阶Petri网 4. 一个Petri网建模实例 5.小结
2
1 Petri Net概述
• 经典的Petri net是由 Carl Adam Petri在 1962年的博士论文 中提出的。 • 是离散事件动态系统（Discrete Event Dynamic System, DEDS）的描述工具，可描述异步、同步、并行逻辑关系， 是描述、分析和控制DEDS的最有效和应用最广泛的方法； • 大量研究(>10.000 publications)，至1985年，它主要被用于 理论界；自从80年中期后，实际的应用越来越多，这主要 是由于引入高阶 Petri nets和许多工具； • 最早是应用于计算机信息处理、然后工程方面（自动制造 系统）、目前在计算机、自动化、通信、交通、电力与电 子、服务与制造都得到广泛应用。
send_mail
ready
• • • •
画出可达图 多少个可达状态? 有无死状态? 两个作者和三个读者的情况是怎样的?
33
agenda
1 Petri Net概述 2. 经典Petri Net 3. 高阶Petri网 4. 一个Petri网建模实例 5.小结
34
3 高阶Petri网
t2
t2
Firing is atomic.
18
托肯迁移的例子
19
不确定性
t1
t2
• 两个转移竞争同一个托肯：冲突 • 即使有两个托肯，依然存在冲突
20
基于Petri Net的流程建模
• 库所代表缓存，渠道，地理位臵，条件或者状态 • 转移代表时间，传输或者转换 • 托肯表示对象 (humans, goods, machines), 信息 或者对象的状态 • 过程的状态用位于库所的托肯来表示，状态之间 的变换用转移来表示
name: Sally age: 28 hairtype: BL free name: Harry age: 28 experience: 2
start waiting busy
finish ready
37
• 每一个转移可以有正式的（非正式的）描述:
–产生的托肯数目 –这些托肯的值 –和(可选) 的一个前提条件
hairdresser ready to begin
client waiting free
start waiting busy
finish ready
注意：如何简化了对多个理发师的建模
36
采用颜色进行扩展
• 某一托肯经常代表了具有某种属性的对象 • 因此，每一托肯具有值（颜色）以表示由托肯 建模的对象的特定属性
t1
p1
p2
t3 p3 p4
连接具有方向，并在库所和转换之间。 托肯Token 是动态对象。 Petri网的状态由分布在库所中的托肯决定
12
Petri网的组成元素
Petri网简称PNG (Petri Net Graph)，它有库所和 转移两种结点 库所（Place）小圆圈 P 转移（Transition）小方块 T 连接（Connection）是库所和转移之间的有向边， 流关系 F,K 托肯（Token）是库所中的动态对象，可以从一 个库所移动到另一个库所 •
1
D=0
39
包含时间属性的交Biblioteka 灯0 0red130 0
0
red2
30 0
safe
yr1
yr2
rg1
5 25
yellow1
yellow2
5
rg2
gy1
gy2
25
green1
green2
40
层次的扩展
• 对复杂的Petri网添加 结构信息的方法，与 DFD类似 • 一个子网是对库所，转 waiting 移和子网的扩展
green2
25
人的一生
孩童 青春期
结婚
单身汉
已婚
离婚
死亡
已故
26
Ball game
每次拿两个球但放 回一个球：
red
br
black
rr
bb
• 拿到2黑或2红放回1黑； • 拿到黑红各1放回1红；
27
某些定义
• 当前状态 库所中托肯的分布情况. • 可达状态 通过一系列激活的转移的点火，从当前状态可以达到的状 态. • 死状态（dead state） br 没有转移能够激活的状态
21
形式化表达
一般Petri网定义为五元组 ∑ = ( P , T ，F , K , M0 )
• 其中, P 为位臵的集合, 用圆圈代表, 表示系统的状态; T 为转移的集合, 用空心矩形代表, 表示系统中的事件; • F 称为P->T的流关系, 其规定资源的输出流; • K 称为T->P的流关系, 其规定资源的输入流; • M0 称为Petri网∑的初始标识。 • Token表示工作对象，转移是网络中的控制点。Petri网进 行算法扩展, 可以使它具有处理模型求解系统运行的能力。
3
Petri网观点可简单的归纳到两个基本概念:
• 事件和条件,许多系统均可从事件与条件的观点去建模； • 事件是系统中的动作, 事件的出现是由系统状态控制的; • 系统状态可描述为一组条件, 条件就是系统状态的谓词 或逻辑描述;
• 前条件：由于事件是动作, 所以它可以发生。为了使事 件发生, 必须使某些条件成立,这种条件称为事件的前条 件; • 后条件：事件的发生可能破坏前条件而使另外的条件成 立, 这种条件称为事件的后条件。
5
Petri网的特点
• 从控制和管理的角度模拟系统, 不涉及系统所依 赖的物理化学原理,这样可以简化某些细节, 易于 理解。 • 精确描述系统中事件的依赖关系和不依赖关系,这 是事件之间存在的、不依赖于观察的关系。 • 具有统一的语言描述系统结构和行为, 方便建模 仿真,从而起到沟通不同子系统间桥梁的作用。 • 与顺序模型不同, Petri网系统比其他图形建模工 具更适于描述并发和冲突。
rg1
yellow1
yellow2
rg2
gy1
gy2 green2
31
green1
安全而公平的交通灯
red1 safe2 red2
yr1
yr2
rg1
yellow1
yellow2
rg2
gy1 safe1
gy2
green1
green2
32
课后练习
begin mail_box rest type_mail read_mail rest receive_mail
10
agenda
1 Petri Net概述 2. 经典Petri Net 3. 高阶Petri网 4. 一个Petri网建模实例 5.小结
11
2 经典Petri Net
• 经典的Petri网是一个由库所 places ( ) 和转移 transitions ( )构成的网络
t2
• 在实际中经典的Petri网并不是非常有用:
– Petri网变得规模太大，太复杂. – 建模可能要花太多的时间. – 不能处理时间和数据信息.
• 因此我们需要使用高阶Petri网，也就是说采用 以下方式来扩展Petri网:
– 颜色——属性描述 – 时间——性能分析 – 层次——结构分解
35
例子
• 理发厅的例子
43
4 一个Petri网建模实例
Petri网建立步骤：
• 根据状态与事件的定义，确定系统的状态集和事件集。 • 确定系统中状态与事件的关系。 • 将库所和转移对应起来，建立Petri网模型图。 • 根据系统情况，决定Petri网模型图的初始状态，确定初始 状态的下个状态的Token数。 • 基于初始状态判断那些事件可被激发，当模型激活后，模 型状态图将发生变化，又引起一些事件被触发。
• • • •
13
Petri网的规则
• 连接是有方向的，其上可以标出权重 • 两个库所或转移之间不允许有边，且不应该有孤 立节点 • 库所可以拥有任意数量的托肯
14
顺序流程
迭代（循环）流程
选择流程
并发流程
15
输入库所/输出库所
p1 t1 p4
p2
p3
• 转移t1具有三个输入库所 (p1, p2 and p3) 和两个 输出库所 (p3 and p4). • 库所p3 既是t1的输入库所又是它的输出库所.
• 复杂性被分解到网络和托肯的值上 • 这种处理产生了紧凑、可管理和自然的过程描述。
• 例子：汽车装配过程
38
时间的扩展
• 为了进行性能分析，需要对持续时间，延迟等 的时间概念进行建模 • 因此，每一个托肯都有一个时间戳，而转移确 定了产生一个托肯的延迟
free 3 9 start waiting D=3 busy 0 D=0 finish ready
8
利用Petri网建模具有以下优点。 • (1) Petri网建立在严格的数学基础上，精确描述系统中事 件的依赖关系和不依赖关系,这是事件之间存在的、不依赖 于观察的关系，已有了许多成熟的分析方法和工具。 • (2) 兼顾了严格语义与图形表示两方面，具有统一的语言描 述系统结构和行为, 方便建模仿真,从而起到沟通不同子系 统间桥梁的作用; • (3) Petri网是一种基于状态的建模方法，与基于事件的过 程建模方法不同, Petri网系统比其他图形建模工具更适于 确定触发方式、描述同步并发系统，并具有更多的柔性。