Tutorial in honor to Prof. Laura Recalde
Continuous Petri Nets:
Expressivity, Analysis and Control of a class of Hybrid Systems
Prof. Alessandro Giua, Universitá de Cagliari, Italy
Prof. Serge Haddad, ENS Cachan, Paris, France
Prof. Manuel Silva, Universidad de Zaragoza, Spain
Abstract
Petri nets constitute one of the more important formal paradigms for modeling and analysis of discrete event systems. The classical state explosion problem for enumerative analysis and synthesis techniques is one of the reasons leading to the so called Continuous and Hybrid Petri nets, obtained by means of a simple relaxation rule
The purpose of this tutorial is to provide an overview of the theory and techniques developed in the last years, really at the intersection of Computer Science, Operations Research and Automatic Control.
Once the basic formalism is presented, expressivity issues will be considered. On one side, it should be pointed out that some NP-co problems become polynomial time complexity in the continuous framework, but undecidability also remains for other that can be considered as basic (even for continuous net systems). Obviously, the cost eventually paid by the relaxation is on the fidelity of the simplified models. For some net classes relaxation is not a problem, but for others, even basic logical properties are lost (an analogous fact: not every non-linear differential equation can be “reasonably” linearized). Nevertheless, for engineering models (like in production systems: manufacturing, logistic, transport…) relaxations are usually well behaved and computational benefits very important.
After introducing the relaxation rule leading to the continuous formalisms, the study of some qualitative and quantitative properties (for example, performance evaluation, both in transient and steady-sate, if exist) will be considered. As pointed out, decidability remains a problem in important cases, for example, under infinite server's semantics.
It is well-known the existence of hierarchies that discriminate between the computational power of discrete time and space dynamical systems. Contrary the situation is more confused for dynamical systems when time and space are continuous. A possible way to discriminate between these models is to state whether they can simulate a Turing machine. For instance, it is known that continuous systems described by an ordinary differential equation (ODE) have this power. However, since the involved ODE is defined by overlapping local ODEs inside an infinite number of regions, this result has no significant application for differentiable models whose ODE is defined by an explicit representation. In this talk, we considerably strengthen this result by showing that Time Differentiable Petri Nets (TDPN) can simulate Turing machines. Indeed the ODE ruling this model is expressed by an explicit linear expression enlarged with the “minimum” operator. More precisely, we present two simulations of a two counter machine by a TDPN in order to fulfill opposite requirements: robustness and boundedness. These simulations are performed by nets whose dimension of associated ODEs is constant. Then, we prove that marking coverability, submarking reachability and the existence of a steady-state are undecidable for TDPNs. Last we show that TDPNs and Time Continuous Petri Nets under infinite server's semantics are computationally equivalent with linear time translations.
In a second part of the tutorial, the computation of steady-states (if exist), and algebraic/algorithmic criteria for observability and controllability of those models will be presented, before dealing with fault diagnosis and supervisory control.
Technically speaking, continuous Petri net systems are hybrid. At the end, the proposed tutorial a window will be open to hybrid net systems, were the marking of some places are not relaxed into de non-negative reals.
The expected audience is people interested in Petri net theory and applications. The appealing point is the new tradeoff between fidelity and analizability of those kinds of relaxed models
Structure
- From 14h00 to 14h45 / Manuel Silva: Fluidification and basic properties of continuous Petri net models
- From 14h45 to 15h30 / Serge Haddad: On the computational power of Timed Differentiable Petri nets
- From 16h00 to 16h4 / Manuel Silva: Observability, Steady-state analysis and parametric optimisation of Continuous PNs under infinite servers' semantics
- From 16h45 to 17h30 / Alessandro Giua: Fault diagnosis and Control of Continuous PNs under infinite servers' semantics