Hybrid and Switched Systems
ECE229 — Fall 2005

Tu Th 2-3:50pm @ Phelps 1437, 4units

Course description

As computers, digital networks, and embedded systems become ubiquitous and increasingly complex, one needs to understand the coupling between logic-based components and continuous physical systems. This prompted a shift in the standard control paradigm—in which dynamical systems were typically described by differential or difference equations—to allow the modeling, analysis, and design of systems that combine continuous dynamics with discrete logic. This new paradigm is called hybrid control.

multiple-tank

This course provides an introduction to hybrid control. We start by presenting a modeling framework for hybrid systems that combines elements from automata theory and differential equations. The students are then guided through a set of techniques that can be used to analyze and design hybrid control systems. The course also includes an overview of simulation tools for hybrid systems with emphasis on Simulink/Stateflow, SHIFT, and Modelica.

transmission

  

In the last part of the course, we cover several fundamental applications of hybrid control. These include the modeling of communication networks, networked control systems, the modeling of bio-chemical reactions, the control of nonlinear systems that cannot be stabilized by continuous control laws, the control of systems with large uncertainty using logic-based supervisors, etc.

The course is essentially self-contained and the students are only expected to be familiar with linear algebra and basic differential equations.

Further information (including a detailed syllabus) is available on the web at:

http://www.ece.ucsb.edu/~hespanha/ece229/

This course was developed with support from the National Science Foundation.

Prerequisites

Consent of instructor. This course is open to ECE, ME, ChE, and CS students.

Recommended preparation: The students should be proficient in linear algebra and basic differential equations (at the level of MATH5A-C) and some scientific programming language (e.g., MATLAB). Basic knowledge of controls concepts (at the level of ECE147A) is helpful but not essential.

Instructor

João P. Hespanha (hespanha at ece.ucsb.edu), phone: (805) 893-7042, office: Engineering I, 5157.

Office hours:     Please email or phone in advance to schedule an appointment.

Textbook

There is no recommended textbook for the course. Most of the material taught is covered by the following references:

[1] A. van der Schaft and H. Schumacher. An Introduction to Hybrid Dynamical Systems. Lecture Notes in Control and Information Sciences 251, Springer-Verlag, 2000.

[2]  D. Liberzon. Switching in Systems and Control. Systems & Control: Foundations and Applications series. Birkhauser, Boston, 2003.

[3]  J. Hespanha. Chapter Stabilization Through Hybrid Control. In Encyclopedia of Life Support Systems (EOLSS), 2004. [pdf]

[4]  J. Hespanha. Tutorial on Supervisory Control. Lecture Notes for the workshop Control using Logic and Switching for the 40th Conf. on Decision and Contr., Orlando, Florida, Dec. 2001. [pdf]

Other papers and notes will also be posted in the course’s webpage to complement the lectures. See References below and right-most column of the Syllabus.

Assessment format

Homeworks – 40% (7-8 assignments)

Final Project – 60% (one-page project proposal is due on Oct 25th, in-class presentation)

Projects

The following two types of projects are possible in this course:

1.      Solution of a research problem relevant to the student’s area of research

2.      Independent study of a topic not covered in class (e.g., reading a paper or book chapter).

A few project ideas:

·        Modeling of network protocols using hybrid systems [see this paper]

·        Modeling of networked control systems (could also have an experimental component) [see this survey]

·        Modeling of sensor networks with stochastic hybrid systems

·        Controlling of walking robots using hybrid systems [see these two papers GrizzleTAC, GrizzleCSM]

·        Modeling of biological chemical reactions using stochastic hybrid systems [see this paper].

·        Survey of controllability and observability results for linear switched and hybrid systems

Design of H-infinity controllers for slowly-switched systems

·        Survey on optimal control of hybrid systems

For more project ideas, students are encouraged to look into the proceedings of the Hybrid Systems: Computation and Control workshop. The full text of the proceedings is available online:  HSCC'98, HSCC'99, HSCC'00, HSCC'01, HSCC'02, HSCC'03, HSCC’04, HSCC'05.

Detailed syllabus

The following is a tentative schedule for the course. As revisions are needed, they will be posted on the course's web page. The rightmost column of the schedule contains the recommended reading for the topics covered on each class. Students are strongly encouraged to read these and background materials prior to the class.

Class

Content

References

Lec. #1

Sep 22

Introduction to switched control systems

Examples: bouncing ball, thermostat, transmission system, inverted pendulum swing-up, multi-tank system, manufacturing systems, supervisory control.

 [1,27,28,29,4]

lecture notes
(last changed 9/25/05)

 

Lec. #2

Sep 27

Part I – Modeling & Simulation

Formal models for hybrid systems:

·        Finite automata

·        Differential equations

·        Hybrid automata

·        Open hybrid automaton

Nondeterministic vs. stochastic systems

·        Nondeterministic hybrid automata

·        Stochastic hybrid automata

[1,8]

lecture notes
(last changed 9/27/05, just a few typos corrected with respect to the 9/25/05 version)

Lec. #3

Sep 29

