Structuring Acyclic Petri Nets for Reachability Analysis and Control

The incidence matrices—from places to transitions and vice versa—of an acyclic Petri net can obtain a block-triangular structure by reordering their rows and columns. This allows the efficient solution of some reachability problems for acyclic Petri nets. This result is further used in supervisory control of Petri nets; supervisors for Petri nets with uncontrollable transitions are constructed by extending the method of Yamalidou et al. (1996) to Petri nets where transitions can be executed simultaneously. A large class of Petri nets with uncontrollable transitions is given for which the maximally permissive supervisor can be realized by a Petri net. The original specification is algorithmically transformed—by using the results for acyclic Petri nets—into a new specification to take the presence of uncontrollable transitions into account. The supervisor is obtained by simple matrix multiplications and no linear integer programs need to be solved. Furthermore, a class of Petri nets is given for which the supervisor can be realized by extending the enabling rule with OR-logic.     

Supervisor synthesis for discrete event systems under partial observation and arbitrary forbidden state specifications

In this paper, we consider the forbidden state problem in discrete event systems modeled by partially observed and partially controlled Petri nets. Assuming that the reverse net of the uncontrollable subnet of the Petri net is structurally bounded, we compute a set of weakly forbidden markings from which forbidden markings can be reached by firing a sequence of uncontrollable/unobservable transitions. We then use reduced consistent markings to represent the set of consistent markings for Petri nets with structurally bounded unobservable subnets. We determine the control policy by checking if the firing of a certain controllable transition will lead to a subsequent reduced consistent marking that belongs to the set of weakly forbidden markings; if so, we disable the corresponding controllable transition. This approach is shown to be minimally restrictive in the sense that it only disables behavior that can potentially lead to a forbidden marking. The setting in this paper generalizes previous work by studying supervisory control for partially observed and partially controlled Petri nets with a general labeling function and a finite number of arbitrary forbidden states. In contrast, most previous work focuses on either labeling functions that assign a unique label to each observable transition or forbidden states that are represented using linear inequalities. More importantly, we demonstrate that, in general, the separation between observation and control (as considered in previous work) may not hold in our setting.     

Supervisory control of deterministic Petri nets with regularspecification languages

Algorithms for computing a minimally restrictive control in the context of supervisory control of discrete-event systems have been well developed when both the plant and the desired behaviour are given as regular languages. In this paper the authors extend such prior results by presenting an algorithm for computing a minimally restrictive control when the plant behaviour is a deterministic Petri net language and the desired behaviour is a regular language. As part of the development of the algorithm, the authors establish the following results that are of independent interest: i) the problem of determining whether a given deterministic Petri net language is controllable with respect to another deterministic Petri net language is reducible to a reachability problem of Petri nets and ii) the problem of synthesizing the minimally restrictive supervisor so that the controlled system generates the supremal controllable sublanguage is reducible to a forbidden marking problem. In particular, the authors can directly identify the set of forbidden markings without having to construct any reachability tree     

Feedback Control Logic for Backward Conflict Free Choice Nets

This paper discusses the forbidden state problem, as specified by generalized mutual exclusion constraints, in the context of supervisory control of discrete event systems modelled by Petri nets. The case of backward-conflict-free and free-choice uncontrollable subnets is considered and it is shown how to transform such subnets in well-formed free-choice nets. Then, the well-formed free-choice nets are decomposed in marked graph components by recurring to minimal T-invariants. The forbidden state problem is so reformulated for the obtained marked graph components into an equivalent one which is shown to be a linear programming problem. Thus, improving existing results in literature, a polynomial complexity solution, suitable for on-line control, is achieved. Free-choice relationship and cycle modelling, that frequently occur in real-life situations, are so allowed in the uncontrollable subnet     

Reduction of constraints for controller synthesis based on safe Petri Nets

