Distributed inversion in timed discrete event systems

We consider a discrete event system (DES) modeled by a timed automaton with partial state and event observations. We view the system as an input-output system, where the input is a sequence of event lifetimes, and the output is the resulting sequence of events, states, and transition epochs. We consider the problem of extracting event lifetimes (input) from observations of the output trajectory, which we callinversion. We give necessary and sufficient conditions forinvertibility, and an algorithm that extracts event lifetimes from any given output observation of an invertible system. We describe a distributed timed DES model based on the prioritized synchronous product of subsystems, and study the inversion problem in this framework. We show that invertibility in the subsystems implies invertibility in the global system. To illustrate our results, we provide an example of a tandem network.     

State based control of timed discrete event systems using binary decision diagrams

This work discusses a new synthesis approach to the supervisory control of timed discrete event systems (TDES), that is more efficient than the existing approaches. With this method, many practical systems can be synthesized on a personal computer. The method exploits binary decision diagrams (BDDs), adapted to the specific structure of TDES. It is shown that the number of nodes in the BDD representing a TDES can be a better measure of the complexity of the TDES than the number of states and transitions. Structural information based on the ‘timers’ for a given TDES together with the reduction properties of BDDs contributes to efficient performance. The success of our approach is illustrated with large versions of an existing example taken from the literature.     

Fault diagnosis of timed discrete event systems using Dioid Algebra

This paper deals with the fault diagnosis problem in a concurrent Timed Discrete Event System (TDES). In a TDES, concurrency leads to more complexity in the diagnoser and appears where, at a certain time, some user must choose among several resources. To cope with this problem, a new model-based diagnoser is proposed in this paper. This diagnoser uses Durational Graph (DG), a main subclass of timed automata for representing the time evolution of the TDES. The proposed diagnoser predicts all possible timed-event trajectories that may be generated by the DG. This prediction procedure is complicated for nondeterministic DG’s that are obtained for concurrent TDES’s. To solve this problem, a new Dioid Algebra, Union-Plus Algebra is introduced in this paper. Based on this Algebra, a reachability matrix is defined for a DG that plays an essential role in predicting the time behavior of TDES. By using reachability matrix, a prediction procedure is carried on via an effective equation set that is similar to linear system state equations in ordinary algebra. These results provide a suitable framework for designing an observer-based diagnoser that is illustrated by an example.     

Control of quantized systems based on discrete event models

This paper presents controller design methods for dynamical systems that are observed by discrete sensors. These sensors induce a partitioning of the state space and only this quantized information is available for the controller. The so-called 'quantized system' is modelled by a discrete-event model that serves as a basis for the controller design methods. However, instead of using solely the classical control methodologies for discrete-event systems as found in the literature, improvements are proposed by including additional information provided by the fact that the underlying plant is continuous by nature, such as continuity of the state trajectories and information on derivatives that holds for parts of the state space. The concept of discretely controlled invariant sets will play a crucial role in the development of control strategies and necessary and sufficient conditions for controlled invariance are presented. Also algorithms are included to compute the smallest and largest discretely controlled invariant sets with respect to a given set. All the techniques and computations are explicitly described by Boolean matrices and vectors and are ready for application. This is demonstrated for a benchmark problem of a two tank system.     

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

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

Supervisory control of timed discrete event systems under partial observation based on activity models and eligible time bounds

To avoid the state–space explosion by including tick events in timed discrete event systems (DESs) under partial observation, a notion of eligible time bounds is introduced and based on the notion, controllability and observability conditions of languages are presented. In particular, this paper shows that these controllability and observability conditions are necessary and sufficient for the existence of a supervisor to achieve the given language specification.     

Robust supervisory control of a class of timed discrete event systems under partial observation

This paper studies robust supervisory control of timed discrete event systems proposed by Brandin and Wonham. Given a set of possible models which includes the exact model of the plant, the objective is to synthesize a robust supervisor such that it achieves legal behavior for all possible models. We show that controllability for each possible model and observability for a suitably defined aggregate model are necessary and sufficient conditions for the existence of a solution to the robust supervisory control problem. Moreover, when there does not exist a solution, a maximally permissive robust supervisor is synthesized under the assumption that all controllable events are observable.     

一类离散事件系统的监控器综合

前向无同步前向无冲突网是每个变迁有且只有一个输入库所并且每个库所最多有一个输入变迁的受限Petri网.针对不可控影响子网为前向无同步前向无冲突网的广义互斥约束,显式地给出了最大允许控制策略的计算方法.并用一个例子给予了说明.     

A control synthesis approach for time discrete event systems

In this paper, we introduce a control synthesis method for discrete event systems whose behavior is dependent on explicit values of time. Our goal is to control the occurrence dates of the controllable events so that the functioning of the system respects given specifications. The system to be controlled is modeled by a time Petri net. In a previous work we proposed a systematic method to build the timed automaton which models the exact behavior of a time Petri net. Furthermore, the forbidden behaviors of the system are modeled by forbidden timed automaton locations. This paper focuses on the control synthesis method, which consists in computing new firing conditions for the timed automaton transitions so that the forbidden locations are no longer reachable.     

Nonblocking supervisory control of timed discrete event systems under communication delays: The existence conditions

This paper addresses the problem of nonblocking supervisory control of timed discrete event systems under communication delays based on the framework proposed by Brandin and Wonham. For such a system, a supervisory control command could be applied to the system after some time-delay limited by a finite bound corresponding to the maximal number of tick occurrences, and some uncontrollable events may unexpectedly occur within this time-delay. This paper presents the necessary and sufficient conditions for the existence of a nonblocking supervisor that can achieve a given language specification in consideration of such delayed communications.     

