Autonomous Cyber-Physical Systems: Stability, Modeling with Hybrid Systems Spring 2018. CS 599. Instructor: Jyo Deshmukh Acknowledgment: Some of the material in these slides is based on the lecture slides for CIS 540: Principles of Embedded Computation taught by Rajeev Alur at the University of Pennsylvania. http://www.seas.upenn.edu/~cis540/ This lecture also uses some other sources, full bibliography is included at the end of the slides. USC Viterbi School of Engineering Department of Computer Science Layout Stability Analysis Hybrid Dynamical Systems Probabilistic Models

USC Viterbi School of Engineering Department of Computer Science 2 Nonlinear Dynamical System Simple Pendulum Arc length Linear velocity: Linear acceleration: sin cos USC Viterbi School of Engineering Department of Computer Science Friction

3 Simple Pendulum Dynamics Let , , and let , and Rewriting previous equation: = For small angles, the above equation is almost linear (replace by ), and we can use techniques for linear systems to show stability But, for any larger angle (less than ), we know the pendulum eventually stops How do we show pendulum system is stable? USC Viterbi School of Engineering Department of Computer Science 4 Use my

method!! Lyapunovs first method Given , Step 1: find the Jacobian matrix for Step 2: Set in to get a matrix in (say ) If linear system , is stable, original nonlinear system is stable locally at the equilibrium point. (Local = exists some neighborhood of equilibrium point) USC Viterbi School of Engineering Department of Computer Science 5 Lyapunovs first method for pendulum Dynamics: =;

Step 2: Step 3: Eigenvalues of satisfy Step 1: USC Viterbi School of Engineering Department of Computer Science 6 both eigenvalues have negative real parts Pendulum is locally stable Lyapunovs second method

Method to prove global stability Relies on notion of Lyapunov Functions Intuition: Find Lyapunov function that could be interpreted as the energy of the system Stable systems eventually lose their energy and return to the quiescent state Prove that the energy of the system (as encoded by the Lyapunov function) decreases over time USC Viterbi School of Engineering Department of Computer Science 7 Lyapunovs Second Method: the math Assume w.l.o.g., that equilibrium point * is at the origin, i.e. 0 is a Lyapunov function over the domain iff: : [Positivity condition] [Derivative negativity condition] if : ,

System is stable in the sense of Lyapunov if such a exists USC Viterbi School of Engineering Department of Computer Science 8 Illustration and Lie-derivative (0) 2 1 ()

() USC Viterbi School of Engineering Department of Computer Science decreases as system evolves, i.e. for every pair of points along a system trajectory, In other words, is a decreasing function in time, or its derivative is negative semidefinite is called Lie derivative of By chain-rule, 9 Lyapunovs second method for pendulum Choose Lyapunov function

Consider ; recall, By observation, , except at , where it is 0 Lets look at the Lie derivative USC Viterbi School of Engineering Department of Computer Science 10 Second method for asymptotic/exponential stability is a Lyapunov function over the domain iff: : [Positivity condition] [Derivative negativity condition] if : ,

System is stable in the sense of Lyapunov if such a exists Asymptotic stability: Change second condition to: [Derivative negativity condition] Exponential stability: Change second condition to: or USC Viterbi School of Engineering Department of Computer Science 11 Challenges with Lyapunovs second method How do we find a Lyapunov function? Maybe use the physics of the system to understand what encodes energy For certain nonlinear systems (those with polynomial dynamics), can some algorithmic methods In general a hard problem

Yet, is a powerful approach to prove global stability USC Viterbi School of Engineering Department of Computer Science 12 Bounded signals A signal is bounded if there is a constant , s.t. Bounded signals:

School of Engineering Department of Computer Science for any Exponential signal: , for USC Viterbi Constant signal : Exponential signal: , for Sinusoidal signals: Not bounded:

13 BIBO stability A system with Lipschitz-continuous dynamics is BIBOstable if: For every bounded input , the output from initial state is bounded Asymptotic stability BIBO stability! Simple helicopter model: Two rotors: Main rotor gives lift, tail rotor prevents helicopter from spinning Torque produced by tail rotor must perfectly counterbalance friction with main rotor, or the helicopter spins USC Viterbi School of Engineering Department of Computer Science 14 Image credit: From Lee & Seshia: Introduction to Embedded Systems - A Cyber-Physical Systems Approach, http://leeseshia.org/

Helicopter Model continued : net torque on tail of the helicopter difference between frictional torque exerted by main rotor shaft and counteracting torque by the tail rotor : rotational velocity of the body Torque = Moment of inertia Rotational acceleration What happens when is a constant input? is not bounded helicopter model is not BIBO-stable! USC Viterbi School of Engineering Department of Computer Science 15 Hybrid Dynamical Systems USC Viterbi School of Engineering Department of Computer Science

16 Hybrid Process Generalization of a timed process Instead of timed transitions, we can have arbitrary evolution of state/output variables, typically specified using differential equations off 60 init 70 USC Viterbi School of Engineering Department of Computer Science ? ? 17 on Hybrid System: Thermostat

