|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.|
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
|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.|