离散事件系统部分可诊断性分析

针对离散事件系统部分可诊断性问题,提出一种量化评价与分析方法。该方法以树状结构的故障模型为基础,引入可诊断度与可诊断深度指标,能够从可诊断故障覆盖程度与精确程度两个方面对系统可诊断性进行评价,其优点是评价结果量化表示,能为部分可诊断系统的进一步评价、分析与对比提供参考。此外,还讨论了故障模型对系统可诊断度与可诊断深度两个评价指标的影响,并给出了故障模型构造的一般原则。实例分析与讨论结果表明,所提出的可诊断度与可诊断深度指标能够准确反映系统在特定故障模型下的部分可诊断状态。所提出的部分可诊断性评价方法能为基于离散事件模型的复杂系统设计与评价提供依据,并能够进一步为智能、自适应和自愈系统的设计提供参考。     

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.     

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.     

基于神经网络和层次SVM的多姿态人脸识别

提出了一种基于神经网络和层次支持向量机的多姿态人脸识别方法。该方法在训练阶段先利用神经网络把姿态人脸图像特征向准标准人脸图像特征映射，再根据聚类结果来训练支持向量机。识别阶段是利用神经网络变换得到待识别图像所对应的准标准图像的特征，再让层次支持向量机初步判断待识别图像最可能所属的人，最后利用否定算法对待识别的人脸图像进行确认。实验表明该算法效果较佳。     

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.     

An Efficient Modular Method for the Control of Concurrent Discrete Event Systems: A Language-based Approach

In this paper, we are interested in the control of a particular class of Concurrent Discrete Event Systems defined by a collection of components that interact with each other. We investigate the computation of the supremal controllable language contained in the language of the specification. We do not adopt the decentralized approach. Instead, we have chosen to use a modular centralized approach and to perform the control on some approximations of the plant derived from the behavior of each component. The behavior of these approximations is restricted so that they respect a new language property for discrete event systems called partial controllability condition that depends on the specification. It is shown that, under some assumptions, the intersection of these “controlled approximations” corresponds to the supremal controllable language contained in the specification with respect to the plant. This computation is performed without having to build the whole plant, hence avoiding the state space explosion induced by the concurrent nature of the plant. It is finally shown that the class of specifications on which our method can be applied strictly subsumes the class of separable specifications.

Diagnosability of fair discrete event systems

Failure diagnosability has been widely studied using discrete event system (DES) models. It is, however, shown in this work by means of a counterexample that the diagnosability condition, which has been shown to be necessary and sufficient in the DES context, fails to hold for many real‐world hybrid systems. This is because the abstraction employed in formulating the DES models obliterates the continuous dynamics. In the present work, a new failure diagnosability mechanism has been developed for discrete time hybrid system (DTHS) models to alleviate this problem. A new diagnosability condition is proposed and its necessity and sufficiency with respect to the diagnosability definition are established formally. Finally, the method of A‐diagnosability, which can also be used to circumvent this problem and which needs additional probabilistic information for diagnosability analysis, has been shown to have a higher computational complexity than the DTHS model based method proposed in this paper. Further, it is also highlighted that the DTHS model based diagnosability analysis technique is capable of diagnosing faults that degrade the temporal performance of the system, which cannot be handled by the A‐diagnosability analysis mechanism. Copyright © 2008 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Modular Design of Real-Time Systems Using Hierarchical Communicating Real-time State Machines

