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.     

State‐Feedback Control for a Class of Timed Petri Nets Subject to Marking Constraints

The paper contributes with an original method of designing a control for discrete event systems modeled by a class of timed Petri nets. Precisely, this work deals with the closed loop control of Timed Event Graphs (TEGs) under specifications expressed with linear marking constraints. The objective of the controller is to limit the number of tokens in some places of these TEGs. The behavior of TEGs is represented by a system of difference equations that are linear in Min‐Plus algebra and the constraints are described by a set of inequalities, which are also linear in Min‐Plus algebra. A formal approach to design control laws that guarantee compliance with these marking constraints is proposed. For this, two sufficient conditions for the existence of control laws are proposed. The computed controls are causal feedbacks, which can be represented by a set of marked and timed places. The proposed method is illustrated in two applications: a manufacturing production line and an assembly system.     

Control of Petri nets subject to strict temporal constraints using Max-Plus algebra

In this paper, we treat the control problem of timed discrete event systems under temporal constraints. This type of constraint is very frequent in production systems, transportation network and in networked automation systems. Precisely, we are interested in the validation of strict temporal constraints imposed on the paths in a timed event graph (TEG) by using Max-Plus algebra. Not all the transitions of the considered TEG model are controllable, i.e. only the input transitions are controllable. An analytical approach for computing state feedback controllers is developed. Sufficient condition is given for the existence of causal control laws satisfying the temporal constraints. In the first, a TEG with observable transitions is considered. Then, the proposed approach is extended to the partially observable TEG. The synthesised feedback can be interpreted by places of control connected to the TEG to guarantee the respect of the time constraints. The proposed method is illustrated in the assembly system example.     

Model predictive control of P-time event graphs

This paper deals with model predictive control of discrete event systems modelled by P-time event graphs. First, the model is obtained by using the dater evolution model written in the standard algebra. Then, for the control law, we used the finite-horizon model predictive control. For the closed-loop control, we used the infinite-horizon model predictive control (IH-MPC). The latter is an approach that calculates static feedback gains which allows the stability of the closed-loop system while respecting the constraints on the control vector. The problem of IH-MPC is formulated as a linear convex programming subject to a linear matrix inequality problem. Finally, the proposed methodology is applied to a transportation system.     

Performance evaluation of nonlinear weighted T-system

This article deals with the analysis of discrete event systems which can be modelled by timed event graphs with multipliers (TEGMs). These graphs are an extension of weighted T-systems studied in the Petri net literature. These models do not admit a linear representation in (min,?+) algebra. This nonlinearity is due to the presence of weights on arcs. To mitigate this problem of nonlinearity and to apply some basic results used to analyse the performances of linear systems in dioid algebra, we propose a linearisation method of mathematical model reflecting the behaviour of a TEGM in order to obtain a (min,?+) linear model.     

Control of discrete event systems with respect to strict duration: Supervision of an industrial manufacturing plant

In this paper, we propose a (max, +)-based method for the supervision of discrete event systems subject to tight time constraints. Systems under consideration are those modeled as timed event graphs and represented with linear (max, +) state equations. The supervision is addressed by looking for solutions of constrained state equations associated with timed event graph models. These constrained state equations are derived by reducing duration constraints to elementary constraints whose contributions are injected in the system’s state equations. An example for supervisor synthesis is given for an industrial manufacturing plant subject to a strict temporal constraint, the thermal treatment of rubber parts for the automotive industries. Supervisors are calculated and classified according to their performance, considering their impact on the production throughput.     

Designing dependable logic controllers using algebraic specifications

Formal methods can strongly contribute to improve dependability of logic controllers during design, by providing means to avoid flaws due to designers’ omissions or specifications misinterpretations. This article presents a formal synthesis method that is aimed at obtaining the control laws of a logic system from specifications given in natural language. The formal framework that underlies the method is a Boolean algebra for logic discrete event systems. The operations and relations of this algebra enable to represent controller specifications formally, to detect inconsistencies within specifications and to generate control laws from a consistent specifications set. The scalability of this method is clearly demonstrated with the help of the case study of an experimental manufacturing line.     