Control of large discrete event systems: constructive algorithms

An automata-based theory has been developed by W.M. Wonham and P.J. Ramadge (SMIA J. Control Optimiz. vol.25, p.206-30, 637-59, 1987) and their associates. Its practical implementation in large real-life systems requires automatic programming schemes, which yield supervisory control programs, and models of the controlled system's behavior (for the purpose of performance analysis). The available data for these constructions would normally consist of a set of local structural models and local operational requirements. In the present study, the authors illuminate the relationship between local and global models and outline some of the basic elements of such schemes based on integration of local data     

Control of discrete event systems modeled as hierarchical statemachines

Discrete-event systems (DESs) are systems in which state changes take place in response to events that occur discretely, asynchronously, and often nondeterministically. A class of DESs modeled as hierarchical state machines (HSMs), a special case of the statecharts formalism introduced recently, is considered. An efficient algorithm is provided for solving reachability problems in the HSM framework. It utilizes the hierarchical structure of HSMs. This efficient solution is used extensively in control applications, where controllers achieving a desired behavior are synthesized online     

Control of stochastic discrete event systems modeled byprobabilistic languages

In Garg et al. (1999) and Garg (1992) the formalism of probabilistic languages for modeling the stochastic qualitative behavior of discrete event systems (DESs) was introduced. In this paper, we study their supervisory control where the control is exercised by dynamically disabling certain controllable events thereby nulling the occurrence probabilities of disabled events, and increasing the occurrence probabilities of enabled events proportionately. This is a special case of “probabilistic supervision” introduced in Lawford and Wonham (1993). The control objective is to design a supervisor such that the controlled system never executes any illegal traces (their occurrence probability is zero), and legal traces occur with minimum prespecified occurrence probabilities. In other words, the probabilistic language of the controlled system lies within a prespecified range, where the upper bound is a “nonprobabilistic language” representing a legality constraint. We provide a condition for the existence of a supervisor. We also present an algorithm to test this existence condition when the probabilistic languages are regular (so that they admit probabilistic automata representation with finitely many states). Next, we give a technique to compute a maximally permissive supervisor online     

Two formal methods for the synthesis of discrete event systems

The design of discrete event systems (DES) is based mainly on either analysis or synthesis approaches. In the synthesis approach, the design process starts from high level requirements which are then automatically refined to obtain lower abstraction levels. In this paper, we begin by introducing the two design approaches and defining the synthesis problem in DESs, and in protocols in particular. Then, we survey and assess some existing protocol synthesis methods. Then, we present two novel formal and systematic methods we have developed for the synthesis of DESs. The first method is used for the design of distributed systems which must satisfy some temporal constraints. The second method takes into account concepts such as controllability and observability, which are used in the control theory of DESs. Finally, we conclude and propose some future works.     

Robust supervisory control of timed discrete event systems under partial observation based on eligible time bounds: The existence conditions

This paper addresses a supervisory control problem for uncertain timed discrete event systems (DESs) under partial observation. An uncertain timed DES to be controlled is represented by a set of possible timed models based on the framework of Brandin and Wonham [(1994). Supervisory control of timed discrete event systems. IEEE Transactions on Automatic Control, 39(2), 329-342]. To avoid the state space explosion problem caused by tick events in the timed models, a notion of eligible time bounds is proposed for a single timed model obtained from the set of all possible timed models. Based on this notion, we present the necessary and sufficient conditions for the existence of a robust supervisor achieving a given language specification for the single timed model. Moreover, we show that the robust supervisor can also achieve the specification for any timed model in the set.     

Some invariance identities for discrete systems

The purpose of this paper is to derive some invariance identities for certain discrete systems which are governed by a set of non–linear recurrence relations. The identities are obtained under the assumption that the discrete Lagrangian possesses an invariance under special types of transformations.     

Cyclic invariance for discrete time-delay systems

This technical communique introduces a new concept of set invariance with respect to linear discrete time dynamics affected by delay. We are interested in the definition and characterization of sequences of cyclically invariant subsets in the state space. The algebraic conditions established in the late ’80s for linear dynamics are generalized to invariance analysis in the presence of delays for given sequences of polyhedral sets.     

Control reconfiguration of discrete event systems controllers with partial observation

In this paper, we develop a framework for reconfiguration of a discrete event system (DES) controller, which has a dynamic event observation set. We will show the designed reconfiguration yields a more tolerable controller than the one designed in [5]. Starting with a maximally permissive controller that has a full observation of its DES, we design a mega-controller that monitors the observation set of the DES controller and its state continuously. Upon a change in the observation set, the mega-controller reconfigures the controller by a aggregation or disaggregation of the controller states. The mega-controller is also responsible for feedback function adjustments if the available observation set causes a conflict in control. We illustrate the reconfiguration procedures by an example.     

离散事件系统N步稳定性分析

讨论基于自动机/形式语言模型的离散事件系统(DES)稳定性问题,引入了确定性离散事件系统N步稳定性定义,并得到了稳定性的判据定理,推导了具体的算法实现。该算法具有多项式复杂度。     

离散事件系统框架下信息物理系统攻击问题综述

信息物理系统(cyber physical system, CPS)由受控对象、传感器、执行器、监控器和通信网络组成,通信网络的使用增加了信息物理系统面临外部攻击的风险.鉴于此,综述基于离散事件系统框架处理信息物理系统攻击问题的相关研究工作.首先对信息物理系统进行简要介绍;然后对信息物理系统中的攻击进行分类;最后重点阐述信息物理系统中攻击策略的设计、攻击的检测与防御以及攻击鲁棒性监控器设计的研究现状.