Virtual Talk Series 2023

February 15 | 13:00 UTC

Talk 1: Probabilistic Hyperproperties of Markov Decision Processes: Information-Flow Properties and Beyond
Presenter: Rayna Dimitrova (CISPA Helmholtz Center for Information Security, Germany)
Talk 2: A Unified Framework for Verification of Observational Properties for Partially-Observed Discrete-Event Systems
Presenter: Xiang Yin (Shanghai Jiao Tong University, China)

For more information about the speakers and the talks please visit the workshop website: https://css-workshop-23.mpi-sws.org/talks/

April 20 | 13:00 UTC

Talk 1: Synthesis of Decentralised Supervisory Control via Contract Negotiation
Presenter: Ana Mainhardt (Max Planck Institute for Software Systems, Germany)
Abstract: In this talk, I will present a method for the synthesis of local supervisors for decentralised discrete event systems where subsystems may have different controllability settings for their shared events, and where the privacy of the local nonshared events plays a vital role. Our approach is based on the negotiation of contracts represented solely over these shared events and describing an agreement between the subsystems, such that they cooperate in disabling events in order to guarantee their local specifications are satisfied. We establish further conditions to ensure correct cooperation and global nonblockingness, which are locally checked and, if necessary, enforced. This way, both during synthesis and execution, the dynamics of a subsystem are only partially observed by others through the events they actually share, without the communication of exclusively local events or the use of a coordinator for their supervisors. We identify the cases where maximal permissiveness can be achieved by our approach; otherwise, it is sacrificed in order to protect privacy.

Talk 2: Max-plus algebra for scheduling and control of manufacturing systems with time-window constraints 
Presenter: Davide Zorzenon (Technische Universität Berlin, Germany)
Abstract: Time-window constraints show up in several industrial settings. Two examples are the baking and printed circuit boards industries, where both insufficient and excessive durations of some processes (e.g., yeast fermentation in the former case, metal deposition in the latter) can irreparably damage the final product. The presence of temporal upper-bound constraints makes the scheduling task in these systems particularly challenging as, counterintuitively, machines may be required to work at reduced pace to avoid constraint violations. The aim of this presentation is to discuss the application of max-plus algebraic methods for (open-loop) scheduling and (closed-loop) control of manufacturing systems with time-window constraints. I will first focus on the computation of two important performance indices: makespan and throughput. In the max-plus algebra, these quantities admit closed-form expressions, resulting in algorithms of lower computational complexity compared to standard techniques based on linear programming or graph theory. In the second part of the talk, I will address the following question: how to control the system such that no temporal constraint violations occur, despite the presence of unforeseeable delays? 

June 15 | 13:00 UTC

Abstract:

Max-plus algebra is suitable to model dynamical discrete event systems. The occurrence date of events is chosen as the state of the system. The state estimation consists in computing the occurrence date of internal events (hidden states) thanks to output measurements and previous states knowledge. The system is assumed to be uncertain, more precisely, its parameters are supposed to be random values belonging to an interval. The talk will compare the different ways to estimate the system state in this uncertain context by considering set-membership approach which can be based on interval analysis, difference bound matrices or max-plus polyhedra. It will be organized as follows : First, linear max-plus systems will be presented and the synthesis of an observer (inspired by the Luenberger observer) allowing an online estimation to be given, then its performance will be analyzed. Then, the scheme of a state filtering approach based on a prediction step and a correction step (inspired by Bayes filtering) will be introduced. Interval analysis will first be considered to implement this filtering, we will show that the set of states obtained contains the real states in a guaranteed way. It is obtained with polynomial complexity, but provides an over approximation of the states set. The difference bound matrices will be then introduced and used to obtain the reachable set (in which the prediction belongs) and the estimated set. This estimated set is the exact set in the sense that all the reachable set under the measurement constraints is depicted, but this filter is with an exponential complexity. The max-plus polyehdra is last considered, it will lead also to the exact set of possible states. It reduces the complexity especially in the prediction step. The tropical polyhedra library (TPL) will be used to implement this filter. The talk will conclude by providing examples to illustrate the results.

August 2023

No Event Scheduled

October 19 | 13:00 UTC

Abstract:

During this session, we will unveil powerful solutions for addressing the complex challenge of high-level path planning in multi-agent systems. Our approach leverages Linear Temporal Logic (LTL) formulas to define mission specifications for teams of agents, which are then seamlessly translated into Buchi automata, encompassing all possible solutions. Discover not one, but two distinct strategies. First, we'll explore a method that involves the computation of a string within the Buchi automaton, which the team model defined as a Petri net endeavors to generate. Secondly, we'll delve into the fusion of the team and specification models, culminating in the resolution of planning dilemmas on a larger scale. This talk will also feature a comprehensive comparison between these two innovative approaches and a third method grounded in transition systems.

December 2023

No Event Scheduled