随着工业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网对物理设备的感知、控制和执行.

本文结构如下: 第1节回顾了标签赋时Petri网和TwinCAT的相关概念; 第2节定义了平行Petri网; 第3节给出了平行Petri网的赋时Petri网和策略Petri网的生成方法; 第4节给出了调度与控制一体化的执行算法; 第5节进行了实验验证; 第6节对全文进行了总结.

1.   基本概念

Petri网结构是一个四元组$ N = (P,T,F,W) $, $ P $和$ T $分别为库所集和变迁集; $F \subseteq (P \times T) \cup (T \times P)$是连接库所和变迁的有向弧集合; $W:F \to \{ 1, 2,\cdots\}$是一个映射, 为$ F $中每条弧指定一个正整数权重. 在本文中, 所有弧的权重默认为1; 令$x\in P\cup T$是Petri网N的节点, $x $ 的前置集$^\bullet x $ 定义为$^\bullet x= \{y \in P \cup T|(y,x) \in F\},$$x $ 的后置集$x^\bullet$ 定义为$x^\bullet = \{y \in P \cup T|(x,y)\in F\};$ $ {C^ - } $和$ {C^ + } $是Petri网结构的前置和后置关联矩阵, $\forall p \in P$, $\forall t \in T$, $(p,t) \in F \Rightarrow {C^ - }(p, t) = W(p,t)$, $(p,t) \notin F \Rightarrow {C^ - }(p,t) = 0$; $(t,p) \in F \Rightarrow {C^ + }(p, t) = W(p,t)$, $(t,p) \notin F \Rightarrow {C^ + }(p,t) = 0$. $C = {C^ + } - {C^ - }$表示其关联矩阵. Petri网记作$ G = (N, {m_0}) $, 其中$ m_0 $为初始标识. 如果$ m \ge {C^ - }(\cdot,t) $, 那么$ t $在标识$ m $下状态使能, 用$ m[t\rangle $表示, 状态使能的变迁$ t $可以激发, 生成新的标识$ m' = m + C( \cdot ,t) $, 记作$ m[t \rangle m' $. $ {T^{\rm{*}}} $是$ T $中的变迁组成的变迁串的集合. $ m[\sigma\rangle $表示变迁激发序列$ \sigma = t_{\sigma1}t_{\sigma2}\cdots t_{\sigma k} $, $k\in \{1, 2,\cdots\}$, 在$ m $处状态使能. $ m[\sigma\rangle m' $表示$ m $经过激发序列$ \sigma $得到新的标识$ m' $. Petri网在初始标识处状态使能的激发序列集合为$ L(G) = \{\sigma\in T^*\mid m_0[\sigma\rangle\} $, 可达标识集为$R(G) = \{m\mid \sigma\in L(G), m_0[\sigma\rangle m\}$.

标签Petri网定义为$ {G_l} = (N,{m_0},\Sigma ,l) $, 其中$ N $为一个Petri网结构, $ \Sigma $为标签的集合, 每个标签为一个字母; $ l:T \to \Sigma\cup\left\{ \varepsilon\right\} $是将标签映射到变迁的标签函数, 每个变迁的标签都是$ \Sigma $中的一个字母或者空字符$ \varepsilon $. 在本文中, 假设任意两个变迁$ t_1 $和$ t_2 $, 如果$ l(t_1)\neq\varepsilon\wedge l(t_2)\neq\varepsilon $, 那么$ l(t_1)\neq l(t_2) $. $ \Sigma^* = \Sigma\cup\{\varepsilon\} $为标签组成的标签串的集合. 存在一个自然映射关系: $ \rho:T^*\to \Sigma^* $, 其中任意变迁序列$ \sigma = t_1t_2\cdots t_n $, $ \rho(\sigma) = l(t_1)l(t_2)\cdots l(t_n) $.

库所赋时Petri网表示为$ {G_d} = (N,{m_0},d) $, $ d:P \to \{ 0\} \cup {\bf{R}^{\rm{ + }}} $表示附在库所上的时延函数, 时延可以是零或正实数. 本文中涉及的赋时Petri网遵从如下假设: 如果一个库所的时延不为0, 那么该库所的最大标识为1. 对于赋时Petri网的任意变迁$ t $, 如果在当前标识下是使能的, 并且它的每一个输入库所中的托肯在其所在的库所的停留时间超过该库所的时延, 那么该变迁可以激发.

TwinCAT^[29]是基于Windows操作系统的PLC控制平台, 并为C/C++ 提供了接口, 可以实现C/C++ 与PLC语言的联合编程.

2.   平行Petri网

在学者提出的平行Petri网^[16]中, 解决了与环境交互的问题, 但缺乏调度相关信息, 需要加入成本因素, 扩展平行Petri网的定义.

定义 1. 平行Petri网是一个11元组$G = \left( {N,{m_0},{\Sigma _{\rm{I}}},{\Sigma _{\rm{O}}},{\Sigma _{\rm{A}}},{\Sigma _{\rm{L}}},{\Sigma _{\rm{id}}},{\lambda _{\rm{A}}},{\lambda _{\rm{L}}},{\lambda _{\rm{id}}},{\lambda _{\rm{z}}}} \right)$, 其中:

1) $ N $是普通Petri网结构.

2) $ m_0 $是初始标识.

3) $ \Sigma_{\rm{I}} $为输入字母表, 每个元素是一个来自传感器的输入信号.

4) $ \Sigma_{\rm{O}} $为输出字母表, 每个元素是一个送往执行机构的输出信号.

5) $ \Sigma_{\rm{id}} $为标签字母表, 其中每个元素是一个标签符号, 用以指定系统事件的身份.

