Course syllabus

Discrete Event Systems

SSY165, 7.5 hp, Study Period 1, HT20

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
Fredrik Hagebring, fredrik.hagebring@chalmers.se

Office Hours: Tuesdays and Fridays, 12:30 - 13:15, online (see Zoom Links)

Study Office

Room EDIT 3342, phone 031-772 3720, madelein@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

TimeEdit

 

Course literature

Introduction to Discrete Event Systems, Bengt Lennartson. Lecture Note 2009, to be downloaded from Modules.

Introduction to Discrete Event Systems - Exercises, Bengt Lennartson. Exercises 2007 - Revised 2018, to be downloaded from Modules.

 

Lecture Program

A preliminary schedule for the lectures. All lectures are held online (see Zoom Links).

Period Week/ Book chapter	Date, Room	Contents
pw 1, Ch. 1	Monday, Aug 31 13-16, Zoom	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 3 8-10, Zoom	Discrete mathematics. Propositional logic, truth tables, tautological equivalences, and implications. Formal proofs.
pw 2, Ch. 2	Monday, Sept 7 13-16, Zoom	Discrete mathematics. Sets, operations on sets, set algebra.
pw 2, Ch. 3	Thursday, Sept 10 8-10, Zoom	Formal models. Automata, sets of states and events, transition relations, partial transition functions, traces, formal languages.
pw 3, Ch. 3	Monday, Sept 14 13-16, Zoom	Formal models. Synchronous composition and language intersection, Petri nets. Introduction of the first home assignment.
pw 3,  Ch. 4, 6	Thursday, Sept 17 8-10, Zoom	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 21 13-16, Zoom	Controller synthesis. Plant, specification, supervisor synthesis, supervisor, or controller implementation.
pw 4, Ch. 8	Thursday, Sept 24 8-10, Zoom	Extended models. Extended finite automata, timed automata, hybrid automata.
pw 5. Ch. 9	Monday, Sept 28 13-16, Zoom	Temporal logic.
pw 5, Ch. 9	Thursday, Oct 1 8-10, Zoom	Temporal logic.
pw 6, Ch. 9	Monday, Oct 5 13-16, Zoom	Temporal logic planning.
pw 6, Ch. 8	Thursday, Oct 8 8-10, Zoom	Extended models. Markov chains.
pw 7, Ch. 8	Monday, Oct 12 13-16, Zoom	Extended models. Queuing theory, Markov decision processes.
pw 7, Ch. 10	Thursday, Oct 15 8-10, Zoom	Reinforcement learning. Short introduction.
pw 8	Monday, Oct 19 13-16, Zoom	Summary. Comments on the written examination.

 

Special Meeting for International Students

All international students are invited to a special meeting in room HC4 every Monday 16:15-17:00 for questions and discussions.

 

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 online via Zoom: Zoom Links

A preliminary schedule for the exercise sessions

Period Week	Date, Room	Exercises
pw 1	Thursday, Sept 3 10-12, Zoom	Introduction 1.1 - 1.8 Discrete mathematics 2.1 - 2.3
pw 2	Thursday, Sept 10 10-12, Zoom	Discrete mathematics 2.4 - 2.6 Formal models 3.1 - 3.5
pw 3	Thursday, Sept 17 10-12, Zoom	Modeling and specification 4.1 - 4.9
pw 4	Thursday, Sept 24 10-12, Zoom	Verification 6.1 - 6.6
pw 5	Thursday, Oct 1 10-12, Zoom	Controller synthesis 7.1 - 7.7
pw 6	Thursday, Oct 8 10-12, Zoom	Temporal Logic, Markov processes, Reinforcement Learning
pw 7	Thursday, Oct 15 10-12, Zoom	Exam October 2019
pw 8	Thursday, Oct 22 10-12, Zoom	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.

Home assignment	Distribution by Canvas on Monday	Submission latest on Friday	Returned on Friday	Re-submission latest on Friday
Assignment 0	Aug 31 (pw 1)	Sept 11 (pw 2)	Sept 18 (pw 3)	Sept 25 (pw 4)
Assignment 1	Sept 14 (pw 3)	Sept 25 (pw 4)	Oct 2 (pw 5)	Oct 9 (pw 6)
Assignment 2	Sept 28 (pw 5)	Oct 9 (pw 6)	Oct 16 (pw 7)	Oct 23 (pw 8)
Assignment 3	Oct 5 (pw 6)	Oct 16 (pw 7)	Oct 23 (pw 8)	Oct 30 (pw 9)

 

Changes made since the last occasion

Changes made for HT20:

• Updated assignment 3 - Temporal Logic and Reinforcement Learning

Changes made for HT19:

• Added assignment 0 - Getting Started with Python for DES
• Added assignment 3 - Model Checking with Temporal Logic

Changes made for HT18:

• Revised exercise material
• Changed programming language of assignments from MATLAB to Python

 

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.
• Give an account for 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.
• Explain and apply basic Markov processes and queuing theory for performance analysis of systems including uncertainties.

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 24/10-2020, am, and first re-sit examination date is Tuesday 5/1-2021, am.

Allowed aids at the examination: Standard mathematical tables such as Beta.