Course syllabus
Discrete Event Systems
SSY165, 7.5 hp, Study Period 1, HT22
The course is offered by the Department of Electrical Engineering
Contact details
Examiner and lecturer
Bengt Lennartson, phone: 031-772 3722, bengt.lennartson@chalmers.se
Teaching assistants
Ludvig Svedlund, ludvige@chalmers.se
Alvin Combrink, combrink@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 Notes 2022, to be downloaded from Files.
Introduction to Discrete Event Systems - Exercises, Bengt Lennartson. Exercises 2007 - Revised 2018, to be downloaded from Files.
Lecture Program
| Lecture nr/ Book chapter | Date, Room | Contents |
|
L1, Ch. 1 |
Monday, Aug 29 |
Introduction. Discrete states and events, automata, typical models from different application areas, closed-loop systems. Synchronous composition, specification, verification, controller synthesis, implementation. |
|
L2, Ch. 2 |
Thursday, Sept 1 |
Discrete mathematics. Propositional logic, truth tables, tautological equivalences, and implications. Formal proofs. |
|
L3, Ch. 2 |
Monday, Sept 5 |
Discrete mathematics. Sets, operations on sets, set algebra. |
|
L4, Ch. 3 |
Thursday, Sept 8 |
Formal models. Automata, sets of states and events, transition relations, partial transition functions, traces, formal languages. |
|
L5, Ch. 3 |
Monday, Sept 12 |
Formal models. Synchronous composition and language intersection, Petri nets. |
|
L6, Ch. 4, 6 |
Thursday, Sept 15 |
Modeling & Specification. Verification. Specification of desired and non-desired behaviors, marked, forbidden, and reachable states. Controllable and uncontrollable events, verification of controllability. |
|
L7, Ch. 7 |
Monday, Sept 19 |
Controller synthesis. Plant, specification, supervisor synthesis. |
|
L8, Ch. 7 |
Thursday, Sept 22 |
Controller synthesis. Supervisor synthesis algorithm. |
|
L9. Ch. 8 |
Monday, Sept 26 |
Extended models. Extended finite automata, timed automata, hybrid automata. |
|
L10, Ch. 9 |
Thursday, Sept 29 |
Temporal logic. |
|
L11, Ch. 9 |
Monday, Oct 3 |
Temporal logic. mu-calculus. |
|
L12, Ch. 10 |
Thursday, Oct 6 |
Reinforcement learning. |
|
L13, Ch. 8 |
Monday, Oct 10 |
Extended models. Markov chains. Queuing theory, Markov decision processes. |
|
L14, Ch 11 |
Thursday, Oct 13 |
Model reduction. Abstraction by Bisimulation. |
|
L15 |
Monday, Oct 17 |
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.
| Date, Room | Exercises | |
|
pw 1 |
Thursday, Sept 1 |
Introduction 1.1 - 1.8 Discrete mathematics 2.1 - 2.3 |
|
pw 2 |
Thursday, Sept 8 |
Discrete mathematics 2.4 - 2.6 |
|
pw 3 |
Thursday, Sept 15 |
Modeling and specification 4.1 - 4.9 |
|
pw 4 |
Thursday, Sept 22 |
Verification 6.1 - 6.6 |
|
pw 5 |
Thursday, Sept 29 |
Controller synthesis 7.1 - 7.7 |
|
pw 6 |
Thursday, Oct 6 |
Temporal Logic |
|
pw 7 |
Thursday, Oct 13 |
Markov processes, Reinforcement Learning |
|
pw 8 |
Thursday, Oct 20 |
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, SB-M022.
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
No changes since last year.
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 October 22, am, and first re-sit examination date is January 5, am. Allowed aids at the examination: Standard mathematical tables such as Beta.
Course summary:
| Date | Details | Due |
|---|---|---|