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

doi:10.19665/j.issn1001-2400.2022.03.022

Abstract

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

CLC Number:

TP2718

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

Figures/Tables 2

References 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

Efficient method for designing optimal control sequences in Petri nets

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 19

Related Articles 15

Metrics

Comments

Recommended 10

[1]	ZHANG Dehua,HAO Xinyuan,ZHANG Nina,WEI Qian,LIU Ying. PSO-DE algorithm based on the optimal selection strategy [J]. Journal of Xidian University, 2022, 49(2): 218-227.
[2]	LV Wenkai,YANG Pengfei,DING Yunqing,ZHANG Heyu,ZHENG Tianyang. JEDERL:A task scheduling optimization algorithm for heterogeneous computing platforms [J]. Journal of Xidian University, 2021, 48(6): 67-74.
[3]	ZHANG Yupeng,WU Zili,CHEN Ming,ZHANG Lulu. Optimization of task scheduling oriented to cross microservice chains [J]. Journal of Xidian University, 2021, 48(6): 32-39.
[4]	ZHAO Hui,FENG Nanzhi,WANG Quan,WAN Bo,WANG Jing. Dynamic semi-online task scheduling method for the edge computing platform [J]. Journal of Xidian University, 2021, 48(6): 8-15.
[5]	LI Haipeng,FENG Dazheng,ZHOU Yongwei. Optimum placement method of multistatic radar barrier coverage [J]. Journal of Xidian University, 2021, 48(2): 147-155.
[6]	LI Yuewu,HU Jianwang,JI Bing. New index for evaluation of the accuracy of the track fusion algorithm [J]. Journal of Xidian University, 2020, 47(1): 111-119.
[7]	ZHANG Yunpu,SHAN Ganlin,DUAN Xiusheng,WANG Meng. Scheduling of active/passive sensors for radiation control [J]. Journal of Xidian University, 2019, 46(6): 67-74.
[8]	LIU Yiming,SHENG Wen,SHI Duanyang. Multi-beam tracking scheduling strategy for phased array radar based on the cost-effectiveness ratio [J]. Journal of Xidian University, 2019, 46(6): 155-162.
[9]	WANG Zengguang,LU Yu,LI Xi,LI Zhiwei. Optimal defense strategy selection based on the static Bayesian game [J]. Journal of Xidian University, 2019, 46(5): 55-61.
[10]	ZHEN Yan,ZHAO Hu. Resource scheduling strategy in hierarchical software defined wireless sensor networks [J]. Journal of Xidian University, 2019, 46(4): 87-98.
[11]	XIA Jun,YANG Yi,LIN Yi. Algorithm for scheduling energy-saving frame-based tasks on the heterogeneous multi-core SoC [J]. Journal of Xidian University, 2019, 46(3): 89-95.
[12]	WANG Yan. Enhanced multi-objective evolutionary algorithm for workflow scheduling on the cloud platform [J]. Journal of Xidian University, 2019, 46(1): 130-136.
[13]	ZHANG Haiwei;WU Aiguo. Non-zero vector finite-control-set model predictive control for optimal time [J]. Journal of Xidian University, 2018, 45(3): 86-90.
[14]	WANG Jianwei;ZHANG Hailin. Cumulative distribution function based resource allocation in the uplink of the small cells network [J]. Journal of Xidian University, 2018, 45(3): 163-168.
[15]	LI Zhao;JIA Wenhao;BAI Yujiao. Adaptive proportional fair scheduling with global-fairness [J]. Journal of Xidian University, 2018, 45(1): 6-11+22.