Observability of continuous Petri nets with infinite server semantics

Timed continuous Petri net (contPN) systems with infinite server semantics are nonlinear systems, particularly a subclass of piecewise linear (PWL) systems. This paper addresses several problems regarding the state observability of these systems. We assume that the initial marking/state is not known and by measuring the marking of some places we want to estimate all the others. First, a study of the different linear systems corresponding to a continuous Petri net system is performed. It is shown that in some cases, some of them are redundant, and so can be disregarded. The notion of distinguishable modes is introduced which helps us in giving a necessary and sufficient criterion for the observability in infinitesimal time. Structural observability, i.e., observability for all possible values of firing rates of transitions, is studied and it is proved that in some cases it can be reduced to a linear problem, even if the system is nonlinear. Using results from linear structured systems, the concept of weak structural or generic observability is considered.     

ON/OFF strategy based minimum-time control of continuous Petri nets

This paper focuses on the target marking control problem of timed continuous Petri nets (TCPN), aiming to drive the system from an initial state to a desired final one. This problem is similar to the set-point control problem in a general continuous-state system. In a previous work, a simple and efficient ON/OFF controller was proposed for Choice-Free nets, and it was proved to be minimum-time (Wang, 2010). However, for general TCPN the ON/OFF controller may bring the system to “blocking” situations due to its “greedy” firing strategy, and the convergence to the final state is not ensured. In this work the ON/OFF controller is extended to general TCPN by adding more “fair” strategies to solve conflicts in the system: the ON/OFF+ controller is obtained by forcing proportional firings of conflicting transitions. Nevertheless, such kind of controller might highly slow down the system when transitions have flows of different orders of magnitude, therefore a balancing process is introduced, leading to the B-ON/OFF controller. A third approach introduced here is the MPC-ON/OFF controller, a combination of Model Predictive Control (MPC) and the ON/OFF strategy; it may achieve a smaller number of time steps for reaching the final states, but usually requires more CPU time for computing the control laws. All the proposed extensions are heuristic methods for the minimum-time control and their convergences are proved. Finally, an application example of a manufacturing cell is considered to illustrate the methods. It is shown that by using the proposed controllers, reasonable numbers of time steps for reaching the final state can be obtained with low computational complexity.     

First-order hybrid Petri nets. An application to distributed manufacturing systems

In this paper we consider Hybrid Petri Nets (HPNs), a particular formalism that combines fluid and discrete event dynamics. We first provide a survey of the main HPN models that have been presented in the literature in the last decades. Then, we focus on a particular HPN model, namely the First-Order Hybrid Petri Net (FOHPN) model, whose continuous dynamics are piece-wise constant. Here the problem of designing an optimal controller simply requires solving on-line an appropriate linear integer programming problem. In this paper we show how FOHPNs can efficiently represent the concurrent activities of Distributed Manufacturing Systems (DMS), and some interesting optimization problems are also solved via numerical simulation.     

Constrained regulation of continuous Petri nets

This paper deals with constrained regulation of continuous Petri nets under the so-called infinite servers semantics. Our aim is to design feedback gains that permit us to reach both desired stationary marking vector and desired asymptotic firing rate vector. The proposed approach takes into account constraints on the control, the marking of the Petri net, and the stability of the closed-loop system. The existence of a solution is first expressed geometrically, in terms of the inclusion of two polyhedral sets. They are reformulated algebraically as linear matrix inequalities, which provides an effective way to calculate feedback gains answering the problem. Finally, an application to an assembly production system is given.     

A linear characterization of the switching dynamic behavior of timed continuous Petri nets with structural conflicts

The behavior of timed continuous Petri nets (TCPN) can be ruled by linear equations during certain time elapses (IB-states), but changes in the marking and conflict solving policies make nonlinear the complete computation of the behavior. In this paper a global characterization of the switching behavior of TCPN through Mixed Linear Integer Programming (MLIP) is presented. The contribution is an analytical technique to compute the evolution graph of a TCPN, which allows deriving MLIP problems from TCPN models including cycles and structural conflicts; conflict resolution policies by priorities and sharing are considered.     

Representation and analysis of behavior for multiprocess systems by using stochastic Petri nets