6) $ {\lambda _{\rm{A}}}:P \to {\Sigma _{\rm{A}}} $是将库所集映射到动作集的函数, 它给每个库所附一个动作函数. 动作函数是从输入信号集合到输出信号集合的映射, 即$ {2^{{\Sigma _{\rm{I}}}}} \to {\Sigma _{\rm{O}}} $, 动作函数的集合为$ \Sigma_{\rm{A}} $; 给定任意库所$ p $, 如果$ \lambda_{\rm{A}}(p)\neq \emptyset $, 那么称库所$ p $为动作库所; 否则, 称其为非动作库所.

7) $ {\lambda _{\rm{L}}}:P \to {\Sigma_{\rm{L}}} $是将库所集映射到激活函数集的函数, 它给每个库所附一个激活函数. 激活函数是用来终止动作函数执行和激活变迁执行的判断条件, 是输入和输出信号集合的集合到0或1的映射, 即 $ {2^{{\Sigma _{\rm{I}}} \cup {\Sigma _{\rm{O}}}}} \to \{ 0,1\} $, $ \Sigma_{\rm{L}} $为激活函数的集合. 且$\forall p\in P: \lambda_{\rm{A}}(p) = \alpha\to\lambda_{\rm{L}}(p) = \bar\alpha$.

8) $ {\lambda _{\rm{id}}}:T \to {\Sigma _{\rm{id}}} \cup \left\{ \varepsilon \right\} $是将变迁映射到标签的函数, 其中, 每一个变迁的标签为一个字母或者一个空字符$ \varepsilon $. 每个变迁至少有一个标签符号, 该标签不与其他变迁共享. $ \forall t_i,t_j\in T,\lambda_{\rm{id}}(t_i) = \lambda_{\rm{id}}(t_j) = \varepsilon $或$ \lambda_{\rm{id}}(t_i)\ne\lambda_{\rm{id}}(t_j) $.

9) $ {\lambda _{\rm{z}}}:{\Sigma _{\rm{A}}} \to \{ 0\} \cup {\bf{R} }^+ $表示每个动作函数对应的动作的执行时间.

定义 2. 给定平行Petri网当前获得的标签集合$ \Sigma_{\rm{E}} $和任意变迁 $ t $, 如果$ \lambda_{\rm{id}}(t)\in\Sigma_{\rm{E}} $, 并且$\forall p\in\,^{\bullet}t: \lambda_{\rm{L}}(p) = 1$, 那么变迁$ t $是同步使能的.

定义 3. 平行Petri网的演化规则定义如下:

1) 一旦动作库所被标识, 立即执行附在库所上的动作函数和激活函数;

2) 如果一个变迁既是状态使能, 又是同步使能, 则该变迁是使能的;

3) 只有使能的变迁可以激发, 且任何变迁$ t $的激发满足状态方程$ m' = m+C(\cdot,t) $.

