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

Optimal supervisory control algorithm of discrete-event systems

作　　者：胡瑜洪 王德光 何家汉 张志恒 HU Yuhong;WANG Deguang;HE Jiahan;ZHANG Zhiheng(The Electrical Engineering College,Guizhou University,Guiyang Guizhou 550025,China)

机构地区：[1]贵州大学电气工程学院,贵阳550025

出　　处：《计算机应用》2023年第7期2271-2279,共9页journal of Computer Applications

基　　金：贵州省省级科技计划项目(黔科合基础-ZK[2022]一般103);贵州大学科研基金资助项目(贵大特岗合字[2021]04号);贵州省教育厅创新群体项目(黔科合支撑[2021]012)。

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

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

分 类 号：TP301[自动化与计算机技术—计算机系统结构]