PhD Course
on
Discrete event and hybrid systems
Discrete event systems
Discrete event systems (DES) theory is the theoretical foundation to the study of dynamical man-made systems, whose evolution is related to the occurrence of asyncronous events, usually not numerical. The most relevant application domains are: manufacturing, process control, supervisory systems, software engineering, transportation and so on. As a result of the combinatoric nature of the analysis, optimization and control problems of DES, the theory of DES has developed slowly with respect to the theory of time-driven systems. During the last fifteen years, to address the requirements from industry of formal methods for the study of DES, the international scientific community has devoted a great effort in this respect, and several important results have been obtained. In particular, solid theoretical foundations have been given within the framework of supervisory control, state observation and fault diagnosis.
Hybrid Systems
Recent technological innovations have caused an ever increasing interest in the study of hybrid systems (HS). The peculiarity of hybrid systems is the interaction between continuous-time dynamics (governed by differential or difference equations), and discrete dynamics and logic rules (described by temporal logic, finite state machines, if-then-else conditions, discrete events, autonomous or forced switching, etc.). The research domain of HS is attracting an ever increasing number of researches. However, several important problems are still open in this framework, such as optimal control and analysis of many relevant properties, such as stability and Zeno phenomena. In particular, the latter is strictly related to the sliding mode theory, and many of its relevant results can be used or extended.
Objectives of the course
The main objective of this course is that of collecting together researches from several universities, working within the framework of discrete and hybrid systems, so as to provide an outline of the main theoretical and application results in these areas. All lectures will be taken at a quite didactic level, so that also PhD students not working in these topics, will be able to understand the proposed results.
Dates and location
All lectures will take place at the
University of Cagliari,
Faculty of Engineering,
Piazza D’Armi,
Cagliari, Italy
in the following dates: March 21, March 27, May 22, June 7, June 20, July 17, 2007.
URL: http://www.diee.unica.it/~seatzu/home_PhD_course.html
Organizers: Carla Seatzu, Elio Usai
Dep. of Electrical and Electronic Engineering
University of Cagliari, Italy
Email: ,
Lecturers
§ Giorgio Bartolini
Dip. Ingegneria Elettrica ed Elettronica, Università di Cagliari, Italy;
Email:
URL: http://www.diee.unica.it/~giob/infoit.html
§ Francesco Basile
Dip. Ingegneria dell’Informazione e Ingegneria Elettrica, Università di Salerno, Italy;
Email:
URL: http://www.diiie.unisa.it/aree/automatica/persone/docenti/fb/fb.htm
§ Maria Paola Cabasino
Dip. Ingegneria Elettrica ed Elettronica, Università di Cagliari, Italy;
Email:
§ Daniele Corona
Delft Center System and Control, Technische Universiteit, Delft, The Netherlands;
Email:
URL: http://www.dcsc.tudelft.nl/~dcorona/
§ Leonid Fridman
Dep. of Control, Div. of Electrical Engineering, Faculdad de Ingegneria, Mexico;
Email:
URL: http://verona.fi-p.unam.mx/~lfridman/
§ Alessandro Giua
Dip. Ingegneria Elettrica ed Elettronica, Università di Cagliari, Italy;
Email:
URL: http://www.diee.unica.it/~giua/infoit.html
§ Christoforos N. Hadjicostis
Dep. of Electrical and Computer Engineering, University of Illinois, Urbana-Champaign, USA;
Email:
URL: http://decision.csl.uiuc.edu/~chadjic/
§ Stéphane Lafortune
Dep. of Electrical Engineering and Computer Science, University of Michigan, Ann-Arbor, USA;
Email:
URL: http://www.eecs.umich.edu/~stephane/
§ Arie Levant
Applied Mathematics Dept., School of Mathematical Sciences, Tel-Aviv University, Israel;
Email:
URL: http://www.tau.ac.il/~levant/
§ Cristian Mahulea
Dep.to Informática e Ingeneiría de Sistemas, Centro Politécnico Superior, Zaragoza, Spain;
Email:
URL: http://webdiis.unizar.es/~cmahulea/
§ Andrea Paoli
Center for research on Complex Automated SYstems (CASY),
Dip. Ingegneria Elettronica, Informatica e Sistemistica, Università di Bologna, Italy;
Email:
URL: http://www-lar.deis.unibo.it/people/apaoli/
§ Giovanni Michele Pinna
Dip. Informatica e Matematica, Università di Cagliari, Italy;
Email:
§ Alessandro Pisano
Dip. Ingegneria Elettrica ed Elettronica, Università di Cagliari, Italy;
Email:
URL: http://www.diee.unica.it/~pisano/infoit.html
§ Carla Seatzu
Dip. Ingegneria Elettrica ed Elettronica, Università di Cagliari, Italy;
Email:
URL: http://www.diee.unica.it/~seatzu/info.html
§ Elio Usai
Dep. of Electrical and Electronic Engineering, University of Cagliari, Italy;
Email:
URL: http://www.diee.unica.it/~eusai/infoit.htm
§ Arjan van der Schaft
Department of Mathematics and Computing Science, University of Groningen, The Netherlands;
Email:
URL: http://wwwhome.math.utwente.nl/~schaftaj/
§ Zhenyu Yang
Dep. of Software and Media Technology, Esbjerg Technical Inst., Aalborg University, Denmark;
Email:
URL: http://www.aaue.dk/adm/dk/personale/yang.html
Detailed Program
March 21, 2007
9.00 – 11.00sala riunioni DIEE (Pad B) / A. Giua / Observers for Petri nets
11.30 – 13.30
sala riunioni DIEE (Pad B) / G.M. Pinna / The theory of regions and the synthesis of nets from computations
15.30 – 17.00
aula B biennio / F. Basile / Supervisory control of Petri nets based on monitor places
March 27, 2007
9.00 – 11.00sala riunioni DIEE (Pad B) / M.P. Cabasino / Identification of place/transition nets
11.30 – 13.30
sala riunioni DIEE (Pad B) / C. Hadjicostis / Coding approaches to reliable descrete event systems design
15.30 – 17.30
sala riunioni DIEE (Pad B) / C. Mahulea / On control of continuous Petri nets
May 23, 2007
9.00 – 11.00sala riunioni DIEE (Pad B) / A. van der Schaft / Analysis and control of complementarity hybrid systems
11.30 – 13.30
sala riunioni DIEE (Pad B) / D. Corona / Adaptive cruise controller for a Smart car: A comparison benchmark for MPC-PWA control methods
15.30 – 17.30
aula β / A. van der Schaft / Composition and bisimulation of hybrid systems
June 6, 2007
9.00 – 11.00sala riunioni DIEE (Pad B) / C. Seatzu / Optimal control of switched systems
11.30 – 13.30
sala riunioni DIEE (Pad B) / Z. Yang / On the controllability and fault tolerance of hybrid dynamical systems
15.30 – 17.30
sala riunioni DIEE (Pad B) / E. Usai / Zeno phenomena in hybrid systems and sliding mode behaviours
June 20, 2007
9.00 – 11.00sala riunioni DIEE (Pad B) / A. Paoli / Supervisory control of discrete event systems
11.30 – 13.30
sala riunioni DIEE (Pad B) / S. Lafortune / Diagnosis of discrete event systems
15.30 – 17.30
sala riunioni DIEE (Pad B) / S. Lafortune / Decentralized control of discrete event systems
July 17, 2007
9.00 – 11.00sala riunioni DIEE (Pad B) / G. Bartolini / Simplex sliding mode control method for nonlinear multiinput uncertain systems
11.30 – 13.30
sala riunioni DIEE (Pad B) / A. Levant / Homogeneous discontinuous control
15.30 – 17.30
sala riunioni DIEE (Pad B) / L. Fridman / Higher order sliding mode observation and identification
18.00 – 20.00
sala riunioni DIEE (Pad B) / A. Pisano / Second-order sliding modes in mechanical and electromechanical systems – Basic principles and implementation results
Abstracts of talks
March 21, 2007
Alessandro Giua, “Observers for Petri nets”
State estimation is a fundamental issue in systems theory. Reconstructing the state of a system from available measurements may be considered as a self-standing problem, or it can be seen as a pre-requisite for solving a problem of different nature, such as stabilization, state-feedback control, diagnosis, filtering, and others. Despite the fact that the notions of state estimation, observability and observer are well understood in time-driven systems, in the area of discrete event systems there are relatively few works addressing these topics and several problems are still open. In this talk I will present two approaches to observer design for Petri net models.
In the first approach, inspired by systems theory, the initial marking (i.e., the initial state) is assumed unknown, while the firing of all transitions can be completely observed. The purpose of the observer is that or reconstructing the initial marking, from which the current one can be uniquely determined given the observed sequence of transition firings.
In the second approach, inspired by the notion of nondeterministic automata typical of computer science, the initial marking is known. However, as the net evolves, the current marking is usually unknown due partial observation: some transitions firings may generate no observable event, or two different transition firings may generate the same observable event. The purpose of the observer is that or keeping track of all possible markings that may have been reached from the initial one with a sequence of firings consistent with the observed behavior.
G. Michele Pinna, “The theory of regions and the synthesis of nets from computations”
In this talk I will review various approaches to the net synthesis based on the notion of regions, introduced by Ehrenfeucht and Rozenberg. The net synthesis problem can be described as follows: from a suitable representation of nets computations is it possible to figure out which system, represented as a Petri net, has actually produced such computations? The first attempt can be traced back to the notion of non sequential process of Petri nets, where a suitable labeling was defined on a representation of computation based on partial orders enriched with informations on the resources used. The notion of resource is quite crucial in Petri nets: elementary nets or condition/events nets identify resources with the holding of certain conditions, whereas other Petri nets models such as place/transition nets allow for multisets of resources. Petri nets computations are in fact driven by the available resources, but these resources are usually abstracted from the computations. In general computations are represented in a much more abstract way, where the notion of resource is hidden, e. g. in the case of Petri Nets transition systems, causal trees, marking graphs or suitable automata (e.g. concurrent, step, higher dimensional or event automata). In these more abstract representations of computations resources can be fruitfully identified with the notion of region. After introducing the notion of regions, I will review various approaches to the synthesis and various categorizations of computations in the light of this notion. I will show also possible generalizations and applications to other fields like Business Process Management. Some ideas about an incremental calculus of regions will be also presented.
Francesco Basile, “Supervisory control of Petri nets based on monitor places”
This talk deals with the problem of enforcing generalized mutual exclusion constraints (GMEC) on place/transition nets with uncontrollable transitions.
First some literature methods that address this problem or are related to it are briefly recalled. Then, an efficient control synthesis technique which enforces GMEC constraints by introducing monitor places to create suitable place invariants is presented in detail.
The method has been shown to be maximally permissive and to give a unique control structure in the case that the set of legal markings is controllable. This is not true for uncontrollable specifications, but the class of monitor places enforcing an uncontrollable specification can be parameterized with respect to the solution of a linear system of equations. This can help to solve the problem to choose the best monitor based solution for a given GMEC according to a suboptimal criterion. If the classical partition of the event set into controllable and uncontrollable events from supervisory control theory is replaced by associating a control and observation cost to each event the supervisory control problem can be formulated as an optimal control problem. Monitor places which enforce the constraint are devised as a solution of an integer linear programming problem whose objective function is expressed in terms of the introduced costs.
March 27, 2007
Maria Paola Cabasino, “Identification of place/transition nets”
In this talk we examine the problem of identifying a Petri net system, given a finite language that it generates. Firstly we consider the problem of identifying a free labeled Petri net system, namely 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 show how this approach can be extended in several ways introducing additional information about the model (structural constraints, conservative components, stationary sequences) or about its initial marking. Furthermore, 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. Finally, we show how given an automaton that represents the coverability graph of a net we are able to solve the problem of determining a net system whose coverability graph is isomorph to the automaton. Our approach requires solving an integer programming problem whose set of unknowns contains the elements of the pre and post incidence matrices and the initial marking of the net.
Christoforos Hadjicostis, “Coding approaches to reliable descrete event systems design”
Fault tolerance has been a long standing necessity in system design and operation. In systems with memory (i.e., state), however, modular redundancy and other traditional approaches to fault tolerance are undesirable not only because they are expensive but also because they rely heavily on the assumption that the error-correcting (e.g. voting) mechanism is fault-free. This talk presents a general framework that systematically addresses these issues in fault-tolerant discrete-event dynamic systems. By replacing the original system with a coded, redundant implementation that retains the original functionality and state, we are able to exploit violations on the state encoding of this redundant implementation and develop error detection, correction and/or reconfiguration techniques. Unlike traditional methodologies that rely on concurrent checking at the end of each event epoch, our approach allows the construction of redundant systems in which detection and identification of errors is based on non-concurrent checks. Thus, the checker of the resulting design can operate at a slower speed than the rest of the system, which relaxes the stringent requirements on its reliability. We demonstrate this approach in the context of linear dynamic systems and finite automata.
Cristian Mahulea, “On control of continuous Petri nets”
Continuous Petri nets (contPN) were introduced as an approximation to deal with the state explosion problem which can appear in discrete event models. When time is introduced, the flow through a fluidified transition can be defined in many ways, the most used in literature are constant and variable speed, which can be seen as some kind of finite and infinite server interpretations of the transitions behaviour. The first point of the talk is to introduce these two semantics, explain some important properties and show that piecewise behaviours are obtained for both semantics. Then, it is proved that for a broad class of nets, timed PN under infinite server semantics is a more accurate approximation of the discrete nets.