Course syllabus
Discrete Event Systems
SSY165, 7.5 hp, Study Period 1, HT21
The course is offered by the Department of Electrical Engineering
Contact details
If you need to contact us, please consider to:
- use the discussion forum for general questions relevant to all students, both related to the lectures, exercises, and assignments;
- ask your questions during Zoom lectures or exercise sessions;
- join the TAs on Zoom during consultation hours;
- send an email (please write ***SSY165*** in the subject when you do);
in descending preferential order.
Examiner and lecturer
Bengt Lennartson, phone: 031-772 3722, bengt.lennartson@chalmers.se
Teaching assistants
Constantin Cronrath, cronrath@chalmers.se
Ludvig Svedlund, ludvige@chalmers.se
Office Hours: Tuesdays and Fridays, 12:30 - 13:15, online (see Zoom Links)
Exam Office
Room EDIT 3342, studadm.e2@chalmers.se
Course purpose
The course aims to give fundamental knowledge and skills in the area of discrete event systems and especially modeling and specification formalisms, simulation, synthesis, optimization, and control function implementation. Typical applications are control functions for embedded systems, control of automated production systems, and communication systems.
Schedule
Course literature
Introduction to Discrete Event Systems, Bengt Lennartson. Lecture Note 2009, to be downloaded from Files.
Introduction to Discrete Event Systems - Exercises, Bengt Lennartson. Exercises 2007 - Revised 2018, to be downloaded from Files.
Lecture Program
All lectures are held at Chalmers (50% of seats are available, first come first served)
and online via Zoom: Zoom Links
A preliminary schedule for the lectures
| Period Week/ Book chapter | Date, Room | Contents |
|
pw 1, Ch. 1 |
Monday, Aug 30 |
Introduction. Discrete states and events, automata, typical models from different application areas, closed-loop systems. Synchronous composition, specification, verification, controller synthesis, implementation. |
|
pw 1, Ch. 2 |
Thursday, Sept 2 |
Discrete mathematics. Propositional logic, truth tables, tautological equivalences, and implications. Formal proofs. |
|
pw 2, Ch. 2 |
Monday, Sept 6 |
Discrete mathematics. Sets, operations on sets, set algebra. |
|
pw 2, Ch. 3 |
Thursday, Sept 9 |
Formal models. Automata, sets of states and events, transition relations, partial transition functions, traces, formal languages. |
|
pw 3, Ch. 3 |
Monday, Sept 13 |
Formal models. Synchronous composition and language intersection, Petri nets. Introduction of the first home assignment. |
|
pw 3, Ch. 4, 6 |
Thursday, Sept 16 |
Modeling & Specification. Verification. Specification of desired and non-desired behaviors, marked, forbidden, and reachable states. Controllable and uncontrollable events, verification of controllability. |
|
pw 4, Ch. 7 |
Monday, Sept 20 |
Controller synthesis. Plant, specification, supervisor synthesis, supervisor, or controller implementation. |
|
pw 4, Ch. 8 |
Thursday, Sept 23 |
Extended models. Extended finite automata, timed automata, hybrid automata. |
|
pw 5. Ch. 9 |
Monday, Sept 27 |
Temporal logic. |
|
pw 5, Ch. 9 |
Thursday, Sept 30 |
Temporal logic. |
|
pw 6, Ch. 9 |
Monday, Oct 4 |
Temporal logic planning. |
|
pw 6, Ch. 8 |
Thursday, Oct 7 |
Extended models. Markov chains. |
|
pw 7, Ch. 8 |
Monday, Oct 11 |
Extended models. Queuing theory, Markov decision processes. |
|
pw 7, Ch. 10 |
Thursday, Oct 14 |
Reinforcement learning. Short introduction. |
|
pw 8 |
Monday, Oct 18 |
Summary. Comments on the written examination. |
Exercises
The student is expected to spend a significant amount of time besides these classes to solve all the problems. Solutions to the exercises are distributed to give additional support.
All Exercises are held at Chalmers (50% of seats are available, first come first served)
and online via Zoom: Zoom Links
A preliminary schedule for the exercise sessions
| Period Week | Date, Room | Exercises |
|
pw 1 |
Thursday, Sept 2 |
Introduction 1.1 - 1.8 Discrete mathematics 2.1 - 2.3 |
|
pw 2 |
Thursday, Sept 9 |
Discrete mathematics 2.4 - 2.6 |
|
pw 3 |
Thursday, Sept 16 |
Modeling and specification 4.1 - 4.9 |
|
pw 4 |
Thursday, Sept 23 |
Verification 6.1 - 6.6 |
|
pw 5 |
Thursday, Sept 30 |
Controller synthesis 7.1 - 7.7 |
|
pw 6 |
Thursday, Oct 7 |
Temporal Logic, Markov processes, Reinforcement Learning |
|
pw 7 |
Thursday, Oct 14 |
Exam October 2020 |
|
pw 8 |
Thursday, Oct 21 |
Questions and preparations for the exam |
Exercise self-activity and support for home assignments
From period week two, a self-activity and support session for exercises and home assignments is offered on Wednesday, 8-10 via Zoom (see Zoom Links).
Home assignments
Three mandatory home assignments, and one optional introductory assignment, are included in the course. These activities are performed in two-member groups. We strongly recommend completing the introductory assignment as preparation for the mandatory ones.
Changes made since the last occasion
Changes made for HT21:
Lecture and exercise sessions are given in lecture hall, but also via zoom. Seat restriction is applied where only half of the seats are allowed to be used. Use every second seat, and first come first served.
Learning objectives and syllabus
After completion of this course, the student should be able to:
- Use basic discrete mathematics in order to be able to analyze discrete event systems.
- Give an account of different formalisms for modeling discrete event systems, especially finite state automata, formal languages, Petri nets, extended finite state automata, timed and hybrid automata, and demonstrate skills to choose between them.
- Present different kinds of specifications, such as progress and safety specifications, defining what a system should and should not do.
- Compute and analyze different properties of discrete event systems such as reachability, coreachability, and controllability.
- Explain the meaning of supervisor synthesis, verification, and simulation.
- Use computer tools in order to perform synthesis and optimization of control functions based on given system models and specifications of desired behavior for the total closed-loop system.
- Formulate and analyze hybrid systems including discrete and continuous dynamics.
- Specify temporal logic properties and verify them by mu-calculus.
- Explain and apply basic Markov processes and queuing theory for performance analysis of systems including uncertainties.
- Apply reinforcement learning based on the dynamic programming principle.
Link to the syllabus on Studieportalen: Study plan
Examination form
Final grade requires an approved written examination and three approved home assignments (assignments 1, 2, and 3).
Regular examination date is Saturday 23/10-2021, am, and first re-sit examination date is Tuesday 4/1-2022, am.
Allowed aids at the examination: Standard mathematical tables such as Beta.
Course summary:
| Date | Details | Due |
|---|---|---|