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
• Things to print
  • Handouts
  • Homeworks
• Course Details
  • Overview
  • Audience
  • Prerequisites
  • Instructor
  • Lecture Time and Location
  • Textbooks
  • Grades
  • Background Reading
• Tentative Schedule
• Related Links

Late Breaking News:

• 03/12/23: The final grades have been submitted (although I'm not sure how long they may take to appear in the student system). You can collect your graded homeworks and projects from me in January. Thanks for an excellent class!
• 03/12/02: The project report is due 12 noon, Tuesday December 16. This deadline is hard, because I am leaving town the following day. Reports may be submitted by hardcopy to my mailbox or by email (pdf or ps format only).
• 03/11/24: I will be out of town Wednesday December 3 to Sunday December 14, and I may not have email access during that time. If you would like to discuss your projects with me (and I encourage you to do so), please email me to arrange a meeting before my trip.
• 03/11/17: The project presentation schedule is posted below.
• 03/11/15: Our guest for November 17 has cancelled his trip. Instead, we will discuss the time triggered architecture Giotto.
• 03/11/06: A partial solution for Homework 2 is now posted.
• 03/11/05: Class is canceled on Wednesday, November 12. The presentations scheduled for this class have been moved (please check below for the updated reading assignment).
• 03/11/05: Homework 3 is now optional and due December 1. Including your class paper presentations, you have 11 homework questions plus the 3 in Homework 3. You may hand in 0-3 of the questions from Homework 3, and I will use the best 11 marks from your homework and paper presentation to determine your final mark (along with your project mark).
• 03/10/31: For Monday's paper on Petri Nets, Qian will be discussing sections I, II, III, IV (A, B, C), V (A, B), VI, and VIII.
• 03/10/27: Homework 3 is available below.
• 03/10/22: All students except the presenter will be asked to fill out a peer assessment form at the conclusion of each student presentation. Copies will be provided in class.
• 03/10/08: A description of the course project (expectations, deadlines, etc.) is linked in the Handout section below. Project proposals are due Monday October 27.
• 03/10/08: Monday October 13 is a holiday. There will be no class, and Homework 2 is further extended to Wednesday, October 15 (don't be late).
• 03/10/06: The reading assignment has been posted in the homework section below. Paper choices and presentation times must be finalized by Friday October 17, and presentations will occupy the subsequent four weeks.
• 03/10/06: Solution/discussion of Homework 1 is now posted. Your solutions for Homework 2 should be modelled after the solution provided for Homework 1, question (1). The due date for Homework 2 has been extended to Monday, October 13 so that you can modify your solutions as necessary.
• 03/10/02: Readings for lectures 9 and 10 are now posted.
• 03/09/29: An additional part (e) to question (3) has been added in Homework 2. The modified version is now available below.
• 03/09/26: In Homework 2 you need to build a simulation of a simple Hybrid System in either the HyVisual simulation tool (a subset of Ptolemy II specificially for Hybrid Systems) or the Ptolemy II simulation tool (for many different models of computation). You may install one of those tools yourself from those web sites. Alternatively, I have installed HyVisual at ~mitchell/Ptolemy/HyVisual/HyVisual on the graduate CS filesystem (eg columbia.cs.ubc.ca). Let me know if you encounter difficulties accessing this installation. At some point I will install the full Ptolemy package as well, but for this assignment the HyVisual subset should be sufficient.
• 03/09/24: Homework 2 is available below.
• 03/09/22: There is an error in the initial conditions for HW #1, Q #2a. It should read x(0) = -log(2).
• 03/09/15: A short handout on reading and reviewing academic articles is available in the handouts section.
• 03/09/11: The CS538A lecture notes by Lygeros are now available at Copyright in the basement of the SUB; the cost is $10.
• 03/09/10: Homework 1 is available below.
• 03/09/02: The first lecture will be held on Monday, September 8, 2003.

Handouts

Homeworks

Homework Submission Policy:

• Get it in soon or I can't release solutions.
• Get it in by the end of the semester, or you won't get a grade.

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:

• Hybrid Systems: Systems which contain interacting discrete and continuous components. For example, the behavior of an unmanned aerial vehicle (UAV) can be modeled by a combination of differential equations (the aerodynamics and low level feedback controllers) and a finite state automata (high level flight path decisions, such as to ascend or descend).
• Embedded Systems: Systems which interact with the outside world through sensors and actuators other than the traditional desktop keyboard and screen. Typically, embedded systems must react (often at real-time rates) to externally generated events.

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

• Computer Science
• Electrical and Computer Engineering
• Mechanical Engineering
• possibly Applied Mathematics and other Engineering disciplines.

Prerequisites: None officially. Students should be able to

• Understand basic concepts in differential equations and logic.
• Program in some language; for example: Matlab, Java or C.
• Familiarity with control theory will be useful, but not required.

Instructor: Ian Mitchell

• Email: mitchell (at) cs (dot) ubc (dot) ca
• Office Location: CISR/CS 233
• Office Phone: (604) 822-2317
• Office Hours: TBA (and by appointment)

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

• Formal lectures will begin Monday September 8.
• There is no lecture Monday September 1 (Labour Day Holiday).
• There is no lecture Wednesday September 3 (cancelled for CS orientation), although I will be available from 10 - 11 in my office if you have any questions.

References:

• Lecture Notes on Hybrid Systems by John Lygeros (available from Copyright in the basement of the SUB; cost is $10).
• The Art of Hybrid Systems by John Lygeros, Shankar Sastry, and Claire Tomlin (the instructor may provide copies to students wishing to pursue further studies in hybrid systems).
• Research papers listed (and linked) in the Schedule below.

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

• 3-8 homework assignments,
• project presentation,
• project report.

Background Material:

• Elementary Classical Analysis by Marsden and Hoffman.
• Elementary Differential Equations and Boundary Value Problems by Boyce and DiPrima.
• Single Variable Calculus and Calculus of Several Variables by Adams.
• Numerical Analysis by Burden and Faires.
• Linear Algebra and Its Applications by Strang.
• Matrix Computations by Golub and Van Loan.
• Nonlinear Systems: Analysis, Stability and Control by Sastry.

The Schedule:

• Topics of future lectures are subject to change.
• Unless otherwise specified, readings are required.
• Some readings and/or links may not be operational from computers outside the UBC domain. If you have problems, please contact the instructor.

Links:

• CS 538A Term 1 Winter 2002-2003 Course Web Page (this page): http://www.cs.ubc.ca/~mitchell/Class/CS538A.2003/index.html
• CS 538A is offered by
• Ian Mitchell
• Department Computer Science
• University of British Columbia
• Elements of this course are drawn from the following courses:
  • Hybrid Systems, taught by Koo, Mitchell and Simic in Spring 2003 at Berkeley.
  • Design of Embedded Systems, taught by Sangiovanni-Vincentelli in Fall, 2002 at Berkeley.
  • Hybrid Systems: Modeling, Analysis, and Control, taught by Tomlin in Spring 2002 at Stanford.
• Research Groups, Centers and Committees
  • Center for Hybrid and Embedded Systems at Berkeley
  • IEEE CSS Technical Committee on Hybrid Systems
  • Virtual Action Group on Hybrid Dynamic Systems for the IEEE's Control Systems Society technical committee on Computer Aided Control System Design.
  • Hybrid Systems Group at the University of Pennsylvania
  • Control and Optimization of Hybrid and Embedded Systems Group at the University of Siena
  • Hybrid Systems Laboratory at Stanford
• Tools
  • CheckMate for verifying hybrid systems.
  • HyTech for verifying linear hybrid systems.
  • Ptolemy II for simulating concurrent, embedded and hybrid systems.
  • What else?
• Conferences and Workshops
  • Hybrid Systems: Computation and Control
  • IEEE Conference on Decision and Control