根据定义1 ~ 3, 我们描述了平行Petri网的定义及其运行规则: 首先, 在库所上附加了动作函数和激活函数, 从而利用动作函数驱动执行机构, 利用激活函数扫描传感器信号实现Petri网与物理实体的交互; 其次, 在变迁上附加了标签字符, 从而可以实现Petri网与信息空间的其他虚拟实体(比如优化策略)之间的同步; 最后, 动作函数上附加了执行时间属性, 从而可以描述系统运行的时间成本, 为优化调度提供了依据.

生产制造等物理信息系统是由众多的单元按照一定的业务逻辑耦合而成的, 因此, 可以采用模块化的方法为其设计平行Petri网模型. 因篇幅限制, 本文不再对平行Petri网的设计问题展开讨论, 在第5节将利用一个实验示例演示其设计过程.

3.   平行Petri网的优化调度方法

3.1   平行Petri网的抽象和简化

平行Petri网为信息物理系统搭建了严谨的数学模型, 而且模型中包含了时间等成本信息. 这意味着可以利用它来研究优化调度问题.

根据平行Petri网的定义, 它的运行需要来自物理世界的同步信号, 因此无法直接作为优化的仿真模型, 而且模型中存在大量与优化调度不相关的冗余结构, 状态空间会组合式快速增长. 虽然目前智能搜索算法可以避免遍历可达图, 但其搜索效率难以保证. 通过网结构的简化技术可以指数地减小可达图的规模, 是降低计算复杂性的有效手段. 因此需要对平行Petri网进行简化, 抽象仅保留调度相关结构和信息的仿真模型. 而赋时Petri网恰好满足这个要求.

定义 4. 如果一个平行Petri网存在有序三元组$ (p,t,p') $, 且满足: 1) $ ^\bullet t = \{p\} $; 2) $ t^\bullet = \{p'\} $; 3) $\lvert^\bullet p\rvert = \lvert p^\bullet\rvert = 1$; 4) $ \lvert^\bullet p'\rvert = \lvert p'^\bullet\rvert = 1 $; 5) $ m_0(p) = m_0(p') = 0 $, 那么称该三元组为一个融合结构, 记作$ \omega $. 融合结构的集合记作$ \Omega $.

定义 5. 给定平行Petri网$ G $和它的一个融合结构$ \omega = (p,t,p') $, 在网中设计库所$ p_{\omega} $, 如果满足下列条件: 1) 对于$ p $的输入变迁$ t' $, 添加一个从$ t' $到$ p_{\omega} $的有向弧, 即$ (t',p_{\omega}) $; 2) 对于$ p' $的输出变迁$ t'' $, 添加一个从$ p_{\omega} $到$ t'' $的有向弧, 即$ (p_{\omega},t'') $, 那么$ p_{\omega} $称为$ \omega $的宏库所.

根据定义4和定义 5, 可以设计将平行Petri网简化为赋时Petri网的算法.

算法 1. 平行Petri网到赋时Petri网的简化算法

输入. 平行Petri网$G = ( N,{m_0},{\Sigma _{\rm{I}}},{\Sigma _{\rm{O}}},{\Sigma _{\rm{A}}},{\Sigma _{\rm{L}}},{\Sigma _{\rm{id}}},{\lambda _{\rm{A}}}, {\lambda _{\rm{L}}},{\lambda _{\rm{id}}},{\lambda _{\rm{z}}})$.

输出. 赋时Petri网$ \bar{G} = (\bar{N},\bar{m}_0, \bar{\lambda}_{\rm{d}}) $.

1 for all $ p\in P $ do

2 　if $ \lambda_{\rm{A}}(p) = \emptyset $ then

3 　　$ \lambda_{\rm{d}}(p) = 0 $;

4 　else

5 　　$ \lambda_{\rm{d}}(p) = \lambda_{\rm{z}}(\lambda_{\rm{A}}(p)) $;

6 　end if

7 end for

8 $ \bar{N} = N $;

9 while $ \Omega\ne\emptyset $ do

