一种Petri网最优控制序列的高效设计方法

doi:10.19665/j.issn1001-2400.2022.03.022

摘要/Abstract

摘要：

提出了一种基于基本标识分析的Petri网最优控制序列设计算法,根据给定的源标识和目标标识集合,生成一个成本最低的控制序列,使得源标识在执行该控制序列后到达指定的目标标识集合。该算法在Petri网的基本标识空间进行Dijkstra搜索,在减少无望分支的同时将搜索范围缩小为可达集的一个较小子集,从而很大程度上缓解了状态爆炸问题。由于搜索过程中全图未知,结点将随着计算动态增加。笔者给出了该算法的最优性证明,证明该算法每次迭代所选取的松弛结点与全局Dijkstra搜索保持一致,故最终得到的最优序列相同。进一步地提出了一种变迁选取规则,通过选择符合特定要求的显式变迁集合,将目标集合隐式可达性的判定问题转换为一个简单代数不等式的逻辑判定,使得无须求解整数规划即可快速确定目标集合的隐式可达性。实验结果表明,与基于整数规划的方法相比,该方法具有在线计算量小、求解速度快的优点,适用于受控系统需要对控制需求作出快速响应的场合。

关键词: Petri网, Dijkstra搜索算法, 基本标识, 控制序列, 调度, 最优控制

Abstract:

An algorithm for designing optimal control sequences in Petri nets based on basic marking analysis is proposed,which drives a plant net from a given source marking to a given target marking set with a least-cost control sequence.The algorithm performs Dijkstra search in the basic marking space of the Petri net so that only a small subset of the reachability set is explored with the unpromising branches discarded,which can alleviate the state explosion problem to a great extent.The entire basic reachability graph is initially unknown and revealed stepwise during the search process.It is proved that the proposed algorithm is optimal,since the nodes relaxed in each iteration is identical to that in the standard Dijkstra search,which guarantees the optimality of the outputted control sequence.Moreover,a rule for selecting the set of explicit transitions is developed so that the verification of implicit reachability can be done by checking the validity of a simple inequality.By doing so,it is now possible to quickly determine the implicit reachability of the target set without solving exhaustive integer linear programming problems.Experimental results show that,compared with the method based on integer linear programming in the literature,the method proposed in this paper has a high computational efficiency and can be used in cases where a plant must respond promptly to a request of reconfiguration.

Key words: Petri nets, Dijkstra search algorithm, basis marking, control sequence, scheduling, optimal

中图分类号:

TP2718

邹岷强,马子玥. 一种Petri网最优控制序列的高效设计方法[J]. 西安电子科技大学学报, 2022, 49(3): 199-205.

ZOU Minqiang,MA Ziyue. Efficient method for designing optimal control sequences in Petri nets[J]. Journal of Xidian University, 2022, 49(3): 199-205.

图/表 2

参考文献 19

[1]	ZHANG J F, LI H Y, FREY G, et al. Reconfiguration Control of Dynamic Reconfigurable Discrete Event Systems Based on NCESs[J]. IEEE Transactions on Control Systems Technology, 2020, 28(3):857-868. doi: 10.1109/TCST.2019.2894566
[2]	徐婷, 乔立红, 赵汉卿. 基于Petri 网的产品研发设计工作流的柔性建模方法[J]. 现代制造工程, 2021, 1:58-63.
	XU Ting, QIAO Lihong, ZHAO Hanqing. A Flexible Modeling Method for Product Development Design Workflow Based on Petri Net[J]. Modern Manufacturing Engineering, 2021, 1:58-63.
[3]	LI S, ZHAO C R. A Deadlock Control Algorithm Using Control Transitions for Flexible Manufacturing Systems Modelling with Petri Nets[J]. International Journal of Systems Science, 2020, 51(5):771-785. doi: 10.1080/00207721.2020.1737268
[4]	王祺, 陈晓亮. 一种用于柔性制造系统混惑状态估计的算法[J]. 西安电子科技大学学报, 2017, 44(2):69-74.
	WANG Qi, CHEN Xiaoliang. Algorithm for Estimating Confusion States of Flexible Manufacturing Systems[J]. Journal of Xidian University, 2017, 44(2):69-74.