In this paper, we present an efficient method based on safe Petri Nets to construct a controller. A set of linear constraints allows forbidding the reachability of specific states. The number of these so-called forbidden states, and consequently the number of constraints, are large and lead to a large number of control places. A systematic method to reduce the size and the number of constraints for safe Petri Nets is offered. By using a method based on Petri Net invariants, maximal permissive controllers are determined.     

Petri网的一类禁止状态问题的混合型监控器算法设计

针对广义互斥约束下Petri网的不可控影响子网为状态机的一类禁止状态问题,给出了观测器的设计方法,并基于观测器得到了求解最大允许控制策略的算法.利用观测器将广义互斥约束简化为单禁止库所约束,并将存在不可控变迁的问题简化为相当于变迁全部可控的问题,这有效地解决了不可控变迁带来的计算复杂性问题.最后,利用一个地铁交通调度示例验证和说明该监控器设计方法.     

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

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

Synthesis of controllers for symmetric systems

This article deals with supervisory control problem for coloured Petri (CP) nets. Considering a CP-net, we build a condensed version of the ordinary state-space, namely the symbolic reachability graph (SRG). This latter graph allows to cope with state-space explosion problem for symmetric systems. The control specification can be expressed in terms of either forbidden states or forbidden sequences of transitions. According to these specifications, we derive the controller by applying the theory of regions on the basis of the SRG. Thanks to expressiveness power of CP-nets, the obtained controller to be connected to the plant model is reduced to one single place.     

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.     

基于GMEC转换算法的Petri网结构控制器综合方法

针对含不可控变迁Petri网系统禁止状态控制器设计问题,提出了一种基于矩阵变换和整数线性规划的结构控制器综合方法。该方法的关键是对代表系统合法状态的广义互斥约束(generalized mutual exclusion constraint, GMEC)进行转换。首先,根据Petri网系统的关联矩阵,将库所集分为无关库所集、不可控库所集和补足库所集。其次,通过对非允许GMEC中补足库所的权值和不可控库所的权值进行处理,并运用整数线性规划将非允许GMEC转换为允许GMEC。在允许GMEC的基础上,根据库所不变量原理设计出Petri网系统的结构控制器。最后,以某零件加工系统为例验证了所提方法的泛用性和高效性,为实际智能制造系统的监督控制器设计提供有效参考方案。     

Some decision problems related to the reachability problem for Petri nets

In this paper, we show that (1) the question to decide whether a given Petri net is consistent, M_o-reversible or live is reduced to the reachability problem in a unified manner, (2) the reachability problem for Petri nets is equivalent to the equality problem and the inclusion problem for the sets of all firing sequences of two Petri nets, (3) the equality problem for the sets of firing sequences of two Petri nets with only two unbounded places under homomorphism is undecidable, (4) the coverability and reachability problems are undecidable for generalized Petri nets in which a distinguished transition has priority over the other transitions, and (5) the reachability problem is undecidable for generalized Petri nets in which some transitions can reset a certain place to zero marking.     

A generalization of state avoidance policies for controlled Petrinets

This paper presents a generalization of forbidden state control synthesis methods for a broad class of controlled Petri nets (CtlPN). An algebra is defined for characterizing the interaction of paths in the Petri net. Given a specification of a forbidden marking set, the net structure is analyzed to determine an algebraic expression to represent the specification. For any net marking (state), evaluation of the expression will indicate whether forbidden markings are reachable and whether control is necessary. The expression is then used for determining the maximally permissive feedback control law     

Reachability analysis of real-time systems using time Petri nets

Time Petri nets (TPNs) are a popular Petri net model for specification and verification of real-time systems. A fundamental and most widely applied method for analyzing Petri nets is reachability analysis. The existing technique for reachability analysis of TPNs, however, is not suitable for timing property verification because one cannot derive end-to-end delay in task execution, an important issue for time-critical systems, from the reachability tree constructed using the technique. In this paper, we present a new reachability based analysis technique for TPNs for timing property analysis and verification that effectively addresses the problem. Our technique is based on a concept called clock-stamped state class (CS-class). With the reachability tree generated based on CS-classes, we can directly compute the end-to-end time delay in task execution. Moreover, a CS-class can be uniquely mapped to a traditional state class based on which the conventional reachability tree is constructed. Therefore, our CS-class-based analysis technique is more general than the existing technique. We show how to apply this technique to timing property verification of the TPN model of a command and control (C2) system.     

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.     

