离散事件系统最优监督控制算法

doi:10.11772/j.issn.1001-9081.2022060884

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (7): 2271-2279.DOI: 10.11772/j.issn.1001-9081.2022060884

• 计算机软件技术 • 上一篇

离散事件系统最优监督控制算法

胡瑜洪, 王德光(), 何家汉, 张志恒

贵州大学电气工程学院，贵阳 550025

收稿日期:2022-06-20 修回日期:2022-08-04 接受日期:2022-08-11 发布日期:2022-08-26 出版日期:2023-07-10
通讯作者: 王德光
作者简介:胡瑜洪（1999—），男，广东揭阳人，硕士研究生，CCF会员，主要研究方向：监督控制理论、机器人路径规划和调度；
王德光（1991—），男，山西侯马人，教授，博士，CCF会员，主要研究方向：监督控制理论、离散事件系统故障诊断、机器人路径规划和调度；
何家汉（1998—），男，广东云浮人，硕士研究生，主要研究方向：离散事件系统故障诊断、不透明性验证；
张志恒（1996—），男，安徽阜阳人，硕士研究生，主要研究方向：离散事件系统故障诊断、可诊断性验证。
基金资助:
贵州省省级科技计划项目（黔科合基础-ZK［2022］一般103）;贵州大学科研基金资助项目(贵大特岗合字［2021］04号);贵州省教育厅创新群体项目(黔科合支撑［2021］012)

Optimal supervisory control algorithm of discrete-event systems

Yuhong HU, Deguang WANG(), Jiahan HE, Zhiheng ZHANG

The Electrical Engineering College，Guizhou University，Guiyang Guizhou 550025，China

Received:2022-06-20 Revised:2022-08-04 Accepted:2022-08-11 Online:2022-08-26 Published:2023-07-10
Contact: Deguang WANG
About author:HU Yuhong， born in 1999， M. S. candidate. His research interests include supervisory control theory， robot path planning and scheduling.
WANG Deguang， born in 1991， Ph. D.， professor. His research interests include supervisory control theory， fault diagnosis for discrete-event systems， robot path planning and scheduling.
HE Jiahan， born in 1998， M. S. candidate. His research interests include fault diagnosis for discrete-event systems， verification of opacity.
ZHANG Zhiheng， born in 1996， M. S. candidate. His research interests include fault diagnosis for discrete-event systems， diagnostic verification.
Supported by:
Guizhou Provincial Science and Technology Program （QianKeHeJiChu-ZK ［2022］ YiBan 103）, Scientific Research Fund of GuiZhou University(GuiDaTeGang ［2021］04);Education Department of Guizhou Province Innovation Group Project(QianKeHeZhiCheng ［2021］012)

摘要/Abstract

摘要：

离散事件系统的监控器可以通过禁止可控事件来使系统满足安全性和活性规范。然而，监控器并不对允许发生的可控事件主动进行选择，所以存在同时允许多个可控事件发生的情况。但在实际应用中，如交通调度、机器人路径规划中，要求系统在每个状态下最多只允许一个可控事件的发生。针对上述问题，引入一种最优机制来量化控制成本，并提出一种离散事件系统最优监督控制算法，以确保系统的安全性和活性，并使事件执行累计的成本最小。首先，给定受控系统和行为约束的自动机模型，并基于Ramadge和Wonham的监督控制理论求解出无阻塞和行为最大许可的监控器；其次，通过定义的成本函数为监控器中每个事件的执行赋予相应成本；最后，利用动态规划思想迭代计算求解出最优定向监控器，从而实现每个状态下最多发生一个可控事件和事件执行累计的成本最小的目标。使用单向列车导轨案例和多轨道列车控制案例来验证所提算法的有效性和正确性。对于上述两个案例，所提算法求解的定向监控器到达目标状态所需的事件执行累计的成本分别为26.0和14.0，低于贪心算法的27.5和16.0，以及Q-learning算法的26.5和14.0。

关键词: 离散事件系统, 监督控制, 最优定向监控器, 成本函数, 交通系统调度

Abstract:

A supervisor of a discrete-event system can prohibit controllable events to ensure the safety and liveness specifications of the system. However， the supervisor does not actively select the controllable events that are allowed to occur， so it is possible that several controllable events occur simultaneously. In practice， such as traffic scheduling and robot path planning， the system is required to allow at most one controllable event to occur in each state. In response to the above problem， an optimal mechanism was introduced to quantify control cost， and an optimal supervisory control algorithm of discrete-event systems was proposed， which not only can guarantee the safety and liveness of the system， but also can minimize the cumulative cost of event execution. Firstly， the automata model of controlled system and behavioral constraints was given， and a nonblocking supervisor with maximum allowable behaviors was solved on the basis of the supervisory control theory of Ramadge and Wonham. Secondly， a cost function was defined to assign the corresponding cost to the execution of each event in the supervisor. Finally， an optimal directed supervisor was calculated iteratively based on dynamic programming to achieve the goals of at most one controllable event occurring in each state and minimizing the cumulative cost of event execution. To verify the effectiveness and correctness of the proposed algorithm， a one-way train guideway example and a multi-track train control example were used. For the above two examples， the cumulative cost of the event execution required for the directed supervisor solved by the proposed algorithm to reach the target state is 26.0 and 14.0 respectively， which is lower than the 27.5 and 16.0 of greedy algorithm and the 26.5 and 14.0 of Q-learning.