Event‐triggered constrained control of positive systems with input saturation

This paper addresses the problem of event‐triggered stabilization for positive systems subject to input saturation, where the state variables are in the nonnegative orthant. An event‐triggered linear state feedback law is constructed. By expressing the saturated linear state feedback law on a convex hull of a group of auxiliary linear feedback laws, we establish conditions under which the closed‐loop system is asymptotically stable with a given set contained in the domain of attraction. On the basis of these conditions, the problem of designing the feedback gain and the event‐triggering strategy for attaining the largest domain of attraction is formulated and solved as an optimization problem with linear matrix inequality constraints. The problem of designing the feedback gain and the event‐triggering strategy for achieving fast transience response with a guaranteed size of the domain of attraction is also formulated and solved as an linear matrix inequality problem. The effectiveness of these results is then illustrated by numerical simulation.     

Control Synthesis of Petri Nets Based on S-Decreases

A method for constructing a controller for a discrete event system modeled by a Petri net is presented in this paper. The control specification of the system is given by a set of linear inequality constraints defined on the marking of the net. The controller that forces the net to obey the constraints is an extended Petri net, which is synthesized based on minimal support S-decreases. The method can deal with general Petri nets with uncontrollable transitions, and then provides a systematic way for synthesizing net-based controllers for discrete event systems.     

Design of real-time periodic control systems through synchronization and fixed priorities

Control systems are often designed using a set of co-operating periodic modules running under control of a real-time operating system. A correct behaviour of the closed-loop controller requires that the system meets timing constraints like periods and latencies, which can be expressed as deadlines. The control system timing requirements are captured through a partition in control paths by which priorities are assigned according to their relative urgency. Latencies are managed through precedence constraints and more or less tight synchronization between modules. The implementation uses the fixed-priority based pre-emption service of an off-the-shelf real-time operating system. Such a system can be modelled with timed event graphs, and its temporal behaviour can be analysed using the underlying (max, plus) algebra. Examples coming from a uni-processor robot controller are provided.     

Event‐triggered global leader‐following consensus of a group of neutrally stable linear systems subject to input saturation

This paper studies the global leader‐following consensus problem for a multiagent system using event‐triggered linear feedback control laws. The leader agent is described by a neutrally stable linear system and the follower agents are also described by a neutrally stable linear system but with saturating input. Both the state‐feedback case and the output‐feedback case are considered. In each case, an event‐triggered control law is constructed for each follower agent and an event‐triggering strategy is designed for updating these control laws. These event‐triggered control laws are shown to achieve global leader‐following consensus when the communication topology among the follower agents is strongly connected and detailed balanced and the leader is a neighbor of at least one follower agent. The Zeno behavior is excluded. The theoretical results are illustrated by simulation.     

基于有限状态进程的事件约束定义

测试分布式程序需要定义事件约束来检测程序执行产生的事件序列.事件约束需要根据程序的规约来推导.FSP是一类描述并发程序形式化规约的进程代数记法.它将并发进程描述为动作序列,其中动作可对应到规约级事件.E-CSPE约束在给定状态谓词下定义前后运行事件间的顺序关系.根据FSP的操作符和并发控制机制可推导E-CSPE约束.推导出来的E-CSPE约束考虑到并发程序的安全和进展属性,可据以判断程序运行的正确性和测试的充分性.     

Event‐triggered probabilistic robust control of linear systems with input constrains: By scenario optimization approach

This paper addresses the problem of probabilistic robust stabilization for uncertain systems subject to input saturation. A new probabilistic solution framework for robust control analysis and synthesis problems is addressed by a scenario optimization approach, in which the uncertainties are not assumed to be norm bounded. Furthermore, by expressing the saturated linear feedback law on a convex hull of a group of auxiliary linear feedback laws, we establish conditions under which the closed‐loop system is probabilistic stable. Based on these conditions, the problem of designing the state feedback gains for achieving the largest size of the domain of attraction is formulated and solved as a constrained optimization problem with linear matrix inequality constraints. The results are then illustrated by a numerical example.     

