Fault detection and isolation in manufacturing systems with an identified discrete event model

In this article a generic method for fault detection and isolation (FDI) in manufacturing systems considered as discrete event systems (DES) is presented. The method uses an identified model of the closed-loop of plant and controller built on the basis of observed fault-free system behaviour. An identification algorithm known from literature is used to determine the fault detection model in form of a non-deterministic automaton. New results of how to parameterise this algorithm are reported. To assess the fault detection capability of an identified automaton, probabilistic measures are proposed. For fault isolation, the concept of residuals adapted for DES is used by defining appropriate set operations representing generic fault symptoms. The method is applied to a case study system.     

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

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

Diagnosability of discrete event systems subject to permanent sensor failures

This paper considers a failure diagnosis problem for discrete event systems subject to permanent sensor failures. A notion of diagnosability subject to permanent sensor failures is introduced with respect to a certain nondeterministic observation mask. For its verification, an aggregated Mealy automaton with a deterministic and state-dependent observation mask is defined. It is shown that the diagnosability of the aggregated Mealy automaton is equivalent to the diagnosability of the original system subject to permanent sensor failures. Then, a method for verifying the diagnosability of the aggregated Mealy automaton is presented. Moreover, the delay bound within which the occurrence of any failure string can be detected subject to permanent sensor failures is computed.     

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.     

Detectability in stochastic discrete event systems

A discrete event system possesses the property of detectability if it allows an observer to perfectly estimate the current state of the system after a finite number of observed symbols, i.e., detectability captures the ability of an observer to eventually perfectly estimate the system state. In this paper we analyze detectability in stochastic discrete event systems (SDES) that can be modeled as probabilistic finite automata. More specifically, we define the notion of A-detectability, which characterizes our ability to estimate the current state of a given SDES with increasing certainty as we observe more output symbols. The notion of A-detectability is differentiated from previous notions for detectability in SDES because it takes into account the probability of problematic observation sequences (that do not allow us to perfectly deduce the system state), whereas previous notions for detectability in SDES considered each observation sequence that can be generated by the underlying system. We discuss observer-based techniques that can be used to verify A-detectability, and provide associated necessary and sufficient conditions. We also prove that A-detectability is a PSPACE-hard problem.     

Full-state perturbation analysis of discrete event dynamic systems

Discrete event dynamic systems are studied within the framework of perturbation analysis in this paper. Perturbation is extended from the event times only to both event times and queue lengths. An approximate technique, full-state perturbation analysis (PA), is developed as an extension of the PA approach. Full-state PA is able to deal with problems involving queue length perturbations which often defy existing PA methods, while it still retains all the advantages of existing PA. Full-state PA is used to calculate the throughput sensitivity to the number of customers in closed queueing networks and the throughput sensitivity to routing change. Numerical examples are given. Experimental results verify the validity and accuracy.This work is supported in part by the National High Technology Project and by Southeast University Research Funds for Young Teachers.     

Diagnosability of discrete event systems and its applications

As man-made systems become more and more complex, diagnostics of component failures is no longer an easy task that can be performed based on experience and intuition. Therefore, it is important to develop a systematic approach to diagnostic problems. Diagnostics can be done either on-line or off-line. By on-line diagnostics, we mean diagnostics performed while the system to be diagnosed is in normal operation. On the other hand, in off-line diagnostics, the system is not in normal operation. We will study both on-line and off-line diagnostics in this paper and identify main features and differences of these two types of diagnostics. We will also introduce the concept of diagnosability and study its properties, all in the framework of discrete event systems. This study is motivated by diagnostic problems in the automotive industry and we will emphasize its applications.     

非线性DEDS的标准结构

非线性DEDS是指由极大极小函数描述的系统, 常见于计算机科学、控制论、运筹学等领域, 考虑非自治非线性DEDS的结构问题, 通过引入白色图和凝白色图, 得到了系统能达和能观的两个充要条件以及系统的标准结构, 同时还给出了它们的矩阵表示.     

Supervisory control using augmented languages in discrete event systems

This paper introduces the concept of an augmented (super) language of a specified language and studies its application to finite state supervisory control. First, we investigate several properties of an augmented language, especially related to controllability of the specified language. We propose an algorithm for the computation of a controllable sublanguage for which a finite state supervisor exists, using an augmented language, and show a sufficient condition for the controllable sublanguage to be supremal. It is shown, however, that such a finite state supervisor is sometimes blocking. Moreover, we discuss the relationship between the Wonham-Ramadge algorithm and our proposed one.     

Stabilization and blocking in state feedback control of discrete event systems

We consider controlled discrete event systems modeled by the Ramadge-Wonham model, with a control specification given in terms of both admissible and target states. We define blocking in state feedback control using the notion of stability of discrete event systems. Intuitively, a system is said to be blocking if some trajectories of admissible states cannot reach target states. For control-invariant predicates we define two performance measures called a prestabilizing measure and a blocking measure. First, we present an algorithm to compute the minimally restrictive nonblocking solution. But the nonblocking solution may be restrictive. Then we present design methods to improve the two performance measures. And we show that the task of logical optimization of a blocking feedback can be done by two steps.     

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     

