Alster

Tutorial Module 1: Fluid & Hybrid Petri Nets

Manuel Silva & Cristian Mahulea, Universidad de Zaragoza

This tutorial module will present the fluidization of discrete event dynamic systems (DEDS), as a relaxation technique for dealing with the classical state explosion problem. This over-approximation is particularly interesting when dealing with DEDS provided with large populations, for which the state explosion problem becomes particularly acute. Heavily loaded or populated DEDS appear in many application domains as in manufacturing, traffic, logistics, bio-chemical or population systems.

Even if named as continuous or fluid, the obtained relaxed models are hybrid in a technical sense. Thus, techniques used for logical verification, performance evaluation or control studies in discrete, hybrid and continuous models can be adapted in some sense. As central modelling paradigm for concurrent and synchronized DEDS, Petri nets (PNs) will be considered in detail. Moreover, the possibilities for transferring concepts and techniques with others paradigms (queuing networks or process algebra, for example) are very important, so there is much space for synergy.

Being a relaxation of DEDS, the analysis and synthesis problems on fluid models are frequently much more tractable at the computational level. In some cases, problems become of polynomial time. Nevertheless, timed fluid PNs (particularly under so called infinite server semantics) are able to simulate Turing Machines (!), so great “expressive power” and “undecidabilities” appear also in the horizon.

Being an approximation, problems like the loss of some discrete properties by means of fluidization will be analyzed. Otherwise stated, not all PN models allows a “reasonable approximation” by fluidization (like not all ordinary differential equations, even provided with constant coefficients, allows a reasonable linearization, for example). Equally important, “non-monotonic behaviours” in untimed and timed models will be stressed, what raises the importance of control strategies. Observation problems deal with full marking reconstruction from the knowledge of the marking of a limited number of places. This can be done for a particular vector of transitions firing speeds, or for any (almost all) value of speeds, so called structural (generic) observability. Diagnosis in presence of faults is a related problem. Controllability is a property related to the capability of driving a system to any desirable (steady) state or state trajectory. After discussing observability and controllability issues, some remarks and possible directions for future research will be presented.

Among the aspects that distinguish the adopted approach are: the focus on the relationships between discrete and continuous PN models, both for untimed, i.e., fully non-deterministic abstractions, and timed versions; the use of structure theory of (discrete) PNs, algebraic and graph based concepts and results; and the bridge to Automatic Control Theory.

Content of the tutorial: Fluidization: a relaxation approach to study heavily loaded discrete event systems. Autonomous (untimed) and timed fluid models. Relations among discrete and fluid “views” of a DEDS. Limitation of the fluidization.. Improvement of fluid approximations: removing spurious solutions and stochastic fluid models. Structural analysis of fluid PN models. Observability and observers. Controllability and controllers. Application examples using SimHPN toolbox.

Important: participants are encouraged to bring their own laptop with MATLAB installed on it if they want to use the relevant tool and get a hands-on experience.

Recommended background reading for the audience:
Basic concepts and notation concerning (discrete) Petri Nets:
M. SILVA: “Introducing Petri nets”, chapter 1 in F. DICESARE, G. HARHALAKIS, J.M. PROTH, M. SILVA and F. VERNADAT, Practice of Petri Nets in Manufacturing, Chapman and Hall, London, 1993 (ISBN 0-412-41230-G), pp 1–62.
For continuous or fluid Petri Nets (our topic in this tutorial), the following reference provide a broad perspective, at the actual stage of knowledge:
M. SILVA, J. JÚLVEZ, C. MAHULEA and C. R. VÁZQUEZ, “On fluidization of discrete event models: observation and control of continuous Petri nets”, Journal on Discrete Event Dynamic Systems, 21(4): 427–497, 2011 (DOI 10.1007/s10626-011- 0116-9).
Of a more introductory level and complementary, it may also be of interest:
M. SILVA, L. RECALDE: “On fluidification of Petri Nets: from discrete to hybrid and continuous models”, Annual Reviews in Control (28): 253-266, 2004. M. SILVA, L. RECALDE: “Petri Nets and Integrality Relaxations: A view of Continuous Petri Net Models”. IEEE Transactions on Systems, Man and Cybernetics. 32 (4): 314- 327, 2002.

<< back

Page last modified: 2012/06/05