State machine with two modes (on / off) State variable models temperature can be tested and updated during discrete mode transitions changes continuously in a mode according to specified differential equation Mode invariants constrain how long machine can stay in any given mode 60 init 70 off ? ? on USC Viterbi School of Engineering Department of Computer Science 18

Executions of Thermostat 60 init 70 Initial state of the machine: (off, ), If machine enters mode off at time , during continuous transition in mode off, decreases according to: Mode switch enabled when , and must happen before If machine enters mode on at time , during continuous transition in mode on, increases according to: Mode switch to off enabled when , and must happen before USC Viterbi School of Engineering Department of Computer Science 19

off ? ? on Modeling a bouncing ball Ball dropped from an initial height of with an initial velocity of Velocity changes according to When ball hits the ground, i.e. when , velocity changes discretely from negative (downward) to positive (upward) I.e. , where is just after , and is a damping constant Can model as a hybrid system! USC Viterbi School of Engineering Department of Computer Science

20 Hybrid Process for Bouncing ball h=0 sound ! ; h [ 10,20 ] , [0,5] What happens as ? USC Viterbi School of Engineering Department of Computer Science 21 Zenos Paradox Described by Greek philosopher Zeno in context of a race between Achilles and a tortoise Tortoise has a head start over Achilles, but is much slower

In each discrete round, suppose Achilles is d meters behind at the beginning of the round During the round, Achilles runs d meters, but by then, tortoise has moved a little bit further At the beginning of the next round, Achilles is still behind, by a distance of meters, where is a fraction 0<<1 By induction, if we repeat this for infinitely many rounds, Achilles will never catch up! If the sum of durations between successive discrete actions converges to a constant, then an execution with infinitely many discrete actions describes behavior only up to time (and does not tell us the state of the system at time and beyond) USC Viterbi School of Engineering Department of Computer Science 22 How to deal with Zeno An infinite execution is called Zeno if infinite sum of all the durations is bounded by a constant, and non-Zeno if the sum diverges Any state in a hybrid process is called Zeno if: If every execution starting in state is Zeno

Non-Zeno if there exists some non-Zeno starting in that state Hybrid process is non-Zeno if any state that you can reach from the initial state is non-Zeno Thermostat: non-Zeno, Bouncing ball: Zeno Dealing with Zeno: remove Zeno-ness through better modeling USC Viterbi School of Engineering Department of Computer Science 23 Non-Zeno hybrid process for bouncing ball h [ 10,20 ] , [0,5] bounce h=0 sound ! ; h=0 < sound ! ; 0 halt USC Viterbi School of Engineering Department of Computer Science 24 Hybrid Process

Inputs, Outputs, States (both continuous and discrete), Internal actions, input and output actions exactly like the asynchronous model Continuous action/transition: ()/ () Discrete mode does not change ( , ) , ( t+ ) ( ) = satisfies the given dynamical equation for mode Output satisfies the output equation for mode : At all times , the state satisfies the invariant for mode USC Viterbi School of Engineering Department of Computer Science 25

Hybrid Process Discrete action/transition: ( , ) Happens instantaneously Changes discrete mode to Can execute only if evaluates to true Changes state variable value from to should satisfy mode invariant of Some definitions make a function of and Output will change from to USC Viterbi School of Engineering Department of Computer Science 26 / ( , ( ) ) Executions of a hybrid process

At each cell boundary, assume that the guard is the equation of the boundary, and the reset is where Invariant for each cell/mode is the open set enclosed by its boundaries Suppose initial state is (1 , 0 , 0 . 9) ( 1 , 0 . 1, 1 ) 0.1 2 ( , 0 . 12, 2 . 01 ) USC Viterbi School of Engineering Department of Computer Science (0,3) 3 4 9 (0,2) 2

5 8 (0,1) 1 6 7 ( , 0 . 11,1 . 01 ) (0,0) 0.99 ( , 0 . 11,2 ) 27 (1,0) (2,0) (3,0) Stability of hybrid systems

Hybrid systems can have surprising results with respect to stability No uniform method like Lyapunov analysis for analyzing all hybrid systems Example: Piecewise Linear (PWL) Dynamical System Special class of hybrid system, in which each mode has linear dynamics, guards, resets are all linear/affine Each mode in the PWL system can have stable dynamics (by doing eigenvalue analysis), but resulting hybrid system may be unstable! USC Viterbi School of Engineering Department of Computer Science 28 Example 2 =0 . 2 1 ? 1 100 = 10 1 (

1 10 = 100 1 ) ( 2 =5 1 ? Dynamics in each mode are stable! USC Viterbi School of Engineering Department of Computer Science 29 ) Simulation results 2 2 =5 1

2 =0.2 1 Initial State 1 USC Viterbi School of Engineering Department of Computer Science 30 Stability analysis for hybrid systems Two main approaches1,2: Find a common Lyapunov function that works for all modes I.e. for each mode , dynamics are , find such that: , and Usually hard to find a one-size-fits-all Lyapunov function Find multiple Lyapunov functions, one for each mode In each mode its Lyapunov function value decreases, and at the switching instant the destination modes Lyapunov function value does not increase value decreases every time mode is entered Finding Lyapunov functions satisfying these conditions is again hard USC Viterbi School of Engineering Department of Computer Science