10 　　从融合结构的集合$ \Omega $中选择任意一个$\omega = $ $ (p,t,p') $;

11 　　根据定义5设计一个宏库所$ p_{\omega} $, 即$ \bar P = \bar P\cup $ $\{p_{\omega}\} $, $ \bar F = \bar F\cup\{(t_1,p_{\omega}),(p_{\omega},t_2)\} $, 其中$ t_1 $是 $ P $的输入变迁, $ t_2 $是$ P $的输出变迁;

12 　　 从$ \bar N $中删除融合结构$ \omega $;

13 　　 $ m_0(p_{\omega}) = 0 $;

14 　　 $ \lambda_{\rm{d}}(p_{\omega}) = \lambda_{\rm{d}}(p)+\lambda_{\rm{d}}(p') $;

15 　　 $ \Omega = \Omega-\{\omega\} $;

16 end while

17 for all $ p\in\bar{P} $ do

18 　　 $ \bar{m}_0(p) = m_0(p) $;

19 　　 $ \bar{\lambda}_{\rm{d}}(p) = \lambda_{\rm{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' $的动作函数$ \lambda_{\rm{A}}(p') = \alpha $, 激活函数$ \lambda_{\rm{L}}(p') = \bar\alpha $, 动作函数执行时间$ \lambda_{\rm{z}}(\alpha) $ = 1; 所以赋给库所$ p' $的时延$ \lambda_{\rm{d}}(p') = \lambda_{\rm{z}}(\alpha) = 1 $. 然后, 去除$ p' $的动作函数$ \alpha $和激活函数$ \bar\alpha $. 库所$ p $和$ p'' $同理.

2) 对于网中的融合结构, 将其压缩为宏库所, 宏库所的时延为原有库所时延之和, 托肯数为0; 对于非融合结构, 则保持不变. 从图1中可以看出, 网中存在融合结构$ (p,t,p'') $, 所以将库所$ p $和$ p'' $以及变迁$ t $压缩为宏库所$ p_{\omega} $, 并添加有向弧$ (t',p_{\omega}) $和$ (p_{\omega},t'') $. 宏库所的时延为5、$ p $和$ p'' $的时延之和. 对于库所$ p' $和变迁$ t' $, 保持不变. 由此即可简化为赋时Petri网模型.

定义 6. 给定一个信息物理系统的平行Petri网, 如果它的一个标识表示这个信息物理系统任务完成时的状态, 则该标识称为平行Petri网的目标标识.

定义 7. 给定一个平行Petri网和它的目标标识$ m_g $, 如果标识$ \bar{m}_g $是赋时Petri网的一个标识, 并且$ \forall p\in\bar{P}:\bar{m}_g(p) = m_g(p) $, 那么$ \bar{m}_g $就是赋时Petri网的目标标识.

定义 8. 给定一个平行(赋时) Petri网, 如果标识变迁的交替序列$\pi = m_{\pi_0}[t_{\pi_1}\rangle m_{\pi_1}[t_{\pi_2}\rangle\cdots m_{\pi_{n-1}} [t_{\pi_n}\rangle$$ m_{\pi_n} $ 满足下列条件: 1) $ m_{\pi_0} = m_0 $; 2) $m_{\pi_{k-1}}\ge C^-(\cdot,t_k)$, $m_{\pi_{k}} = m_{\pi_{k-1}} + C(\cdot,t_k)$, $1 \le k \le n$; 3) $ m_{\pi_n} $是一个平行(赋时) Petri网的目标标识, 那么称$ \pi $为平行(赋时) Petri网的一条执行轨迹. 变迁序列$ t_{\pi_1}t_{\pi_2}\cdots t_{\pi_n} $称为$ \pi $的激发序列, 记作$ \pi^{\uparrow} $. $ \pi $的运行时间记作$ d(\pi) $.

定义 9. 给定一个平行(赋时) Petri网执行轨迹的集合$ \Pi $, 如果一条执行轨迹的执行时间最小, 那么称其为最优执行轨迹, 平行(赋时) Petri网的最优执行轨迹的集合记作$ \Pi^* $.

定义 10. 给定一个平行Petri网及其赋时Petri网, 如果$ \pi $是平行Petri网的一条执行轨迹, $ \bar\pi $是赋时Petri网的一条执行轨迹, 并且从$ \pi $的激发序列$ \pi^\uparrow $中剔除不存在于赋时Petri网的变迁后的变迁序列等于$ \bar\pi $的激发序列, 那么$ \pi $和$ \bar\pi $是同步的.

定理 1. 给定任意平行Petri网和其赋时Petri网, 下列结论成立: 1) 对于平行Petri网上的每一条执行轨迹, 赋时Petri网上都有一条唯一的执行轨迹与之同步; 2) 对于赋时Petri网上的一条执行轨迹, 平行Petri网上都有至少一条执行轨迹与之同步.

证明. 假设平行Petri网的执行轨迹为$\pi = m_0[\pi^\uparrow\rangle m_g$, 其中, $ \pi^\uparrow = t_{\pi_1}t_{\pi_2}t_{\omega_1}t_{\omega_2}\cdots t_{\omega_m}t_{\pi_n} $, $t_{\omega_m}\in \omega_m$, $ m\in\{1,2,\cdots\} $; 简化得到的赋时Petri网的执行轨迹为$ \bar\pi = \bar{m}_0[\bar{\pi}^{\uparrow}\rangle\bar{m}_g $, 其中, $ \bar{\pi}^\uparrow = t_{\pi_1}t_{\pi_2}\cdots t_{\pi_n} $. 根据算法1和定义4, $ m_0 $和$ m_g $不是融合结构的一部分, $\exists p_0,p_g \in \bar P,\bar{m}_0(p_0) = m_0(p_0),\bar{m}_g(p_g) = m_g(p_g).$ 所以只需证明激发序列$ \pi^\uparrow = \bar{\pi}^\uparrow $, 即可证明$ \pi $和$ \bar\pi $是同步的. 因为$ t_{\omega_m} $是$ \pi $中的变迁但不是$ \bar\pi $中的变迁, 同时也是融合结构$ \omega_m $的组成元素, 将平行Petri网简化为赋时Petri网时需要压缩融合结构, 压缩$ \omega_m $意味着$ t_{\omega_m} $被移除, 所以移除$ t_{\omega_m} $后得到$ \pi = \bar\pi $, 根据定义10, $ \pi $和$ \bar\pi $是同步的. 而且由于平行Petri网中存在融合结构, 所以简化得到的赋时Petri网的变迁集$ \bar T\in 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网$ \bar G $.

输出. 策略Petri网$ \hat G = (\hat N,\hat{m}_0) $.

1 生成赋时Petri网的可达图$ R(\bar G,\bar{m}_0) = (V,F,W) $, 顶点集$ V $中的元素表示可达图中的标识, 那么$ F $中 的有序对$ (v_1,v_2) $表示网可以从标识$ v_1 $经过一个变 迁$ t = W(v_1,v_2) $的激发到达标识$ v_2 $;

2 计算赋时Petri网最优执行轨迹的集合$ \Pi^* $;

3 从可达图$ R $上删除所有不在最优执行轨迹上的标识 对应的结点, 得到的子图记作$ R^* $;

4 for all $ v\in V^* $ do

5 为$ v $设计一个库所$ p_v $;

6 $ \hat P = \hat P\cup \{p_v\} $;

7 if $ v $是初始标识then

8 $ \hat{m}_0(p_v) = 1 $;

9 else

10 $ \hat{m}_0(p_v) = 0 $;

11 end if

12 end for

13 for all $ w\in W^* $ do

14 为有序对$ (v_1,v_2) $对应库所对$ (p_{v_1},p_{v_2}) $设计一 个变迁$ t_{v_1v_2} $;

15 画一条有向弧使得$ p_{v_1} $指向$ t_{v_1v_2} $, 画另外一条 有向弧使得$ t_{v_1v_2} $指向$ p_{v_2} $;

16 $ \hat T = \hat T\cup\{t_{v_1v_2}\} $;

17 end for

算法2描述了平行Petri网的策略Petri网的生成过程, 步骤1 ~ 3移除了赋时Petri网可达图中不在最优轨迹上的标识结点, 得到了只包含组成最优轨迹标识结点的子图$ R^* $; 步骤4 ~ 17为$ R^* $中每个标识结点设计对应库所, 对于初始标识对应库所, 其库所标识为1, 其他库所标识为0, 对于具有先后关系的标识, 为其对应库所设计了变迁并用有向弧连接, 构成了策略Petri网$ \hat G $.

定义 11. 对于策略Petri网中的任意一条路径, 如果网中没有任何一条路径可以包含它, 那么称其为极大路径.

由算法2可得到下列性质:

性质 1. 策略Petri网是一个状态机.

性质 2. 策略Petri网是无环的.

性质 3. 策略Petri网内始终只有一个托肯.

性质 4. 策略Petri网的一条极大路径唯一地表示赋时Petri网的一条最优执行轨迹.

性质1 ~ 4可由算法2直接推导, 其证明从略.

4.   平行Petri网和策略Petri网的同步执行算法

得到策略Petri网后, 需要给出与其平行Petri网的同步执行算法, 使得调度和控制在一个系统中同步进行.

定义 12. 给定平行Petri网$ G $和其策略网$ \hat G $, 同步标签函数$ \hat{\lambda}_{\rm{id}} $是从平行Petri网的变迁集合到字符集合的一个映射, 其中$ \forall t\in T $, $t\in \hat T\to\hat{\lambda}_{\rm{id}}(t) = \lambda_{\rm{id}}(t)$, $ t\not\in \hat T\to\hat{\lambda}_{\rm{id}}(t) = \varepsilon $.

定义 13. 给定平行Petri网和其策略Petri网, 它们的同步运行条件是: 1) $ \forall t\in T $, 如果存在同步标签函数$ \hat{\lambda}_{\rm{id}}(t) = \lambda_{\rm{id}}(t) $, 那么平行Petri网和策略Petri网中的变迁$ t $只有在同时使能时才能激发, 且为同时激发; 2) $ \forall t\in T $, 如果$ \hat{\lambda}_{\rm{id}}(t) = \varepsilon $, 平行Petri网中的变迁$ t $满足使能条件时立即激发.

定理 3. 如果平行Petri网与策略Petri网同步执行, 那么平行Petri网可以在最短的时间内到达目标标识.

证明. 根据性质1 ~ 4和定理1, 平行Petri网中的任意一条最优轨迹, 策略Petri网上都有一条极大路径与之同步, 同时根据定义9, 最优轨迹的执行时间最短. 两者同步执行时, 假设变迁$ t $在策略Petri网标识$ \hat m $下使能, 经过空字符变迁, 平行Petri网当前标识$ m $才能演化到$ m' $, $ m' $是平行Petri网中使得变迁$ t $使能的标识. 根据定义13, 只要遇到空字符变迁就立即激发, 所以$ m $连续激发, 而策略Petri网标识$ \hat m $下当前使能变迁为 $ t $, 未满足同步运行条件, 不会继续演化, 直到平行Petri网到达标识$ m' $, 存在变迁$ t $使得$ \hat{\lambda}_{\rm{id}}(t) = \lambda_{\rm{id}}(t) $, 使得两个网中的变迁$ t $同步使能. 所以平行Petri网和策略Petri网同步执行时, 假设平行Petri网当前标识为$ m $, 策略Petri网当前标识为$ \hat m $, 对于任意策略Petri网当前标识下使能的变迁, 平行Petri网都可以通过激发空字符变迁到达使得该变迁使能的标识, 即

综上, 平行Petri网可以在最短时间内到达目标标识. □

根据定义12和定义13, 设计了策略Petri网与平行Petri网同步执行的算法.

算法 3. 策略Petri网与平行Petri网同步执行算法

输入. 平行Petri网$ G $, 策略Petri网$ \hat G $.

输出. 平行Petri网的目标标识$ m_g $, 策略Petri网的目标标识$ \hat{m}_g $.

function Strategy-net$(\hat m )$ returns $ (\hat m, \beta) $

1 while $ \hat m\ne\hat{m}_g $ do

2 $ {\Sigma _{\rm{E}}} = \emptyset $;

3 for all $ t\in\hat T $ do

4 if $\hat m \ge\hat{C}^ - \left( {\cdot,t} \right)$ then

5 $ {\Sigma _{\rm{E}}} = {\Sigma _{\rm{E}}} \cup \{ {\hat\lambda _{\rm{id}}}(t)\} $;

6 end if

7 end for

8 $\beta = {\rm{{random}}}({\Sigma _{\rm{E}}})$;

9 $\hat m = \hat m + \hat{C}(\cdot,t)$;

10 return $ (\hat m, \beta) $

11 end while

function Parallel-net$(\hat m, \beta)$

1 while $ m\ne m_g $ do

2 $ \hat m = \hat m_0 $;

3 $ (\hat m, \beta) $ = Strategy-net$(\hat m)$;

4 for all $ t\in T $ do

5 读取下位机PLC中的变量$ \gamma $;

6 if $[m\ge C^-(\cdot,t)]\wedge[\wedge_{p\in ^\cdot t}\gamma(p)]$ then

7 if $ \hat{\lambda}_{\rm{id}}(t) = =\varepsilon $ then

8 $m = m+C(\cdot,t)$;

9 向下位机PLC发送标识$ m $;

10 跳转到步骤3;

11 else if $ \hat{\lambda}_{\rm{id}}(t) = =\beta $ then

12 $ m = m+C(\cdot,t) $;

13 向下位机PLC发送标识$ m $;

14 跳转到步骤2;

15 end if

16 end if

17 end for

18 end while

function PLC()

1 for $ p\in P $ do

2 读取上位机标识$ m $;

3 if $ m(p)\ge 1 $ then

4 if $ p $是非动作库所do

5 $ \lambda_{\rm{L}}(p) = 1 $;

6 else

7 执行动作函数$ \lambda_{\rm{A}}(p) $, 并以其计算结果更新 PLC的输出;

8 $ \lambda_{\rm{L}}(p) = 1 $;

9 end if

10 $ \gamma(p) = \lambda_{\rm{L}}(p) $;

11 向上位机发送变量$ \gamma $;

12 end if

13 end for

算法3由Strategy-net、Parallel-net和PLC三个函数构成. Strategy-net和Parallel-net运行于同一计算内核上, 负责计算和决策平行Petri网的演化进程; PLC运行在另一个计算内核, 负责感知和执行物理实体. Parallel-net和PLC通过ADS (Automation device specification)通信^[16]进行数据传递. 三个函数同时执行, PLC负责读取当前标识并执行动作函数和激活函数; 策略网中, $ \Sigma_{\rm{E}} $是当前可选择的同步标签集合, 遍历当前所有可激发变迁, 将其同步标签放入集合$ \Sigma_{\rm{E}} $, 从中随机选择一个标签$ \beta $传递给Parallel-net; Parallel-net读取PLC中的激活函数$ \gamma $, 使平行网不断演化直到与$ \beta $标签相同的变迁激发, 进行下一循环.

如图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网. 在初始标识下, $ p_{12} $有两个托肯, 代表供料单元中存在两个A型工件; $ p_{1} $有一个托肯, 代表输送单元在初始位置. 在目标标识下, $ p_{49} $应有两个托肯, 表示所有工件加工完成; $ p_1 $有一个托肯, 表示夹具搬运单元回到初始位置.

图 4  柔性组装实验系统平行Petri网

Fig. 4  Parallel Petri nets of flexible assembly system

下载: 全尺寸图片 幻灯片

将图4所示平行Petri网进行简化: 根据算法1, 删除表1中所示的所有融合结构, 添加宏库所, 保留调度相关的结构和信息, 将其压缩简化为图5所示的赋时Petri网模型.

表 1  平行Petri网到赋时Petri网转换表

Table 1  Conversion table from parallel Petri nets to timed Petri nets

$t\in\omega$	$p\not\in\omega$	$p\in\omega$	$p_w$	$\lambda_{\rm{z}}(p)$	$\bar{\lambda}_{\rm d}(p)$	$\bar{\lambda}_{\rm d}(p_w)$
$t_{16}$, $t_{17}$		$p_{15}$, $p_{16}$, $p_{17}$	$p_{14}$	3, 70, 3		76
$t_{20}$, $t_{21}$		$p_{18}$, $p_{19}$, $p_{20}$	$p_{15}$	2, 35, 3		40
$t_{28}$, $t_{29}$		$p_{29}$, $p_{30}$, $p_{31}$	$p_{20}$	2, 35, 3		40
$t_{32}$, $t_{33}$		$p_{32}$, $p_{33}$, $p_{34}$	$p_{21}$	2, 35, 3		40
$t_{40}$, $t_{41}$		$p_{41}$, $p_{42}$, $p_{43}$	$p_{24}$	3, 70, 3		76
$t_{44}$, $t_{45}$		$p_{44}$, $p_{45}$, $p_{46}$	$p_{25}$	2, 35, 3		40
$t_{14}$		$p_{13}$, $p_{14}$	$p_{13}$	0, 30		30
$t_{23}$, $t_{24}$		$p_{21}$, $p_{22}$, $p_{23}$	$p_{16}$	0, 35, 0		35
$t_{25}$, $t_{26}$		$p_{24}$, $p_{25}$, $p_{26}$	$p_{17}$	0, 40, 0		40
$t_{35}$, $t_{36}$		$p_{35}$, $p_{36}$, $p_{37}$	$p_{22}$	0, 40, 0		40
$t_{37}$, $t_{38}$		$p_{38}$, $p_{39}$, $p_{40}$	$p_{23}$	0, 45, 0		45
	$p_{1}$, $p_{3}$, $p_{5}$			0	0
	$p_{7}$, $p_{12}$, $p_{49}$			0	0
	$p_{2}$, $p_{4}$, $p_{6}$			35	35
	$p_{8}$, $p_{9}$, $p_{10}$, $p_{47}$			35	35

下载: 导出CSV 

| 显示表格

图 5  柔性组装实验系统赋时Petri网

Fig. 5  Timed Petri nets of flexible assembly system

下载: 全尺寸图片 幻灯片

根据算法2, 首先, 利用C语言编写了赋时Petri网的可达图算法, 将系统赋时Petri网模型描述为矩阵形式输入可达图算法中, 计算图5所示赋时Petri网的可达图; 其次, 仅保留可达图中所有最优轨迹上的结点, 并为其设计对应库所, 即可构成图6所示柔性组装实验系统的策略Petri网, 为了简化方便, 图5中的变迁用弧和上面的标签来表示. 策略Petri网的初始状态下, 只有$ \hat p_1 $有一个托肯; $ \hat p_{83} $或$ \hat p_{84} $任一库所被标识则是策略Petri网所要达到的目标状态.

图 6  柔性组装实验系统策略Petri网

Fig. 6  Strategy Petri nets of flexible assembly system

下载: 全尺寸图片 幻灯片

根据算法3中的PLC函数, 为图4所示平行Petri网编写动作函数和激活函数的TwinCAT PLC程序. 以图4中供料单元为例, $ p_{12} $和$ p_{14} $为缓冲库所, 所以动作函数$ \lambda_{\rm{A}}(p_{12}) = \lambda_{\rm{A}}(p_{14}) = \emptyset $, 激活函数$ \lambda_{\rm{L}}(p_{12}) $和$ \lambda_{\rm{L}}(p_{14}) $始终为1; $ p_{13} $代表料筒传感器感知到工件A, 推杆将其推出并收回的动作过程, 所以为该库所的动作函数$ \lambda_{\rm{A}}(p_{13}) $编写了PLC程序.

根据算法3中策略Petri网和平行Petri网的同步算法, 设计了平行Petri网和策略Petri网的C语言执行引擎程序Strategy-net和Parallel-net, 将图4所示平行Petri网和图6所示策略Petri网的关联矩阵输入到引擎程序中, 驱动两个网开始同步执行. 以图4为例, 初始状态下, 策略Petri网有且只有一个使能变迁$ t_{13} $, 所以同步标签为$ \hat{\lambda}_{\rm{id}}(t_{13}) = a $, 将其传递给平行Petri网; 此时平行Petri网中$ p_{12} $被标识, $ t_{13} $状态使能, 且$ \lambda_{\rm{L}}(p_{12}) = 1 $, 当接收到来自策略Petri网的标签信息时, 满足条件$ \hat{\lambda}_{\rm{id}}({t_{13}}) = \lambda_{\rm{id}}({t_{13}}) = a $, 平行Petri网和策略Petri网中的$ t_{13} $同时激发, $ p_{13} $和$ \hat p_2 $获得托肯. 一旦$ p_{13} $被标识, 平行Petri网从策略Petri网中获取当前同步标签$ \hat{\lambda}_{\rm{id}}(t_{19}) = b $, 然后执行动作函数$ \lambda_{\rm{A}}(p_{13}) $, 直到动作函数执行完毕, 激活函数变为1, $ t_{14} $激发. 由于$ \hat\lambda_{\rm{id}}(t_{14}) = \varepsilon $, 策略Petri网中已使能变迁$ t_{19} $不激发直到平行Petri网演化到$ p_{14} $被标识. 此时, 下一步执行面临多种选择. 平行Petri网可以选择激发$ t_{13} $, 把第2个工件送入供料单元; 可以选择激发$ t_1 $, 使夹具搬运单元直接向加工单元移动; 也可以激发$ t_{15} $或$ t_{19} $, 让夹具搬运单元携带第1个工件, 将其送入加工单元或装配单元. 由于当前策略Petri网中已使能变迁为$ t_{19} $, 引导平行Petri网选择变迁$ t_{19} $, 此时同步标签相同, 两个网中$ t_{19} $同时激发, 平行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网本身的拓扑结构, 研究网结构分解技术, 将大型调度问题等价分解为多个小型子问题, 减小计算复杂性, 使该方法能更好地应用于更为复杂的制造系统.