CS 538A, Term 1, Winter 2003-2004 Class Home Page

Computational Techniques for Hybrid and Embedded Systems Design

Contents of this page

Late Breaking News:


# Date Topic
1 Friday, Sept. 5 List of likely course topics
2 Monday, Sept. 15 Reading and reviewing academic articles
3 Wednesday, Oct. 8 Project Description. A list of potential projects is available from the professor.
4 Monday, Nov. 17 Course Survey (pdf) or Course Survey (tex).


Homework Submission Policy:

# Due Date Assignment Solution Other Files
1 September 22 Problem Set Solutions none
2 October 15 Problem Set Solutions HyVisual simulation tool (specificially for Hybrid Systems) or Ptolemy II simulation tool (for many different models of computation)
* October 17 Reading Assignment no solution Peer Assessment Form. Copies will be provided in class for you to fill out.
3 December 1 Problem Set Solutions This assignment is optional, and can be used to offset low marks from previous assignments.

Course Details

Overview: Computer controlled systems are pervasive in the modern world: cars, aircraft, communications and power networks, appliances, games, and many more devices contain hidden microchips. Unfortunately, the methodologies used to design these systems have not scaled as fast as the complexity of the systems themselves. All too often, problems are not detected until late in the design cycle, thus increasing costs and delaying production. Modification and re-use are also difficult in this environment, because so much of the design and testing is done at the lowest levels of abstraction.

In this class we will investigate a collection of techniques for designing, simulating, analyzing, verifying and controlling these systems. These techniques are drawn from the fields of computer science, control engineering and applied mathematics. In particular, we will look at two overlapping classes of systems:

Among the systems falling into one or both of these categories are applications in aerospace, automobiles, robotics, mechatronics and process control.

In addition to attending lectures, students will be expected to read and discuss academic papers, experiment with some design and analysis tools and complete a course project (which may be tailored to each student's own research or interests).

Intended Audience: Graduate students in

Prerequisites: None officially. Students should be able to

Instructor: Ian Mitchell

Lectures: 10 - 11:30, Mondays and Wednesdays, Forest Sciences Center (FSC) 1402.


Grades: Your final grade will be based on a combination of

The relative weighting will depend on how many homework assignments I come up with.

Background Material:

The Schedule:

# Date Topic Links Readings
1 Sept 8 Introduction Softwalls Project Required: Softwalls FAQ
2 Sept 10 Notation. Elementary set analysis. Fire drill. Continuity. Linear algebra. Vector calculus none Optional: Marsden and Hoffman, Adams, Strang from the background texts
3 Sept 15 Dynamic systems and mathematical models. Differential Equations. Matlab's introduction to initial value ODEs (available locally through Matlab's helpdesk) Required: Lygeros notes chapters 1, 2.
Optional: Boyce and DiPrima, Sastry, Burden and Faires from the background texts
4 Sept 17 Four basic properties of mathematical models. Reading and reviewing academic papers. Reading and reviewing academic articles Required: Lygeros notes chapter 2.
Optional: Boyce and DiPrima, Sastry from the background texts
5 Sept 22 Embedded Systems Design (paper discussion). Tagged signal model. A Framework for Comparing Models of Computation by Lee and Sangiovanni-Vincentelli. Proceedings of the IEEE v.85, n.3 (March 1997) Special Issue on Hardware/Software Codesign Required: Design of Embedded Systems: Formal Models, Validation and Synthesis by Edwards, Lavagno, Lee and Sangiovanni-Vincentelli
6 Sept 24 Finite State Machines and Statecharts The STATEMATE Semantics of Statecharts by Harel and Naamad Required: Statecharts: A Visual Formalism for Complex Systems by Harel and STATEMATE: A Working Environment for the Development of Complex Reactive Systems by Harel et. al.
7 Sept 29 Hybrid Automata and Hybrid Time Trajectories none Required: Lygeros notes chapter 3
8 Oct 1 Hybrid Executions, Classifications and Nondeterminism none Required: Lygeros notes chapter 4
9 Oct 6 Validating designs and Introduction to Reachability Ian's defense slides. Ian's thesis. Required: Lygeros notes chapter 5.1; Computational Techniques for the Verification of Hybrid Systems by Tomlin, Mitchell, Bayen and Oishi. Optional: Safety Verification of Conflict Resolution Maneuvers by Tomlin, Mitchell and Ghosh.
10 Oct 8 Hybrid Reachability, Reading Assignment and Project Discussion none Optional: A Game Theoretic Approach to Controller Design for Hybrid Systems by Tomlin, Lygeros and Sastry.
11 Oct 13 Thanksgiving Holiday (no class)
12 Oct 15 CheckMate, Transition Systems, Bisimulation CheckMate toolbox Required: Lygeros notes chapters 6.1 and 6.2; Computational Techniques for Hybrid System Verification and Computing Polyhedral Approximations to Flow Pipes for Dynamic Systems, both by Chutinan and Krogh
13 Oct 20 Abstractions, Deductive Methods, Stability none Required: Lygeros notes chapter 5.2. Optional: Sastry chapter 5.
14 Oct 22 Lyapunov Methods for Continuous Systems none Required: Multiple Lyapunov Functions and Other Analysis Tools for Switched and Hybrid Systems by Branicky. Optional: Sastry chapter 5. Boyce and DiPrima chapter 9.5. Perspectives and Results on the Stability and Stabilizability of Hybrid Systems by DeCarlo, Branicky, Pettersson and Lennartson.
15 Oct 27 Paper presentation and LaSalle's Invariance Principle none Required:A Formal Specification Model for Hardware/Software Codesign by Chiodo et. al. (presented by Jun Wang)
16 Oct 29 Paper presentation and Lyapunov Methods for Hybrid Systems none Required:Autonomous Formation Switching for Multiple Mobile Robots by Axelsson, Muhammad and Egerstedt (presented by Pengpeng Wang)
17 Nov 3 Paper presentation none Required:Petri Nets: Properties, Analysis and Applications by Murata (presented by Qian Huang).
18 Nov 5 Paper presentation and Timed Automata none Required: Processes, Interfaces and Platforms. Embedded Software Modeling in Metropolis by Balarin et. al (presented by Suwen Yang). Lygeros notes chapter 6.3. Optional:A Theory of Timed Automata by Alur and Dill.
19 Nov 10 Paper presentations (2) none Required: Fast Marching for Hybrid Control by Branicky and Hebbar (presented by Georg Wittenburg). Simulation Takes Off with Hardware by Ledin (presented by Fahong Li). Optional: A Fast Marching Algorithm for Hybrid Systems by Branicky, Hebbar and Zhang.
20 Nov 12 Class Cancelled
21 Nov 17 Time Triggered Architecture Giotto home page Optional: Giotto: a Time-Triggered Language for Embedded Programming by Henzinger, Horowitz and Kirsch.
22 Nov 19 Paper presentation and course summary none Required: Hybrid Verification of an Interface for an Automatic Landing by Oishi et al (presented by Joseph Luk).Optional: What's Ahead for Embedded Software? by Lee.
23 Nov 24 Project Presentations: Fahong Li, Suwen Yang, Jun Wang.
24 Nov 26 Project Presentations: Joseph Luk, Georg Wittenburg, Pengpeng Wang, Qian Huang.
Dec 2-16 Exam Period, Projects due at 12 noon, Tuesday, Dec 16.


If you encounter other research groups, tools or conferences that you would like to include in this list, please contact the instructor.

CS 538A Term 1 Winter 2002-2003 Class Page
maintained by Ian Mitchell