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

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

离散事件动态系统的分层最优监控

采用流网络的完备最小割将Ｋｕｍａｒ提出的离散事件系统最优监控理论拓展到标识语言的情形,提出了在受控系统的可达状态集中优化某种指标的分层优化思想,给出了寻找可控最优子语言的算法。     

浅谈格蕴涵代数上的同余关系

本文在对格蕴涵代数上的同余关系分析研究中,对同余关系所具有的商格蕴涵代数进行详细分析研究,了解不同类别同余关系之间的关联,希望能够对格蕴含代数内的同余关系有着全面分析研究.     

离散事件系统的一种最优监控综合方法

本文基于ＤＥＳ的Ｄ－自动机模型，提出一种最优监控综合问题，然后讨论了该问题解的存在性，最后利用极小代数给出了求解该问题的方法。     

基于关系的最粗粒度划分问题的并行算法

关系最粗粒度的划分问题ＰＣＰＰ在并发系统的验证方面起着重要的作用。本文提出了ＲＣＰＰ问题的一种有效的并行算法,其中假设标号转移系统中有ｍ个转移和ｎ个状态,利用ｍ／ｎ＾∈个ＣＲＥＷ处理器算法所需的运行时间为Ｏ（ｎ＾１＋∈）（对于任意固定的∈〈１）。     

基于有限状态机最小化理论的同余关系研究*

对有限状态机(FA)的最小化理论进行了研究,提出了原机器M与其最小机器M′之间还存在一种更近的关系,即同余关系。为机器M与M′构造相关的代数系统,证明了两者之间存在同余关系。实验表明,同余关系对简化系统描述具有重要意义,为揭示原系统与约简系统之间蕴涵的更为深刻的内在关系提供了必要的理论基础。     

动态系统的一致同余安全

研究动态系统的安全问题．针对动态系统运行时间配置的可变特性，引入了动态系统的进程代数模型和复杂动态系统概念，定义了动态系统的一致安全性质和一致同余安全性质．基于观察同余等价，构造了一类一致同余安全模型．本文证明，动态系统的安全性质是一致安全性质，而对于复杂动态系统，其安全性质是一致同余安全性质．     

离散事件系统仿真中的优化算法

计算机仿真是研究离散事件系统的一类重要方法。在仿真环境下对离散事件系统的参数进行优化是设计高性能系统的必要保证。本文给出了随机型优化问题的分类，并综述了离散 参数和连续参数随机型优化问题中典型的求解算法。     

剩余格中同余关系的简化

在剩余格中定义了一种只依赖于交运算和蕴含算子的同余关系,简化了[L]作为泛代数的同余关系的表达式,证明了这种同余关系和滤子之间仍然是一一对应的,并且这种对应关系是相应的完备格之间的一个同构。     

离散事件系统分布式仿真任务分配的启发式算法

本文首先介绍了离散事件系统的异步分布式仿真方法,然后,针对任务分配问题,发展了一种启发式算法,它由过程聚类和过程重新分配两部分组成。     

A distributed algorithm for strong bisimulation reduction of state spaces

It is a known problem that state spaces can grow very large, which makes operating on them (including reducing them) difficult because of operational memory shortage. In an attempt to extend the size of the state spaces that can be dealt with, we designed and implemented a bisimulation reduction algorithm for distributed memory settings using message passing communication. By using message passing, the same implementation can be used on both clusters of workstations and large shared memory machines. The algorithm performs reduction of large labeled transition systems modulo strong bisimulation. We justify its correctness and termination and provide an evaluation of the worst-case time and message complexity and some performance data from a prototype implementation. Both theory and practice show that the algorithm scales up with the number of workstations.     

Opacity of discrete-event systems under nondeterministic observation mechanism

For some practical systems modeled by discrete-event systems (DESs), the event observation mechanism may be no longer static/fixed due to sensor faults/failures, packet loss, and/or measurement uncertainties. It is required to redefine the observations of events. Therefore, it is interesting to reconsider the opacity in the context of abnormal conditions as mentioned. In this paper, we extend notions of initial-state opacity (ISO), current-state opacity (CSO), and initial-and-final-state opacity (IFSO) in a standard setting to an advanced framework of nondeterministic observations (i.e., the event-observation mechanism is state-dependent and nondeterministic) by taking the output-observation-equivalence instead of the natural projection-equivalence into account. To efficiently verify them, we construct three new matrix-based information structures in this advanced framework called an initial-state estimator, a current-state estimator, and an initial-and-final-state estimator using the Boolean semi-tensor product (BSTP) theory. Accordingly, the matrix-based criteria for verifying these three types of opacity are given, respectively. Computational complexity analysis as well as illustrative examples are also provided for the proposed results.     

观测永久丢失下随机离散事件系统故障预测的验证算法

