随机计时离散事件系统的软控制任务研究

本文通过引入马氏决策过程中的迭代算法,研究了计时离散事件系统的随机优化监控综合问题。为了对不确定的人造系统实施监控,在考虑事件的操作时间的基础上,利用带有发生事件概率分布函数的随机计时离散事件系统模型对系统建模。为了对这类随机系统实施监控,在传统方法中,采用控制任务的最大可控子语言设计控制器,不能体现系统模型的随机特性。本文提出利用软控制任务代替原控制任务的方法,使其超出原控制任务的概率在给定的容许度约束范围内。首先,通过在计时离散事件系统中定义计时事件的发生概率映射和发生费用函数,利用离散事件系统的逻辑特性,构造事件发生序列的期望费用函数,进而确立马氏决策过程的最优方程,建立软控制任务与期望费用函数之间的关系。然后,通过计算事件发生序列的费用值,提出利用有限费用值可以用来确定软控制任务,进而基于逻辑监控方法,确定最优监控器。最后,利用计算有限费用值的迭代过程,提出迭代算法,并给出了计算实例。     

On optimal control of a class of partially observed discrete event systems

We are interested in a new class of optimal control problems for discrete event systems. We adopt the formalism of supervisory control theory (Proc. IEEE 77(1) (1989) 81) and model the system as a finite state machine (FSM). Our control problem is characterized by the presence of uncontrollable as well as unobservable events, the notion of occurrence and control costs for events and a worst-case objective function. We first derive an observer for the partially unobservable FSM, which allows us to construct an approximation of the unobservable trajectory costs. We then define the performance measure on this observer rather than on the original FSM itself. We then use the algorithm presented in Sengupta and Lafortune (SIAM J. Control Optim. 36(2) (1998)) to synthesize an optimal submachine of the C-observer. This submachine leads to the desired supervisor for the system.     

Grid automata and supervisory control of dense real-time discrete event systems

We present a generalization of the classical supervisory control theory for discrete event systems to a setting of dense real-time systems modeled by Alur and Dill timed automata. The main problem involved is that in general the state space of a timed automaton is (uncountably) infinite. The solution is to reduce the dense time transition system to an appropriate finite discrete subautomaton, the grid automaton, which contains enough information to deal with the timed supervisory control problem (TSCP). The plant and the specifications region graphs are sampled for a granularity defined in a way that each state has an outgoing transition labeled with the same time amount. We redefine the controllability concept in the context of grid automata, and we provide necessary and sufficient solvability conditions under which the optimal solution to centralized supervisory control problems in timed discrete event systems under full observation can be obtained. The enhanced setting admits subsystem composition and the concept of forcible event. A simple example illustrates how the new method can be used to solve the TSCP.     

Optimal sensor activation for diagnosing discrete event systems

The problem of dynamic sensor activation for event diagnosis in partially observed discrete event systems is considered. Diagnostic agents are able to activate sensors dynamically during the evolution of the system. Sensor activation policies for diagnostic agents are functions that determine which sensors are to be activated after the occurrence of a trace of events. The sensor activation policy must satisfy the property of diagnosability of centralized systems or codiagnosability of decentralized systems. A policy is said to be minimal if there is no other policy, with strictly less sensor activation, that achieves diagnosability or codiagnosability. To compute minimal policies, we propose language partition methods that lead to efficient computational algorithms. Specifically, we define “window-based” language partitions for scalable algorithms to compute minimal policies. By refining partitions, one is able to refine the solution space over which minimal solutions are computed at the expense of more computation. Thus a compromise can be achieved between fineness of solution and complexity of computation.     

Diagnosability of fuzzy discrete event systems

