Discrete event and hybrid systems
March 21, March 27, May 23, June 6, June 20, July 17, 2007
Dep.of Electrical and Electronic Engineering
|[ Home ] [ Lecturers ] [ Program ] [ Abstract of talks ]|
Abstracts of talks
March 21, 2007
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.
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.
Starting with the crucial question of how to control a timed contPN system, an approach based on the idea of slowing down the firing flow of transitions is considered. Firstly, we abstract the constraints on the states and inputs and we try to understand the behavior of contPN and interpret classical results in the contPN case. In particular, the poles of the underlying linear systems are studied and an interesting finding is that the non-controllable ones are zero-valued. Considering then the constraints, the steady-state control is study trying to characterize the equilibrium states for a constant control action. For some particular net subclasses, unique solutions are algebraically obtained. A LPP is purposed to computes the optimal steady-state for a given control action.
May 23, 2007
Arjan van der Schaft, “Analysis and control of complementarity hybrid systems“
In recognition of the fact that many systems contain both continuous and discrete aspects, considerable study has been devoted to "hybrid systems". The formulation of equations of motion for hybrid systems in explicit form, including the event rules and the description of the continuous dynamics for every possible mode, is in many cases a formidable task, and there is a clear need for devices that enable the modeler to work in what might be called a "high-level language". A formalism that can be used for this purpose is the so-called complementarity formalism. The formalism is applicable to a broad class of physical hybrid systems, as well as to hybrid systems described by an underlying dynamics subject to piecewise-linear constraints.
This talk surveys some of the key notions in the complementarity modeling and analysis of hybrid systems. Furthermore, we describe the relation between complementarity systems and the framework of port-Hamiltonian systems, which turns out to be a happy marriage. The theory of port-Hamiltonian systems offers tools for control, in particular for stabilization, based on the identified Hamiltonian structure of the system. We discuss the potential of these techniques for control of complementarity port-Hamiltonian systems.
The design of an adaptive cruise controller (ACC) for a Smart car, which is a type of small car, is proposed as a benchmark set-up for several existing control methods based on model predictive control (MPC), developed for nonlinear and piecewise affine (PWA) systems and on a tuned proportional-integral (PI) action. Each of these methods has been already applied to specific case studies, different from method to method. We propose therefore the study of implementing and comparing them over a common benchmark, allowing to assess their main properties, characteristics and strong/weak points. The ACC aims to achieve the tracking of a leading vehicle and energy saving, within specific constraints, that model physical limitations, safety/comfort issues, environmental protection and mechanical stress of the vehicle. In simulation, a realistic model of the Smart, that involves gear box and engine nonlinearities, is considered. A description of the methods to be compared is presented, and the comparison keys, obtained under a given simulation scenario, are collected in a table. In particular, trades-off between complexity and accuracy of the solution, as well as computational aspects are highlighted.
Arjan van der Schaft, “Composition and bisimulation of hybrid systems”
A common theme
in the theory of concurrent processes and in systems and control theory is to
characterize systems which are 'externally equivalent'. The idea is that we only
want to distinguish between two systems if the distinction can be detected by an
external system interacting with these
In concurrent processes the crucial notion in this endeavor is the concept of bisimulation which expresses when a sub-process can be considered to be externally equivalent to another (hopefully simpler) process. On the other hand, classical notions in systems and control theory are state space equivalence of dynamical systems, and reduction of a dynamical system to an equivalent system with minimal state space dimension. These notions have been instrumental in e.g. linking input-output models to state space models, and in studying the properties of interconnected systems.
In this talk
we will show how the notion of bisimulation for concurrent processes can be
extended to continuous dynamical systems, and how the developed notion unifies
the concepts of state space equivalence and reduction. Furthermore we show how
by merging this notion with the standard notion of bisimulation for concurrent
one obtains a structural bisimulation notion for hybrid systems.
June 6, 2007
Carla Seatzu, “Optimal control of switched systems“
In this talk we focus on a particular class of hybrid systems, namely switched piecewise affine autonomous systems, and present an optimal control procedure whose objective is that of minimizing a quadratic performance index over an infinite time horizon. We first show how an optimal solution can be computed under the assumption that the switching sequence has a finite length, and the decision variables are the switching instants and the sequence of operating modes. Then, we generalize this approach to the case of an infinite number of admissible switches. The main advange of such a procedure, that is based on dynamic programming arguments, is that it identifies the regions of the state space where an optimal mode switch should occur, therefore providing a state feedback control law.
An application to the design of semiactive suspension system for vehicles is also presented.
Hybrid Control Systems (HCS) are usually referred to as control systems that involve both continuous and discrete dynamics as well as continuous and discrete controls. The controller in HCS not only supervises the dicrete transitions, but also controls the continuous behaviors, and in most cases these two functionalites need to be cooperated. Therefore, the controllability concept of HCS should reflect the influence of input signals on the evolution of continuous and disrecte states as well. This talk will focus on the following isses.
(1) What's the meaning of controllability in HCS?
(2) How to analyze this kind of system property?
First of all,
a unified approach for controllability analysis for a general class of HCS will
be presented. Then, an algebraic methods/criteria will be introduced for a class
of linear switching systems.
It is well known that in some cases hybrid systems can lead to the so called Zeno phenomenon, i.e., theoretically infinite frequency switching appears in the system behaviour. Such a behaviour can be considered as a mathematical modelling of a solution of a differential inclusion, which is common to appear in constrained mechanical systems. Since this behaviour has quite interesting properties of invariance and robustness, it can be useful to force, even artificially, infinite frequency switching in the control system; this is the usual working state of variable structure systems with sliding modes.
In this lecture the origin of “natural” and “artificial” sliding modes are described, ant their main characteristics and features are discussed by means of simple examples.
June 20, 2007
Andrea Paoli, “Supervisory control of discrete event systems”
The rapid evolution of computing, communication, and sensor technologies has brought about the proliferation of new dynamic systems, mostly technological and often highly complex. The activity in these systems is governed by operational rules designed by humans; their dynamics are therefore characterized by asynchronous occurrences of discrete events. These features lend themselves to the term discrete event system for this class of dynamic systems. This talk will introduce the audience to the area of discrete event systems modeled by automata, with specific focus on control issues: the main problem addressed will be “how to limit the evolution of a discrete event system to meet some specifications in presence of uncontrollable and unobservable events”.
Some necessary concepts from formal language theory will be introduced together with automata and their associated composition operations. In the second part of the talk, the theory of supervisory control of discrete event systems will be presented. Two fundamental discrete-event system-theoretic properties will be discussed: controllability and observability. These properties arise as necessary and sufficient conditions for the existence of discrete-event controllers for an important class of control specifications. Finally some theoretical results to deal with uncontrollable and unobservable specifications will be presented.
Stephane Lafortune, “Diagnosis of discrete event systems”
interested in the detection of ``significant'' events, such as faults, in
technological systems whose dynamics are modeled in the framework of discrete
event systems. In the first part of the talk, we will review the salient
features of a methodology for fault diagnosis of discrete event sytems termed
the ``Diagnoser Approach.'' This approach has been successfully used in several
domains, incuding document processing systems and intelligent transportation
systems. In the second part of the talk, we will present some recent extensions
of this methodology regarding
Stephane Lafortune, “Decentralized control of discrete event systems”
This talk will present a critical overview of key results on the control of partially-observed distributed discrete event systems. Both decentralized and distributed control architectures will be considered. In decentralized architectures, a set of local supervisors work jointly to enforce a global specification on the controlled behavior; these supervisors have different information structures and do not communicate in real-time. The state-of-the art in decentralized control will be reviewed with focus on the role of inference and on the curse of undecidability. In ``distributed" architectures, the supervisors are allowed to exchange information in real-time, leading to what are called networked systems. In several classes of networked systems, energy, bandwidth, and/or security often require to minimize communications among supervisors. The intricacies of the synthesis of minimum communication policies will be illustrated. Recent results on this topic will be presented.
July 17, 2007
Giorgio Bartolini, “Simplex sliding mode control method for nonlinear multiinput uncertain systems”
The methodology known as Sliding Modes Control consists in the implementation of motions artificially constrained to surfaces in the state space. The constraints are chosen such that the reduced order free motion(zero dynamics) is characterized by good properties in particular stability, precise tracking and insesitivity to disturbances. The attained zerodynamics can be suitable to be furtherly dealt with by other synthesis methods. The attainment of the constrained motion must be achieved in finite time despite of uncertainties, disturbances and exogenous disturbances. This problem requires the solution of differential inequalities which unavoidably leads to discontinuous control laws.
Considering multiinput nonlinear uncertain systems with vector-constraint equations a particular discontinuous control strategy,based on the properties of simplices of vectors, appears to be very promising. As the first step the constraint vector space is partioned in non overlapping regions with disjoint interiors constituted by the cones positively spanned by the vectors of the simplex except one at a time. At any cone it is associated a fixed vector of the simplex. The resulting variable stucture control system can be viewed also as a "switched control " or a "quantized control" system discontinuous on the boundaries of the cones and at the origin of the considered space. It has been proved, by Liapunov-like methods adapted to the theory of differential equation with discontinuous r.h.s., that any system belonging to a rather wide class can be forced to satisfy the chosen constraints in a finite time interval. This method will be further endowed with an antichattering procedure and used to deal with the control of systems in regular form non affine in the control law. Interesting application to the control of systems with monodirectional actuators will be also provided.
Arie Levant, “Homogeneous discontinuous control”
features of dynamic systems are found to provide for a number of general
practically important features. In particular, asymptotic stability implies
finite time convergence, if the system
uncertain single-input-single-output regulation problem is shown to be only
solvable by means of discontinuous control via the so-called high-order sliding
mode. The homogeneity approach allows to facilitate design and investigation of
new high-order sliding-mode controllers, featuring such attractive properties as
practical continuity of the control in the presence of noises. Robust
output-feedback controllers are produced, provided robust exact homogeneous
differentiators are used. The asymptotic accuracy of the controllers is shown
to be the best possible under given circumstances.
Leonid Fridman, "Higher Order Sliding Mode Observation and Identification"
A high-order sliding-mode observer is designed for time invariant systems with unknown bounded single input, providing for the global observation of the state and the output under sufficient and necessary conditions of strong observability or strong detectability. The observation is finite-time-convergent and exact in the strong observability case. The accuracy of the proposed observation and identification schemes is estimated via the sampling step or magnitude of deterministic noises.
The value of the equivalent output injection is used to identify perturbations directly. Continuous time versions of least square and forgetting factor methods are proposed to identify unknown time-invariant parameters respectively. The possible applications to the fault detection are considered. Applications to the robotics, vehicle parameter estimations, backlash identification are discussed.
Alessandro Pisano, “Second-order sliding modes in mechanical and electromechanical systems – Basic principles and implementation results”
This lecture is devoted to address some practical control problems involving mechanical and eletromechanical systems operating under uncertainty conditions. In particular, the effective application of second-order sliding mode control (2-SMC) techniques is demonstrated. The main theoretical tools involved will be introduced first, namely:
i. The "Dynamical 2-SMC", an approach providing superior robustness performance while avoiding discontinuities in the generalized control forces.
ii. The "Observer-based" and "Parallel-filter" 2-SMC, two approaches to deal with systems with high relative degree undergoing partial state-feedback.
iii. The "Frequency-shaped 2-SMC", a design tool which can effectively account for the presence of parasitic actuator dynamics.
Each topic will be discussed making reference to practical examples involving: hydrojet-actuated marine vessels, electrohydraulic "double stage" valves, robotic master/slave haptic interfaces, active pantographs for high-speed train transportation systems. Experimental results are given, and the most relevant implementation issues emerged in the experimental activities will be addressed in some detail.
|Download the PDF file of the program.|