针对随机离散事件系统在故障预测时可能出现系统观测永久丢失,导致预测不准确的问题,提出一种观测永久丢失下故障预测验证的算法。首先对观测永久丢失的随机离散事件系统的U-可预测性进行了形式化。其次使用随机预测器构造了一个随机离散事件系统的U-预测器,实现了系统的故障预测。基于U-预测器,提出了随机离散事件系统U-可预测性的充分必要条件及验证算法,并且引入成对的方式,明显地改进了该验证算法的复杂度。仿真结果表明,该验证算法使得观测永久丢失下系统故障预测准确。最后,实例说明观测永久丢失下故障预测验证算法的应用。结果表明,该验证算法相比现有同类验证算法应用范围更广,验证结果更精确。     

Hierarchical control of timed discrete-event systems

An abstract hierarchical control theory is developed for a class of timed discrete-event systems (TDES) within the discrete-event control architectural framework proposed earlier by the authors. For this development, a control theory for TDES is introduced in the spirit of a prior theory of Brandin. A notion of time control structures is introduced, and on its basis a general property of hierarchical consistency is achieved by establishing control consistency — namely preservation of time control structures through the aggregation mapping in a two-level hierarchy.     

Queue reduction in discrete-event systems by relabeling

The customer population of entities potentially requesting to join a queue for service often have identical structure, i.e., the same state set and isomorphic transitions. The state size of the automaton modeling a queue will grow rapidly with increase of the size of this population. However, by relabeling the queue arrival events and service events to the same symbols respectively, the automaton model of a queue will be converted to the structure of a buffer, which is proved to be independent of the total size of the customer population, as long as the queue size is held fixed. We propose the model of a dynamic buffer to embody order and shift of a queue. The result is applied to a manufacturing facility with a dynamic buffer to manage the repair of broken down machines.     

Sample-path analysis of stochastic discrete-event systems

This paper presents a unified sample-path approach for deriving distribution-free relations between performance measures for stochastic discrete-event systems extending previous results for discrete-state processes to processes with a general state space. A unique feature of our approach is that all our results are shown to follow from a single fundamental theorem: the sample-path version of the renewal-reward theorem (Y=X). As an elementary consequence of this theorem, we derive a version of the rate-conservation law under conditions more general than previously given in the literature. We then focus on relations between continuous-time state frequencies and frequencies at the points of an imbedded point process, giving necessary and sufficient conditions for theASTA (Arrivals See Time Averages), conditionalASTA, and reversedASTA properties. In addition, we provide a unified approach for proving various relations involving forward and backward recurrence times. Finally, we give sufficient conditions for rate stability of an input-output system and apply these results to obtain an elementary proof of the relation between the workload and attained-waiting-time processes in aG/G/l queue.Research was partially supported by the National Science Foundation under Grant no. DDM-8719825. The government of the United States of America has certain rights in this material. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation. The research of this author was also partially supported by a grant from Centre International des Étudiants et Stagiares (C.I.E.S.) while he was visiting INRIA, Sophia-Antipolis, Valbonne, France (1991–92).     

Supervision localization of timed discrete-event systems

We study supervisor localization for real-time discrete-event systems (DES) in the Brandin–Wonham framework of timed supervisory control. We view a real-time DES as comprised of asynchronous agents which are coupled through imposed logical and temporal specifications; the essence of supervisor localization is the decomposition of monolithic (global) control action into local control strategies for these individual agents. This study extends our previous work on supervisor localization for untimed DES, in that monolithic timed control action typically includes not only disabling action as in the untimed case, but also “clock preempting” action which enforces prescribed temporal behavior. The latter action is executed by a class of special events, called “forcible” events; accordingly, we localize monolithic preemptive action with respect to these events. We demonstrate the new features of timed supervisor localization with a manufacturing cell case study and discuss a distributed control implementation.     

对称离散事件系统事件重标记观测器性质研究

当离散事件系统(discrete-event systems,DES)由多组结构相同的组件构成时,则称离散事件系统具有对称性.为了化简对称离散事件系统的状态空间,本文提出事件重标记映射,将完成相同任务的事件标记为同一事件,将与控制无关的不可控事件设为不可观测事件,并将其标记为空字符擦除.为了确保事件重标记前后系统对应的最大监督控制器具有相同的控制效果,本文引入重标记观测器(relabeling observer property,ROP)的概念并给出判断被控对象对应的语言关于事件重标记映射是否具有重标记观测器性质的算法;然后运用重标记观测器性质证明事件重标记前后监督控制器控制效果的等价性,从而可用简化后的监督控制器实现与事件重标记操作前相同的控制任务.最后通过实例验证所提理论的正确性.     

The relationship of controllability between classical and fuzzy discrete-event systems

We have known that the controllability of classical discrete-event systems has already been extended into fuzzy discrete-event systems. In this paper, firstly, we recall some related definitions and results of the controllability for classical and fuzzy discrete-event systems, respectively. Secondly, we are concerned with the relationship of the controllability between classical and fuzzy discrete-event systems. In particular, we show that there is an equivalence of the controllability between the two systems to some extent, some special proofs are also presented. Finally, we use this equivalence to extend some general controllability properties of classical discrete-event systems into fuzzy ones.