[5]	POCCI M, DEMONGODIN I, GIAMBIASI N, et al. Testing Experiments on Synchronized Petri Nets[J]. IEEE Transactions on Automation Science and Engineering, 2014, 11(1):125-138. doi: 10.1109/TASE.2013.2290774
[6]	YUE H, XU S L, ZHOU G R, et al. Estimation of Least-Cost Transition Firing Sequences in Labeled Petri Nets by Using Basis Reachability Graph[J]. IEEE Access, 2019, 7:165387-165398. doi: 10.1109/ACCESS.2019.2952056
[7]	LEFEBVRE D, LECLERCQ E. Control Design for Trajectory Tracking with Untimed Petri Nets[J]. IEEE Transactions on Automatic Control, 2015, 60(7):1921-1926. doi: 10.1109/TAC.2014.2363311
[8]	LEFEBVRE D. Near-Optimal Scheduling for Petri Net Models with Forbidden Markings[J]. IEEE Transactions on Automatic Control, 2018, 63(8):2550-2557. doi: 10.1109/TAC.2017.2767827
[9]	ZHANG J F, LI H Y, FREY G, et al. Shortest Legal Firing Sequence of Net Condition/Event Systems Using Integer Linear Programming[C]// Proceedings of IEEE 14th International Conference on Automation Science and Engineering.Piscataway:IEEE, 2018:1556-1561.
[10]	LI J, ZHOU M C, GUO T, et al. Robust Control Reconfiguration of Resource Allocation Systems with Petri Nets and Integer Programming[J]. Automatica, 2014, 50 (3):915-923. doi: 10.1016/j.automatica.2013.12.015
[11]	郝晋渊, 孙丹丹, 郝真鸣, 等. 基于标签Petri网的自动制造系统初始资源配置优化[J]. 电子测量与仪器学报, 2020, 34(8):30-36.
	HAO Jinyuan, SUN Dandan, HAO Zhenming, et al. Initial Resource Allocation Optimization of Automated Manufacturing Systems Using Labeled Petri Nets[J]. Journal of Electronic Measurement and Instrumentation, 2020, 34(8):30-36.
[12]	蒋忠远, 张秀艳, 马子玥. 智能电网中电能存储系统的容量优化[J]. 西安电子科技大学学报, 2015, 42(6):106-112.
	JIANG Zhongyuan, ZHANG Xiuyan, MA Ziyue. Capacity Optimization for Power Storage Systems in Smart Grids[J]. Journal of Xidian University, 2015, 42(6):106-112.
[13]	KLOETZER M, MAHULEA C. Path Planning for Robotic Teams Based on LTL Specifications and Petri Net Models[J]. Discrete Event Dynamic Systems-Theory and Applications, 2020, 30(1):55-79. doi: 10.1007/s10626-019-00300-1
[14]	丁明, 张书玲, 张琛, 等. 一种航空电子系统安全性需求验证方法[J]. 西安电子科技大学学报, 2019, 46(3):66-73.
	DING Ming, ZHANG Shuling, ZHANG Chen, et al. Method for the Verification of Safety Requirements of Avionics Systems[J]. Journal of Xidian University, 2019, 46(3):66-73.
[15]	马子玥, 童音. 采用基本标识图的Petri网控制策略[J]. 西安电子科技大学学报, 2016, 43(6):68-73.
	MA Ziyue, TONG Yin. Supervisor Synthesis in Petri Nets Based on Basis Marking Graphs[J]. Journal of Xidian University, 2016, 43(6):68-73.
[16]	CABASINO M P, GIUA A, SEATZU C. Fault Detection for Discrete Event Systems Using Petri Nets with Unobservable Transitions[J]. Automatica, 2010, 46(9):1531-1539. doi: 10.1016/j.automatica.2010.06.013
[17]	MA Z Y, TONG Y, LI Z W, et al. Basis Marking Representation of Petri Net Reachability Spaces and its Application to the Reachability Problem[J]. IEEE Transactions on Automatic Control, 2017, 62 (3):1078-1093. doi: 10.1109/TAC.2016.2574120
[18]	SCHRIJVER A. On the History of the Shortest Path Problem[J]. Documenta Mathematica, 2012, 17 (1):155-167.
[19]	GIUA A, DICESARE F, SILVA M. Generalized Mutual Exclusion Constraints for Petri nets with Uncontrollable Transitions[C]// Proceedings of IEEE International Conference on Systems,Man and Cybernetics.Piscataway:IEEE, 1992:974-979.

源标识M_s	算法1			ILP-D
源标识M_s	搜索空间	时间/s	最小成本	搜索空间	时间/s	最小成本
[2 0 1 3 0 1 0 0 0 0 1 0 0 1 0 2 6 3]	1 398	0.96	59	1 241	10.86	59
[0 4 0 0 0 2 0 1 0 1 0 0 0 1 0 1 7 3]	1 002	0.58	58	877	7.47	58
[0 0 0 0 0 3 0 1 0 1 0 0 0 3 1 1 7 1]	473	0.22	30	283	2.23	30
[2 0 0 0 0 1 0 2 0 0 1 0 0 2 1 0 6 2]	756	0.40	41	579	4.87	41
[2 0 0 1 0 0 0 2 0 0 1 1 0 0 2 0 6 4]	1 081	0.68	43	1 414	12.53	43
[0 0 0 3 1 1 1 0 0 2 0 1 0 0 0 2 6 4]	1 549	1.23	51	1 561	14.03	51
[0 0 0 0 0 4 0 1 0 0 0 1 1 1 1 1 7 2]	679	0.34	35	687	5.57	35
[1 0 0 0 0 1 0 0 0 0 1 3 0 2 1 2 6 2]	446	0.22	30	401	3.23	30
[4 0 0 0 0 0 0 0 0 0 3 2 0 0 0 2 4 4]	2 089	1.92	55	2 124	19.29	55
[1 1 0 1 1 0 0 0 0 0 1 1 2 0 1 2 5 2]	974	0.59	43	1 029	8.76	43