In this paper, discrete event systems (DESs) are reformulated as fuzzy discrete event systems (FDESs) and fuzzy discrete event dynamical systems (FDEDSs). These frameworks include fuzzy states, events and IF-THEN rules. In these frameworks, all events occur at the same time with different membership degrees. Fuzzy states and events have been introduced to describe uncertainties that occur often in practical problems, such as fault diagnosis applications. To measure a diagnoser’s fault discrimination ability, a fuzzy diagnosability degree is proposed. If the diagnosability of the degree of the system yields one a diagnoser can be implemented to identify all possible fault types related to a system. For any degree less than one, researchers should not devote their time to distinguish all possible fault types correctly. Thus, two different diagnosability definitions FDEDS and FDES are introduced. Due to the specialized fuzzy rule-base embedded in the FDEDS, it is capable of representing a class of non-linear dynamic system. Computationally speaking, the framework of diagnosability of the FDEDS is structurally similar to the framework of diagnosability of a non-linear system. The crisp DES diagnosability has been turned into the term fuzzy diagnosability for the FDES. The newly proposed diagnosability definition allows us to define a degree of diagnosability in a class of non-linear systems. In addition, a simple fuzzy diagnosability checking method is introduced and some numerical examples are provided to illustrate this theoretical development. Finally, the potential applications of the proposed method are discussed.     

A graph-theoretic optimal control problem for terminating discrete event processes

Most of the results to date in discrete event supervisory control assume a zero-or-infinity structure for the cost of controlling a discrete event system, in the sense that it costs nothing to disable controllable events while uncontrollable events cannot be disabled (i.e., their disablement entails infinite cost). In several applications however, a more refined structure of the control cost becomes necessary in order to quantify the tradeoffs between candidate supervisors. In this paper, we formulate and solve a new optimal control problem for a class of discrete event systems. We assume that the system can be modeled as a finite acylic directed graph, i.e., the system process has a finite set of event trajectories and thus is terminating. The optimal control problem explicitly considers the cost of control in the objective function. In general terms, this problem involves a tradeoff between the cost of system evolution, which is quantified in terms of a path cost on the event trajectories generated by the system, and the cost of impacting on the external environment, which is quantified as a dynamic cost on control. We also seek a least restrictive solution. An algorithm based on dynamic programming is developed for the solution of this problem. This algorithm is based on a graph-theoretic formulation of the problem. The use of dynamic programming allows for the efficient construction of an optimal subgraph (i.e., optimal supervisor) of the given graph (i.e., discrete event system) with respect to the cost structure imposed. We show that this algorithm is of polynomial complexity in the number of vertices of the graph of the system.Research supported in part by the National Science Foundation under grant ECS-9057967 with additional support from GE and DEC.     

Supervisory control of discrete event systems with state-dependent controllability

This article studies the supervisory control problem of discrete event systems (DES) with state-dependent controllability. The new problem is given with the background of operating systems where the processes and the interrupt service routines (ISR) are supervised and coordinated. The new model is novel because the controllability of an event is changeable in the lifetime of system evolution, and dependent on the system state. Two fundamental problems are concerned with the new model: supervisor existence problem and supervisor synthesis problem. We derive a necessary and sufficient condition for the existence of the supervisor, and introduce an algorithm to synthesise the supremal supervisor in a given specification. With the background of process and ISR management in operating systems, some examples are given to show how the new model can be applied to practical computing.     

Reliable supervisory control for general architecture of decentralized discrete event systems

In this paper, we investigate the reliable decentralized supervisory control of discrete event systems (DESs) under the general architecture, where the decision for controllable events is a combination of the conjunctive and disjunctive fusion rules. By reliable control, we mean that the performance of closed-loop systems will not be degraded even in the face of possible failures of some local supervisors. The main contributions are twofold. First, a necessary and sufficient condition for the existence of a k-reliable decentralized supervisor under the general architecture is presented after introducing notions of -controllability and k-reliable -coobservability. Second, a polynomial-time algorithm to verify the reliable -coobservability of a specification is proposed.     

Fault prognosis of discrete event systems: An overview