Key words: discrete-event system, supervisory control, optimal directed supervisor, cost function, traffic system scheduling

中图分类号:

TP301

胡瑜洪, 王德光, 何家汉, 张志恒. 离散事件系统最优监督控制算法[J]. 计算机应用, 2023, 43(7): 2271-2279.

Yuhong HU, Deguang WANG, Jiahan HE, Zhiheng ZHANG. Optimal supervisory control algorithm of discrete-event systems[J]. Journal of Computer Applications, 2023, 43(7): 2271-2279.

图/表 14

图1 离散事件系统监督控制框图

Fig. 1 Supervisory control block diagram of discrete-event system

图2 最优定向监控器的求解框图

Fig. 2 Block diagram of solving optimal directed supervisor

图3 监控器S和它的4个定向监控器

Fig. 3 Supervisor S and its four directed supervisors

图4 例3的自动机模型

Fig. 4 Automata model of example 3

图5 例4的监控器模型

Fig. 5 Supervisor model of example 4

图6 两种案例示意图

Fig. 6 Schematic diagrams of two cases

图7 两种案例的自动机模型

Fig. 7 Automata models of two cases

图8 单向列车导轨系统的自动机模型V

Fig. 8 Automata V of one-way train guideway system

图9 单向列车导轨系统的监控器S

Fig. 9 Supervisor S of one-way train guideway system

图10 监控器S的DP-最优定向监控器

Fig. 10 DP-optimal directed supervisor of supervisor S

图11 贪心算法求解的最优定向监控器

Fig. 11 Optimal directed supervisors solved by greedy algorithm

图12 Q-learning算法求解的最优定向监控器SDQ1

Fig. 12 Optimal directed supervisorSDQ1 solved by Q-learning algorithm

图13 多轨道列车控制系统模型和它的监控器以及求解的最优定向监控器

Fig. 13 Model of multi-track train control system and its supervisor and solved optimal directed supervisors

表1 本文算法和其他两种算法在不同案例下的结果对比

Tab. 1 Result comparison of the proposed algorithm and other two algorithms in different cases

案例	算法	状态数	变迁数	事件累积执行总成本
单向列车导轨案例	贪心算法	14	16	27.5
	Q-learning	16	19	26.5
	本文算法	16	18	26.0
多轨道列车控制案例	贪心算法	8	7	16.0
	Q-learning	7	6	14.0
	本文算法	7	6	14.0

参考文献 21

1	RAMADGE P J G， WONHAM W M. The control of discrete event systems［J］. Proceedings of the IEEE， 1989， 77（1）： 81-98. 10.1109/5.21072
2	WONHAM W M， CAI K. Supervision of discrete-event systems： basics［M］// Supervisory Control of Discrete Event Systems， CCE. Cham： Springer， 2019： 85-146. 10.1007/978-3-319-77452-7_3
3	辛宗洋.基于RW框架的离散事件系统监督控制理论计算和仿真平台［J］.工业控制计算机， 2009， 22（12）： 39-41， 43. 10.3969/j.issn.1001-182X.2009.12.021
	XIN Z Y. Computation and simulation platform for supervisory control of discrete event system based on RW structure［J］. Industrial Control Computer， 2009， 22（12）： 39-41， 43. 10.3969/j.issn.1001-182X.2009.12.021
4	焦亭，刘振国.组件多工作模式下的离散事件系统监督控制方法研究［J］.控制理论与应用， 2020， 37（3）： 534-539. 10.7641/CTA.2019.80621
	JIAO T， LIU Z G. Study on the supervisory control of discrete-event systems incorporating components with several working modes［J］. Control Theory and Applications， 2020， 37（3）： 534-539. 10.7641/CTA.2019.80621
5	史晶锌，舒少龙，林峰，等.基于监督控制理论的家庭住宅用电安全性控制研究［J］.现代建筑电气， 2014， 5（1）： 9-15.
	SHI J X， SHU S L， LIN F， et al. Control for safety of home electric usage based on supervisory control theory［J］. Modern Architecture Electric， 2014， 5（1）： 9-15.
6	荣胜波，朱军，史勃，等.监督控制理论在多任务机床控制系统中的应用［J］.机床与液压， 2011， 39（22）： 85-87. 10.3969/j.issn.1001-3881.2011.22.028
	RONG S B， ZHU J， SHI B， et al. The application of supervisory control theory to control system of multiple-task machine tool［J］. Machine Tool and Hydraulics， 2011， 39（22）： 85-87. 10.3969/j.issn.1001-3881.2011.22.028
