EECS 381/409: Discrete Event and Hybrid Systems

Spring 2008, Prof. Michael Branicky

MW 12:30-13:45, White 322

Bulletin Description (381):

Today, the most interesting computer code and microprocessor designs are "embedded" and hence interact with the physical world, producing a mixture of digital and analog domains. This class studies an array of tools for understanding and designing these "hybrid systems." Topics covered include: basics of language and finite state automata theory, discrete-event dynamic systems, Petri nets, timed and hybrid automata, and hybrid dynamical systems. Simulation and verification concepts and languages for these models. Stability analysis, complexity issues, and control of discrete event and hybrid systems.

Graduate Version (409):

Students taking the graduate version of the course are required to do extra homework problems, including full proofs, plus a substantial research project.

Information Sheet

Lecture Notes / Handouts

14 JAN: Lecture #1: Course Mechanics / Hybrid Systems: Applications and Models   Handout
16 JAN: Lecture #2: Discrete-Event Systems / From Continuous to Hybrid   ODEs Handout

21 JAN: No Class (MLK Holiday)
23 JAN: Lecture #3: Base Discrete Model: Finite Automata (FA)   FA Handout

28 JAN: Lecture #4: FA Elaborations / Adding Time to Automata
31 JAN: Lecture #5: From Discrete to Hybrid / FA with Output   Mealy/Moore Handout

04 FEB: Lecture #6: DFA Reachability / Minimization / Synthesis

06 FEB: Lecture #7: Subset Construction Algorithm / e-NFAs   SCA Example Handout

11 FEB: Lecture #8: e-NFAs and Diagnosis   Diagnosis Handout   Real World Diagnosis Handout
13 FEB: Lecture #9: Regular Expressions (REGEXs)   REGEXs Handout

18 FEB: Lecture #10: Intro. to DES Control   DES Handout
20 FEB: Lecture #11: DES Control   DES Control Handout
Chapter 2: Languages and Automata [Cassandras and Lafortune]
Control of DES [Ramadge and Wonham]

25 FEB: Lecture #12: DES Control 2   Product Automata Example: E-Commerce
27 FEB: Lecture #13: Omega Automata   Buchi Automata Handout

03 MAR: Lecture #14: Timed Automata
A Theory of Timed Automata [Alur and Dill]
Hardware Timing Verification Using KRONOS [Maler and Yovine]
05 MAR: Lecture #15: Midterm Exam in class

10 MAR: No lecture: Spring Break
12 MAR: No lecture: Spring Break

17 MAR: Lecture #16: Timed Automata 2   Timed Automata in Practice Handout
19 MAR: Lecture #17: Hybrid Automata   Example Hybrid Automata Handout
Conversions Among Classes of Hybrid Automata [Henzinger, Kopke, Puri, and Variaya]

24 MAR: Lecture #18: Linear Hybrid Automata and HyTech   HyTech Handout
26 MAR: Lecture #19: Reachability and Verification 1

31 MAR: Lecture #20: Reachability and Verification 2   NL Hybrid Reachability Handout
02 APR: Lecture #21: Hybrid Systems Simulation   HS Simulation Handout   Addendum

07 APR: Lecture #22: Petri Nets 1   PN Handout
Chapter 4 [Cassandras and Lafortune]
The Discrete Event Modeling and Trajectory Planning of Robotic Assembly Tasks [McCarragher and Asada]
09 APR: Lecture #23: Petri Nets 2

14 APR: Lecture #24: Petri Net Analysis 1   PN Coverability Alg. Handout
16 APR: Lecture #25: Petri Net Analysis 2   PN Analysis Handout   PN Examples Handout

21 APR: Lecture #26: Intro. to Markov Chains   MC Intro. Handout   MC Probs. Handout
Sections 7.1-2 [Cassandras and Lafortune]
Chapter 7 [Luenberger]
23 APR: No Lecture

28 APR: Lecture #27 Advanced Markov Chains   Advanced MC Handout
Modeling and Throughput Prediction for Flexible Parts Feeders [Branicky, Causey, Quinn]

07 MAY (8:30-11:30am): FINAL EXAM

Problem Sets

Problem Set #1 (due 06 FEB)   Solutions   Post-Mortem
Problem Set #2 (due 18 FEB)   Examples   Solutions   Post-Mortem
Problem Set #3 (due 27 FEB)   FAQ   Solutions   Post-Mortem
Problem Set #4 (due 19 MAR)   Solutions   Post-Mortem
Problem Set #5 (due 02 APR)   Solutions   Post-Mortem   Graduate Problem 5.GP
Main HyTech Site
Obtaining/Accessing HyTech
HyTech Demo Code Files: Train Gate   Fischer Mutual Exclusion
Problem Set #6 (due 09 APR)   FAQ   Solutions   Post-Mortem   Graduate Problem 6.GP
Matlab code: ha.m   haz.m   myballode.m (MSB)   ballode.m (Matlab)   naiveball.m
Problem Set #7 (due 21 APR)   Solutions   Post-Mortem
Problem Set #8 (due 28 APR)   Solutions   Post-Mortem

Graduate Project Problems

Example HyTech Project Problems: Distributed Control over a Communication Channel   Buffering at a Network Bottleneck   Airplane Landing
Example Matlab Project Problems: TCP Congestion   LEGO Robots Egg-Gathering Contest

Midterm Exam

Sample Midterm with Answers (Spring 2005)
Midterm   Solutions   Post-Mortem

Midterm Grades Overview

Final Exam

Information Sheet

Final Exam and Course Grades Post-Mortem

Links

UMDES-LIB Software Home Page
HyTech
Created: 2008-01-13. Last Modified: 2008-05-08.