Fault prognosis of discrete event systems (DES) is an active field of research and has become important due to the high demand on systems’ safety and reliability. The aim of this paper is to provide the state-of-the-art on fault prognosis of DES, as well as quick directions regarding many aspects of the research on this topic. This overview was carried out using a systematic approach, which allowed us to find and select papers with minimum bias. In total, 74 papers were selected and analyzed in this overview. A classification and an analysis of these papers are made regarding the modeling formalism and decision structure of prognosis of DES. Specific notions of prognosis are also presented. A survey on these papers was performed, regarding practical applications and related problems of prognosis. Results show that most papers present solutions based on languages & automata (56), and most papers consider the centralized decision structure (45). Also, we have found 17 different papers with examples of practical applications of prognosis of DES. We have identified research gaps, such as applications of distributed prognosis and distributed prognosis of Petri nets. Finally, the research activity on prognosis of DES is growing 16.14% by year on average, accordingly to the number of published papers on this topic between 2006 and 2020.     

Time/fuel optimal control of constrained linear discrete systems

A unified approach to solving three common optimal control problems is presented, for linear systems under general constraints. The problems are: (1) the time optimal control problem; (2) the fuel optimal control problem in fixed time; (3) the time optimal control problem with a fuel constraint. A special purpose linear programming algorithm is used. State variable constraints are efficiently handled by a cutting plane algorithm. An example of a sixth order system with two inputs and two state variable constraints illustrates the method as implemented on a personal computer.     

非确定型离散事件系统双模拟控制的实现

近年来,双模拟等价关系与离散事件系统监控理论相结合的研究引起了国内外许多学者的广泛关注.本文针对作者在前期工作中提出的非确定型离散事件系统的双模拟控制机制,进一步探讨其实现问题.利用投影映射对系统规范说明语言进行等价类划分,构造了一棵计算树,得到了一个判断规范说明是否具有基于模拟关系可观性的多项式算法,证明了双模拟控制机制是多项式时间算法可实现的.同时,通过对控制器配备具有存储和判断功能的模拟关系识别器,阐述了这种双模拟控制机制是物理可实现的.     

Control of large scale discrete event systems: Task allocation and coordination

To control a large scale discrete event system, decentralized control and hierarchical control can be used, where several local supervisors are used to control events in local sites and a coordinator is used to coordinate the local supervisors. Two important problems that need to be solved in such a control architecture are task allocation and coordination. That is, how to allocate tasks to the supervisors, and how to coordinate those tasks. We propose and solve a task allocation problem of assigning tasks to the local supervisors and a minimal intervention problem of coordinating tasks so that the intervention by the coordinator is minimal.     

Abstraction-based verification of codiagnosability for discrete event systems

In this paper, we investigate the verification of codiagnosability for discrete event systems (DES). That is, it is desired to ascertain if the occurrence of system faults can be detected based on the information of multiple local sites that partially observe the overall DES. As an improvement of existing codiagnosability tests that resort to the original DES with a potentially computationally infeasible state space, we propose a method that employs an abstracted system model on a smaller state space for the codiagnosability verification. Furthermore, we show that this abstraction can be computed without explicitly evaluating the state space of the original model in the practical case where the DES is composed of multiple subsystems.     

Diagnosability of a class of discrete event systems based on observations

The diagnosability of discrete event systems has been a topic of interest to many researchers. The diagnosability conditionsfor various systems have evolved based on a regularity condition that is imposed on faulty traces with respect to their observablecontinuations. Improving upon this weak but necessary condition, a new model of diagnosability that is based on sensor outputs,which are called observations, upon a command input is proposed in this paper. Necessary and sufficient conditions are derivedfor the proposed diagnosability model. The search performance of the proposed diagnosability condition is of linear complexityin terms of the power set of the system events and observations, compared to the exponential complexity of the search with theexisting diagnosability regularity condition. Moreover, a system that is not diagnosable according to the existing diagnosabilitycondition may be diagnosable in the proposed diagnosability model, which includes observations.     

The concept of residuals for fault localization in discrete event systems

In this paper an approach for fault localization in closed-loop Discrete Event Systems is proposed. The presented diagnosis method allows fault localization using a fault-free system model to describe the expected system behavior. Via a systematic comparison of the observed and the expected behavior, a fault can be detected and a set of fault candidates is determined. Inspired by residuals known from diagnosis in continuous systems, different set operations are introduced to generate the fault candidate set. After fault detection and a first fault localization, a procedure is given to render the fault localization more precisely by an analysis of the further observed system behavior. Special emphasis is given to the use of identified models for the fault-free system behavior. The approach is explained using a laboratory manufacturing facility.     

