Feedback control for a class of discrete event systems with critical time

This paper presents an algebraic approach for control laws synthesis of timed event graphs subjected to strict temporal constraints. This class of discrete event systems is deterministic, in the sense that its behaviour only depends on the initial marking and on the control that is applied. This behaviour can be modelled by a linear equations system in Min-Plus algebra. The temporal constraint is represented by an inequality that is also linear in the Min-Plus algebra. Then, a method for the synthesis of control laws ensuring the respect of constraints is described. We give explicit formulas characterising a control law, which ensures the validity of the temporal constraints. It is a causal feedback control, involving delays. The method is illustrated on an example.     

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.     

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

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

Modular nonblocking state feedback control of discrete event systems and its application to dynamic oligopolistic markets

This article addresses a modular state feedback supervisory control problem where two local controllers should achieve a common control objective against another local controller. Each local controller has its own control objective described as a predicate. This article also addresses a nonblocking modular control problem in which a discrete event system controlled by three local controllers tends to reach the common marked states of two local controllers that are, however, prohibited by the third local controller. For a case study, we apply the proposed theory to an oligopolistic market composed of two firms and one government. Two oligopolistic firms have a common objective to maximise their total profit through collusion. However, the government prevents them from engaging in collusion. We show that the modular supervisory control theory presented in this article can be used to solve the problem of ‘how can the firms maximise their total profit against the intervention of government’?     

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.     

Decentralized state feedback control of discrete event systems

In this paper, we consider decentralized state feedback control of discrete event systems with a (global) control specification given by a predicate. In this framework, instead of a global state feedback, each local state feedback controls a part of the system according to local information so that global behaviors satisfy the global control specification. We introduce the notion of n-observability of predicates, and present necessary and sufficient conditions for the existence of a decentralized state feedback which achieves the global control specification.     

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.     

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

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

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

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

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.     

离散事件系统的无死锁模块化状态反馈控制

本文讨论离散事件系统的无死锁模块化状态反馈问题。首先我们定义自动机的交与并运算，然后通过引入自动机对的Ｄ－不变关系，我们证明当控制目标是两个谓词的交时，模块化状态反馈控制器是无死锁的充要条件是各子控制器是无死锁的且相应的控制器满足Ｄ－不变关系。我们证明了一个给定的自动机对于另一自动机的Ｄ－不变子自动机类有最大元存大，并由此给出一个综合算法。     

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

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

Polynomial-time verification of diagnosability of fuzzy discrete event systems

A fuzzy approach to perform diagnosis of fuzzy discrete event systems(FDESs)is proposed by constructing diagnosers,which may more effectively cope with the problems of vagueness and fuzziness arising from failure diagnosis of fuzzy systems.However,the complexity of constructing this kind of diagnosers is exponential in the state space and the number of fuzzy events of the system.In this paper,we present an algorithm for verifying the diagnosability of FDESs based on the construction of a nondeterministic automaton called F-verifier instead of diagnosers.Both the construction of F-verifiers and the verification of diagnosability of FDESs can be realized with a polynomial-time complexity.     

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

在研究基于混合信息的分散监控时,由于部分监控器与部分控制器发生失败,故提出了一种新型的混合可靠分散监控问题.通过修改局部可控事件集与不可控事件集,提出新的可控语言与可靠联合可观察语言定义,进而得到混合可靠分散监控器存在的充分必要条件就是整体约束语言是可靠联合可观察,可控闭的.之后,又通过研究整体约束与混合子约束之间的关系,给出了判别混合可靠分散监控器存在的一个充分条件,即混合子约束分别满足基于谓词的可观察,可控性与基于语言的联合可观察,可控封闭性.     

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.     

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

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

Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks

Supervisory control theory is a well-established theoretical framework for feedback control of discrete event systems whose behaviours are described by automata and formal languages. In this article, we propose a formal constructive method for optimal fault-tolerant scheduling of real-time multiprocessor systems based on supervisory control theory. In particular, we consider a fault-tolerant and schedulable language which is an achievable set of event sequences meeting given deadlines of accepted aperiodic tasks in the presence of processor faults. Such a language eventually provides information on whether a scheduler (i.e., supervisor) should accept or reject a newly arrived aperiodic task. Moreover, we present a systematic way of computing a largest fault-tolerant and schedulable language which is optimal in that it contains all achievable deadline-meeting sequences.     

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.     

Suboptimal time management of discrete event systems with uncontrollable events modeled by Petri nets

Preventing systems from entering to forbidden states is a crucial issue in discrete event systems control. Adding supervisors to the system is a common method to avoid entering to forbidden states. In discrete event systems modeled by Petri net adding a supervisor could be done by means of control places. Since, the time is not considered in designing this supervisor, in presence of uncontrollable transitions adding control places can lead to increase the operation time of the system modeled by timed Petri net. Because, the firing of some transitions is prevented when it is not necessary. So, to design a more efficient controller, we will be required to use time information of the system component. Therefore, in this paper, a method for optimizing the time behavior of a supervised timed Petri net will be proposed. To obtain an efficient operation, some timed places as timer will be added to the net. The time of this timer places is calculated to permit firing of some controllable transitions in order to enter into some weakly forbidden states while entering to forbidden states is prevented. This concept leads to increase the speed of system as well as obtain an acceptable operation. This method can be applied for all systems modeled by Petri nets. The efficiency of proposed approach will be discussed and validated with a case study.     

Control of a class of discrete event systems with disturbances and capacity constraints: Application to a disassembly problem

This study proposes an analytical control method for the meeting of capacity constraints in discrete event systems with disturbances. More precisely, it consists of computing control laws for partially controllable and observable timed event graphs that are subject to marking constraints. To resolve the issue, linear Min-Plus models are used to describe the behavior of these graphs, and the constraints are expressed by inequalities in Min-Plus algebra. Sufficient conditions for the existence of causal control laws to guarantee marking specifications are established. Finally, to illustrate the efficiency of the proposed approaches in this paper, an application for a disassembly process with some disturbance inputs and limited component capacities is carried out.