随着工业4.0的发展, 越来越多的设备集成在同一个工业互联网中, 构成了大规模的信息物理系统, 状态空间组合式快速增长; 与此同时, 传统制造的单一性已经无法满足市场需要, 订单趋向于小批量、定制化和多批次, 生产过程的动态变化日趋剧烈; 无论是调度策略的求解, 还是执行控制代码设计和调试, 都面临指数级计算复杂性的挑战, 加上调度层和控制层相互割裂, 很难满足信息物理系统对生产事件的快速灵活响应的要求.
平行系统[1]的提出为信息物理系统的实现提供了可行方案, 信息和物理虚实结合, 在信息空间中计算决策, 在物理世界控制执行[2]. 这意味着, 可以将调度策略求解和控制指令计算作为虚拟对象, 自动化装置作为实体对象, 虚拟对象与实体对象平行演化, 在统一的时空里实现调度优化和控制执行.
Petri网能够描述在信息物理系统中的顺序、并行、同步和异步行为, 是刻画信息空间的优秀建模工具. 但是如果用来做控制, Petri网缺少与实体对象之间的输入输出接口; 如果用来做调度, 又缺少成本信息, 所以需要扩展Petri网语法语义.
文献[3]研究了Petri网的活性问题, 用于设计更高允许度的死锁预防的控制器. 文献[4]提出了将原始约束转化为可容许约束的方法, 克服了不可控或不可观测变迁给控制器带来的设计困难. 这些方法的提出都为设计信息物理系统的Petri网模型提供了理论支撑. 同时为了解决Petri网在输入输出上的局限性, 研究者们对Petri网做了相应扩展[5-8]. 文献[9]利用控制解释Petri网对期望的闭环系统行为进行建模, 从模型中提取离散事件控制器以便在可编程逻辑控制器(Programmable Logical Controller, PLC)上实现控制逻辑. 文献[10]提出了分布式的控制方法, 利用控制解释Petri网建立中央控制器, 为具有输入输出信号的本地控制器分配控制任务. 文献[11]研究了有色Petri网, 其中有色的托肯代表了产品类型以及状态变化时的相关信息, 减小了模型的规模. 文献[12]给出了梯形图到普通Petri网的转化算法, 并通过生成的可达图来定位梯形图中的竞争路径. 文献[13]则通过将Petri网与一阶逻辑相结合构建了系统执行框架用于实际的制造系统中. 文献[14, 15]分别给出了扩展Petri网到现场可编程门阵列(Field-Programmable Gate Array, FPGA)和PLC的翻译方法, 加快了程序开发的进程. 但以上工作中, Petri模型仍需要翻译成控制语言, 不足以描述平行系统, 于是我们在文献[16]中提出了平行Petri网, 在原有网结构的基础上定义了动作函数和激活函数, 可以描述平行系统物理层中各单元的行为, 同时封装的传感和执行变量为信息层和物理层的交互提供了通道.
如果要考虑优化问题, 那么就需要将成本因素扩展到Petri网模型当中. 通过给库所或变迁赋上时间, 引入赋时Petri网的概念, 就可以形式化地给出调度优化问题[17-19], 即通过搜索赋时Petri网可达图, 找到最小执行时间, 求解出系统的最优调度策略. 文献[20, 21]分析了网结构的行为属性, 针对定时离散事件系统具有工作周期的特点, 研究了赋时事件图中所有可能的循环来进行调度. 但现有研究更多的是将赋时Petri网与智能搜索算法相结合来进行调度. 文献[22]率先将赋时Petri网与A*算法相结合, 该方法不需要通过遍历可达图, 而是通过构建启发式函数来求解调度策略. 文献[23]通过开发新的启发式函数, 考虑了系统中的托肯剩余时间, 带有权重的弧以及多资源情况, 扩大了A*算法在赋时Petri网中的使用范围. 文献[24]利用集束搜索算法在可达图每一层仅扩展设定宽度的结点, 使得搜索以受控的方式向目标结点前进, 大大节省了搜索时间. 文献[25]则利用遗传算法对赋时Petri网进行调度, 并设计了控制器避免系统死锁. 文献[26]通过智能体综合考虑了系统Petri网模型, 环境信息以及满意度模型实现了对任务的规划调度. 为提高算法搜索效率, 文献[27, 28]中对复杂系统进行了模块化建模, 提高了大型系统的Petri网设计效率.
在前期工作[16]中, 我们并未考虑调度优化问题. 本文大幅扩展了平行Petri网的定义, 分别给变迁和动作函数加上了标签和时间信息, 使之不局限于对系统的控制, 同样也适用于调度, 从而构建出制造系统的平行Petri网模型. 同时通过简化压缩平行Petri网, 仅保留原有模型中调度相关的结构和信息, 使其转化为赋时Petri网, 利用赋时Petri网求解出最优调度策略, 将其描述为策略Petri网, 最后借助同步算法使得系统平行网与策略网同步执行, 在此基础上设计了C和PLC程序, 借助TwinCAT平台, 实现了平行Petri网对物理设备的感知、控制和执行.
本文结构如下: 第一节回顾了标签赋时Petri网和TwinCAT的相关概念; 第二节定义了平行Petri网; 第三节给出了平行Petri网的赋时Petri网和策略Petri网的生成方法; 第四节给出了调度与控制一体化的执行算法; 第五节进行了实验验证; 第六节对全文进行了总结.
1. 基本概念
Petri网结构是一个四元组N=(P,T,F,W)N=(P,T,F,W), PP和TT分别为库所集和变迁集; F⊆(P×T)∪(T×F⊆(P×T)∪(T×P)P)是连接库所和变迁的有向弧集合; W:F→{1,W:F→{1,2,?}2,?}是一个映射, 为FF中每条弧指定一个正整数权重. 在本文中, 所有弧的权重默认为1; C−C−和C+C+是Petri网结构的前置和后置关联矩阵, ∀p∈P∀p∈P, ∀t∈T∀t∈T, (p,t)∈F⇒C−(p,t)=W(p,t)(p,t)∈F⇒C−(p,t)=W(p,t), (p,t)∉F⇒(p,t)∉F⇒C−(p,t)=0C−(p,t)=0; (t,p)∈F⇒C+(p,t)=W(p,t)(t,p)∈F⇒C+(p,t)=W(p,t), (t,p)∉(t,p)∉F⇒C+(p,t)=0F⇒C+(p,t)=0. C=C+−C−C=C+−C−表示其关联矩阵. Petri网记作G=(N,m0)G=(N,m0), 其中m0m0为初始标识. 如果m≥C−(⋅,t)m≥C−(⋅,t), 那么tt在标识mm下状态使能, 用m[t⟩m[t⟩表示, 状态使能的变迁tt可以激发, 生成新的标识m′=m+C(⋅,t)m′=m+C(⋅,t), 记作m[t⟩m′m[t⟩m′. T∗T∗是TT中的变迁组成的变迁串的集合. m[σ⟩m[σ⟩表示变迁激发序列σ=tσ1tσ2?tσkσ=tσ1tσ2?tσk, k∈{1,2,?}k∈{1,2,?}, 在mm处状态使能. m[σ⟩m′m[σ⟩m′表示mm经过激发序列σσ得到新的标识m′m′. Petri网在初始标识处状态使能的激发序列集合为L(G)={σ∈T∗∣m0[σ⟩}L(G)={σ∈T∗∣m0[σ⟩}, 可达标识集为R(G)=R(G)={m∣σ∈L(G),m0[σ⟩m}{m∣σ∈L(G),m0[σ⟩m}.
标签Petri网定义为Gl=(N,m0,Σ,l)Gl=(N,m0,Σ,l), 其中NN为一个Petri网结构, ΣΣ为标签的集合, 每个标签为一个字母; l:T→Σ∪{ε}l:T→Σ∪{ε}是将标签映射到变迁的标签函数, 每个变迁的标签都是ΣΣ中的一个字母或者空字符εε. 在本文中, 假设任意两个变迁t1t1和t2t2, 如果l(t1)≠ε∧l(t2)≠εl(t1)≠ε∧l(t2)≠ε, 那么l(t1)≠l(t2)l(t1)≠l(t2). Σ∗=Σ∪{ε}Σ∗=Σ∪{ε}为标签组成的标签串的集合. 存在一个自然映射关系: ρ:T∗→Σ∗ρ:T∗→Σ∗, 其中任意变迁序列σ=t1t2?tnσ=t1t2?tn, ρ(σ)=l(t1)l(t2)?l(tn)ρ(σ)=l(t1)l(t2)?l(tn).
库所赋时Petri网表示为Gd=(N,m0,d)Gd=(N,m0,d), d:P→{0}∪R+d:P→{0}∪R+表示附在库所上的时延函数, 时延可以是零或正实数. 本文中涉及的赋时Petri网遵从如下假设: 如果一个库所的时延不为0, 那么该库所的最大标识为1. 对于赋时Petri网的任意变迁tt, 如果1)在当前标识下是使能的, 并且2)它的每一个输入库所中的托肯在其所在的库所的停留时间超过该库所的时延, 那么该变迁可以激发.
TwinCAT[29]是基于Windows操作系统的PLC控制平台, 并为C/C++ 提供了接口, 可以实现C/C++ 与PLC语言的联合编程.
2. 平行Petri网
在我们提出的平行Petri网[16]中, 解决了与环境交互的问题, 但缺乏调度相关信息, 需要加入成本因素, 扩展平行Petri网的定义.
定义 1. 平行Petri网是一个十一元组G=G=(N,m0,ΣI,ΣO,ΣA,ΣL,Σid,λA,λL,λid,λz)(N,m0,ΣI,ΣO,ΣA,ΣL,Σid,λA,λL,λid,λz), 其中:
1) NN是普通Petri网结构;
2) m0m0是初始标识;
3) ΣIΣI为输入字母表, 每个元素是一个来自传感器的输入信号;
4) ΣOΣO为输出字母表, 每个元素是一个送往执行机构的输出信号;
5) ΣidΣid为标签字母表, 其中每个元素是一个标签符号, 用以指定系统事件的身份;
6) λA:P→ΣAλA:P→ΣA是将库所集映射到动作集的函数, 它给每个库所附一个动作函数. 动作函数是从输入信号集合到输出信号集合的映射, 即2ΣI→ΣO2ΣI→ΣO, 动作函数的集合为ΣAΣA; 给定任意库所pp, 如果λA(p)≠∅λA(p)≠∅, 那么称库所pp为动作库所; 否则, 称其为非动作库所;
7) λL:P→ΣLλL:P→ΣL是将库所集映射到激活函数集的函数, 它给每个库所附一个激活函数. 激活函数是用来终止动作函数执行和激活变迁执行的判断条件, 是输入和输出信号集合的集合到0或1的映射, 2ΣI∪ΣO→{0,1}2ΣI∪ΣO→{0,1}, ΣLΣL为激活函数的集合. 且∀p∈P:∀p∈P:λA(p)=α→λL(p)=α¯λA(p)=α→λL(p)=α¯;
8) λid:T→Σid∪{ε}λid:T→Σid∪{ε}将变迁映射到标签的函数, 其中每一个变迁的标签为一个字母或者一个空字符εε. 每个变迁至少有一个标签符号, 该标签不与其它变迁共享. ∀ti,tj∈T,λid(ti)=λid(tj)=ε∀ti,tj∈T,λid(ti)=λid(tj)=ε或者λid(ti)≠λid(tj)λid(ti)≠λid(tj);
9) λz:ΣA→{0}∪R+λz:ΣA→{0}∪R+表示每个动作函数对应的动作的执行时间.
定义 2. 给定平行Petri网当前获得的标签集合ΣEΣE和任意变迁tt, 如果λid(t)∈ΣEλid(t)∈ΣE, 并且∀p∈?t:∀p∈?t:λL(p)=1λL(p)=1, 那么变迁tt是同步使能的.
定义 3. 平行Petri网的演化规则定义如下:
1) 一旦动作库所被标识, 立即执行附在库所上的动作函数和激活函数;
2) 如果一个变迁既是状态使能, 又是同步使能, 则该变迁是使能的;
3) 只有使能的变迁可以激发, 且任何变迁tt的激发满足状态方程m′=m+C(⋅,t)m′=m+C(⋅,t).
根据定义1−3, 我们描述了平行Petri网的定义及其运行规则: 首先, 在库所上附加了动作函数和激活函数, 从而利用动作函数驱动执行机构, 利用激活函数扫描传感器信号实现Petri网与物理实体的交互; 其次, 在变迁上附加了标签字符, 从而可以实现Petri网与信息空间的其他虚拟实体(比如优化策略)之间的同步. 最后, 动作函数上附加了执行时间属性, 从而可以描述系统运行的时间成本, 为优化调度提供了依据.
生产制造等物理信息系统是由众多的单元, 按照一定的业务逻辑耦合而成的, 因此我们可以采用模块化的方法为其设计平行Petri网模型. 因篇幅限制, 本文不再对平行Petri网的设计问题展开讨论, 在本文第五节将利用一个实验示例演示其设计过程.
3. 平行Petri网的优化调度方法
3.1 平行Petri网的抽象和简化
平行Petri网为信息物理系统搭建了严谨的数学模型, 而且模型中包含了时间等成本信息. 这意味着我们可以利用它来研究优化调度问题.
根据平行Petri网的定义, 它的运行需要来自物理世界的同步信号, 因此无法直接作为优化的仿真模型, 而且模型中存在大量与优化调度不相关的冗余结构, 状态空间会组合式快速增长. 虽然目前智能搜索算法可以避免遍历可达图, 但其搜索效率难以保证. 通过网结构的简化技术可以指数地减小可达图的规模, 是降低计算复杂性的有效手段. 因此需要对平行Petri网进行简化, 抽象仅保留调度相关结构和信息的仿真模型. 而赋时Petri网恰好满足这个要求.
定义 4. 如果一个平行Petri网存在有序三元组(p,t,p′)(p,t,p′), 且满足: 1) ?t={p}?t={p}, 2) t?={p′}t?={p′}, 3) |?p|=|?p|=|p?|=1|p?|=1, 4) |?p′|=|p′?|=1|?p′|=|p′?|=1, 5) m0(p)=m0(p′)=0m0(p)=m0(p′)=0, 那么称该三元组为一个融合结构, 记作ωω. 融合结构的集合记作ΩΩ.
定义 5. 给定平行Petri网GG和它的一个融合结构ω=(p,t,p′)ω=(p,t,p′), 在网中设计库所pωpω, 如果它满足下列条件: 1) 对于pp的输入变迁t′t′, 添加一个从t′t′到pωpω的有向弧, 即(t′,pω)(t′,pω), 2) 对于p′p′的输出变迁t′′t″, 添加一个从pωpω到t′′t″的有向弧, 即(pω,t′′)(pω,t″); 那么pωpω称为ωω的宏库所.
根据定义4−5, 我们可以设计将平行Petri网简化为赋时Petri网的算法.
算法1. 平行Petri网到赋时Petri网的简化算法.
输入: 平行Petri网G=(N,m0,ΣI,ΣO,ΣA,ΣL,Σid,λA,G=(N,m0,ΣI,ΣO,ΣA,ΣL,Σid,λA,λL,λid,λz)λL,λid,λz).
输出: 赋时Petri网G¯=(N¯,m¯0,λ¯d)G¯=(N¯,m¯0,λ¯d).
1) for all p∈Pp∈P do
2) if λA(p)=∅λA(p)=∅ then
3) λd(p)=0λd(p)=0;
4) else
5) λd(p)=λz(λA(p))λd(p)=λz(λA(p));
6) end if
7) end for
8) N¯=NN¯=N;
9) while Ω≠∅Ω≠∅ do
10) 从融合结构的集合ΩΩ中选择任意一个ω=ω=(p,t,p′)(p,t,p′);
11) 根据定义5设计一个宏库所pωpω, 即P¯=P¯=P¯∪{pω}P¯∪{pω},F¯=F¯∪{(t1,pω),(pω,t2)}F¯=F¯∪{(t1,pω),(pω,t2)}, 其中t1t1是PP的输入变迁, t2t2是PP的输出变迁;
12) 从N¯N¯中删除融合结构ωω;
13) m0(pω)=0m0(pω)=0;
14) λd(pω)=λd(p)+λd(p′)λd(pω)=λd(p)+λd(p′);
15) Ω=Ω−{ω}Ω=Ω−{ω};
16) end while
17) for all p∈P¯p∈P¯ do
18) m¯0(p)=m0(p)m¯0(p)=m0(p);
19) λ¯d(p)=λd(p)λ¯d(p)=λd(p);
20) end for
算法1描述了平行Petri网到赋时Petri网的简化过程, 包含两个部分: 首先, 删除控制相关信息; 其次, 将融合结构压缩为宏库所. 我们以图1为例阐述整个简化过程的细节:
图1 平行Petri网到赋时Petri网简化过程
Fig.1 Process of simplifying parallel Petri nets into timed Petri nets
1) 首先, 给库所附加时延, 对于动作库所, 其时延为对应动作函数的执行时间; 对于非动作库所, 其时延为0; 其次, 移除平行Petri网各库所上的动作函数和激活函数一类的控制信息. 如图1中的平行Petri网所示, 库所p′p′的动作函数λA(p′)=αλA(p′)=α, 激活函数λL(p′)=α¯λL(p′)=α¯, 动作函数执行时间λz(α)λz(α) = 1; 所以赋给库所p′p′的时延λd(p′)=λz(α)=1λd(p′)=λz(α)=1; 然后, 去除p′p′的动作函数αα和激活函数α¯α¯. 库所pp和p′′p″同理.
2) 对于网中的融合结构, 将其压缩为宏库所, 宏库所的时延为原有库所时延之和, 托肯数为0; 对于非融合结构, 则保持不变. 从图1中可以看出, 网中存在融合结构(p,t,p′′)(p,t,p″), 所以将库所pp和p′′p″以及变迁tt压缩为宏库所pωpω, 并添加有向弧(t′,pω)(t′,pω)和(pω,t′′)(pω,t″). 宏库所的时延为5, pp和p′′p″的时延之和. 对于库所p′p′和变迁t′t′, 保持不变. 由此即可简化为赋时Petri网模型.
定义 6. 给定一个信息物理系统的平行Petri网, 如果它的一个标识表示这个信息物理系统任务完成时的状态, 则该标识称为平行Petri网的目标标识.
定义 7. 给定一个平行Petri网和它的目标标识mgmg, 如果标识m¯gm¯g是赋时Petri网的一个标识, 并且∀p∈P¯:m¯g(p)=mg(p)∀p∈P¯:m¯g(p)=mg(p), 那么m¯gm¯g就是赋时Petri网的目标标识.
定义 8. 给定一个平行(赋时)Petri网, 如果标识变迁的交替序列π=mπ0[tπ1⟩mπ1[tπ2⟩?mπn−1π=mπ0[tπ1⟩mπ1[tπ2⟩?mπn−1[tπn⟩[tπn⟩mπnmπn, 满足下列条件: (1) mπ0=m0mπ0=m0, (2) mπk−1≥C−(⋅,tk)mπk−1≥C−(⋅,tk), mπk=mπk−1+C(⋅,tk)mπk=mπk−1+C(⋅,tk), 1≤k≤1≤k≤nn, (3) mπnmπn是一个平行(赋时) Petri网的目标标识. 那么称ππ为平行(赋时) Petri网的一条执行轨迹; 变迁序列tπ1tπ2?tπntπ1tπ2?tπn称为ππ的激发序列, 记作π↑π↑. ππ的运行时间记作d(π)d(π).
定义 9. 给定一个平行(赋时) Petri网执行轨迹的集合ΠΠ, 如果一条执行轨迹的执行时间最小, 那么称其为最优执行轨迹, 平行(赋时) Petri网的最优执行轨迹的集合记作Π∗Π∗.
定义 10. 给定一个平行Petri网及其赋时Petri网, 如果ππ是平行Petri网的一条执行轨迹, π¯π¯是赋时Petri网的一条执行轨迹, 并且从ππ的激发序列π↑π↑中剔除不存在于赋时Petri网的变迁后的变迁序列等于π¯π¯的激发序列, 那么ππ和π¯π¯是同步的.
定理 1. 给定任意平行Petri网和其赋时Petri网, 下列结论成立: 1) 对于平行Petri网上的每一条执行轨迹, 赋时Petri网上都有一条唯一的执行轨迹与之同步; 2) 对于赋时Petri网上的一条执行轨迹, 平行Petri网上都有至少一条执行轨迹与之同步.
证明. 假设平行Petri网的执行轨迹为π=π=m0[π↑⟩mgm0[π↑⟩mg, 其中, π↑=tπ1tπ2tω1tω2?tωmtπnπ↑=tπ1tπ2tω1tω2?tωmtπn, tωm∈tωm∈ωmωm, m∈{1,2,?}m∈{1,2,?}; 简化得到的赋时Petri网的执行轨迹为π¯=m¯0[π¯↑⟩m¯gπ¯=m¯0[π¯↑⟩m¯g, 其中, π¯↑=tπ1tπ2?tπnπ¯↑=tπ1tπ2?tπn. 根据算法1和定义4, m0m0和mgmg不是融合结构的一部分, ∃p0,pg∈P¯,m¯0(p0)=m0(p0),m¯g(pg)=mg(pg)∃p0,pg∈P¯,m¯0(p0)=m0(p0),m¯g(pg)=mg(pg). 所以只需证明激发序列π↑=π¯↑π↑=π¯↑即可证明ππ和π¯π¯是同步的. 因为tωmtωm是ππ中的变迁但不是π¯π¯中的变迁, 同时也是融合结构ωmωm的组成元素, 将平行Petri网简化为赋时Petri网时需要压缩融合结构, 压缩ωmωm意味着tωmtωm被移除, 所以移除tωmtωm后得到π=π¯π=π¯, 根据定义10, ππ和π¯π¯是同步的. 而且由于平行Petri网中存在融合结构, 所以简化得到的赋时Petri网的变迁集T¯∈TT¯∈T, 所以简化得到的赋时Petri网中的执行轨迹是唯一的. 同理可证得2). □
定理 2. 给定任意平行Petri网和其赋时Petri网, 下列结论成立: 1) 对于平行Petri网上的每一条最优执行轨迹, 赋时Petri网上都有一条唯一的最优轨迹与之同步; 2) 对于赋时Petri网上的一条最优轨迹, 平行Petri网上都有至少一条最优轨迹与之同步.
根据定义9和定理1, 很容易证明定理2, 故该证明从略.
3.2 平行Petri网的策略网生成方法
在将平行Petri网简化为赋时Petri网之后, 可以通过搜索可达图求解出最优执行轨迹, 一条最优执行轨迹对应一个调度策略. 而最优执行轨迹不止一条, 因此最优调度策略本质上是变迁的偏序关系. 为了形式化地表示这样的偏序关系, 本文拟将其建模为一个普通Petri网(称为策略Petri网), 以便于利用它与平行Petri网同步, 实现平行Petri网按照最优策略执行.
根据定义6−9, 我们给出了赋时Petri网的最优调度策略的Petri网描述方法.
算法2. 策略Petri网的生成算法.
输入: 赋时Petri网G¯G¯.
输出: 策略Petri网G^=(N^,m^0)G^=(N^,m^0).
1) 生成赋时Petri网的可达图R(G¯,m¯0)=(V,F,W)R(G¯,m¯0)=(V,F,W), 顶点集VV中的元素表示可达图中的标识, 那么FF中的有序对(v1,v2)(v1,v2)表示网可以从标识v1v1经过一个变迁t=W(v1,v2)t=W(v1,v2)的激发到达标识v2v2;
2) 计算赋时Petri网最优执行轨迹的集合Π∗Π∗;
3) 从可达图RR上删除所有不在最优执行轨迹上的标识对应的结点, 得到的子图记作R∗R∗;
4) for all v∈V∗v∈V∗ do
5) 为vv设计一个库所pvpv;
6) P^=P^∪{pv}P^=P^∪{pv};
7) if vv是初始标识then
8) m^0(pv)=1m^0(pv)=1;
9) else
10) m^0(pv)=0m^0(pv)=0;
11) end if
12) end for
13) for all w∈W∗w∈W∗ do
14) 为有序对(v1,v2)(v1,v2)对应库所对(pv1,pv2)(pv1,pv2)设计一个变迁tv1v2tv1v2;
15) 画一条有向弧使得pv1pv1指向tv1v2tv1v2, 画另外一条有向弧使得tv1v2tv1v2指向pv2pv2;
16) T^=T^∪{tv1v2}T^=T^∪{tv1v2};
17) end for
算法2描述了平行Petri网的策略Petri网的生成过程, 步骤1-3移除了赋时Petri网可达图中不在最优轨迹上的标识结点, 得到了只包含组成最优轨迹标识结点的子图R∗R∗; 步骤4-17为R∗R∗中每个标识结点设计对应库所, 对于初始标识对应库所, 其库所标识为1, 其他库所标识为0, 对于具有先后关系的标识, 为其对应库所设计了变迁并用有向弧连接, 构成了策略Petri网G^G^.
定义 11. 对于策略Petri网中的任意一条路径, 如果网中没有任何一条路径可以包含它, 那么称其为极大路径.
由算法2可得到下列性质:
性质 1. 策略Petri网是一个状态机.
性质 2. 策略Petri网是无环的.
性质 3. 策略Petri网内始终只有一个托肯.
性质 4. 策略Petri网的一条极大路径唯一地表示赋时Petri网的一条最优执行轨迹.
性质1−4可从算法2直接推导过来, 其证明从略.
4. 平行Petri网和策略Petri网的同步执行算法
得到策略Petri网后, 需要给出与其平行Petri网的同步执行算法, 使得调度和控制在一个系统中同步进行.
定义 12. 给定平行Petri网GG和其策略网G^G^, 同步标签函数λ^idλ^id是从平行Petri网的变迁集合到字符集合的一个映射, 其中∀t∈T∀t∈T, t∈T^→λ^id(t)=t∈T^→λ^id(t)=λid(t)λid(t), t∉T^→λ^id(t)=εt∉T^→λ^id(t)=ε.
定义 13. 给定平行Petri网和其策略Petri网, 它们的同步运行条件是: 1) ∀t∈T∀t∈T, 如果存在同步标签函数λ^id(t)=λid(t)λ^id(t)=λid(t), 那么平行Petri网和策略Petri网中的变迁tt只有在同时使能时才能激发, 且为同时激发; 2) ∀t∈T∀t∈T, 如果λ^id(t)=ελ^id(t)=ε, 平行Petri网中的变迁tt满足使能条件时立即激发.
定理 3. 如果平行Petri网与策略Petri网同步执行, 那么平行Petri网可以在最短的时间内到达目标标识.
证明. 根据性质1−4和定理1, 平行Petri网中的任意一条最优轨迹, 策略Petri网上都有一条极大路径与之同步, 同时根据定义9, 最优轨迹的执行时间最短. 两者同步执行时, 假设变迁tt在策略Petri网标识m^m^下使能, 经过空字符变迁, 平行Petri网当前标识mm才能演化到m′m′, m′m′是平行Petri网中使得变迁tt使能的标识. 根据定义13, 只要遇到空字符变迁就立即激发, 所以mm连续激发, 而策略Petri网标识m^m^下当前使能变迁为tt, 未满足同步运行条件, 不会继续演化, 直到平行Petri网到达标识m′m′, 存在变迁tt使得λ^id(t)=λid(t)λ^id(t)=λid(t), 使得两个网中的变迁tt同步使能. 所以平行Petri网和策略Petri网同步执行时, 假设平行Petri网当前标识为mm, 策略Petri网当前标识为m^m^, 对于任意策略Petri网当前标识下使能的变迁, 平行Petri网都可以通过激发空字符变迁到达使得该变迁使能的标识, 即
∀t∈T,m^≥C^−(⋅,t),∃σ∈T∗ε,m′=m+C⋅σ?,m′≥C−(⋅,t).
∀t∈T,m^≥C^−(⋅,t),∃σ∈Tε∗,m′=m+C⋅σ→,m′≥C−(⋅,t).
(1)
综上, 平行Petri网可以在最短时间内到达目标标识. □
根据定义12−13, 设计了策略Petri网与平行Petri网同步执行的算法.
算法3. 策略Petri网与平行Petri网同步执行算法.
输入: 平行Petri网GG, 策略Petri网G^G^.
输出: 平行Petri网的目标标识mgmg, 策略Petri网的目标标识m^gm^g.
function Strategy-net(m^m^) returns (m^,β)(m^,β)
1) while m^≠m^gm^≠m^g do
2) ΣE=∅ΣE=∅;
3) for all t∈T^t∈T^ do
4) if m^≥C^−(⋅,t)m^≥C^−(⋅,t) then
5) ΣE=ΣE∪{λ^id(t)}ΣE=ΣE∪{λ^id(t)};
6) end if
7) end for
8) β=random(ΣE)β=random(ΣE);
9) m^=m^+C^(⋅,t)m^=m^+C^(⋅,t);
10) return (m^,β)(m^,β)
11) end while
function Parallel-net(m^,β)(m^,β)
1) while m≠mgm≠mg do
2) m^=m^0m^=m^0;
3) (m^,β)(m^,β) = Strategy-net(m^)(m^);
4) for all t∈Tt∈T do
5) 读取下位机PLC中的变量γγ;
6) if [m≥C−(⋅,t)]∧[∧p∈⋅tγ(p)][m≥C−(⋅,t)]∧[∧p∈⋅tγ(p)] then
7) if λ^id(t)==ελ^id(t)==ε then
8) m=m+C(⋅,t)m=m+C(⋅,t);
9) 向下位机PLC发送标识mm;
10) 跳转到步骤3;
11) else if λ^id(t)==βλ^id(t)==β then
12) m=m+C(⋅,t)m=m+C(⋅,t);
13) 向下位机PLC发送标识mm;
14) 跳转到步骤2;
15) end if
16) end if
17) end for
18) end while
function PLC()
1) for p∈Pp∈P do
2) 读取上位机标识mm;
3) if m(p)≥1m(p)≥1 then
4) if pp是非动作库所do
5) λL(p)=1λL(p)=1;
6) else
7) 执行动作函数λA(p)λA(p), 并以其计算结果更新PLC的输出;
8) λL(p)=1λL(p)=1;
9) end if
10) γ(p)=λL(p)γ(p)=λL(p);
11) 向上位机发送变量γγ;
12) end if
13) end for
算法3由Strategy-net、Parallel-net和PLC三个函数构成, Strategy-net和Parallel-net运行于同一计算内核上, 负责计算和决策平行Petri网的演化进程; PLC运行在另一个计算内核, 负责感知和执行物理实体. Parallel-net和PLC通过ADS通信[14]进行数据传递. 三个函数同时执行, PLC负责读取当前标识并执行动作函数和激活函数; 策略网中, ΣEΣE是当前可选择的同步标签集合, 遍历当前所有可激发变迁, 将其同步标签放入集合ΣEΣE, 从中随机选择一个标签ββ传递给Parallel-net; Parallel-net读取PLC中的激活函数γγ, 使平行网不断演化直到与ββ标签相同的变迁激发, 进行下一循环.
如图2所示, 算法3实际上给出了调度与控制一体化方法的执行框架, 该框架分为信息层和物理层, 信息层将平行Petri网和策略Petri网融合为一, 平行Petri网与物理系统同步, 一旦其中的动作库所被标识, 便调用封装的动作函数对输入信号进行计算处理, 并不断更新输出信号对物理系统进行实时控制. 策略Petri网负责优化调度平行Petri网的执行, 从而实现了调度和控制同步进行. 最终实现物理与信息平行演化, 虚实相互融合.
图2 基于平行Petri网的调度与控制一体化执行框架
Fig.2 Integrated execution framework of scheduling and control based on parallel Petri nets
5. 实验验证
如图3所示, 该柔性组装实验系统包括供料、加工、装配、分拣和夹具搬运五个单元, 其工艺流程为: 供料单元将A型工件送至物料台; 夹具搬运单元夹取A型工件, 并将其运输到下一单元; 此后存在两种加工流程: (1) 将A型工件运输到加工单元进行冲压, 然后在装配单元将B型工件装入A型工件, 最后通过分拣单元将不同材质的工件分流到物料槽中; (2) 先将A型工件运输至装配单元装配, 再送到加工单元冲压, 最后送至分拣单元分流. 本实验系统选用了倍福嵌入式PC(CX2040)作为控制器, 以Visual Studio和TwinCAT作为软件平台编写实验系统的调度和控制程序.
图3 柔性组装实验系统
Fig.3 Experiment system of flexible assembly
如图4所示, 为柔性组装实验系统每个单元建立一个平行Petri网模块, 并按照工艺流程将其组合为一个完整的平行Petri网. 在初始标识下, p12p12有两个托肯, 代表供料单元中存在两个A型工件; p1p1有一个托肯, 代表输送单元在初始位置. 在目标标识下, p49p49应有两个托肯, 表示所有工件加工完成; p1p1有一个托肯, 表示夹具搬运单元回到初始位置.
图4 柔性组装实验系统平行Petri网
Fig.4 Parallel Petri nets of flexible assembly system
将图4所示平行Petri网进行简化: 根据算法1, 删除表1中所示的所有融合结构, 添加宏库所, 保留调度相关的结构和信息, 将其压缩简化为图5所示的赋时Petri网模型.
表1 平行Petri网到赋时Petri网转换表
Table1 Conversion table from parallel Petri nets to timed Petri nets
t∈ωt∈ω p∉ωp∉ω p∈ωp∈ω pwpw λz(p)λz(p) λ¯d(p)λ¯d(p) λ¯d(pw)λ¯d(pw)
t16t16、t17t17 p15p15、p16p16、p17p17 p14p14 3、70、3 76
t20t20、t21t21 p18p18、p19p19、p20p20 p15p15 2、35、3 40
t28t28、t29t29 p29p29、p30p30、p31p31 p20p20 2、35、3 40
t32t32、t33t33 p32p32、p33p33、p34p34 p21p21 2、35、3 40
t40t40、t41t41 p41p41、p42p42、p43p43 p24p24 3、70、3 76
t44t44、t45t45 p44p44、p45p45、p46p46 p25p25 2、35、3 40
t14t14 p13p13、p14p14 p13p13 0、30 30
t23t23、t24t24 p21p21、p22p22、p23p23 p16p16 0、35、0 35
t25t25、t26t26 p24p24、p25p25、p26p26 p17p17 0、40、0 40
t35t35、t36t36 p35p35、p36p36、p37p37 p22p22 0、40、0 40
t37t37、t38t38 p38p38、p39p39、p40p40 p23p23 0、45、0 45
p1p1、p3p3、p5p5 0 0
p7p7、p12p12、p49p49 0 0
p2p2、p4p4、p6p6 35 35
p8p8、p9p9、p10p10、p47p47 35 35
图5 柔性组装实验系统赋时Petri网
Fig.5 Timed Petri nets of flexible assembly system
根据算法2, 首先利用C语言编写了赋时Petri网的可达图算法, 将系统赋时Petri网模型描述为矩阵形式输入可达图算法中, 计算图5所示赋时Petri网的可达图; 其次, 仅保留可达图中所有最优轨迹上的结点, 并为其设计对应库所, 即可构成图6所示柔性组装实验系统的策略Petri网,为了简化方便, 图5中的变迁用弧和上面的标签来表示. 策略Petri网的初始状态下, 只有p^1p^1有一个托肯; p^83p^83或p^84p^84任一库所被标识则是策略Petri网所要达到的目标状态.
图6 柔性组装实验系统策略Petri网
Fig.6 Strategy Petri nets of flexible assembly system
根据算法3中的PLC函数, 为图4所示平行Petri网编制动作函数和激活函数的TwinCAT PLC程序. 以图3中供料单元为例, p12p12和p14p14为缓冲库所, 所以动作函数λA(p12)=λA(p14)=∅λA(p12)=λA(p14)=∅, 激活函数λL(p12)λL(p12)和λL(p14)λL(p14)始终为1; p13p13代表料筒传感器感知到工件A, 推杆将其推出并收回的动作过程, 所以为该库所的动作函数λA(p13)λA(p13)编写了PLC程序.
根据算法3中策略Petri网和平行Petri网的同步算法, 设计了平行Petri网和策略Petri网的C语言执行引擎程序Strategy-net和Parallel-net, 将图4所示平行Petri网和图6所示策略Petri网的关联矩阵输入到引擎程序中, 驱动两个网开始同步执行. 以图4为例, 初始状态下, 策略Petri网有且只有一个使能变迁t13t13, 所以同步标签为λ^id(t13)=aλ^id(t13)=a, 将其传递给平行Petri网; 此时平行Petri网中p12p12被标识, t13t13状态使能, 且λL(p12)=1λL(p12)=1, 当接收到来自策略Petri网的标签信息时, 满足条件λ^id(t13)=λid(t13)=aλ^id(t13)=λid(t13)=a, 平行Petri网和策略Petri网中的t13t13同时激发, p13p13和p^2p^2获得托肯. 一旦p13p13被标识, 平行Petri网从策略Petri网中获取当前同步标签λ^id(t19)=bλ^id(t19)=b, 然后执行动作函数λA(p13)λA(p13), 直到动作函数执行完毕, 激活函数变为1, t14t14激发. 由于λ^id(t14)=ελ^id(t14)=ε, 策略Petri网中已使能变迁t19t19不激发直到平行Petri网演化到p14p14被标识. 此时, 下一步执行面临多种选择. 平行Petri网可以选择激发t13t13, 把第二个工件送入供料单元; 可以选择激发t1t1, 使夹具搬运单元直接向加工单元移动; 也可以激发t15t15或t19t19, 让夹具搬运单元携带第一个工件, 将其送入加工单元或装配单元. 由于当前策略Petri网中已使能变迁为t19t19, 引导平行Petri网选择变迁t19t19, 此时同步标签相同, 两个网中t19t19同时激发, 平行Petri网继续沿着策略Petri网安排的最优轨迹执行. 以此类推, 两个网同步演化直到达到目标状态.
在实验过程中, 采集了两个工件在各个加工单元中的运行时间, 如图7所示, 绘制了各单元的运行甘特图, 其中y轴代表柔性组装实验系统的各个单元, x轴代表运行时间. 工件1在各个单元中的加工时间分别为30 s、40 s、45 s、30 s和155 s, 工件2在各个单元中的加工时间分别为30 s、40 s、45 s、30 s和355 s, 符合图4所示平行Petri网中不同工件在各模块中的加工时间; 同时, 采集得到的系统总执行时间为625 s, 与算法2中求解得到的最优轨迹的执行时间, 即系统的最小执行时间相等, 说明平行Petri网和策略Petri网能够同步运行, 且该执行轨迹为系统的最优执行轨迹.
图7 柔性组装实验系统最优调度甘特图
Fig.7 Optimal scheduling Gantt chart of flexible assembly system
本实验首先利用平行Petri网对柔性组装系统进行建模, 并为各个库所的动作函数和激活函数设计了PLC程序, 实现了平行Petri网对系统的控制; 其次, 将平行Petri网简化为赋时Petri网, 利用可达图算法求解出最优调度策略, 并将其表征为策略Petri网; 最后, 将平行Petri网和策略Petri网描述为矩阵形式, 将其输入C语言编写的同步算法中, 通过采集到的时间数据与求解得到的最优执行时间对比, 验证了该调度与控制一体化方法的可行性. 该方法的优势在于, 系统面对订单变化、故障等突发情况时, 即使求解得到了最优调度策略, 仍要面临繁冗的控制程序设计和调试过程, 大大降低了系统的可靠性和稳定性. 而本文方法是将调度和控制问题合二为一, 同步算法的提出使得我们可以把精力放在策略Petri网的设计上, 而不必再纠结于如何实现最优执行策略的问题. 当发生上述情况时只需将最优调度策略输入所设计的同步算法中, 就可以实现对实际系统的调度控制, 大大节省了时间, 使得系统能够柔性迅捷响应外界需求和变化, 提高生产效率.
6. 结论
本文提出了制造系统的控制与调度一体化的方法. 利用平行Petri网构建制造系统的信息物理模型, 并压缩简化平行Petri网为赋时Petri网, 利用赋时Petri网求解最优调度策略, 并将其表示为策略Petri网, 设计了同步执行算法使得和平行Petri网同步运行, 并编写了C语言和PLC程序, 以TwinCAT为计算平台, 实现验证了本文方法, 在一个统一的模型上求解调度和控制问题, 使得调度问题的最优解本身即可以控制执行, 提高了系统对于生产事件的快速灵活响应的能力.
本文接下来的工作, 将基于平行Petri网本身的拓扑结构, 研究网结构分解技术, 把大型调度问题等价分解为多个小型子问题, 减小计算复杂性, 使该方法能更好的应用于更为复杂的制造系统.