事件空间离散完整系统的Noether理论

研究差分离散变分原理和事件空间中离散完整系统的Noether理论. 运用差分离散变分方法,通过群的无限小变换,得到了事件空间中离散完整系统的差分离散变分原理,并建立了离散的运动方程. 得到了系统的Noether对称性的判据方程和Noether守恒量的形式以及其存在的条件. 举例说明结果的应用.     

State estimation and detectability of probabilistic discrete event systems

A probabilistic discrete event system (PDES) is a nondeterministic discrete event system where the probabilities of nondeterministic transitions are specified. State estimation problems of PDES are more difficult than those of non-probabilistic discrete event systems. In our previous papers, we investigated state estimation problems for non-probabilistic discrete event systems. We defined four types of detectabilities and derived necessary and sufficient conditions for checking these detectabilities. In this paper, we extend our study to state estimation problems for PDES by considering the probabilities. The first step in our approach is to convert a given PDES into a nondeterministic discrete event system and find sufficient conditions for checking probabilistic detectabilities. Next, to find necessary and sufficient conditions for checking probabilistic detectabilities, we investigate the “convergence” of event sequences in PDES. An event sequence is convergent if along this sequence, it is more and more certain that the system is in a particular state. We derive conditions for convergence and hence for detectabilities. We focus on systems with complete event observation and no state observation. For better presentation, the theoretical development is illustrated by a simplified example of nephritis diagnosis.     

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

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

判定非确定离散事件系统稳定性的梯度搜索算法

讨论基于非确定自动机/形式语言模型的非确定离散事件系统(NDES)稳定性问题.引入非确定离散事件系统稳定性的定义,并得到了稳定性的判据定理.给出了基于梯度的搜索算法,该算法可有效消除观测器的冗余,从而降低了计算复杂度.     

On-line control of partially observed discrete event systems

It is well known that the design of supervisors for partially observed discrete-event systems is an NP-complete problem and hence computationally impractical. Furthermore, optimal supervisors for partially observed systems do not generally exist. Hence, the best supervisors that can be designed directly for operation under partial observation are the ones that generate the supremal normal (and controllable) sublanguage. In the present paper we show that a standard procedure exists by which any supervisor that has been designed for operation under full observation, can be modified to operate under partial observation. When the procedure is used to modify the optimal full-observation supervisor (i.e., the one that generates the supremal controllable language), the resultant modified supervisor is at least as efficient as the best one that can be designed directly (that generates the supremal normal sublanguage). The supervisor modification algorithm can be carried out on-line with linear computational complexity and hence makes the control under partial observation a computationally feasible procedure.     

离散事件系统的混合分散监控

研究了混合信息下的分散监控综合问题.首先提出δ-可观察(hδ-可观察)可控闭语言是(状态部分可观察下)状态反馈综合解存在的充要条件,并由此得到n-联合可观察、可控闭的系统约束是保证混合分散监控器存在的充要条件,进而得到纯分散监控器(控制器)存在的充要条件为n-可观察(n-hδ-可观察)可控闭语言被满足.最后,又通过研究系统约束与混合约束的关系,提出混合分散监控器存在的充分条件是可观察、可控闭语言与可观察可控谓词被满足.     

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.     

基于Petri网诊断器的离散事件系统模式故障的在线诊断

本文研究基于Petri网诊断器的离散事件系统模式故障的在线诊断问题.先构建一种用于模式故障在线诊断的自动机,给出了基于这种自动机的在线诊断方法.然后将自动机转换为Petri网并进一步构造了可用于S型模式故障或T型模式故障在线诊断的Petri网诊断器,提出了基于Petri网诊断器的模式故障在线诊断算法.通过分析算法的复杂性,得到了该算法具有多项式空间复杂性的结论.     

分布式多机器人运动控制的离散事件系统方法

传统多机器人系统的运动控制主要依赖于机器人的动力学方程或运动学方程,通过求解微分方程组来获得机器人的输入控制信号.随着系统中机器人数量的增加和运行环境的复杂化,动力学方程很难描述多机器人系统的运动行为,且无法很好地解决诸如死锁等逻辑故障.本文简略综述了国内外的研究现状,重点介绍笔者所在研究组开展的关于离散事件系统方法在多机器人运动控制方面的应用性研究工作.其动机在于:1)基于离散事件系统方法的运动控制能够有效地解决系统运行过程中产生的诸如死锁等逻辑故障.首先,利用离散事件系统模型对多机器人系统的运动进行建模,从而降低计算复杂性;其次,基于所得离散事件系统模型,设计分布式安全运动控制算法,使各个机器人可以自主地、无碰撞地、无死锁地运动;设计分布式鲁棒运动控制算法,使得失效的机器人对系统的影响最小.2)基于离散事件系统方法的运动控制策略可以结合传统的基于运动学方程的运动控制方法,从而使系统不但能够避免顶层的逻辑故障,而且能够确定机器人执行器的输入信号.