Trajectories of hybrid system

·        Solution to an hybrid system

·        Execution of an hybrid system

Degeneracies

·        Finite-escape time

·        Chattering

·        Zeno trajectories

·        Non-continuous dependency on the initial-state

[5,6,7]

lecture notes
(last changed 9/29/05)

Lec. #4

Oct 4

Numerical simulation of hybrid automata

·        simulations of ODEs

·        zero-crossing detection

Simulators

·        Simulink

·        Stateflow

·        SHIFT

[9,10,11,12,13]

lecture notes
(last updated 10/6/05)

Simulink/Stateflow files
(last changed 10/2/05)

SHIFT files (untested)
(last changed 10/2/05)

Modelica files
(last changed 10/2/05)

Lec. #5

Oct 6

Simulators (cont.)

·        Modelica

Part II – Analysis & Design

Properties of hybrid automata

·        sequence properties (safety, liveness)

·        ensemble properties (stability)



[14]

lecture notes
(last changed 10/2/05)

Lec. #6

Oct 11

Safety/Reachability

·        transition systems

·        reachability algorithms

·        controller synthesis based on reachability

[15, 16,17, 18]

lecture notes
(posted on 10/9/05)

Lec. #7

Oct 13

Safety/Reachability (cont.)

Lyapunov stability of ODEs

·        epsilon-delta and beta-function definitions

·        Lyapunov’s stability theorem

·        LaSalle’s invariance principle

·        Stability of linear systems

[19]

lecture notes
(posted on 10/9/05)

MATLAB files
(posted on 10/9/05)

Oct 18

No class

Oct 20

No class

 

Lec. #8

Oct 25

Project proposal due!

Lyapunov stability of ODEs (cont.)

Lyapunov stability of hybrid systems

[3,19,20,21]

lecture notes
(posted on 10/9/05)

An alternative view
(posted on 10/9/05)

Lec. #9

Oct 27

Analysis tools for hybrid systems:

Impact maps

·        Fixed-point theorem

·        Stability of periodic solutions 

[3,23]

lecture notes
(posted on 10/9/05)

Mathematica file
(posted on 10/9/05)

Lec. #10

Nov 1

Impact maps (cont.)

Switched systems

·        Linear Switched systems

·        Lyapunov stability of switched systems

[2,3]

lecture notes
(posted on 10/31/05)

Lec. #11

Nov 3

 

Stability under arbitrary switching

·        Instability caused by switching

·        Common Lyapunov function

·        Converse results

·        Algebraic conditions

[2,3]

lecture notes
(posted on 10/31/05)

MATLAB files
(posted on 10/31/05)

Lec. #12

Nov 8

Controller realization for stable switching

[24]

lecture notes
(posted on 10/31/05)

Lec. #13

Nov 10

Stability under slow switching

·        Dwell-time switching

·        Average dwell-time

·        Stability under brief instabilities

Stability under state-dependent switching

·        State dependent common Lyapunov function

·        Multiple Lyapunov functions

·        LaSalle’s invariance principle

[3, 20,21,22]

lecture notes
(updates on 11/12/05)

Lec. #14

Nov 15

Computational methods to construct multiple Lyapunov functions—Linear Matrix Inequalities (LMIs)

Part III – Applications

Vision-based control

[3,25]

lecture notes
(posted on 11/12/05)

 

 

 

[34]

 

Lec. #15

Nov 17

Modeling of network traffic

[31]

lecture notes
(posted on 11/12/05)

Lec. #16

Nov 22

Stochastic hybrid systems

·        Communication networks

·        Networked control system

·        Bio-chemical reactions

[8,32]

lecture notes  NEW
(posted on 11/22/05)

Nov 24

Thanksgiving holiday

 

Lec. #17

Nov 29

Student projects presentations

 

Lec. #18

Dec 1

Student projects presentations

 

References

Modeling

[5] R. Goebel, J. Hespanha, A. Teel, C. Cai, R. Sanfelice. Hybrid Systems: Generalized Solutions and Robust Stability. In Proc. of the 6th IFAC Symp. on Nonlinear Contr. Systems, Sep. 2004. [pdf]

[6] Jun Zhang, K. Johansson, John Lygeros, S. Sastry. Dynamical Systems Revisited: Hybrid Systems with Zeno Executions. In Nancy A. Lynch and Bruce H. Krogh (ed.). Hybrid Systems: Computation and Control. Springer, Mar. 2000.

[7] K. Johansson, M. Egerstedt, J. Lygeros, S. Sastry. On the regularization of Zeno hybrid automata. Syst. & Contr. Lett., 38:141-150, 1999.

[8] J. Hespanha. A Model for Stochastic Hybrid Systems with Application to Communication Networks. 2005. To appear in Nonlinear Analysis Special Issue on Hybrid Systems. [pdf]

Simulation

[9] T. Simsek. SHIFT Tutorial: A first course for SHIFT programmers. Technical report. University of California, Berkeley, Jan. 1999.

[10] The Mathworks Inc. Using Simulink (version 4), Nov. 2000.