Reachability and control synthesis for piecewise-affine hybrid systems on simplices

In this paper, we consider the synthesis of control laws for piecewise-affine hybrid systems on simplices. The construction is based on the solution to the control-to-facet problem at the continuous level, and on dynamic programming at the discrete level. The construction is given as an explicit algorithm using only linear algebra and reach-set computations for automata; no numerical integration is required. The method is conservative, in that it may fail to find a control law where one exists, but one cannot hope for a sharp algorithm for control synthesis since reachability for piecewise-affine hybrid systems is undecidable.     

Suboptimal supervisory control of Petri nets in presence of uncontrollable transitions via monitor places

This paper deals with the problem of enforcing generalized mutual exclusion constraints (GMEC) on place/transition nets with uncontrollable transitions. An efficient control synthesis technique, which has been proposed in the literature, enforces GMEC constraints by introducing monitor places to create suitable place invariants. The method has been shown to be maximally permissive and to give a unique control structure in the case that the set of legal markings is controllable. This paper investigates on and formally shows that the class of controllers obtained by this technique may not have a supremal element for uncontrollable specifications. Moreover, it is shown that the family of monitor places enforcing an uncontrollable specification can be parameterized with respect to the solution of a linear system of equation. An algorithm to obtain such parameterization is presented here.     

Min-max functions

A variety of problems in operations research, control theory, computer science, etc., can be modeled as discrete event systems with maximum and minimum constraints. When these systems require only maximum constraints (or, dually, only minimum constraints) they can be studied by linear methods based on max-plus algebra. Systems with mixed constraints, however, are nonlinar from this perspective and relatively little is known about their behaviour. The paper lays the foundations of the theory of discrete event systems with mixed constraints. We introduce min-max functions,F:R ⁿ R ⁿ , which are constructed using finitely many operations of min, max and +, and study them as dynamical systems. Among other results, we give a complete account of the periodic behavior of functions of dimension 2; we introduce and characterize the concept of balance which generalizes irreducibility in the linear theory; and we give a formula for the cycle time (eigenvalue) of a min-max function which generalizes the maximum cycle mean formula.     

参数摄动时一类离散事件动态系统的渐近性能估计和鲁棒性条件*

本文针对一类在极大代数上可表示为线性模型的离散事件动态系统,讨论了参数摄动对系统周期稳态性能的影响,给出了定量估计参数摄动下性能改变量的一个关系式,建立了性能对参数摄动不敏感的鲁棒性条件。本文的结果,对确定系统参数的允许摄动范围,使之不破坏离散生产过程的有序和协调运行,是有指导意义的。     

A temporal logic approach to discrete event control for the safety canonical class

This paper presents a temporal logic formulation of discrete event control which forms a new theoretical basis for control analysis and synthesis of a class of discrete event systems (DES). Based on the formulation, a basic supervisory control theory is developed for a control objective specified by an invariance formula belonging to the safety canonical class of Manna and Pneuli. Using the safety canonical class as a basis, the refinement and generalization of the existing basic predicate framework are demonstrated. A simple example illustrates the formal axiomatic means to perform control-theoretic analysis and synthesis under the new formulation.     

基于事件代数的入侵检测系统

该文提出了一种基于事件代数的多事件入侵特征的形式化定义机制,用一组事件运算来表示入侵特征,对多事件入侵检测特征定义中的若干普遍问题给出了系统化的解决方案。文章还提出了一种“带约束的有色Petri网模型”来构造事件检测引擎。     

基于时间分布特征的博客突发事件检测

博客是目前网络舆论的重要载体之一,如何自动检测博客中的突发事件对于舆情分析与疏导具有重要的研究价值。针对目前突发事件检测中存在的时间信息有歧义的虚假突发事件问题,本文提出了一种基于时间分布特征的博客突发事件检测方法。该方法通过波峰检测和计算事件文档与背景语料文档之间、事件相关文档和不相关文档之间的时间分布差异来判断该事件在时间特征上是否具有突发性和关联性。实验结果表明,该方法可有效检测博客中的突发事件并可有效去除时间信息有歧义的虚假突发事件。