Course syllabus

Discrete Event Systems

SSY165, 7.5 hp, Study Period 1, HT19

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 (e.g. clarifications on assignments);
• ask your questions during lectures or exercise sessions;
• come to the TA's office 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, room EDIT 5330 / 5324 (E-building, Hörsalsvägen 11, floor 5, east wing along Hörsalsvägen)

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

Preliminary schedule for the lectures

Period Week/ Book chapter	Date, Room	Contents
pw 1, Ch. 1	Monday 2/9 13-16, HC4	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 5/9 8-10, HA4	Discrete mathematics. Propositional logic, truth tables, tautological equivalences and implications. Formal proofs.
pw 1, Ch. 2	Thursday 5/9 10-12, HA1	Discrete mathematics. Sets, operations on sets, set algebra.
pw 2, Ch. 3	Monday 9/9 13-16, HC4	Formal models. Automata, sets of states and events, transition relations, partial transition functions, traces, formal languages.
pw 2	Thursday 12/9 8-10	No lecture
pw 3, Ch. 3	Monday 16/9 13-16, HC4	Formal models. Synchronous composition and language intersection, Petri nets. Introduction of the first home assignment.
pw 3,  Ch. 4, 6	Thursday 19/9 8-10, HA4	Modeling & Specification. Verification. Specification of desired and nondesired behaviors, marked, forbidden and reachable states. Controllable and uncontrollable events, verification of controllability.
pw 4, Ch. 7	Monday 23/9 13-16, HC4	Controller synthesis. Plant, specification, supervisor synthesis, supervisor or controller implementation.
pw 4, Ch. 8	Thursd 26/9 8-10, HA4	Extended models. Extended finite automata, timed automata, hybrid automata.
pw 5 Extra notes	Mond 30/9 13-16, HC4	Temporal logic.
pw 5 Extra notes	Thursd 3/10 8-10, HA4	Temporal logic.
pw 6 Extra notes	Mond 7/10 13-16, HC4	Temporal logic planning.
pw 6, Ch. 8	Thursd 10/10 8-10, HA4	Extended models. Markov chains.
pw 7, Ch. 8	Mond 14/10 13-16, HC4	Extended models. Queuing theory, Markov decision processes.
pw 7, Ch. 8	Thursd 17/10 8-10, HA4	Reinforcement learning. Short introduction.
pw 8 Extra notes	Mond 21/10 13-16, HC4	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.

Preliminary schedule for the exercise classes

Period Week/ Book chapter	Date, Room	Exercises
pw 1	Thursday 5/9 10-12, HA1	Lecture
pw 2, Ch. 1, 2	Thursday 12/9 10-12, SB-H7	Introduction 1.1 - 1.8 Discrete mathematics 2.1 - 2.3
pw 3, Ch. 2, 3	Thursday 19/9 10-12, SB-H7	Discrete mathematics 2.4 - 2.6 Formal models 3.1 - 3.5
pw 4, Ch. 4	Thursday 26/9 10-12, SB-H7	Modelling and specification 4.1 - 4.9
pw 5, Ch. 6	Thursday 3/10 10-12, SB-H7	Verification 6.1 - 6.6
pw 6, Ch. 7	Thursday 10/10 10-12, SB-H7	Controller synthesis 7.1 - 7.7
pw 7, Ch. 8	Thursday 17/10 10-12, SB-H7	Markov processes, exam October 2016
pw 8	Thursday 24/10 10-12, SB-M022	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, in room 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.

Home assignment	Distribution by Canvas on Monday	Submission latest on Friday	Returned on Friday	Re-submission latest on Friday
Assignment 0	2/9 (pw 1)	13/9 (pw 2)	20/9 (pw 3)	27/9 (pw 4)
Assignment 1	16/9 (pw 3)	27/9 (pw 4)	4/10 (pw 5)	11/10 (pw 6)
Assignment 2	30/9 (pw 5)	11/10 (pw 6)	18/10 (pw 7)	25/10 (pw 8)
Assignment 3	14/10 (pw 7)	18/10 (pw 7)	25/10 (pw 8)	1/11 (pw 9)

 

Changes made since the last occasion

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 26/10-2019, am, and first re-sit examination date is Wednesday 8/1-2020, am.

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