Principles and engineering of process control with Petri nets

Event-related control is considered in which process and related process control can be described by states and transitions that can be represented concisely by a Petri net (PN). Both process and related process control systems are event-related, causal, and concurrent and define a special type of PN using a few primitives that are assembled to form a net for which structural and dynamic invariants apply. The PNs can be used for a general approach to event-related process control in simulating, checking, debugging, and stating the quantitative deviations from the ideal solution for any given process control system. The technique can be applied to continuous or discrete processes, and provides formal checks at all development stages. It allows for components with nonideal behavior and yields numerical performance criteria. The invariants allow the PN to be structured in such a way that even complex process control systems become manageable. Examples are presented for the control tasks in an electrical substation     

Specification and analysis of parallel/distributed software andsystems by Petri nets with transition enabling functions

An approach for visually specifying parallel/distributed software using Petri nets (PNs) extend with transition enabling functions (TEFs) is investigated. The approach is demonstrated to be useful in the specification of decision-making activities that control distributed computing systems. PNs are employed because of their highly visual nature that can give insight into the nature of the controller of such a system and because of their analytical properties. In order to increase the expressive power of PNs, the extension of TEFs is used. The main focus is the specification and analysis of parallel/distributed software and systems. A key element of this approach is a set of rules derived to automatically transform such an extended net into a basic PN. Once the rules have been applied to transform the specification, analytical methods can be used to investigate characteristic properties of the system and validate correct operation     

基于Time Petri Net的实时系统冲撞检测与消解

time Petri net(TPN)在实时控制系统的建模中得到广泛应用,而冲撞是Petri网及其扩展模型的重要行为,解决冲撞是正确分析模型动态行为的关键.由于引入时间约束,使得TPN模型的使能和触发语义比Petri网模型的语义复杂,冲撞的检测及消解变得更加困难.首先根据时间约束,给出了变迁持续使能时延迟区间的计算方法,并证明了该方法的正确性;然后在此基础上定义并证明了TPN模型中冲撞的检测方法;给出了冲撞时间区间及修改时间约束的冲撞消解方法;最后通过实例验证说明了该方法的有效性和正确性.     

Liveness-enforcing supervision of bounded ordinary Petri nets usingpartial order methods

This paper combines and refines recent results into a systematic way to verify and enforce the liveness of bounded ordinary Petri nets. The approach we propose is based on a partial-order method called network unfolding. Network unfolding maps the original Petri net to an acyclic occurrence net. A finite prefix of the occurrence net is defined to give a compact representation of the original net reachability graph while preserving the causality between net transitions. A set of transition invariants denoted as base configurations is identified in the finite prefix. These base configurations capture all of the fundamental executions of the net system, thereby providing a modular way to verify and synthesize supervisory net systems. This paper proves necessary and sufficient conditions that characterize the original net liveness and the existence of maximally permissive supervisory policies that enforce liveness     

线性定常系统的Petri网解耦控制

将Petri网与现代控制理论相结合,应用于连续系统的性能分析如可控性、可观性和稳定性等已日益普遍,但Petri网应用于系统的解耦控制研究很少.提出了广义连续自控网系统的形式化定义,描述了线性定常系统的广义连续自控网系统模型并分析了广义连续自控网系统模型与状态空间描述的等效性.基于状态反馈动态解耦的基本原理,探讨了利用Petri网模型结构实现线性定常系统解耦控制的新方法.该方法采用图的遍历算法,可有效的判断系统的可解耦性以及实现解耦控制律,避免了传统解耦控制方法中计算所需的大量矩阵运算.最后给出了两个具体的应用实例.     

Petri网的硬件实现

Petri网是异步并发现象建模的重要工具,Petri网的硬件实现将为并行控制器的设计提供有效的途径.给出了几种Petri网系统的硬件实现方法,包括带抑制弧和允许弧的C/E系统、P/T系统、T-时延Petri网系统;给出了硬件实现中非纯网的处理方法.首先讨论实现各种Petri网的逻辑电路;然后用ABEL语言对逻辑电路进行描述;最后给出了一个用解释Petri网描述的服务系统的例子,说明如何使用硬件(CPLD)实现的方法.实验结果表明了上述方法的正确性.这对于离散事件动态系统控制器的设计,尤其是片上并行控制器、多处理器芯片的设计都具有十分重要的意义.     

Framework for modeling and analysis of distributed problem-solving systems

Petri nets have the basic concepts necessary to model distributed systems with asynchronous processes. Petri nets are not directly applicable to certain kinds of systems like distributed intelligent systems (DISs). These are complex systems where multiple intelligent agents cooperate through communication to achieve the solution to a problem. The paper identifies the limitations of ordinary Petri nets for modeling DISs and proposes extensions. The extended Petri net incorporates colored tokens, inhibition arcs, non-primitive places and transitions, multiple copies of tokens and cumulative places. It is called a distributed problem-solving Petri net. The definitions and analysis techniques are given and illustrated by means of an example.     