7	TATSUMOTO Y， SHIRAISHI M， CAI K， et al. Application of online supervisory control of discrete-event systems to multi-robot warehouse automation［J］. Control Engineering Practice， 2018， 81： 97-104. 10.1016/j.conengprac.2018.09.003
8	GONZALEZ A G C， ALVES M V， VIANA G S， et al. Supervisory control-based navigation architecture： a new framework for autonomous robots in industry 4.0 environments［J］. IEEE Transactions on Industrial Informatics， 2018， 14（4）： 1732-1743. 10.1109/tii.2017.2788079
9	UMEMOTO H， YAMASAKI T. Optimal LLP supervisor for discrete event systems based on reinforcement learning ［C］// Proceedings of the 2015 IEEE International Conference on Systems， Man， and Cybernetics. Piscataway： IEEE， 2015： 545-550. 10.1109/smc.2015.106
10	KAYMAKCI O， ANIK V G， USTOGLU I. A local modular supervisory controller for a real railway station ［C］// Proceedings of the 2010 IET International Conference on System Safety. Stevenage： IET， 2010： 1-6. 10.1049/cp.2010.0844
11	PASSINO K M， ANTSAKLIS P J. On the optimal control of discrete event systems ［C］// Proceedings of the 28th IEEE Conference on Decision and Control， Volume 3. Piscataway： IEEE， 1989： 2713-2718. 10.1109/cdc.1989.70672
12	BARBEAU M， FRAPPIER M， KABANZA F， et al. A supervisory control synthesis case study： the antenna control system［DB/OL］. （2013-09-27）［2022-05-14］. .
13	JING H， KUMAR R. Nonblocking directed control of discrete event systems ［C］// Proceedings of the 44th IEEE Conference on Decision and Control. Piscataway： IEEE， 2005： 7627-7632.
14	杨宪泽.基于图搜索算法的探讨［J］.西南民族学院学报， 1998， 24（2）： 117-122.
	YANG X Z. Probe into graph search algorithms［J］. Journal of Southwest Nationalities College （Natural Science Edition）， 1998， 24（2）： 117-122.
15	巫光福，万路萍.遗传算法在移动机器人路径规划的研究［J］.长江信息通信， 2021， 34（6）： 10-14.
	WU G F， WAN L P. Research on genetic algorithms in path planning of mobile robots［J］. Changjiang Information and Communications， 2021， 34（6）： 10-14.
16	徐英卓，李凯，周俊.基于改进蚁群算法的钻井救援车辆路径规划［J］.计算机系统应用， 2022， 31（4）： 268-272.
	XU Y Z， LI K， ZHOU J. Path planning of drilling rescue vehicle based on improved ant colony algorithm［J］. Computer Systems and Applications 2022， 31（4）： 268-272.
17	宋勇，李贻斌，李彩虹.移动机器人路径规划强化学习的初始化［J］.控制理论与应用， 2012， 29（12）： 1623-1628.
	SONG Y， LI Y B， LI C H. Initialization in reinforcement learning for mobile robots path planning［J］. Control Theory and Applications， 2012， 29（12）： 1623-1628.
18	付冰，周作建，张维芯.贪心算法在智能导检中的应用研究［J］.软件导刊， 2022， 21（1）： 136-140. 10.11907/rjdk.211844
	FU B， ZHOU Z J， ZHANG W X. Research on the application of greedy algorithm in intelligent guidance of health examination［J］. Software Guide， 2022， 21（1）： 136-140. 10.11907/rjdk.211844
19	蔡豪，袁正道.云数据中心基于贪心模式的虚拟机选择算法［J］.计算机应用， 2020， 40（6）： 1707-1713.
	CAI H， YUAN Z D. Greedy algorithm optimization based virtual machine selection strategy in cloud data center［J］. Journal of Computer Applications， 2020， 40（6）： 1707-1713.
20	赵海妮，焦健.基于强化学习的渗透路径推荐模型［J］.计算机应用 2022， 42（6）： 1689-1694.
	ZHAO H N， JIAO J. Recommendation model of penetration path based on reinforcement learning［J］. Journal of Computer Applications， 2022， 42（6）： 1689-1694.
21	赵彦清，朱琦.基于Q学习的异构网络选择新算法［J］.计算机应用， 2011， 31（6）： 1461-1464， 1479. 10.3724/sp.j.1087.2011.01461
	ZHAO Y Q， ZHU Q. New Q-learning based heterogeneous network selection algorithm［J］. Journal of Computer Applications， 2011， 31（6）： 1461-1464， 1479. 10.3724/sp.j.1087.2011.01461

[1]	李多芹, 方贤文, 王丽丽, 邵叱风. 基于感知成本的流程模型与事件日志有效对齐[J]. 《计算机应用》唯一官方网站, 2022, 42(10): 3154-3161.
[2]	曹琦何中市余磊. 基于DEVS/CD++的抢险救灾物资保障仿真建模研究[J]. 计算机应用, 2008, 28(11): 2967-2969.
[3]	郭楠李志蜀宋卓洋. 基于离散时间系统的地面等待策略模型研究[J]. 计算机应用, 2007, 27(11): 2626-2629.

离散事件系统最优监督控制算法

Optimal supervisory control algorithm of discrete-event systems

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 14

参考文献 21

相关文章 3

编辑推荐

Metrics