MARKING ESTIMATION OF PETRI NETS WITH PAIRS OF NONDETERMINISTIC TRANSITIONS

We present a technique for estimating the marking of a Petri net based on the observation of transition labels. In particular, the main contribution of the paper consists in deriving a methodology that can handle the case of nondeterministic transitions, i.e., transitions that share the same label. Under some technical assumptions, the set of markings consistent with an observation can be represented by a linear system with a fixed structure that does not depend on the length of the observed word.     

State Estimation of λ-free Labeled Petri Nets with Contact-Free Nondeterministic Transitions*

In this paper we deal with the problem of estimating the marking of a labeled Petri net with nondeterministic transitions. In particular, we consider the case in which nondeterminism is due to the presence of transitions that share the same label and that can be simultaneously enabled. Under the assumption that: the structure of the net is known, the initial marking is known, the transition labels can be observed, the nondeterministic transitions are contact-free, we present a technique for characterizing the set of markings that are consistent with the actual observation. More precisely, we show that the set of markings consistent with an observed word can be represented by a linear system with a fixed structure that does not depend on the length of the observed word.*Contact author is Alessandro Giua.     

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.     

Marking Estimation of Petri Nets With Silent Transitions

In this paper, we deal with the problem of estimating the marking of a labeled Petri net system based on the observation of transitions labels. In particular, we assume that a certain number of transitions are labeled with the empty string , while unique labels taken from a given alphabet are assigned to each of the other transitions. Transitions labeled with the empty string are called silent because their firing cannot be observed. Under some technical assumptions on the structure of the unobservable subnet, we formally prove that the set of markings consistent with the observed word can be represented by a linear system with a fixed structure that does not depend on the length of the observed word.     

标注Petri网中的最小初始标识估计

为获得制造系统初始化时的最小资源以实现最优资源分配,利用标注Petri网对系统进行建模,并研究标注Petri网的最小初始标识估计问题。给定一个标注Petri网,在不可观测变迁组成无环子网的情况下,基于动态规划提出一种新的最小初始标识估计算法。在观察到给定的标注序列后,放宽不可观测变迁发生个数的限制,并根据该算法构建节点的演化过程。当出现相同的发生数向量时,仅保留当前极小的初始标识估计,并通过节点的演化过程对极小初始标识估计的托肯总数进行对比。为验证算法的有效性,给出一个制造系统的标注Petri网模型实例,最终得到的最小初始标识为［1000］^T,且对应的变迁发生序列为t₁t₃t₄t₆,满足给定标注Petri网的结构要求。实验结果表明,与传统基于动态规划的算法相比,该算法获得的最小初始标识估计具有更小的托肯总数。     

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.     

On the Regularity of Petri Net Languages

Petri nets are known to be useful for modeling concurrent systems. Once modeled by a Petri net, the behavior of a concurrent system can be characterized by the set of all executable transition sequences, which in turn can be viewed as a language over an alphabet of symbols corresponding to the transitions of the underlying Petri net. In this paper, we study the language issue of Petri nets from a computational complexity viewpoint. We analyze the complexity of theregularity problem(i.e., the problem of determining whether a given Petri net defines an irregular language or not) for a variety of classes of Petri nets, includingconflict-free,trap-circuit,normal,sinkless,extended trap-circuit,BPP, andgeneralPetri nets. (Extended trap-circuit Petri nets are trap-circuit Petri nets augmented with a specific type ofcircuits.) As it turns out, the complexities for these Petri net classes range from NL (nondeterministic logspace), PTIME (polynomial time), and NP (nondeterministic polynomial time), to EXPSPACE (exponential space). In the process of deriving the complexity results, we develop adecomposition approachwhich, we feel, is interesting in its own right, and might have other applications to the analysis of Petri nets as well. As a by-product, an NP upper bound of the reachability problem for the class of extended trap-circuit Petri nets (which properly contains that of trap-circuit (and hence, conflict-free) and BPP-nets, and is incomparable with that of normal and sinkless Petri nets) is derived.     

On-Line Monitoring of Large Petri Net Models Under Partial Observation

We consider a Petri Net model of the plant. The observation is given by a subset of transitions whose occurrence is always and immediately sensed by a monitoring agent. Other transitions not in this subset are silent (unobservable). Classical on-line monitoring techniques, which are based on the estimation of the current state of the plant and the detection of the occurrence of undesirable events (faults), are not suitable for models of large systems due to high spatial complexity (exponential in the size of the entire model). In this paper we propose a method based on the explanation of plant observation. A legal trace minimally explains the observation if it includes all unobservable transitions whose firing is needed to enable the observed transitions. To do so, starting from an observable transition, using backward search techniques, a set of minimal explanations is derived, which are sufficient for detecting whether a fault event must have occurred for sure in the plant or not. The technique also allows production of a set of basis markings for the estimation of the current state of the plant. The set of all possible current markings can then be characterized as the unobservable reach of these basis markings. The computational complexity of the algorithm depends on the size of the largest connected subnet which includes only unobservable transitions. This allows monitoring of plants of any size in which there is no large unobservable subnet. We also illustrate the applicability of the method for the monitoring of a class of infinite state systems, unbounded Petri Nets with unobservable trap circuits, and we show how this can be useful for distributed implementations.

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.     

