Estimation of Least-Cost Planning Sequence for Labeled Petri Nets

doi:10.3778/j.issn.1673-9418.2011035

Abstract

Abstract:

To solve the least-cost planning sequence problem of a manufacturing system which is modeled by labeled Petri nets, an algorithm based on backtracking method is proposed. Given a labeled Petri net with its structure and an initial marking, the searching stages are divided into parts according to the given labeled sequence. In each stage, the transition with the minimal cost fires at first. With the observation of all the labels following this rule, the sum of the costs of transitions in the firing sequence is the minimum total cost. The least-cost planning sequence and the corresponding total cost are stored. The proposed method traverses the solution space tree according to the depth-first strategy. By taking the current minimum total cost as the constraint condition, the markings and the sequence of transitions that do not need to be searched can be eliminated in other paths. Therefore, the searching space is reduced. An illustrative example shows the feasibility of the method. Compared with the execution of dynamic programming method, the proposed method needs a smaller amount of calculation and achieves higher work efficiency.

Key words: discrete event systems, labeled Petri nets, backtracking method, least-cost planning sequences

摘要：

针对制造系统的标注Petri网模型，提出一种基于回溯法估计系统最小代价计划序列的算法。已知标注Petri网模型的网结构与初始标识，根据给定的标注序列划分搜索阶段，每个标注对应的代价较小的变迁优先发生。按此规则观测到所有的标注后，对应的变迁发生序列代价的加和为最小总代价，并储存最小代价计划序列及总代价。按照深度优先策略遍历解空间树，以当前最小总代价为约束条件，剔除其他路径中不必搜索的标识以及变迁发生序列，缩小搜索空间。通过实例验证了该方法的可行性，与动态规划法执行结果相比，提出的方法能够实现更少的计算量和更高的工作效率。

关键词: 离散事件系统, 标注Petri网, 回溯法, 最小代价计划序列

ZHOU Guangrui, XU Shulin, GUO Yiyun, LU Faming, YUE Hao. Estimation of Least-Cost Planning Sequence for Labeled Petri Nets[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(7): 1350-1358.

周广瑞, 徐淑琳, 郭乙运, 鲁法明, 岳昊. 标注Petri网的最小代价计划序列估计[J]. 计算机科学与探索, 2021, 15(7): 1350-1358.

References

[1] RAN N. Supervisor synthesis and fault detection of discrete event systems using Petri nets[D]. Hangzhou: Zhejiang University, 2017.
冉宁. 基于Petri网的离散事件系统的监控器综合与故障检测[D]. 杭州: 浙江大学, 2017.
[2] YUAN C Y. Petri nets: theory and application[M]. Beijing: Publishing House of Electronics Industry, 2005.
袁崇义. Petri网原理与应用[M]. 北京: 电子工业出版社, 2005.
[3] WU Z H. Petri nets: an introduction[M]. Beijing: China Machine Press, 2006.
吴哲辉. Petri网导论[M]. 北京: 机械工业出版社, 2006.
[4] YUE H, HU H S, WU W M, et al. Polynomial-complexity supervisory control for flexible assembly systems based on Petri nets[J]. International Journal of Computer Integrated Manufacturing, 2018, 31(1): 71-86.
[5] MA Z Y, TONG Y. Supervisor synthesis in Petri nets based on basis marking graphs[J]. Journal of Xidian University, 2016, 43(6): 68-73.
马子玥, 童音. 采用基本标识图的Petri网控制策略[J]. 西安电子科技大学学报, 2016, 43(6): 68-73.
[6] LU F M, ZENG Q T, DUAN H, et al. Decidability method of Petri net nonreachability marks and its application in deadlock detection[J]. Computer Integrated Manufacturing Systems, 2016, 22(2): 465-475.
鲁法明, 曾庆田, 段华, 等. Petri网不可达标识的判定方法研究及其在死锁检测中的应用[J]. 计算机集成制造系统, 2016, 22(2): 465-475.
[7] DU N, HU H S, ZHOU M C. A survey on robust deadlock control policies for automated manufacturing systems with unreliable resources[J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(1): 389-406.
[8] LI S Y, 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.
[9] LUO J C, LIU Z Q, WANG S G, et al. Robust deadlock avoidance policy for automated manufacturing system with multiple unreliable resources[J]. IEEE-CAA Journal of Automatica Sinica, 2020, 7(3): 812-821.
[10] JIANG J X, HUANG Z Q, MA W W, et al. Research on information flow control in service composition for privacy requirement[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(3): 370-379.
姜家鑫, 黄志球, 马薇薇, 等. 满足隐私需求的服务组合信息流控制方法研究[J]. 计算机科学与探索, 2018, 12(3): 370-379.
[11] FANG X W, ZHAO F, FANG H, et al. The fusion analysis method about the change region of the business process model based on behavior inclusion in Petri net[J]. Chinese Journal of Computers, 2018, 41(3): 695-708.
方贤文, 赵芳, 方欢, 等. 基于Petri网Behavior Inclusion 的业务流程变化域融合分析[J]. 计算机学报, 2018, 41(3): 695-708.
[12] LI L X, HADJICOSTIS C N. Minimum initial marking estimation in labeled Petri nets[J]. IEEE Transactions on Automatic Control, 2013, 58(1): 198-203.
[13] ABDELLATIF A, TELMOUDI A J, BONHOMME P, et al. Minimum initial marking estimation of labeled Petri nets based on GRASP inspired method (GMIM)[J]. Cybernetics and Systems, 2020, 51(4): 467-484.
[14] LI L X, HADJICOSTIS C N. Least-cost planning sequence estimation in labelled Petri nets[J]. Transactions of the Institute of Measurement and Control, 2011, 33(3/4): 317-331.
[15] 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.
[16] 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.
[17] LEVITIN A. Introduction to the design and analysis of algorithms[M]. Upper Saddle River: Addison-Wesley, 2011.
[18] WANG C, GAO Y, LIU C, et al. Vehicle routing problem with simultaneous delivery and pickup problem solving by backtracking search optimization algorithm[J]. Computer Integrated Manufacturing Systems, 2019, 25(9): 2237-2247.
王超, 高扬, 刘超, 等. 基于回溯搜索优化算法求解带时间窗和同时送取货的车辆路径问题[J]. 计算机集成制造系统, 2019, 25(9): 2237-2247.
[19] WANG H, CHEN P F, WANG P. Deterministic scheduling algorithms for WIA-PA industrial wireless sensor networks[J]. Acta Electronica Sinica, 2018, 46(1): 68-74.
王恒, 陈鹏飞, 王平. 面向WIA-PA工业无线传感器网络的确定性调度算法[J]. 电子学报, 2018, 46(1): 68-74.
[20] YU D J, YING Y K, ZHANG L, et al. Balanced scheduling of distributed workflow tasks based on clustering[J]. Knowledge-Based Systems, 2020, 199: 1-13.
[21] ZHAI Z N, LU Y H, YU F H, et al. Backtracking tree-decomposition method with complete independence for workflow satisfiability decision (≠)[J]. Journal of Frontiers of Computer Science and Technology, 2018, 12(12): 2021-2032.
翟治年, 卢亚辉, 余法红, 等. 工作流可满足决策(≠)的完备独立树分解回溯法[J]. 计算机科学与探索, 2018, 12(12): 2021-2032.