Decision making in fuzzy discrete event systems

The primary goal of the study presented in this paper is to develop a novel and comprehensive approach to decision making using fuzzy discrete event systems (FDES) and to apply such an approach to real-world problems. At the theoretical front, we develop a new control architecture of FDES as a way of decision making, which includes a FDES decision model, a fuzzy objective generator for generating optimal control objectives, and a control scheme using both disablement and enforcement. We develop an online approach to dealing with the optimal control problem efficiently. As an application, we apply the approach to HIV/AIDS treatment planning, a technical challenge since AIDS is one of the most complex diseases to treat. We build a FDES decision model for HIV/AIDS treatment based on expert’s knowledge, treatment guidelines, clinic trials, patient database statistics, and other available information. Our preliminary retrospective evaluation shows that the approach is capable of generating optimal control objectives for real patients in our AIDS clinic database and is able to apply our online approach to deciding an optimal treatment regimen for each patient. In the process, we have developed methods to resolve the following two new theoretical issues that have not been addressed in the literature: (1) the optimal control problem has state dependent performance index and hence it is not monotonic, (2) the state space of a FDES is infinite.     

Decentralized control of networked discrete event systems with communication delays

In many practical systems, supervisory control is not performed by one centralized supervisor, but by multiple local supervisors. When communication networks are used in such a system as the medium of information transmission, the communication channels between local supervisors and the system to be controlled will unavoidably result in communication delays. This paper investigates how to use these local supervisors to control the system in order to satisfy given specifications even under communication delays. The specifications are described by two languages: a minimal required language which specifies the minimal required performance that the supervised system must have and a maximal admissible language which specifies the maximal boundary that the supervised system must be in. The results show that if the control problem is solvable, then there exists the minimal control policy which can be calculated based on state estimates. Furthermore, we derive algorithms to check whether the control problem is solvable or not.     

Lagrange stability and boundedness of discrete event systems

Recently it has been shown that the conventional notions of stability in the sense of Lyapunov and asymptotic stability can be used to characterize the stability properties of a class of logical discrete event systems (DES). Moreover, it has been shown that stability analysis via the choice of appropriate Lyapunov functions can be used for DES and can be applied to several DES applications including manufacturing systems and computer networks (Passino et al. 1994, Burgess and Passino 1994). In this paper we extend the conventional notions and analysis of uniform boundedness, uniform ultimate boundedness, practical stability, finite time stability, and Lagrange stability so that they apply to the class of logical DES that can be defined on a metric space. Within this stability-theoretic framework we show that the standard Petri net-theoretic notions of boundedness are special cases of Lagrange stability and uniform boundedness. In addition we show that the Petri ent-theoretic approach to boundedness analysis is actually a Lyapunov approach in that the net-theoretic analysis actually produces an appropriate Lyapunov function. Moreover, via the Lyapunov approach we provide a sufficient condition for the uniform ultimate boundedness of General Petri nets. To illustrate the Petri net results, we study the boundedness properties of a rate synchronization network for manufacturing systems. In addition, we provide a detailed analysis of the Lagrange stability of a single-machine manufacturing system that uses a priority-based part servicing policy.     

State observability and condition observability for a class of interacting discrete event systems

This paper introduces the concepts of state observability and condition observability for condition systems, a class of systems composed of discrete state components which interact via discrete binary signals called conditions. Given a set of externally observed conditions, state observability implies that the state of the system can be determined from the observations, and condition observability implies that all unobserved input and output conditions of the system can be determined from the observations. In this paper, we present a class of systems which is state observable and condition observable. We present a method to synthesize an observer system to provide state and condition signal estimates for a single component subsystem.     

基于有限容量库所的离散事件系统的Petri网控制器综合——第2部分

FCP方法的基本思想已在第一部分作了介绍. 第二部分给出了离散事件系统在最一般情况下约束的Petri网控制器的设计方法, 并证明FCP方法是最大容许控制的. 此外, 已有文献里的自动导航车辆协调系统的例子将被用来说明FCP方法所具有的优点和特点.