This paper proposes a methodology for the development of distributed real-time systems. The methodology consists of the Hierarchical Communicating Real-Time State Machines (H-CRSM) modelling language, and the Violin toolset. H-CRSM combines Statecharts constructs with CSP-like timed communications. Violin provides a visual environment supporting in a seamless way all the life-cycle development phases of an H-CRSM system. Temporal validation rests on assertion checking during system simulation. Code generation is based on Java and a customizable runtime. The practical use of H-CRSM/Violin is shown by an example. A preliminary version of this paper appears in Proc. of Joint Modular Languages Conference (JMLC'2003), Klagenfurt, Austria, August 2003, LNCS 2789, Springer, pp. 110–121. Angelo Furfaro, Phd, is a computer science assistant professor at Unical, DEIS, teaching object-oriented programming. His research interests include: multiagent systems, Petri nets, parallel simulation, verification of time-dependent systems, distributed measurement systems. He is a member of ACM. Libero Nigro is a full professor of computer science at Unical, DEIS, where he teaches object-oriented programming, software engineering and real-time systems courses. He is the responsible of Software Engineering Laboratory (www.lis.deis.unical.it). His current research interests include: software engineering of time-dependent and distributed systems, real-time systems, Petri nets, modeling and parallel simulation of complex systems, distributed measurement systems. Prof. Nigro is a member of ACM and IEEE. Francesco Pupo, Phd, is a computer science assistant professor at Unical, DEIS, teaching introductory programming and computer architecture courses. His research interests include: Petri nets, discrete-event simulation, real-time systems, distributed measurement systems.     

一类高阶线性系统的分层控制

近年来, 一种基于系统层次结构的分层控制方法发展了起来, 它主要针对的是高阶复杂系统. 为了分析和控制这类系统, 我们首先根据需要构建一个合适的低阶抽象系统, 然后在此基础上分析和设计原始系统控制律, 即所谓的接口函数. 本文将此方法用于一类高阶线性系统的稳定控制问题, 并得到了相应的控制律. 最后, 算例部分的仿真结果说明了这种方法的有效性.     

An Approach to Post Mortem Diagnosability Analysis for Interacting Finite State Systems

We present a model based approach to diagnosability analysis for interacting finite state systems where fault isolation is deferred until the system comes to a standstill. Local abstractions of the system model are used to alleviate the state space explosion. Pairs of closely coupled automata are merged and replaced by a single automaton with an equivalently behavior as seen from the rest of the system; interaction between the merged automata is internalized and the new equivalent automaton is subsequently abstracted from internal behavior irrelevant to fault isolation. In moderately concurrent systems these steps can often be iterated until the system consists of a single automaton providing a compact encoding of all possible fault scenarios of the original model. We illustrate how the resulting abstraction can be used as a basis for post mortem diagnosability analysis.     

Graded State Machines: The Representation of Temporal Contingencies in Simple Recurrent Networks

We explore a network architecture introduced by Elman (1990) for predicting successive elements of a sequence. The network uses the pattern of activation over a set of hidden units from time-step t-1, together with element t, to predict element t + 1. When the network is trained with strings from a particular finite-state grammar, it can learn to be a perfect finite-state recognizer for the grammar. When the net has a minimal number of hidden units, patterns on the hidden units come to correspond to the nodes of the grammar; however, this correspondence is not necessary for the network to act as a perfect finite-state recognizer. Next, we provide a detailed analysis of how the network acquires its internal representations. We show that the network progressively encodes more and more temporal context by means of a probability analysis. Finally, we explore the conditions under which the network can carry information about distant sequential contingencies across intervening elements to distant elements. Such information is maintained with relative ease if it is relevant at each intermediate step; it tends to be lost when intervening elements do not depend on it. At first glance this may suggest that such networks are not relevant to natural language, in which dependencies may span indefinite distances. However, embeddings in natural language are not completely independent of earlier information. The final simulation shows that long distance sequential contingencies can be encoded by the network even if only subtle statistical properties of embedded strings depend on the early information. The network encodes long-distance dependencies by shading internal representations that are responsible for processing common embeddings in otherwise different sequences. This ability to represent simultaneously similarities and differences between several sequences relies on the graded nature of representations used by the network, which contrast with the finite states of traditional automata. For this reason, the network and other similar architectures may be called Graded State Machines.     

Diagnosability of delay-deadline failures in fair real time discrete event models

In this article a method for failure diagnosis of real time discrete event systems (RTDES) with ‘fairness of traces’ has been developed. Discrete event system (DES) modelling framework with provision for associating timing information with the transitions are required for handling real time systems. RTDES models and timed DES (TDES) models are examples of such modelling frameworks. Failure diagnosis in untimed DES models enables only the study of diagnosability of failures resulting in a change in the logical behaviour of the failed system. In addition to logical failures, failure diagnosis in RTDES and TDES models also enables diagnosability of failures that change the timing behaviour of the system but maintain the logical behaviour. Many systems exhibit fairness of traces with respect to transitions in the sense that any trace that visits a state infinitely often has infinitely many occurrences of all the transitions that emanate from that state. The abstraction employed in obtaining their (timed) DES models often obliterates this property. The RTDES and TDES diagnosability conditions, proposed in the literature and which do not consider fairness, are shown to be inadequate in this article. A new diagnosability condition is achieved by taking into account this fairness property in the RTDES models and shown to be necessary and sufficient for such systems. An analysis of time complexity for analysing the diagnosability of systems with fairness of traces is presented.     

Petri网上的禁止状态监控器综合

给出了Petri网上广义互斥约束的最大允许监控器综合方法,其中该监控问题满足两个条件：正权值禁止库所的影响子网是状态机;负权值禁止库所的输入和输出变迁均只有一个输入库所.首先得到了监控器存在的充分和必要条件;其次构造了约束等价转换的方法,该方法可将存在不可控变迁的监控问题简化为相当于变迁全部可控的监控问题.最后通过一个例子说明了该方法的可行性.     

Discrete event diagnosis using labeled Petri nets. An application to manufacturing systems

In this paper an approach to on-line diagnosis of discrete event systems based on labeled Petri nets is presented. The approach is based on the notion of basis markings and justifications and it can be applied both to bounded and unbounded Petri nets whose unobservable subnet is acyclic. Moreover it is shown that, in the case of bounded Petri nets, the most burdensome part of the procedure may be moved off-line, computing a particular graph called Basis Reachability Graph.Finally, the effectiveness of the proposed procedure is analyzed applying a MATLAB diagnosis toolbox we developed to a manufacturing example taken from the literature.     

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.     

基于多边形逼近和有限状态机的笔段提取-合并算法

汉字的基本特征表示是笔段,提出一种基于多边形逼近和有限状态机的笔段提取-合并算法.该算法首先找到笔画的拐点(最小内角值小于指定阈值),然后分别寻找拐点两侧曲线段上的拐点,反复执行,直到再也找不到拐点为止.依次连接一个笔画中所有曲线的起点和终点,就形成了该笔画的笔段系列.随后,运用有限状态机描述并判定笔段的状态,并以此判定笔段的合并要求,以最大限度地减少冗余笔段.实验表明,这种算法具有较低的计算复杂度和很好的逼近效果,能适应手写汉字的笔段提取合并要求.     

两类模糊有限状态机积的交换性

利用代数工具矩阵、半群等对两类模糊有限状态机的交换性作了进一步的研究.首先给出了模糊有限状态机是可交换的几个等价刻画,即模糊有限状态机交换与其状态转移矩阵关于模糊矩阵乘法交换等价,与其输入集上字符串关于同余关系构成的乘法半群交换等价,并讨论了模糊有限状态机的直积、级联积、圈积以及和的交换性.其次提出了Mealy-型模糊有限状态机是可交换的概念,同时在新的概念下详细地研究了Mealy-型模糊有限状态机的直积、级联积、圈积以及和、商的交换性.得到了两个(Mealy-型)模糊有限状态机的完全直积、和交换的充要条件;得到两个(Mealy-型)模糊有限状态机的圈积、级联积交换的一个充分条件;证明了商Mealy-型模糊有限状态机保持原Mealy-型模糊有限状态机的交换性.最后给出判别模糊有限状态机交换性的算法.     

An Improved Approach to Test Diagnosability of Bounded Petri Nets

For bounded Petri nets, Cabasino et al. propose a diagnosability test method that is based on the analysis of a modified basis reachability graph and a basis reachability diagnoser. However, its complexity is exponential in the number of nodes of the basis reachability diagnoser. In order to reduce the complexity of their method, this paper presents a new diagnosability test approach for bounded Petri nets. We present the concept of an extended basis reachability graph and prove that our approach is of polynomial complexity in the number of nodes of extended basis reachability graphs. An example is given to illustrate the application of the presented approach.      

Active fault tolerant control of discrete event systems using online diagnostics

The aim of this paper is to deal with the problem of fault tolerant control in the framework of discrete event systems modeled as automata. A fault tolerant controller is a controller able to satisfy control specifications both in nominal operation and after the occurrence of a fault. This task is solved by means of a parameterized controller that is suitably updated on the basis of the information provided by online diagnostics: the supervisor actively reacts to the detection of a malfunctioning component in order to eventually meet degraded control specifications. Starting from an appropriate model of the system, we recall the notion of safe diagnosability as a necessary step in order to achieve fault tolerant control. We then introduce two new notions: (i) “safe controllability”, which represents the capability, after the occurrence of a fault, of steering the system away from forbidden zones and (ii) “active fault tolerant system”, which is the property of safely continuing operation after faults. Finally, we show how the problem can be solved using a general control architecture based on the use of special kind of diagnoser, called “diagnosing controller”, which is used to safely detect faults and to switch between the nominal control policy and a bank of reconfigured control policies. A simple example is used to illustrate the new notions and the control architecture introduced in the paper.     

Symbolic Bounded Model Checking of Abstract State Machines

Abstract State Machines (ASMs) allow modeling system behaviors at any desired level of abstraction, including a level with rich data types, such as sets, sequences, maps, and user-de.ned data types. The availability of high-level data types allow state elements to be represented both abstractly and faithfully at the same time. In this paper we look at symbolic analysis of ASMs. We consider ASMs over a .xed state background T that includes linear arithmetic, sets, tuples, and maps. For symbolic analysis, ASMs are translated into guarded update systems called model programs. We formulate the problem of bounded path exploration of model programs, or the problem of Bounded Model Program Checking (BMPC) as a satis.ability problem modulo T . Then we investigate the boundaries of decidable and undecidable cases for BMPC. In a general setting, BMPC is shown to be highly undecidable (Σ₁¹ -complete); and even when restricting to .nite sets the problem remains re-hard (Σ⁰₁-hard). On the other hand, BMPC is shown to be decidable for a class of basic model programs that are common in practice. We use Satis.ability Modulo Theories (SMT) for solving BMPC; an instance of the BMPC problem is mapped to a formula, the formula is satis.able modulo T if and only if the corresponding BMPC problem instance has a solution. The recent SMT advances allow us to directly analyze speci.cations using sets and maps with specialized decision procedures for expressive fragments of these theories. Our approach is extensible; background theories need in fact only be partially solved by the SMT solver; we use simulation of ASMs to support additional theories that are beyond the scope of available decision procedures.