Scheduling and control of real-time systems based on a token player approach

Petri nets are a powerful formalism for the specification and verification of concurrent systems, such as sequential systems and manufacturing systems. To deal with real-time systems whose time issues become essential, different extensions of Petri nets with time have been proposed in the literature. In this paper, a new scheduling and control technique for real-time systems modeled by ordinary P-time Petri nets is proposed. Its goal is to provide a scheduling for a particular firing sequence, without any violation of timing constraints ensuring that no deadline is missed. It is based on the firing instant notion and it consists in determining an inequality system generated for a possible evolution (in terms of a feasible firing sequence for the untimed underlying Petri net) of the model. This system can be used to check reachability problems as well as evaluating the performances of the model considered and determining the associated control for a definite functioning mode and it introduces partial order on the execution of particular events.     

Petri网的标注可达

本文基于Petri网的可达树的概念,给出标注可达树定义,并且证明网N与其标注可达树是一一对应的,然后,我们给出了网N与相应的标注可达树的相互转换算法。     

无界Petri网的可达树的综述

Petri网自提出以来得到了学术界和工业界的广泛关注. Petri网系统的可达性是最基本性质之一.系统的其他相关性质都可以通过可达性进行分析.利用等价的有限可达树来研究无界Petri网可达性,依然是一个开放性问题.该研究可以追溯到40年前,但由于问题本身的复杂性和难度太大,直到最近20年,经过国内外诸多学者的不懈努力,才逐渐取得了一些阶段性的成果和部分突破.本文回顾了近40年来国内外学者为彻底解决该问题作出的贡献.重点对4种开创性的研究成果展开讨论,分别为有限可达树、扩展可达树、改进可达树及新型改进可达树.探讨了今后无界Petri网可达性问题的研究方向.     

区间速率连续Petri网可达稳态必要性分析

文章就区间速率连续Petri网可达稳态的必要性问题进行研究,在介绍区间速率连续Petri网及其使能、引发语义的基础上首先给出区间速率连续Petri网在指定标识下具有稳态的条件;其次通过提出区间速率连续Petri网一种标识向量等价类划分方法从而给出分析区间速率连续Petri网可达稳态必要性的有效方法;最后给出一个应用例子,考察区间速率连续Petri网的可达稳态问题。     

Supervisory control based on minimal cuts and Petri net sub-controllers coordination

This paper addresses the synthesis of Petri net (PN) controller for the forbidden state transition problem with a new utilisation of the theory of regions. Moreover, as any method of control synthesis based on a reachability graph, the theory of regions suffers from the combinatorial explosion problem. The proposed work minimises the number of equations in the linear system of theory of regions and therefore one can reduce the computation time. In this paper, two different approaches are proposed to select minimal cuts in the reachability graph in order to synthesise a PN controller. Thanks to a switch from one cut to another, one can activate and deactivate the corresponding?PNcontroller. An application is implemented in a flexible manufacturing system to illustrate the present method. Finally, comparison with previous works with experimental results in obtaining a maximally permissive controller is presented.     

Reachability analysis in T-invariant-less Petri nets

An algorithm for reachability analysis in place/transition Petri nets having no transition invariants (T-invariants) is proposed. Given a Petri net with initial and target markings, a so-called complemented Petri net is created first that consists of the given Petri net and an additional complementary transition. Thereby, the reachability task is reduced to computation and investigation of those minimal-support and linearly combined T-invariants of the complemented Petri net, in which the complementary transition fires only once. Then, for each T-invariant with a single firing of the complementary transition, the algorithm will try to create a reachability path from the given initial marking to the target marking.