This paper proposes a new approach to visually represent the behavior of multiprocess in a computer network system using stochastic Petri net (SPN) and an aggregate approach of SPN and Markov renewal process (MRP) to conduct behavior analysis and performance evaluation for the system. SPN is employed because of its highly visual nature that can give insight into the nature of the modeled system and because of its expressive power for an exponentially distributed event. In order to increase the analytical power of the SPN model, MRP is introduced and an embedded transference probability matrix is applied to obtain the steady-state solution of the model, from which it is possible to obtain automatically the performance measures of the multiprocess computer network system.     

Rapid and modular prototyping-based Petri nets and distributed simulation for manufacturing systems

This paper presents an approach to simulate and implement by stepwise refinement the whole manufacturing system (MS) by means of distributed simulation. This approach is based on the use of different classes of Petri nets to model different levels of a manufacturing system. Furthermore these classes may match the abstraction levels of a high-level Petri net used to model the MS. Each level can be simulated on a processor or a cluster of processors which can communicate between themselves using a network. The main contribution is to give the opportunity to combine simulation, performance evaluation and emulation. The emulation means that a part of the system can be run in real time while the other part is simulated. Moreover based on the abstraction levels of high-level Petri nets, subsystems can be integrated step-by-step from the design stage to the implementation one, allowing inter-changeability between simulated components and real-time physical systems. This approach is achieved by defining a simulation engine which involves a local simulator, an emulator and an interface to the physical process. Criteria are defined to use an emulator or a local control software for a physical process as a logical process for the conservative distributed simulation.     

On the fluidization of Petri nets and marking homothecy

The analysis of Discrete Event Dynamic Systems suffers from the well known state explosion problem. A classical technique to overcome it is to relax the behavior by partially removing the integrality constraints and thus to deal with hybrid or continuous systems. In the Petri nets framework, continuous net systems (technically hybrid systems) are the result of removing the integrality constraint in the firing of transitions. This relaxation may highly reduce the complexity of analysis techniques but may not preserve important properties of the original system. This paper deals with the basic operation of fluidization. More precisely, it aims at establishing conditions that a discrete system must satisfy so that a given property is preserved by the continuous relaxation. These conditions will be mainly based on the marking homothetic behavior of the system. The focus will be on logical properties as boundedness, B-fairness, deadlock-freeness, liveness and reversibility. Furthermore, testing homothetic monotonicity of some properties in the discrete systems is also studied, as well as techniques to improve the quality of the fluid relaxation by removing spurious solutions.     

SimHPN: A MATLAB toolbox for simulation, analysis and design with hybrid Petri nets

This paper presents a MATLAB embedded package for hybrid Petri nets called SimHPN. It offers a collection of tools devoted to simulation, analysis and synthesis of dynamical systems modeled by hybrid Petri nets. The package supports several server semantics for the firing of both, discrete and continuous, types of transitions. Besides providing different simulation options, SimHPN offers the possibility of computing steady state throughput bounds for continuous nets. For such a class of nets, optimal control and observability algorithms are also implemented. The package is fully integrated in MATLAB which allows the creation of powerful algebraic, statistical and graphical instruments that exploit the routines available in MATLAB.     

Analysis of strong and strong periodic detectability of bounded labeled Petri nets

Detectability describes the property of a system to uniquely determine, after a finite number of observations, the current and the subsequent states. Different notions of detectability have been proposed in the literature. In this paper, we formalize and analyze strong detectability and strong periodic detectability for systems that are modeled as labeled Petri nets with partial observation on their transitions. We provide three new approaches for the verification of such detectability properties using three different structures. The computational complexity of the proposed approaches is analyzed and the three methods are compared. The main feature of all the three approaches is that they do not require the calculation of the entire reachability space or the construction of an observer. As a result, they have lower computational complexity than other methods in the literature.     

Removing dead transitions in timed-arc Petri nets

Timed-arc Petri nets (TAPNs) are a timed extension of Petri nets where tokens are assigned an age indicating the time elapsed from its creation, and PT-arcs (place to transition arcs) are labelled with time intervals that are used to restrict the age of the tokens that can be used to fire the adjacent transition. This is a rather pathological model, as reachability is undecidable, whereas some other known properties of Petri nets, like boundedness, coverability and even termination, are decidable. This article focuses on the problem of detecting dead transitions, i.e. transitions that can be removed from the model since they can never become enabled. We prove that this problem is decidable for TAPNs with natural times, and we present an algorithm that can be used to find dead transitions in the particular case of 1-safe TAPNs.     