[11] The Mathworks Inc. Stateflow User’s Guide (version 4), Sep. 2000.

[12] M. Otter, H. Elmqvist. Modelica: Languages, Libraries, Tools, Workshop and EU-Project RealSim. Simulation News Europe, pp. 3-8, Dec 2001.

[13] Modelica Association. Modelica ™ — A Unified Object-Oriented Language for Physical Systems Modeling: Tutorial. Available at http://www.modelica.org/.

Reachability and other sequence properties

[14] Z. Manna and A. Pnueli, The Temporal Logic of Reactive and Concurrent Systems: specification. Springer-Verlag, Berlin, 1992.

[15] T. Henzinger, P. Kopke, A. Puri, P. Varaiya. What's decidable about hybrid automata? ACM Symposium on Theory of Computing, pp. 373-383, 1995.

[16] G. Lafferriere, G. Pappas, S. Sastry. O-Minimal Systems. Syst. & Contr. Lett., 13:1-21, 2000.

[17] P. Ramadge, W. Wonham. The control of discrete event systems. Proc. of the IEEE, 77(1):81-98, 1989.

[18] J. Lygeros, C. Tomlin, S. Sastry. Controllers for reachability specifications for hybrid systems. Automatica, 35(3):349-370, Mar. 1999.

Stability

[19] H. K. Khalil, Nonlinear Systems, 2nd edition, Prentice Hall, 1996.

[20] M. Branicky. Multiple Lyapunov functions and other analysis tools for switched and hybrid systems. IEEE Trans. Automatic Control, 43(4):475-482, April 1998.

[21] H. Ye, A. Michel, L. Hou. Stability Theory for Hybrid Dynamical Systems. IEEE Trans. Automatic Control, 43(4):461-474, Apr. 1998.

[22] J. Hespanha. Uniform Stability of Switched Linear Systems: Extensions of LaSalle's Invariance Principle. IEEE Trans. on Automat. Contr., 49(4):470-482, Apr. 2004. [pdf]

[23] J. Grizzle, G. Abba, F. Plestan. Asymptotically stable walking for biped robots: analysis via systems with impulse effects, IEEE Transactions on Automatic Control, 46(1):51—64,  Jan. 2001. [pdf]

[24] J. Hespanha, A. S. Morse. Switching Between Stabilizing Controllers. Automatica, 38(11), Nov. 2002.

[25] S. Boyd, L. El Ghaoui, E. Feron, V. Balakrishnan. Linear Matrix Inequalities in System and Control Theory. SIAM, 1994.

[26] D. Liberzon, A. S. Morse, Basic problems in stability and design of switched systems. IEEE Control Systems Magazine, vol. 19, no. 5, pp. 59-70, Oct. 1999.

[27] A. Matveev, A. Savkin. Qualitative Theory of Hybrid Dynamical Systems. Control Engineering, Birkhäuser, 2000.

Applications

 [28] S. Hedlund, A. Rantzer. Optimal Control of Hybrid Systems. In Proc. of the 38th Conf. on Decision and Contr., Dec. 1999.

[29] K. Åström, K. Furuta. Swinging up a pendulum by energy control. Automatica 36:287-295, 2000.

[30] J. Hespanha, D. Liberzon, A. S. Morse. Overcoming the limitations of adaptive control by means of logic-based switching. Syst. & Contr. Lett., 49(1):49-65, Apr. 2003. [pdf]

[31] S. Bohacek, J. Hespanha, J. Lee, K. Obraczka. A Hybrid Systems Modeling Framework for Fast and Accurate Simulation of Data Communication Networks. In Proc. of the ACM Int. Conf. on Measurements and Modeling of Computer Systems (SIGMETRICS), June 2003. [pdf]

[32] J. Hespanha, A. Singh. Stochastic Models for Chemically Reacting Systems Using Polynomial Stochastic Hybrid Systems. 2005. To appear in the Int. J. on Robust Control Special Issue on Control at Small Scales. [pdf]

Homeworks

Modelica’s simulator dymola is available in the computer bradbury.ece.ucsb.edu and in the Linux workstations in the E1 lab. To get started do as follows:

1.      Add the dymola directory to your PATH environment variable

      In bradbury.ece.ucsb.edu, this can be done using the tcsh command

setenv PATH /usr/local/dymola/bin:$PATH

In the E1 lab, this can be done using the tcsh command

setenv PATH /eci/dymola /bin:$PATH

2.      Start the simulator using the command

dymola5 thermostat.mo

Documentation is available online and in references [12-13] above

 

Number

Posted on

Due date

Exercises

1

9/25/2005

10/6/2005

homework #1

requires material from lectures #1 and #2

Solution will be provided in class

2

10/2/2005

10/13/2005

homework #2

requires material from lectures #2 and #3

3

10/9/2005

10/25/2005

homework #3

requires material from lectures #4 and #5

4

11/4/2005

11/10/2005

homework #4  NEW

requires material from lectures #6 and #9

5

11/6/2005

11/17/2005

homework #5  NEW

requires material from lectures #11 and #12

6

7

8