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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Opacity of discrete event systems and its applications

In this paper, we investigate opacity of discrete event systems. We define two types of opacities: strong opacity and weak opacity. Given a general observation mapping, a language is strongly opaque if all strings in the language are confused with some strings in another language and it is weakly opaque if some strings in the language are confused with some strings in another language. We show that security and privacy of computer systems and communication protocols can be investigated in terms of opacity. In particular, two important properties in security and privacy, namely anonymity and secrecy, can be studied as special cases of opacity. We also show that by properly specifying the languages and the observation mapping, three important properties of discrete event systems, namely observability, diagnosability, and detectability, can all be reformulated as opacity. Thus, opacity has a wide range of applications. Also in this paper we provide algorithms for checking strong opacity and weak opacity for systems described by regular languages and having a generalized projection as the observation mapping.     

Real time identification of discrete event systems using Petri nets

The paper defines the identification problem for Discrete Event Systems (DES) as the problem of inferring a Petri Net () model using the observation of the events and the available output vectors, that correspond to the markings of the measurable places. Two cases are studied considering different levels of the system knowledge. In the first case the place and transition sets are assumed known. Hence, an integer linear programming problem is defined in order to determine a modelling the DES. In the second case the transition and place sets are assumed unknown and only an upper bound of the number of places is given. Hence, the identification problem is solved by an identification algorithm that observes in real time the occurred events and the corresponding output vectors. The integer linear programming problem is defined at each observation so that the can be recursively identified. Some results and examples characterize the identified systems and show the flexibility and simplicity of the proposed technique. Moreover, an application to the synthesis of supervisory control of systems via monitor places is proposed.     

Supervisory control of discrete event systems with communication delays and partial observations

This paper presents necessary and sufficient conditions for the existence of a nonblocking supervisor that achieves a given language specification for a discrete event system (DES) with communication delays and partial observations. In many practical situations, some uncontrollable events can subsequently occur before a proper control action is applied to the DES due to delays in sensing, communicating, and actuating. Moreover, some of the uncontrollable events may be unobservable. To achieve a given language specification in such situations, this paper presents a language property called delay observability which assures no confliction in making a decision for legal controllable events under partial observation and delay communication.     

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.     

Modeling and control of discrete event systems using finite state machines with variables and their applications in power grids

Control theories for discrete event systems modeled as finite state machines have been well developed to address various fundamental control issues. However, finite state machine model has long suffered from the problem of state explosion that renders it unsuitable for some practical applications. In an attempt to mitigate the state explosion problem, we propose an efficient representation that appends finite sets of variables to finite state machines in modeling discrete event systems. We also present the control synthesis techniques for such finite state machines with variables (FSMwV). We first present our notion and means of control under this representation. We next present our algorithms for both offline and online synthesis of safety control policies. We then apply these results to the control of electric power grids.     

Formal approach to fault diagnosis in distributed discrete event systems with OBDD

In this paper, we study the fault diagnosis problem for distributed discrete event systems. The model assumes that the system is composed of distributed components which are modeled in labeled Petri nets and interact with each other via sets of common resources (places). Further, a component’s own access to a common resource is an observable event. Based on the diagnoser approach proposed by Sampath et al., a distributed fault diagnosis algorithm with communication is presented. The distributed algorithm assumes that the local diagnosis process can exchange messages upon the occurrence of observable events. We prove the distributed diagnosis algorithm is correct in the sense that it recovers the same diagnostic information as the centralized diagnosis algorithm. Furthermore, we introduce the ordered binary decision diagrams (OBDD) in order to manage the state explosion problem in state estimation of the system.     

Decentralized supervisory control of discrete event systems with communication delays based on conjunctive and permissive decision structures

In many practical discrete event systems (DESs), some unexpected and uncontrollable events can subsequently occur before a proper control action is actually applied to a plant due to communication delays. For such DESs, this paper investigates necessary and sufficient conditions for the existence of a nonblocking decentralized supervisor that can correctly achieve a given language specification when the decentralized supervisor is assumed to have a conjunctive and permissive decision structure. In particular, this paper presents a notion of delay-coobservability for a given language specification and shows that it is a key condition for the existence of such a decentralized supervisor.     

Delay-coobservability and its algebraic properties for the decentralized supervisory control of discrete event systems with communication delays

In networked control systems, uncontrollable events may unexpectedly occur at a plant before a proper control command is applied to it due to communication delays. In this paper, we address the problem of decentralized supervisory control under such communication delays based on the C&P (conjunctive and permissive) and D&A (disjunctive and antipermissive) decision architecture. In particular, for the existence of a decentralized supervisor, we present the notion of delay-coobservability of a given language specification and a polynomial-time algorithm for verifying it. In addition, algebraic properties of the delay-coobservability are investigated. We further present a synthesis method of the decentralized supervisor for practical usefulness.     

Bisimilarity control of partially observed nondeterministic discrete event systems and a test algorithm

In this paper, the bisimilarity control of discrete event systems (DESs) under partial observations is investigated, where the plant and the specification are allowed to be nondeterministic. A notation of simulation-based controllability and a synchronization scheme for the supervised system are formalized based on the simulation relation between the specification and the plant. It is shown that the existence of bisimilarity supervisors is characterized by the notions of the simulation-based controllability and the language observability, which extends the traditional results of supervisory control from language equivalence to bisimulation equivalence. In addition, a polynomial algorithm to test the simulation-based controllability is developed by constructing a computing tree. This algorithm together with the test of language observability can be used to check the existence of bisimilarity supervisors.     

Fault detection for discrete event systems using Petri nets with unobservable transitions

In this paper we present a fault detection approach for discrete event systems using Petri nets. We assume that some of the transitions of the net are unobservable, including all those transitions that model faulty behaviors. Our diagnosis approach is based on the notions of basis marking and justification, that allow us to characterize the set of markings that are consistent with the actual observation, and the set of unobservable transitions whose firing enable it. This approach applies to all net systems whose unobservable subnet is acyclic. If the net system is also bounded the proposed approach may be significantly simplified by moving the most burdensome part of the procedure off-line, thanks to the construction of a graph, called the basis reachability graph.     

非线性DEDS的周期时间配置与凝着色图

对于用极大极小函数描述的非线性离散事件动态系统(DEDS)，提出一种凝着色图方法。用该方法证明了不同周期时间的数日等于凝点的数日。在此基础上给出了能用状态反馈(独立)配置周期时间的充要条件，解决了与传统线性控制系统极点配置问题完全对应的问题。将该结果应用于线性DEDS，得到了配置域及缩短的周期时间。