基于修正状态类图的标签时间Petri网系统故障诊断

针对具有不可观事件的离散事件系统的故障问题,提出了一种基于标签时间Petri网的诊断方法。首先,对标签时间Petri网系统现有的修正状态类图(modified state class graph, MSCG)进行分析,提出MSCG的改进算法。其次,对于给定的可观标签序列和观测时间,通过求解由改进的MSCG的路径信息构建的线性规划问题,获得所有与可观标签序列时间一致的有效路径,从而分析系统的故障情况。最后,以交替位协议为实例分析验证了所提方法的有效性,为复杂的实时系统故障诊断问题提供有效方案。     

Identification of Petri Nets from Knowledge of Their Language

In this paper we deal with the problem of identifying a Petri net system, given a finite language generated by it. First we consider the problem of identifying a free labeled Petri net system, i.e., all transition labels are distinct. The set of transitions and the number of places is assumed to be known, while the net structure and the initial marking are computed solving an integer programming problem. Then we extend this approach in several ways introducing additional information about the model (structural constraints, conservative components, stationary sequences) or about its initial marking. We also treat the problem of synthesizing a bounded net system starting from an automaton that generates its language. Finally, we show how the approach can also be generalized to the case of labeled Petri nets, where two or more transitions may share the same label. In particular, in this case we impose that the resulting net system is deterministic. In both cases the identification problem can still be solved via an integer programming problem.

Complexity of some problems in Petri nets

We consider the complexity of several standard problems for various classes of Petri nets. In particular, the reachability problem, the liveness problem and the k-boundedness problems are analyzed. Some polynomial time and polynomial space complete problems for Petri nets are given. We then show that the problem of deciding whether a Petri net is persistent is reducible to reachability, partially answering a question of Keller. Reachability and boundedness are proved to be undecidable for the Time Petri net introduced by Merlin. Also presented is the concept of controllability, i.e., the capability of a set of transitions to disable a given transition. We show that the controllability problem requires exponential space, even for 1-bounded nets.     

DEDS对象化高级Petri网模型研究——对象化高级Petri网上的一致性网络

针对对象化高级Petri网缺乏标识的状态空间度量,采用谓词集对各位置上的可达标识 进行完全划分,形成与加色网等价的一致性网络.原网络的语言是其任何一个一致性网络语 言的子集,因而可以用加色网来定义及分析对象化高级Petri网的各种不变量.     

Diagnosis of Partially Observed Petri Net Based on Analytical Redundancy Relationships

In this paper, we design an efficient diagnosis technique for partially observed discrete event systems modeled by labeled Petri nets. The fault detection is based on analytical redundancy relationships derived from the nominal model. The decomposition of the T_un‐induced subnet to connected subgraphs allows determining the subgraphs that may contain faults. To appreciate the fault localization, a set of analytical redundancy relationships is etablished for each fault transition based on the fault model. The proposed diagnosis approach is independent of the length of the observed sequence and independent of the number of unobservable transitions. The detected faults with the proposed approach are faults which led to a change in the number of tokens in the net.     

Diagnosability of Petri nets with observation graphs

This paper addresses the problem of diagnosability for dynamic discrete event systems modeled with bounded or unbounded Petri nets that are deadlock-free and monitored with sensor configurations with marking and event measurements. The proposed method gives necessary and sufficient conditions for diagnosability. It is based on the transformation of the coverability graph into an observation graph that encodes all observation sequences of measured markings and events with respect to the sensor configuration. This graph also encodes all sequences of transitions that may fire from any reachable marking of the Petri net. Diagnosability is determined by analyzing the paths and circuits in the observation graph. The method is illustrated with several examples of bounded or unbounded Petri nets.     

Maximally Permissive Petri Net Supervisors for Flexible Manufacturing Systems with Uncontrollable and Unobservable Transitions

This paper presents a deadlock prevention policy to obtain behaviorally optimal supervisors for flexible manufacturing systems with uncontrollable and unobservable transitions. The conditions of uncontrollability and unobservability of transitions are revealed in the sense of the implementation of a Petri net supervisor. Then, integer linear programming models are designed to obtain a Petri net supervisor such that all legal markings are reachable and the number of control places is reduced. We also show that a controllable transition can be unobservable and self‐loops can be used to disable the transition but do not observe its firing. Finally, examples are provided to illustrate the proposed approach.     

Supervisory control of partially observable marked graphs

This note presents a control synthesis approach for discrete event systems modeled by marked graphs with unobservable transitions. It solves forbidden state problems characterized by a set of general mutual exclusion constraints. We prove that for any sequence of observable transitions, there exist a unique marking from which all other possible current markings can be reached unobservably. This salient feature allows us to design efficient control policies based on proper separation of observation and control.