31 Design Application: Autonomous Guided Vehicle Objective: Steer vehicle to follow a given track Control inputs: linear vehicle speed , vehicle angular velocity , start/stop Constraints on control inputs: Designer choice: only if , otherwise USC Viterbi School of Engineering Department of Computer Science 32 On/Off control for Path following Go straight Turn right

? ? ? ? ? ? ? Stationary

USC Viterbi School of Engineering Department of Computer Science Track Turn left 33 When , controller decides that vehicle goes straight, otherwise executes a turn command to bring error back in the interval Design Application: Robot Coordination Autonomous mobile robots in a room, goal for each robot: Reach a target at a known location Avoid obstacles (positions not known in advance)

Minimize distance travelled Design Problems: Cameras/vision systems can provide estimates of obstacle positions When should a robot update its estimate of the obstacle position? Robots can communicate with each other How often and what information can they communicate? High-level motion planning What path in the speed/direction-space should the robots traverse? USC Viterbi School of Engineering Department of Computer Science 34 Path planning with obstacle avoidance 2 Assumptions:

( , 2) Obstacle 2 2= ( 2 , 2 ) 2= ( 2 , 2 ) ( , ) Goal 1 Two-dimensional world Robots are just points Each robot travels with a fixed speed Dynamics for Robot : ; Obstacle 1 1= ( 1 , 1 )

( , 1) 1=( 1 , 1 ) USC Viterbi School of Engineering Department of Computer Science 35 Design objectives: Eventually reach Always avoid Obstacle1 and Obstacle 2 Minimize distance travelled Divide path/motion planning into two parts 1. 2. Computer vision tasks Actual path planning task

Assume computer vision algorithm identifies obstacles, and labels them with some easy-torepresent geometric shape (such as a bounding boxes) In this example, we will assume a sonar-based sensor, so we will use circles Assuming the vision algorithm is correct, do path planning based on the estimated shapes of obstacles Design challenge: Estimate of obstacle shape is not the smallest shape containing the obstacle Shape estimate varies based on distance from obstacle USC Viterbi School of Engineering Department of Computer Science 36 Estimation error 1= ( 1 , 1 ) Estimated shape from distance 1 Estimated shape from distance

Robot maintains radii and that are estimates of obstacle sizes Every seconds, executes following update to get estimates of shapes of each obstacle: Smallest shape bounding obstacle Computation of is symmetric Estimated radius (from distance d) , where is a constant USC Viterbi School of Engineering Department of Computer Science 37 Path planning

1 1 1 2 4 3 ( , ) 2 USC Viterbi School of Engineering Department of Computer Science Choose shortest path to target (to minimize time)

If estimate of obstacle 1 intersects , calculate two paths that are tangent to obstacle 1 estimate If estimate of obstacle 2 intersects , or obstacle 1, calculate tangent paths Plausible paths: and Calculate shorter one as the planned path 38 Dynamic path planning Path planning inputs: Current position of robot Target position Position of obstacles and estimates Output: Direction for motion assuming obstacle estimates are correct May be useful to execute planning algorithm again as robot moves! Because estimates will improve closer to the obstacles Invoke planning algorithm every seconds USC Viterbi School of Engineering

Department of Computer Science 39 Communication improves planning Every robot has its own estimate of the obstacle s estimate of obstacle might be better than s Strategy: every seconds, send estimates to other robot, and receive estimates For estimate , use final estimate = Re-run path planner USC Viterbi School of Engineering Department of Computer Science 40 Improved path planning through communication New path available

because estimate of obstacle 1 improved after receiving estimate from 1 1 1 2 4 3 1 ( , ) 1 1 (0) 2 1 () School of Engineering Department of Computer Science

4 3 2 Old path USC Viterbi 2 ( , ) 41 Hybrid State Machine for Communicating Robot USC Viterbi School of Engineering Department of Computer Science 42

Advantage of using hybrid processes Hybrid process combines computation, communication and control Elegant machine that exemplifies the basic operation of a cyber-physical system Allows design-space exploration through simulations and reachability analysis We can check effect of parameter choices on the behavior of the system USC Viterbi School of Engineering Department of Computer Science 43 Bibliography 1. Alur, Rajeev. Principles of cyber-physical systems. MIT Press, 2015. 2. H. Lin and P. J. Antsaklis, "Stability and Stabilizability of Switched Linear Systems: A Survey of Recent Results," in IEEE Transactions on Automatic Control, vol. 54, no. 2, pp. 308-322, Feb. 2009.

3. Branicky, Michael S. "Multiple Lyapunov functions and other analysis tools for switched and hybrid systems." IEEE Transactions on automatic control 43.4 (1998): 475-482. 4. Slotine, Jean-Jacques E., and Weiping Li. Applied nonlinear control. Vol. 199. No. 1. Englewood Cliffs, NJ: Prentice hall, 1991. USC Viterbi School of Engineering Department of Computer Science 44