基于Petri网诊断器的离散事件系统模式故障的在线诊断

本文研究基于Petri网诊断器的离散事件系统模式故障的在线诊断问题.先构建一种用于模式故障在线诊断的自动机,给出了基于这种自动机的在线诊断方法.然后将自动机转换为Petri网并进一步构造了可用于S型模式故障或T型模式故障在线诊断的Petri网诊断器,提出了基于Petri网诊断器的模式故障在线诊断算法.通过分析算法的复杂性,得到了该算法具有多项式空间复杂性的结论.     

A new Petri net modeling technique for the performance analysis of discrete event dynamic systems

An interesting modeling problem is the need to model one or more of the system modules without exposition to the other system modules. This modeling problem arises due to our interest in these modules or incomplete knowledge, or inherent complexity, of the rest of the system modules. Whenever the performance measures (one or more) of the desired modules are available through previous performance studies, data sheets, or previous experimental works, the required performance measures for the whole system can be predicted from our proposed modeling technique. The incomplete knowledge problem of the dynamic behavior of some system modules has been studied by control theory. In the control area, such systems are known as partially observed discrete event dynamic systems, or POS systems. To the best of our knowledge, the performance evaluation of the POS system has not been addressed by the Petri net theory yet.Therefore, in this paper, we propose a new modeling technique for solving this kind of problem based on using the Petri net theory (i.e. Stochastic Reward Nets (SRNs)) in conjunction with the optimal control theory. In this technique, we develop an SRN Equivalent Model (EM) for the modeled system. The SRN EM-model consists of two main nets and their interface nets. One of the main nets represents the part(s) of interest or the known part(s) of the overall POS system that allows us to model its dynamic behavior and evaluate its performance measures. The other main net represents the remaining part(s) of the overall POS system that feeds the part(s) of interest. The well-known maximum principles have been used to develop an algorithm for determining the unknown transition rates of the proposed model. Numerical simulations are given to show that the proposed approach is more effective than the conventional modeling techniques, especially when dealing with systems having a large number of states.     

Petri net representation of multi-valued logical regulatory graphs

Relying on a convenient logical representation of regulatory networks, we propose a generic method to qualitatively model regulatory interactions in the standard elementary and coloured Petri net frameworks. Logical functions governing the behaviours of the components of logical regulatory graphs are efficiently represented by Multivalued Decision Diagrams, which are also at the basis of the translation of logical models in terms of Petri nets. We further delineate a simple strategy to sort trajectories through the introduction of priority classes (in the logical framework) or priority functions (in the Petri net framework). We also focus on qualitative behaviours such as multistationarity or sustained oscillations, identified as specific structures in state transition graphs (for logical models) or in marking graphs (in Petri nets). Regulatory circuits are known to be at the origin of such properties. In this respect, we present a method that allows to determine the functionality contexts of regulatory circuits, i.e. constraints on external regulator states enabling the corresponding dynamical properties. Finally, this approach is illustrated through an application to the modelling of a regulatory network controlling T lymphocyte activation and differentiation.     

Stochastic Petri net analysis of a replicated file system

The authors present a stochastic Petri net model of a replicated file system in a distributed environment where replicated files reside on different hosts and a voting algorithm is used to maintain consistency. Witnesses, which simply record the status of the file but contain no data, can be used in addition to or in place of files to reduce overhead. A model sufficiently detailed to include file status (current or out-of-date) as well as failure and repair of hosts where copies or witnesses reside, is presented. The number of copies and witnesses is not fixed, but is a parameter of the model. Two different majority protocols are examined     

A compact Petri net representation and its implications foranalysis

We explore a property-independent, coarsened, multilevel representation for supporting state reachability analysis for a number of different properties. This multilevel representation comprises a reachability graph derived from a highly optimized Petri net representation that is based on task interaction graphs and associated property-specific summary information. This highly optimized representation reduces the size of the reachability graph but may increase the cost of the analysis algorithm for some types of analyses. We explore this tradeoff. To this end, we have developed a framework for checking a variety of properties of concurrent programs using this optimized representation and present empirical results that compare the cost to an alternative Petri net representation. In addition, we present reduction techniques that can further improve the performance and yet still preserve analysis information. Although worst-case bounds for most concurrency analysis techniques are daunting, we demonstrate that the techniques that we propose significantly broaden the applicability of reachability analyses     