基于有色Petri网并发进程模型及死锁避免方法

并发进程具有明显的异步并发性,而Petri网是描述异步并发系统的有效工具,但是目前将Petri网用于并发进程控制问题的研究还几乎没有。为此通过引入扩展有色Petri网,为并发进程建立了模型,并给出了避免死锁的有效方法。     

Reduction methods for real-time systems using Delay Time Petri Nets

We present a new net-reduction methodology to facilitate the analysis of real-time systems using Delay Time Petri Nets (DTPNs). Net reduction is one of the most important techniques for reducing the state-explosion problem of Petri nets. However, the application of net reduction to current timed-extensions of Petri nets (such as Merlin's Time PNs) is very limited due to the difficulty faced in the preservation of timing constraints. To overcome this problem, we introduce DTPNs which are inspired by Merlin's (1976) Time PNs, Senac's (1994) Hierarchical Time Stream PNs, and Little's (1991) Timed PNs. We show that DTPNs are much more suitable for net reduction. Then, we present a new set of DTPN reduction rules for the analysis of schedule and deadlock analysis. Our work is distinct from the others since our goal is to analyze real-time systems and the reduction methods we propose preserve both timing properties (schedule) and deadlock. To evaluate our framework, we have implemented an automated analysis tool whose main functions include net reduction and class-graph generation. The experimental results show that our net-reduction methodology leads to a significant contribution to the efficient analysis of real-time systems     

The use of Petri Nets for Occam programming for transputers

There is undoubtedly a need for software-design tools for parallel programming. A main problem with design tools for parallel programming is their inability to check for liveness (no deadlock) and safeness. In this paper, the use of Ordinary Petri net as a software design tool for Occam Petri Net and Occam constructs are discussed. The similarities between Ordinary Petri Net and Occam constructs are highlighted, and an Occam Petri Net model is proposed as a design tool to aid in writing Occam codes. The Occam Petri Net model is graphical. It is capable of modelling deterministic concurrent and choice systems. As a top-down design, the net is similar to Occam ‘folds’, and, in its use in bottom-up implementation, it is similar to unfolding. This unfolding using the Occam Petri Net model makes writing Occam source codes easier. The availability of Petri Net CASE tools will make it more attractive for designing Occam programs.     

Analysis of the Petri net model of parallel manufacturing processes with shared resources

A method of analysis for a class of Petri nets (PNs) called parallel process net with resources (PPNRs) is presented in this paper. The proposed analysis method is based on reduced reachability graph (RRG) of PPNRs to verify the correspondence between required specification of manufacturing system and its PN representation. In order to reduce the reachability graph (RG), a new technique is proposed which incorporates the transition vectors (TVs) to determine all the enabled transitions at a given state of system and to recognize them as dependent or independent. An algorithm, based on the idea of simultaneous execution of concurrently enabled independent transitions, is developed to reduce the RG and its analysis is also performed. Moreover, relationship between the reduction of RG and parallel structure in the PN model is discovered. The proposed technique replaces the RG by a structure which directly depicts concurrent execution and does not show the irrelevant states by presenting the concurrent behavior of system in the reduced state space. The analysis of PPNRs based on RRG generated by proposed method is also presented and demonstrated by a practical example.     

基于模块化可达图的服务组合验证及BPEL代码生成

为了解决基于中介器服务组合方法的状态爆炸和不能自动生成BPEL(business process execution language)的问题,提出了一种基于Petri网模块化可达图的服务组合验证方法.服务组合的Petri网模型通过中介变迁进行模型分割,分别对各个部分构建可达图,再对模块化可达图进行服务组合可行性分析.采用模块化可达图可以大量节省空间开销,有效避免空间爆炸问题.在验证服务组合可行的情况下提出了基于ECA规则形式的BPEL过程代码自动生成方法,也就是将服务组合Petri网模型的中介变迁以及每个服务对外接口的调用或操作都映射生成为ECA规则形式的BPEL代码段.通过对一个电子商务实例进行分析,说明了所提出方法的有效性.     

Structure-Based Deadlock Checking of Asynchronous Circuits

It is important to verify the absence of deadlocks in asynchronous circuits. Much previous work relies on a reachability analysis of the circuits’ states, with the use of binary decision diagrams (BDDs) or Petri nets to model the behaviors of circuits. This paper presents an alternative approach focusing on the structural properties of well-formed asynchronous circuits that will never suffer deadlocks. A class of data-driven asynchronous pipelines is targeted in this paper, which can be viewed as a network of basic components connected by handshake channels. The sufficient and necessary conditions for a component network consisting of Steer, Merge, Fork and Join are given. The slack elasticity of the channels is analyzed in order to introduce pipelining. As an application, a deadlock checking method is implemented in a syntax-directed asynchronous design tool -- Teak. The proposed method shows a great runtime advantage when compared against previous Petri net based verification tools.     

物料清单构造中嵌套检查改进算法

结合物料清单（BOM）递归遍历、非递归遍历和层次遍历方法,针对多层次通用件的广泛适用构成的复杂产品,将实用性较强的网状BOM构造方法和无向无环图（DAG）的基本理论相融合,提出了一种新的BOM嵌套检查及合法性检查改进算法。该算法采用自顶向下方式逐层分解,设计不同的标志位及迭代来决定当前操作对象,充分利用关系数据库的操作特点,不受内存限制,具有较高的执行效率。     

并行计算的Petri网建模和FPGA实现

在分析现有Petri网建模及其FPGA实现方法的基础上, 首先探讨了并行计算的Petri网建模方法, 将并行计算任务分解成多个并行处理单元, 用IOPT网为系统进行建模; 然后提出了构造监控层和算法层的双层结构以实现模型到FPGA实现的具体映射, 有效解决了Petri网模型中变迁只能表示简单加减运算的问题。通过矩阵乘法的应用示例, 表明了上述方法的正确性和通用性。最后提出了进一步的研究方向。     

On supervisory policies that enforce liveness in completelycontrolled Petri nets with directed cut-places and cut-transitions

The process of synthesizing a supervisory policy that enforces liveness in a Petri net (PN), where each transition can be prevented from firing by an external agent, can be computationally burdensome in general. We consider PNs that have a directed cut place or a cut-transition. A place (transition) in a connected PN is said to be a cut place (cut-transition) if its removal will result in two disconnected component PNs. A cut place is said to be a directed cut-place, if in the original PN, all arcs into this cut place emanate from transitions in only one of the two disconnected component PNs. The authors show there is a supervisory policy that enforces liveness in the original PN if and only if similar policies exist for two PNs derived from the disconnected components obtained after the removal of the directed cut-place (cut-transition). The utility of this observation in alleviating the computational burden of policy synthesis is illustrated via example     

Synthesis of supervisors enforcing general linear constraints in Petri nets

Efficient techniques exist for the design of supervisors enforcing constraints consisting of linear marking inequalities. This note shows that without losing the benefits of the prior techniques, the class of constraints can be generalized to linear constraints containing marking terms, firing vector terms, and Parikh vector terms. We show that this extended class of constraints is more expressive. Furthermore, we show that the extended constraints can describe any supervisor consisting of control places arbitrarily connected to the transitions of a plant Petri net (PN). The supervisor design procedure we propose is as follows. For PNs without uncontrollable and unobservable transitions, a direct method for the design of a PN supervisor that is least restrictive is given. For PNs with uncontrollable and/or unobservable transitions, we reduce the problem to the design of supervisors enforcing linear marking inequalities.     

Branching processes of Petri nets

Summary The notion of a branching process is introduced, as a formalization of an initial part of a run of a Petri net, including nondeterministic choices. This generalizes the notion of a process in a natural way. It is shown that the set of branching processes of a Petri net is a complete lattice, with respect to the natural notion of partial order. The largest element of this lattice is the unfolding of the Petri net.     

Real-time software specification and validation with Transnet

The paper presents the executable specification method for real-time (embedded) systems Transnet. The method is based on an extension to Petri nets. A specification is developed by a problem decomposition into a set of parallel processes. Each process is defined by an extended Petri net with functions assigned to transitions, and conditions and time constants assigned to arcs. It is shown that Transnet matches with the characteristics of the intended class of applications. The available specification languages and the internal representation of data which describe the functional as well as nonfunctional requirements are outlined. The advantages of the Petri net-based representation and the possibilities of automatic net analysis and early validation are discussed.     

Tutorial and Survey Articles: An introduction to Petri Nets

This paper describes the fundamental concepts and characteristics of Petri nets (PNs) that make them a significant tool for modeling and analyzing asynchronous systems with concurrent and parallel activities and follows the extensions that improved the implementation capabilities of the original PNs.

Their first and most relevant extension was time modeling, a vital aspect of system performances not considered in the original version. There are several possibilities for introducing time in PNs. Among them, a technique that associates time with places is presented in some detail. As PNs tend to become cumbersome and time consuming when large and complex systems are involved, a method for decomposing timed PNs of open queuing networks is reviewed here.

Though initially developed as an information/computer-based technique, PNs were immediately adopted in a variety of application areas, such as manufacturing, design, planning and control. Viewed through a more recently developed programming perspective, the ordinary PNs became “high level” PNs suitable for defining different data types and for applying hierarchical approaches.

It is expected that the robust theoretical basis of this tool coupled with its visual and flexibility features will continue to appeal to researchers and practitioners alike in a variety of domains and as a result will continue to evolve and expand.