Quantitative analysis of continuous weighted marked graphs

This paper deals with the computation of the asymptotic firing rate vector and the stationary marking of continuous weighted marked graphs under infinite servers semantics. The continuous weighted marked graphs are a particular class of continuous Petri net where each place has exactly one input and one output transition. First, we give an explicit formula to compute the asymptotic firing rate vector of transitions using the structure of the given net. Then, under the assumption that there exists only one critical circuit in the strongly connected continuous neutral weighted marked graphs, an original approach to compute the vector of stationary marking is presented. Finally, an application to a flexible manufacturing system is given.     

Modeling,analysis and performance evaluation for fault diagnosis and Fault Tolerant Control in bottle-filling plant modeled using Hybrid Petri nets

In this paper, an approach to achieve fault diagnosis and Fault Tolerant Control in a typical bottle-filling plant using event based techniques is discussed. For this purpose, the plant is modeled using Hybrid Petri nets which enable study and analysis with regard to the working of the plant. Once effective modeling is done based on two different case studies considered, new algorithms are proposed to achieve fault diagnosis and Fault Tolerant Control on the models developed. Finally, performance measures with regard to the models proposed are evaluated to check the correctness of the models developed. Both analytical and numerical results are obtained which are highly useful to understand plant behavior.     

A new stochastic Petri net model and its applications to logistics systems

This is a summary of the author’s PhD thesis supervised by Lionel Amodeo and Hoaxun Chen and defended on 29 November 2005 at the Université de Technologie de Troyes (France). The thesis is written in French and is available from the author upon request. This work deals with a new stochastic Petri net model and its applications for modeling and studying logistics systems and more generally discrete event dynamic systems.      

Supervisory controller design to enforce some basic properties in timed-transition Petri nets using stretching

Supervisory controller design to enforce boundedness, reversibility, and liveness in timed-transition Petri nets with firing durations is considered. It is assumed that both controllable and uncontrollable transitions may be present and more than one transition may fire simultaneously. The approach of stretching is used to represent the state of the system. Algorithms are presented to design a supervisory controller using the forbidden states approach to enforce boundedness and reversibility simultaneously. The designed controller also guarantees T-liveness for the largest possible subset T of the set of transitions. In particular, boundedness, reversibility, and liveness are simultaneously enforced whenever it is possible. The designed controller is also the least restrictive controller which enforces boundedness and reversibility simultaneously.     

A Petri net approach to the modelling and analysis of flexible manufacturing systems

In this paper we present an approach for modelling and analyzing flexible manufacturing systems (FMSs) using Petri nets. In this approach, we first build a Petri net model (PNM) of the given FMS in a bottom-up fashion and then analyze important qualitative aspects of FMS behaviour such as existence/absence of deadlocks and buffer overflows. The basis for our approach is a theorem we state and prove for computing the invariants of the union of a finite number of Petri nets when the invariants of the individual nets are known. We illustrate our approach using two typical manufacturing systems: an automated transfer line and a simple FMS.A shorter version of this paper was presented at the 1st ORSA/TIMS Special Interest Conference on FMSs, University of Michigan, Ann Arbor, August 1984.     

A comprehensive approach of planning and scheduling based on petri nets

The main results available on the use of black-and-white Petri nets for modelling, planning and scheduling manufacturing systems are presented. In the first part of the paper, the basics of Petri nets necessary to understand the subsequent presentation are introduced. Particular attention is paid to event graphs, a particular type of Petri nets used for modelling and evaluating ratio-driven systems. The second part of the paper is devoted to ratio-driven systems, their modelling and their scheduling. Job-shops, assembly systems, and KANBAN systems are used to illustrate this section. Finally, the general case is investigated of manufacturing systems subject to changing demands. An approach based on conflict-free Petri nets with input and output transitions is proposed for planning and scheduling this type of system.     

Some open problems in the design and use of modern production systems

During the past two decades, manufacturing systems have moved towards automation, integration and modularity. These trends will certainly continue in the future due to the constraints of the market and to evolution of resources and worker requirements. As a consequence, the design and use of manufacturing systems are increasingly expensive. Numerous methods and tools have been developed to face up to this situation, but some complementary aids could be provided for designers and manufacturing engineers. The goal of this paper is to present important open problems whose solutions could certainly significantly improve the design and use of modern production systems.