模糊空间Petri网的规则表示及动态推理

为便于表示模糊空间Petri网的状态变迁规则,根据空间关联影响区域分布现实特点,提出了空间模糊Petri网中的状态关联影响规则、变迁关联影响规则和多阈值激活规则。依据模糊产生式规则的特点,详细描述了10种具体的推理规则和表示组件,并以实例加以说明。在此基础上,结合模糊空间Petri网的特点提出了动态推理过程算法,可以实现各种空间状态规则因子的转化。动态推理的过程不仅可以获取某种“结果”,而且可以挖掘基于空间位置关联的中间状态及引起中间状态变化的事件,可以有效地指导风险过程预测和控制。     

应用带标识的模糊Petri网的知识表示方法

提出一种在某些库所中带有标识的模糊Petri网模型来进行知识表示。为了获得更多的加权模糊产生式规则的信息,在知识表示的过程中考虑了权值,确定性因子,阈值等参数。这种模糊Petri网充分利用了Petri网的并行处理能力。随着带标识的模糊Petri网的运行,网中标识的变化可以标记加权模糊推理的运行。通过文中给出的基于相似性测度的计算方法可以更加高效地计算出多层加权模糊推理的推理结果。     

Stochastic Petri net modeling of wave sequences in cardiac arrhythmias

We describe a methodology for modeling heart rhythms observed in electrocardiograms. In particular, we present a procedure to derive simple dynamic models that capture the cardiac mechanisms which control the particular timing sequences of P and R waves characteristic of different arrhythmias. By treating the cardiac electrophysiology at an aggregate level, simple network models of the wave generating system under a variety of diseased conditions can be developed. These network models are then systematically converted to stochastic Petri nets which offer a compact mathematical framework to express the dynamics and statistical variability of the wave generating mechanisms. Models of several arrhythmias are included in order to illustrate the methodology.     

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.     

On the distributed orchestration of stochastic discrete event simulations

Discrete event simulations are a powerful technique for modeling stochastic systems with multiple components where interactions between these components are governed by the probability distribution functions associated with them. Complex discrete event simulations are often computationally intensive with long completion times. This paper describes our solution to the problem of orchestrating the execution of a stochastic, discrete event simulation where computational hot spots evolve spatially over time. Our performance benchmarks report on our ability to balance computational loads in these settings. Copyright © 2013 John Wiley & Sons, Ltd.     

基于Petri网的并发事件流程模型修复分析

目前,流程模型可以从大量的事件日志中挖掘出来,以重放大多数的日志.但是,少数偏离流程模型的日志亦是有效的,为了使事件日志与流程模型更加拟合,模型修复是一个很好的方法.提出了基于Petri网的并发事件流程模型修复分析方法.首先,找到事件日志与流程模型的最优对齐,筛选出用于修复的并发事件;其次,利用提出的重构子流程的修复方法,对筛选得到的并发事件进行重构;最后,根据算法嵌入到原始模型中以实现模型修复,并通过一个具体实例说明了该方法的合理有效性.修复后的模型可以完全重放给定的事件日志,并且能够避免因循环造成的多余行为的发生,同时也在最大程度上保留了原始模型的使用价值.     

Merged processes: a new condensed representation of Petri net behaviour

Model checking based on Petri net unfoldings is an approach widely applied to cope with the state space explosion problem. In this paper, we propose a new condensed representation of a Petri net’s behaviour called merged processes, which copes well not only with concurrency, but also with other sources of state space explosion, viz sequences of choices and non-safeness. Moreover, this representation is sufficiently similar to the traditional unfoldings, so that a large body of results developed for the latter can be re-used. Experimental results indicate that the proposed representation of a Petri net’s behaviour alleviates the state space explosion problem to a significant degree and is suitable for model checking.V. Khomenko is a Royal Academy of Engineering/Epsrc Research Fellow supported by the RAEng/Epsrc grant EP/C53400X/1 (Davac).M. Koutny is supported by the EC IST grant 511599 (Rodin).W. Vogler is supported by the DFG-project STG-Dekomposition VO 615/7-1     

An optimal termination testing procedure for discrete event simulations

