IEEE CSS TC DES Tutorial Series 2021
The IEEE CSS TC DES is organizing a Virtual Lightning Tutorial Series on Discrete Event Systems throughout 2021 to enhance communications in our community during the current Covid-19 pandemic. In order to access past talks, you will need to register on the page below under "Registration."
Recordings and slides of past talks available here
Date & Time:
The tutorials take place virtually via Zoom on the 3rd Thursday of each month in 2021 (except August) at 13:00 UTC (Paris 14:00, New York City 8:00, Beijing 21:00). Please see the detailed schedule below.
Scope:
In order to include members of our community on all levels (ranging from PhD-students to post-docs, to junior and senior faculty members) we have decided on the format of “lightning tutorials”, followed by a virtual coffee break organized via break-out rooms randomly assigning 5-6 people to a room for more informal chatting. Lightning tutorials are rather short (≈ 40 minutes) and are intended to introduce a fundamental or emerging topic/sub-field of DES research to a broad audience. They can be thought of as an introduction to a review paper or a book chapter, introducing the particular topic/sub-field, why it is worth studying (either from a theoretical or a practical perspective), its main insights (what is known/what is unknown) and maybe a list of influential papers in this field.
Registration:
Registration is free. For security reasons we require pre-registration. Participants will receive log-in details to the virtual zoom meeting after registration.
Schedule:
*January 21 | 13:00 UTC
University of Cyprus, Cyprus
State Estimation And Event Inference In DES: Implications To Detectability, Diagnosability And Opacity
Abstract:
We discuss recursive algorithms for state estimation and event inference, both of which are key tasks for monitoring and control of discrete event systems. In particular, we discuss algorithms for current-, initial-, and delayed-state estimation. We also discuss implications to various pertinent properties of interest, such as detectability (i.e., the ability to determine the exact system state after a finite number of events), diagnosability (i.e., the ability to detect within finite time the occurrence/type of a fault), and opacity (i.e., the guarantee that outsiders will never be able to infer that the system state lies within a set of certain secret/critical states). The talk also briefly discusses the extension of state estimation and event inference methodologies in emerging decentralized/distributed observation settings.
*February 18 | 13:00 UTC
The University of Michigan, United States
Discreet Event Systems: Opacity and Its Enforcement
Abstract:
Opacity is an information-flow property used in privacy and security applications. A dynamic system is opaque if an external observer that knows the system model and makes online observations of its behavior is not able to detect with certainty some "secret" information about the system. We discuss various notions of opacity and their verification in the context of discrete event systems modeled by automata or transition systems: current-state opacity, initial-state opacity, and K-step opacity. Then we consider how to enforce opacity for systems that are not opaque. We focus on opacity enforcement using obfuscation when an external interface edits the outputs of the system in order to confuse the observer. We present solution methodologies for different variations of this problem. We conclude with illustrative examples of opacity in the context of location privacy in location-based services.
*March 18 | 13:00 UTC
The University of Michigan, United States
Abstractions: A Bridge Between Continuous Dynamics and Discrete Event Systems
Abstract:
In this talk, we will give an overview of finite abstractions, which are graph-based representations for continuous-state control systems. If these finite abstractions are constructed properly, they can be used to design controllers using techniques from discrete event systems or reactive synthesis in a way that the designed controller can be implemented on the underlying continuous control system (namely, the concrete system) and provide guarantees on the closed-loop behavior. In order to lead to a correct-by-construction design, the abstract system should satisfy a certain relation with the concrete system. We will introduce several such relations including, (bi)simulation relations, over-approximations, feedback refinement relations, and discuss what type of properties are preserved under these relations. Finally, we will discuss various ways of constructing these abstractions, e.g., based on gridding or partitioning the state space, for different classes of systems, e.g., discrete-time or continuous-time. Several examples will be used throughout to demonstrate these techniques in action. The talk will conclude with a summary of more recent results and a discussion on several research directions.
*April 22 | 13:00 UTC
Northeastern University, United States
Distributed Synthesis
Abstract:
I will give a brief tutorial of synthesis in a distributed setting, where the goal is to automatically synthesize, if they exist, a set of distributed observers or controllers which together achieve a specific goal. Rather than giving an exhaustive survey I will focus on specific aspects of the problem. In particular, my talk will be structured in two parts. In the first part I discuss theoretical aspects, specifically decidability and undecidability. In the second part I discuss distributed synthesis in practice, specifically, automatically synthesizing protocols such as the Alternating Bit Protocol using a combination of example scenarios and formal specifications as user inputs.
*May 20 | 13:00 UTC
Politecnico di Bari, Italy
A Survey on Petri Nets Models for Logistics and Transportation Systems
Abstract:
Logistics and transportation systems are man-made systems that are well suited for modeling in a discrete event system framework and particularly by Petri Nets (PNs), due to their different characteristics: distributed, parallel, deterministic, stochastic, discrete, and continuous. The paper presents a survey on the various Petri nets modeling frameworks proposed in the related literature for logistics and transportation systems, with applications to modeling, simulation, analysis, optimization and control. In particular, we focus on papers dealing with freight transportation and outline and classify the related works conducted using PNs as regards the proposed framework and addressed problems. We also debate the approach's viability, discussing contributions and limitations, and identify future research potentials.
*June 17 | 13:00 UTC
Hong Kong University of Science and Technology, China
From Perturbation Analysis of DEDS to a General Optimization Theory in the AI Era
Abstract:
Information systems have many special features such as large scale, big data, uncertainty, dynamic structure, and no mathematical models or unknown parameters. The traditional model-based analytical approach may not be suitable for the optimization of such systems. Learning-based approach must be used. “Learning” refers to the process of predicting the behavior of other related systems by analyzing a sample path of a given system. Perturbation analysis (PA) is one of the early development in this direction, which provides the performance derivatives based on a single sample path. Relative optimization can be viewed as an extension of PA from infinitesimal changes to finite ones. Its essential idea is comparing the performance measures under two different policies based on analyzing the system under one policy. The philosophy behind this approach, the main concepts and results, its difference with dynamic programming, and its relation with reinforcement learning, etc., are discussed. Examples show that this learning-based approach solves some long-standing issues in optimization and therefore pushes forward the development of optimization theory.
*July 22 | 13:00 UTC
University of Cagliari, Italy
Partially Observed Discrete Event Systems: from Estimation to Cyber-Security
Abstract:
In partially observed discrete event systems, an agent observing a plant has incomplete information concerning its evolution. The most basic problem in this setting is that of state estimation, which in the automatic control literature is usually solved by building a so-called “state observer”. Reconstructing the state of a partially observed discrete event system is a fundamental approach that can be tailored to solve a variety of related problems. In this talk, I will briefly address two issues. The first issue is the separation principle between controller and observer. Building on well-known results, I will present some conditions that allow a designer to optimally solve a supervisory control problem under partial observation -- for either state specifications or language specifications -- by separately designing a controller and a state observer. The second issue is the problem of state estimation under attack. I will present an approach, recently developed by my research group, that allows one to study how an intruder, capable of tampering with the observations generated by a plant, can deceive an agent monitoring it so that the agent’s estimate is marred.
*September 16 | 13:00 UTC
Chalmers University of Technology, Sweden
On Modular and Compositional Approaches to Compute Supervisors
Abstract:
The state-space explosion problem is a practical, not just theoretical, obstacle when verifying the correctness of or computing supervisors for discrete-event systems. Though it is known to be unavoidable in general, many approaches exist to mitigate it either by looking at special cases or by designing algorithms and/or data structures that work well in practice. This talk gives an overview of the modular and incremental, and compositional abstraction-based approaches, focusing on a practical context but also giving some theoretical depth. These approaches aim to exploit the modular structure of the problem formulation, that the plant and the specification are both made up of individual components, with the respective monolithic model given by the composition of these components; other than that, the approaches use no structural knowledge of the system. The modular/incremental approach computes a supervisor by carefully selecting appropriate components so as to avoid enumerating the entire global state-space. This works very well in practice. However, though the resulting modular supervisor, comprising one supervisor component for each specification component, is guaranteed to be controllable and maximally permissive with respect to the global plant and the given specification, it does not guarantee nonblocking. The compositional abstraction-based approach uses property-preserving abstractions to remove redundancy, and to incrementally compute a modular supervisor that, in addition to controllability and maximal permissiveness, does guarantee nonblocking. This approach has shown remarkable efficiency for many industrial problem formulations.
*October 21 | 13:00 UTC
University of Erlangen-Nuremberg, Germany
Supervisory Control of Non-Terminating Processes — a Concise Introduction
Abstract:
Supervisory Control Theory is a branch of control that addresses dynamic systems which take spontaneous transitions between a finite number of states. Since its introduction by P.J. Ramadge and W.M. Wonham in the late 1980s, this field of research has attracted a large variety of contributions, which discuss specific aspects of control, e.g., partial observation, modular/decentralised/hierarchical system architectures, fault diagnosis, fault tolerance, opacity and resilience. The vast majority of the literature utilises -languages (languages of finite-length words, typically realised by finite automata) as their base model to represent the plant, the control objective and the closed-loop behaviour. Although this setting is perfectly adequate for many conceivable applications, -languages fall short when it comes to more general liveness properties like e.g. eventuality. This is addressed by J.Thistle and W.M. Wonham in a study of the plain supervisory control problem but with omega-languages (languages of infinite-length words) as base model. In my presentation, I will recall the latter variant of supervisory control and highlight in which aspects it differs from the more common setting with * -languages.
*November 18 | 13:00 UTC
Joanna (Asia) van de Mortel – Fronczak
Eindhoven University of Technology, Netherlands
Synthesis-Based Engineering of Supervisory Controllers – From Specification to Implementation
Abstract:
In cyber-physical systems, safety and availability are of utmost importance. To satisfy requirements on safety and availability, suitable supervisory controllers need to be employed. Supervisory control theory provides a foundation on which a model-based engineering method has been developed, providing guarantees on the correctness of resulting supervisory controllers with respect to the defined requirements. In this lecture, an overview will be given of the recent research projects at Eindhoven University of Technology aiming at the development of extensions to this method, and of supporting tools, giving rise to an integrated approach to the design of supervisory controllers for complex real-life systems. This includes a mathematically underpinned, straightforward and error-free path to implementation of the designed controllers. The research projects are related to the partnership with Rijkswaterstaat which is a part of the Dutch Ministry of Infrastructure and Water Management.
*December 9 | 13:00 UTC
Boston University, United States
Event-Driven Control for Complex Problems in Network Systems
Abstract:
There is a growing trend to solve control and optimization problems for systems with time-driven or hybrid dynamics by replacing the classical time-driven control mechanisms with event-driven ones. The benefits of this approach include: reducing communication in networked systems; overcoming the complexity of dynamic optimization problems; and guaranteeing the satisfaction of hard safety constraints to overcome the myopic nature of time-driven sampling-based control (since these constraints may be violated within any given sampling interval). We will overview such event-driven control mechanisms and describe their use in two classes of problems. First, in complex dynamic optimization problems where event-driven receding horizon control bypasses the “curse of dimensionality”. An application to mobility-on-demand systems will be presented where a discrete event system is embedded into the inherently hybrid system that captures the assignment of vehicles to ride requests. Second, we will describe how an event-triggered control approach can be used in safety-critical multi-agent network systems with potentially unknown agent dynamics.