In this paper we consider discrete-event simulations which yield results until a termination condition is satisfied. The simulation can proceed beyond this time, but no useful information is generated. The time at which the termination condition will be satisfied is not known initially, and is taken to be randomly distributed with some prescribed density. It is necessary, therefore, to periodically check the termination condition, and this consumes CPU time. The question that we address is how to distribute checking time to minimize expected CPU expenditure. We do this by taking a limit in which the cost of checking is small, and then minimizing the limiting expected CPU expenditure. In general, uniformly distributed checking times are not optimal. The layouts of checking times which are generated by our minimization procedure can significantly outperform constant checking intervals.     

A discrete Petri net model for cephalostatin-induced apoptosis in leukemic cells

Understanding the mechanisms involved in apoptosis has been an area of extensive study due to its critical role in the development and homeostasis of multi-cellular organisms. Our special interest lies in understanding the apoptosis of tumor cells which is mediated by novel potential drugs. Cephalostatin 1 is a marine compound that can induce apoptosis in leukemic cells in a dose- and time-dependent manner even at nano-molar concentrations using a recently discovered pathway that excludes the receptor-mediated pathway and which includes both the mitochondrial and endoplasmic reticulum pathways (Dirsch et al., Cancer Res 63:8869–8876, 2003; López-Antón et al., J Biol Chem 28:33078–33086, 2006). In this paper, the methods and tools of Petri net theory are used to construct, analyze, and validate a discrete Petri net model for cephalostatin 1-induced apoptosis. Based on experimental results and literature search, we constructed a discrete Petri net consisting of 43 places and 59 transitions. Standard Petri net analysis techniques such as structural and invariant analyses and a recently developed modularity analysis technique using maximal abstract dependent transition sets (ADT sets) were employed. Results of these analyses revealed model consistency with known biological behavior. The sub-modules represented by the ADT sets were compared with the functional modules of apoptosis identified by Alberghina and Colangelo (BMC Neurosci 7(Suppl 1):S2, 2006).     

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.     

Modeling and formal verification of embedded systems based on a Petri net representation

In this paper we concentrate on aspects related to modeling and formal verification of embedded systems. First, we define a formal model of computation for embedded systems based on Petri nets that can capture important features of such systems and allows their representation at different levels of granularity. Our modeling formalism has a well-defined semantics so that it supports a precise representation of the system, the use of formal methods to verify its correctness, and the automation of different tasks along the design process. Second, we propose an approach to the problem of formal verification of embedded systems represented in our modeling formalism. We make use of model checking to prove whether certain properties, expressed as temporal logic formulas, hold with respect to the system model. We introduce a systematic procedure to translate our model into timed automata so that it is possible to use available model checking tools. We propose two strategies for improving the verification efficiency, the first by applying correctness-preserving transformations and the second by exploring the degree of parallelism characteristic to the system. Some examples, including a realistic industrial case, demonstrate the efficiency of our approach on practical applications.     

Stochastic Petri net models of Ca2+ signaling complexes and their analysis

Mathematical models of Ca²⁺ release sites derived from Markov chain models of intracellular Ca²⁺ channels exhibit collective gating reminiscent of the experimentally observed phenomenon of stochastic Ca²⁺ excitability (i.e., puffs and sparks). Ca²⁺ release site models are composed of a number of individual channel models whose dynamic behavior depends on the local Ca²⁺ concentration which is influenced by the state of all channels. We consider this application area to illustrate how stochastic Petri nets and in particular stochastic activity networks can be used to model dynamical phenomena in cell biology. We highlight how state-sharing composition operations as supported by the M?bius framework can represent both mean-field and spatial coupling assumptions in a natural manner. We investigate how state-of-the-art techniques for the numerical and simulative analysis of Markov chains associated with stochastic Petri nets scale when modeling Ca²⁺ signaling complexes of physiological size and complexity.     

Implementation of real-time distributed control for discrete event robotic systems using Petri nets

This article presents a systematic method of modeling and implementing real-time control for discrete-event robotic systems using Petri nets. Because, in complex robotic systems such as flexible manufacturing systems, the controllers are distributed according to their physical structure, it is desirable to realize real-time distributed control. In this article, the task specification of robotic processes is represented as a system control-level net. Then, based on the hierarchical approach, it is transformed into detailed subnets, which are decomposed and distributed into the local machine controllers. The implementation of real-time distributed control through communication between the system controller and the machine controllers on a microcomputer network is described for a sample robotic system. The proposed implementation method is sufficiently general, and can be used as an effective prototyping tool for consistent modeling, simulation, and real-time control of large and complex robotic systems.