LESSON TRANSCRIPTS (videos not available):

Lesson: Modeling Translational Mechanical Systems

0:06

Now the question that we should ask ourselves is so far all the examples I've presented, they were some discrete
systems, sequential circuit or vending machines. They have discrete behavior. Now the question of interest is,
what if you are interested to model physical systems using the notion of system I have introduced? Many
systems around us are actually physical system. For example, if you look at the self driving car, if you look at the
behavior of a self driving car, so it's a physical system and the modeling framework for modeling a self driving
car it's going to be much more involved. Now first let's look at the physical system, and how they can be
generally modeled using some mathematical puts. For example, let's say you're interested in model translational
mechanical system. If you recall from your undergraduate or even physics in high school, you got exposed to
Newton's Law. Newton's Law says the summation of the force applied to a mass is equal to the mass times
acceleration, or mass times second derivative of displacement with respect to time. Let's look at this simple
example. You're looking from the top, there is a mass underground. Let's assume there is no friction. This math is
connected with a spring to your [inaudible] and we assume the displacement in this direction is actually the
positive displacement. Very good. Now, what are the force applied to this mass? In fact, if the displacement is
positive, because the mass get a stretch, so the force is actually in the opposite direction of the displacement. If
you recall, usually for spring, the force that spring applies to the mass is equal to the spring cofficient K times
the displacement of the mass. With the negative minus K times displacement with respect to time. Now we apply
Newton's law. We know that the mass times acceleration based on the nets law is equal to -K x(t). Now if we
multiply both sides of the equality, the acceleration of the mass is equal to minus the cofficient of the spring
divided by the mass times the displacement itself. You see what is this object. Now I have a second order
differential equation describing the displacement of the mass. Of course, this is a different modeling framework.
By no means this is a notion of system that I have introduced so far. This is a differential equation, but that's fine.
Later on I will tell you, how can we grab this modeling framework, this differential equation, and represent it as
a notion of system that I have introduced previously. This is another example. What if there is a force applying to
the math and poling the mass in this direction, in the same direction as displacement? In this case now we have
two forces being applied to the mass. One is from the spring, which is downward, the other one is the external
force, which is toward, upward. Again, the same idea. Times the acceleration of the mass is equal to f-K times
displacement. Then we divide both sides of the equality. Then we get this new differential equation that simply
says the acceleration of the mass is equal to -K/M*x(t)+F, which also can be a time varying force divided by the
mass. This is now a second order differential equation. Let's say I am interested in first order differential
equation, but that's easy. What I can do is I can actually introduce two state variables. One is called x_1t, which
is simply the displacement itself. The other one x_2t, which is the velocity of the mass. Now if I rewrite this,
second order differential equation in this vector form. Based on this introduced state variable x_1 and x_2, what
do I get? I get that this vector, the derivative of this vector, x_1, x_2 with respect to time, is equal to the two by
two matrix times the vector x_1, x_2 plus this constant metric times the external force. This is called in many of
the control theory literature, this is called state space representation of this mass spring. Example, so you see is
first order differential equation, but it is a vector differential equation is not anymore a scalar type differential
equation.
Play video starting at :6:16 and follow transcript6:16

Let's look at actually this simple example. Let's say we are interested to model quarter car suspension as a
differential equation. Again, I reiterate that here we are first modeling physical system as differential equations
by using newton's Law. Then later on I will tell you how these differential equation modeling can be transferred
to the modeling using the notion of system which I introduced previously. In this case we have two masses. One
is the quarter of the body of the car. I have M/4. M is the mass of the car. Then it's displacement is x_c.

Play video starting at :7:28 and follow transcript7:28

How many forces are being applied to this? Let's say two forces. One from the spring, the other one is from the
damper. Let's call it f_1, f_2. Now I have another mass which is the wheel mass m. Which forces are applied to
this? There is one force downward, which is the spring with the coefficient K_t. So I call it f_3. Of course f_1
and f_2 are also applying to this mass, but to the toward up f_1, f_2. Since we are using newton's Law, this is
translational modeling. We can actually decompose due to the linearity property. Meaning that I can write, apply
Newton's Law first on the mass with the M. I apply newton's law to the math with a m and then I can combine to
come up with a model of this quarter car suspension.

Play video starting at :8:54 and follow transcript8:54

Here. Let's write the, what is f_1?

Play video starting at :9:3 and follow transcript9:03

F_1 is equal to, let's look k_s times, what was the displacement of the small mass? That was X_w.

Play video starting at :9:37 and follow transcript9:37

F_1=K_s*X_c-X_w, what if two? As you know the force of the damper is proportional to the velocity, not the
displacement itself. If 2=C_s*X_c. Dot means derivative with respect to time X_w dot. What about if 3=2, so
what was the coefficients of the K_t?

Play video starting at :10:21 and follow transcript10:21

Let's write the Newton's law first with the mass thing. Then the acceleration which is X_w double dot with
respect to time is equal 2. I have f_1+f_2-f_3. Which is equal to K_s(X_c-X_w) + C_s( X_c dot minus k_t X_w
dot-K_t. Now we write the newton slow for your mass.

Play video starting at :11:29 and follow transcript11:29

Then I have m divided by 4x_c double dot is equal to -f_1-f_2 which is equal to k_s (x_w-x_c)+c_s (x_w dot

Play video starting at :12:5 and follow transcript12:05

-x_c dot). I can of course, divide both sides of the equality by the corresponding masses. Then I get these sets of
differential equation Thus c_s divided by m. Again,
Play video starting at :12:34 and follow transcript12:34

I have two second order differential equation. Now what I can do is I can introduce again for state variable
x_1(t)=x_w, and then x_2(t)= x_w dot, and then x_3(t) = x_c, and x_4(t) = x_c dot. By introducing these four
state variable, now, one can readily actually verify that if you put them in a vector x_1 dot equal to a matrix, it's
a four by four matrix times the vector containing all those state variable. Because I'm interested in a first order
differential equation. What are the entries of this matrix? Let's see. X_1 dot = x_w dot, and we know x_w dot is
actually x_2. That's easy, 0, 1, 0, 0. What about x_2 dot? X_2 dot is x_w double dot, which is equal to k_s by n
x_c. Let's see, x_w - k_s/m - k_t/m - c_s/m. K_s/m.

Play video starting at :15:16 and follow transcript15:16

The last entry is c_s/m.

Play video starting at :15:28 and follow transcript15:28

X_3 dot which is equal to x_c dot, which is actually our x_4. That's easy, 0, 0, 0, 1. Eventually x_4 dot = 2. Now,
I'm looking at this equation, look at this double star. I am using this to find the entries of the matrix. By the way,
later on I will show you how sets of first order differential equation. I'm going to use them to actually represent
these mechanical system via a notion of system which I have introduced in this class. At the end of the day, I
would like to convince you that the notion of system I introduced in this course is general enough that can model
beverage vending machine, sequential circuit, turnstile, as well as actual mechanical system. Here let's fill out
the last row of this matrix.

Play video starting at :16:39 and follow transcript16:39

4/m and then minus or plus 4c_s/m -4k_s/m -4c_s/m. Here

Play video starting at :17:9 and follow transcript17:09

I was able to model order car suspension using these four dimensional first order differential equation.

Lesson: Modeling Rotational Mechanical Systems

0:05

As in the previous slide, one can also model rotational mechanical system using Newton's law. In this particular
case, Newton's law says the summation of torque applied to the mask is equal to J, which is the moment of
inertia of the system times angular acceleration. J times second derivative of Theta with respect to time. That's
the summary of Newton's law for rotational mechanical system. Let's look at this example of a rotational
mechanical system containing two of these. In this case, we have two angle. Angle of Disk 1 and Disk 2. Here is
one and here is two other torsion stiffness. As you know, the force, if you have torsion stiffness, the force
actually due to that is equal to torsion stiffness times the angle of the disc in this case. This is very similar to the
damper in the previous example of the spring case. In the spring case you had the force was equal to springer
coefficients times the displacement. In this case, the force is equal to torsion stiffness times angle. Now let's
actually apply Newton law to this example. If we look at disc number 1, how many forces are being applied?
One, through the torsion stiffness is one due to the angle Theta_1, and the other one is due to torsion stiffness is
two and the difference of the angle Theta_1 and Theta_2. Let's write that. For disc number 1, I have two torque,
one. So to Torque 1 minus Torque 2 is equal to, so -S_1 Theta_1 because the torsion stiffness is acting against
the movement of the disc. Plus is 2 times Theta_2 minus Theta_1. Now we can also apply Newtons law to disc
number 2. In this case t_2 is equal to -2 times Theta_2 minus Theta_1. Now if we substitute rather than t_1 and
t_2. We can write J_1 second derivative of Theta_1 and rather than t_2, we can write J_2 second derivative of
Theta 2. In this case, the equation boils down to this second order differential equation. J_1 Theta_1 double dot
is equal 2 minus S_1 Theta_1 plus S_2 times Theta 2 minus Theta 1. J_2 Theta_2 double dot is equal to -2
Theta_2 minus Theta_1. Again, this is a second order differential equation, we would like to write it as a first
order differential equation. The same as previous examples we did, we introduce new state variables. Namely,
we call Theta_1 to be x_1. Theta_1 dot to be x_2, Theta_2 to be x_3, and Theta_2 dot to be x_4. We put x_1,
x_2, x_3, x_4 in a vector. This is our state vector. Now if we write these differential equations using these new
state variables, we get the x_1, x_2, x_3, x_4 dot is equal to this matrix times the state vector itself. As you can
see, the elements of this matrix are based on the characteristics of the rotational mechanical system. Namely, a
momentum in ratio of Disk 1 and 2 and the torsion stiffness 1 and 2. The bottom line is we are also able to model
rotational mechanical system as a first order differential equation of this form. Again, later on I will show you
how these types of models, first order differential equation in a vector form can be also described using the
notion of system I introduced in this course.

Lesson: Modeling Analog Circuits

0:06

What about modeling electrical circuits, namely analog ones? Actually, we can actually leverage similar rules as
what we have for the mechanical circuit to actually model electric circuit as well. The math is very similar. If
you look in the electric law, voltage across an inductance is given by this formula, V(t) is equal to the inductance
coefficients times derivative of current with respect to time, i dot of t, which i dot of t is equal to second
derivative of accumulated charge with respect to time. This is very close to the force being equal to M, second
derivative of displacement. What about voltage across a resistor? V(t) is equal to simply the resistor coefficient
times current, and current is equal to first derivative of accumulative charge with respect to time, so is R*q dot.
Now you have similar things for the force when you have a damper. Is the damper coefficient times
displacement derivative with respect to time. What about voltage across a capacitor? Again, V(t) is equal to 1
divided by capacitor coefficients integral of the current with respect to time. An integral of current with respect
to time is simply accumulated charge itself. This is equal to exactly what we had in mechanical law. If you have
a spring, what is the force of the spring, is equal to spring coefficients times displacement. If you recall, in case
you have taken any courses in circuit theory, we know that based on Kirchhoff law, the summation of voltages in
a loop is equal to zero. If you look at the loop, the summation of all the voltages in that loop should be equal to
zero. This is actually equal to what we call Newton's law. The summation of forces applied to a mass is equal to
zero.

Play video starting at :2:34 and follow transcript2:34

In this case, one can actually analyze mechanical systems and hydraulic ones very much in the same way as
electric ones and vice versa. You can see this duality between mechanical law and electric law also.

Lesson: Modeling Example: Electric Passive Filter

0:07

So, as an example, let's actually look at this electric passive filter containing two inductor, two capacitors and see
how can we actually model this this LC circuit, right? So what we're going to do, we're going to apply the the
law that I explained in the previous slide to be able to actually model this circuit, okay? So if you look at the
inductors, we have two inductors, right? L1 and L2, so what is the voltage across the inductor is equal to L times
derivative of current with respect to time. So what about the capacitor? So in the case of capacitor, current going
through the capacitor is equal to C times derivative of voltage across the capacitor with respect to time. So, if
you recall from, if you have taken courses on differential equations, in particular linear differential equations,
there are actually ways of solving differential equations and one of them is by using what is called Laplace
transformation. So, the concept is very easy. For example, if you have a signal in time, its Laplace
transformation in s domain is equal to integral from 0 to infinity. The function in time f(t)e to the power -st dt.
And these are some of the nice property of Laplace transformation. Laplace transformation of the derivative of a
function with respect to time is equal to s times F(s) minus the function itself at time 0. What about the Laplace
transformation of second derivative of F with respect to time? So it's equal to s to the power 2, its Laplace
transformation- s times the function itself at time 0 minus its derivative at time 0. So you see, one of the
beautiful things about using Laplace transformation is we can actually get rid of the derivative operator and
everything become algebraic equations, right? So, for example, in the case of inductor, so we have v(t) is equal
to L times derivative of current with respect to time. So now let's take Laplace transformation from both side of
the equality. So what do we get? V(s) equal to L times, so what is Laplace transformation of a derivative of
current with respect to time? Is s times I, capital I(s), which is Laplace transformation of i(t). So here I assume
the current at time 0 is equal to 0. To make the modeling simpler, we assume that all the initial conditions in the
circuit are equal to 0. So let's look at the capacitor i(t), the current passing through the capacitor is equal to c, the
derivative of the voltage across the capacitor with respect to time. So now, if we put this into the Laplace
domain, we get capital I(s) which is Laplace transformation of i(t) is equal to sCV(s). Here again, I assume the
voltage in time domain across the capacitor at time 0 is equal to 0. So if we have resistors in the circuit, which in
this example we do not have any resistor, we have two inductors, we have two capacitors, and a voltage source.
But in general, if you have also resistors in the circuit, so we know that in time domain the voltage across the
resistor is equal to its resistance times the current going through it. So now, if we put this in Laplace domain, we
get capital V(s) is equal to R times capital I(s). So now what we're going to do to model this electric passive
filter, so what we're going to do, we're not going to work in time domain. What we're going to do, we're going to
work in Laplace domain, solve systems of equation in Laplace domain and then we go back to time domain. So
let's see how that works. Okay, so now you see, I am working in the Laplace domain, so V(s). So V(s) is the
voltage of the source is equal to so now what I'm going to do, I'm going to apply Kershaw flaw, right? Is equal to
I1(s) passing through the first inductor L1 s plus, so now the current I1 pass through C1, right? 1/C1s times I1(s).
And then what is the current passing through C2? Is I1 minus I2. I1 coming this way, I2 goes this way, their
subtraction is the current passing through C2. So then I have 1/C2s multiply I1(s)- I2(s) that's the current passing
through C2. And this is what we get by going through this first loop. So now if we go through this loop, what we
get is I2(s), L2, this is L2. So I2(s) times L2 times s = 1/C2s. Again, what is the current going through this
capacitor? Is I1(s) minus I2(s).
Play video starting at :6:38 and follow transcript6:38

So now, if we denote, if again, remember, we need to define some state variables. So if we denote two state
variables, X1(s) = I1(s)/s, remember here we are actually considering the accumulated charge as the state
variable in this circuit. And the same thing X2(s) is equal to I2(s)/s. By introducing these two state variable, now
I can actually simplify this algebraic equation. You see, that's the good thing about working in Laplace domain.
So we get rid of all the derivatives and everything we are dealing with is a simple algebraic equation that we
need to solve. So by introducing these two state variables, so now one can write L1s to the power 2 X1(s) is
equal to this equation and L2s to the power 2 X2(s) is equal to this. So you see what happened. We actually solve
an algebraic equation in the Laplace domain by looking at this new state variable we have introduced, right? So
now we have all the ingredients. So what we do is so now we take the inverse of Laplace transformation and we
go to the time domain. So if we go to time domain, remember s2 X1(s) is actually the same as second derivative
of X1 in time. Again, s2 times X2(s) is the second derivative of X2 with respect to time. Here, of course, we
assume that all the initial conditions are 0 to reach to this from the Laplace domain to go to time domain. Same
thing here- 1/C1 X1 of t- 1/C2 X1 of t- X2 of t + v(t). And in this case we get 1/C2 X1 of t- X2 of t. Now we
have two second order differential equation. The question is, can you transfer the above set of second order
differential equation to a set of first order differential equation in a vector form? Remember, you have to
introduce new state variables to be able to transfer this set of second order differential equation to a set of first
order differential equation in a vector form. So, okay, let's see how can we actually transform this set of second
order differential equation to a set of first order one in a vector form. Okay, what I'm going to do is I said, okay, I
introduced this state variable X1 hat of t = X1 of t. So now I can write this in a vector form X1 hat, it's going to
be a four by four matrix times the vector of new introduced state variable, namely X1 hat, X2 hat, okay? So X1
hat dot is equal to X2. So that's easy 0, 1, 0, 0 and X2 hat dot is equal to X1 double dot, which is so which is
equal to -1/C1L1 and -1/C2 L1. So that's X1. And we also have X2, which is X3. So then it's 0, 1, C2L1. Again,
0, here is also 0, 0, 0, 1. And the last row is 1/C2L2, 0, and then -1/C2L2, and then 0. And then we have plus a
vector 0, 1, 0, 0 v(t). So that's how we write this set of second order differential equation as a first order
differential equation in a vector form.

Lesson: Modeling Example: Cart With iInverted pPendulum

0:06

So another example of a physical system is cart with inverted pendulum. This modeling framework is actually
very powerful and has been used a lot in many application including like, sending rocket out of a space. So,
similar modeling will be used in those cases as well. So, if you look at the figure on the right hand side, we have
a cart in which there is an inverted pendulum. On top, there is a mass connected through a rod, to the base of the
cart. So the idea is the cart is moving toward left and right and the goal is to keep small mass m in the upright
position. So, let's assume capital h and v be the horizontal and vertical forces exerted by the card on the
pendulum. So now, I'm not going to go into the details of how this model is exactly getting extracted. But if we
apply the Newton's law, to the linear movements of the cart. So then what we have is capital m is the mass of the
cart, right. Times its acceleration is equal to u, the external force on the car minus h. H is the horizontal force
exerted by the cart on the pendulum. So now if you write Newton's Law, so what you get is h is actually equal to
this term m times the second derivative of y plus l sine theta with respect to time. And then you can expand it
and then you get this nonlinear term. And then, also if you look at the vertical case, mg- v is equal to this, which
you get this nonlinear term, right? So, you can also apply Newton's law to the rotational movement of the
pendulum, along the upright position. So then you get a movement of the pendulum around the hinge and then
you get this nonlinear equation.
Play video starting at :2:22 and follow transcript2:22

So, now let's go to the next slide. So, the previous equations are of course nonlinear. We had sinus term, we had
theta dot to the power two, we have theta times theta dot. So, since the design objective in many of the examples
modeled using inverted pendulum. For example, sending rocket is to maintain the pendulum at the vertical
position, we can assume that. So if this, you see this small mass m is very close to the vertical position. So that
means theta, and theta dot are very small. So now under this assumption that theta and theta dot are small.

Play video starting at :3:10 and follow transcript3:10

So then we can assume that sine of theta, is equal to theta. If theta is a very small angle, its sine, sinus is actually
equal to the angle itself. And the cosine of theta is also equal to one in that case. So now we can also drop these
terms, because these terms are going to be very small like theta to the power two. If theta is very small, power
two is going to be small, the same thing with other terms. So now, under this assumption, by removing this term.
And assuming that sine of theta is equal to theta and cosine of theta is equal to one. So, the equations in the
previous slide actually boils down to this nice linear second order differential equation. So again, you see we
have a set of second order differential equation. So remember, according to previous sessions, one can actually
using by introducing several state variables. We can actually write this as a first order differential equation, but in
a vector form. And these are the new state variables. I introduce y, I put it equal to x2 of the y dot is equal to x2,
theta is equal to x3, theta dot equal to x4. Now, if I put x1, x2, x3, x4 in a vector. So now I come up with this
first order differential equation in a vector form. So, the derivative of a state vector, with respect to time is equal
to this matrix. You see, many of the parameters of this matrix are zero and the nonzero. One depends on the mass
of the small mass on the on the rod and the big mass of the cart. And the gravitational acceleration plus the
lengths of the rod. Plus a constant vector, which also depends on the mass of the cart and the lengths of the rod
times u(t). U(t) is the external force applied to the cart.

Lesson: Modeling Sample-and-Hold Linear Systems As Systems

0:05

So far we were able to actually model many physical system, even electrical circuits using first order differential
equation, both in a vector form. To do so we leverage Newton's Law for either translational or rotational
mechanical system. Or we use the counter parts of them for the electric circuits. Then we were able to use
Newton's Law or [inaudible] law to drive those systems of first order differential equation in the vector form.
But then the catch case those first order differential equation in vector form, by no means they are actually in the
form of the notion of system which are introduced in the beginning of this course. Now the question of interest
that we have to answer is, how can we model this differential equation as a notion of system? Let us consider the
continuous time linear system described by this first order differential equation, which is in the vector form.
Here, z of t z is a vector containing a state variables. You see, z is a signal in time. Its domain is time, but co
domain is a vector which is N dimensional. This is our state signal which is continuously changing with respect
to time.
Play video starting at :1:48 and follow transcript1:48

New is our control input, which is also changing every time, and its domain is non-negative real number and the
co-domain is m dimensional vectors. That's the input to the system. Now what we do is we sample this
continuous time system with a sampling time which is positive real numbers. We apply a constant input within
the duration t, to obtain a discrete time version of this system. Look at this diagram. Here we have our original
continuous time linear system, which is evolving in continuous time. Now what we do is we actually measure
the state trajectory of the system with the sampling time T. What comes out of it is actually a signal which is
discrete in time. We also put what is called zero order hold before the plant, because the plant, the input to the
system has to be a continuous time signal. What we do is we put a zero order hold box before the system. The
role of the zero order hold is it gets discrete input values. Then it keeps those discrete input value constant within
every duration T. Now if you look at this system within this dash box, so this is actually called sample hold
version of this continuous time system. Now if you look at this sample and hold version of this original
continuous time system, we can now model the sample and hold version simply using an infinite simple system
of this form. Let's see what are the tops of this simple system. X is equal to our estate set, which is R^n and we
assume that every estate can be also initial estate is also equal to R^n, what is external input? U. Remember the
input signal? It was a signal which was changing in time and it was providing a vector which was M
dimensional. Then the external input set is R^n and the main ingredient is actually the transition function. How
this transition function F is defined actually based on this linear differential equation, so you see starting from
state X under a constant input, F(x,u) is a single point which is computed using this mathematical equation, so
E^AT. Remember T was the sampling time, and this matrix A is the same matrix appearing here. This is actually
an exponential matrix. E^AT, E is in fact a constant, N by N matrix times the initial state plus. This is also an N
by N matrix which is also constant and can be computed times B which B is N by M. Then we have a N by N
times N by M, which gives us an N by M a matrix, and then times the constant input U. You see that's how the
sample and hold version of a linear control system described by this first order differential equation in the vector
form can be modeled using a simple system which is infinite. Why it's infinite? Look at the set of a state and the
set of input. They are dimensional and dimensional, euclidean space which are actually also uncountable.

Lesson: Timed Automata: Syntax

0:07

Sometimes timing information is also very important when we are modeling systems. For example, let's say we
have sequence of events right here. I know that initially we start from states 0 under label S_1 we go to Z_1.
Under S_2, we stay in Z_1 or under S_1 we go back to Z_0. Here, if you look at this state diagram, no
information about the period of time between events is disclosed. For example, if you look at here, we are in
state Z_0 and there under action S_1 we go to Z_1, we stay in Z_1, and there under action S_2 we stay in Z_1,
and then under action S_1, we go back to Z_0. You see if you look at this state diagram, we have no idea how
long the system was in state Z_0, how long it was in estate Z_1. So the timing information is not provided. So
the question is, is timing information required? Yes. In some application we would like to know how long has
been passed since, for example we've been in a particular state. Look at this physical case study. So we have this
water level control. Now, the controller is in charge of switching the pump on and off. Depending how long the
pump is on or off, that will actually affect the height of the liquid inside the tank. In this case, delay in switching
the pump results in switching appropriate levels of the liquid inside the tank. In this case, quantitative time
information is needed. We need to know how long the pump was on or off. One of the most important modeling
framework which has been leveraged in the autonomous systems and cyber physical systems community is
called timed automata. First what I will do is I will introduce syntax and semantics of time automata. Then later
on I will show how a timed automata can also be represented as a notion of system I have introduced in this
course. Timed automata introduce a finite set of real valued clocks. Clocks can reset to zero by discrete
transitions. They show the time elapsed since the last transitions, and the transitions are also labeled by time
conditions. Let's first look at some examples. Even though I have not introduced the syntax of time automata,
let's dive into some case study to get familiarized and then we dive into the syntax of time automata. Look at this
example, example 1. This is a time automata, it has two location Z_0, Z_1. Let's see how we read. We go from
location Z_0 to Z_1 under action a and when we take this transition, the clock variable x get reset to zero. Or we
can go from Z_1 to Z_0 under action b as long as clock variable x is less than two. That's how we read these
labels on the transitions. This means what? Means the delay between action a and action b is smaller than two.
Why is that? Because when we took this transition, the reset got zero, and then if we take this transition, the time
has to be less than two seconds. That means the delay between a and b is smaller than two units of time. Let's
look at this time automata. How many locations we have. We have four locations, Z_0, Z_1, Z_2 and Z_3. We
can go from location Z_0 to location Z_1 under action A and in that case the clock variable number 1 get reset to
zero. We can go from location Z_1 to Z_2 under action B, and in that case, second clock variable get reset to
zero, not the first one, the second one, meaning that the first clock variable is still running. We can go from
location Z_2 to Z_3 under action c if the first clock variable is less than one unit of time. Finally, we can go from
location Z_3 to Z_0 under action d if second clock variable is bigger than two units of time. Now, based on this
time automata,
Play video starting at :5:48 and follow transcript5:48

you see the delay between a and c is not larger than one. Why is that? Because if we take action a from location
Z_0 to Z_1, first clock variable get reset to zero. Then if you're supposed to take this transition from Z_2 to Z_3,
that can only happen if the first clock variable is less than one. That means the delay between, we see, action a
and action c is not larger than one units of time. What about the delay between seeing action b and d? Look what
happens. If we are supposed to take this transition from Z_1 to Z_2 under action b, the second clock variable get
reset to zero. If you are supposed to take the transition from location Z_3 to Z_0, that can only happen if the
second clock variable is bigger than two units of time. This means the delay between seeing actions b and d is
definitely not smaller than two units of time. Now let's look at the syntax of timed automata. Timed automata
simply is this object which is a tuple containing, let's see what are all these components and elements are. What
is L? L is a finite set of locations. L_0 is a set of initial locations. U is a finite set of actions. What is C? C is a
finite set of clock variables. Here we can have n clock variables, each of them is a scalar. What is in invariance?
Invariance is a map from location to P. It's called invariant assignment function. What is P? P is a set of timing
conditions of this form. For example, clock variable j less than or equal to q, or clock variable j being greater or
equal to q, where q is a rational number. Note that we can also have negation of p, or we can have "and" of two
timing condition to actually develop more complex timing condition. If we go back to the previous examples,
you see these are the timing condition. If second clock variable is bigger than two, then I can take a transition
from location Z_3 to location Z_0. Or here, if the first clock variable is less than one, I can take the transition
from location Z_2 to Z_3 under action c. You see how the timing conditions are actually allowing us to take a
transition between different locations. You can actually have then "and" of two timing conditions. For example,
X_1 less than one and X_2 bigger than something. What about the arrow? That is actually the state transition
relation. Formally, the state transition relation is simply this tuple. You see the element inside the state transition
relation, or the tuple of this form. How do we read that?
Play video starting at :9:46 and follow transcript9:46

This tuple belongs to a state transition relation of the timed automata, which means l is the current location, l
prime is the next location, u is the input symbol, p is enabling conditions; why there's a timing conditions on top
of the transitions, an C_ res means those subset of clock variables which get reset to zero by taking the transition
from l to l prime. Again, I read how this tuple belongs to the transition relation, if I can go from location l to
location l prime under input symbol u, as long as the timing condition p is satisfied. When I take this transition
from l to l prime, a subset of clock variables get reset to zero. That's how we read these elements inside the state
transition relation.

Play video starting at :11:3 and follow transcript11:03

Now let's see how the semantics of the timed automata is defined. Namely, how does timed automata evolve?
How it's behavior, the state run of timed automata, how do they evolve? Of course timed automata get initialized
at the initial location, and initially all the clock variables are equal to zero. Then if the timing condition p
evaluates to one, and the invariance of the current state is valid, then we take a transition and the transition can
be executed. In that case, all assigned clocks, is remember a subset of clock variables, might get reset to zero,
they get reset.

Play video starting at :11:56 and follow transcript11:56

Now let's look at the state run of the time automata, so r is a state run of timed automata. When you say state run,
so what are the information we need to keep track, location and clock variables. Look at this pair. The first part is
denote location, the second one is a vector containing all the clock variables. The same thing, location l_1, x_1 is
the vector containing all the clock variables and so on, so forth. Very good. I go from l_0, x_0 under u_1 to l_1,
x_1. First, if in variance of location l_0 is valid, x_0 satisfies the timing condition from transition from l_0 to
l_1. In addition, subsets of those clock variables in this particular transition get reset to zero. Again, I repeat, so
this can be a state run of time automata if for all i bigger than equal to one, the transition of this form exists such
that, so in variance of l_i-1 is valid, x_i-1 satisfy the timing condition p_i.

Play video starting at :13:37 and follow transcript13:37

If clock variable, the jth clock variable is inside a subset that are supposed to get reset to zero, so the j
component of the clock variable in the next pair is equal to zero and the rest remain as what it was previously. I
should also emphasize that invariants are the only means to force the transition to be taken. Let's have a recap of
how do we actually interpret the time automata or how they stay to in a state run containing pairs of location and
clock variables can be interpreted based on a time automata. Initially time automata get initialized at location l_0
and all the clock variables are equal to zero. Then you see is there a discrete transition from location l_0 to
another location? You will take that discrete transition if invariants of location l_0 is valid and the timing
conditions on top of the discrete transition from l_0 to l_1 is also valid, and input action is the corresponding
symbol on top of that discrete transition from l_0 to l_1. If you take this transition, subsets of the clock variables
get reset to zero. Which subset? Based on what is being reported on top of that particular discrete transition from
location l_0 to location l_1. In summary, if you are given such a particular state run, which simply it's a pairs of
location, vector of clock variables, location, vector of clock variables, location, vector of clock variables. Is this
a potential state run of the time automata? It can be if for every i bigger than equal to 1, this transition exists
inside time automata such that invariants of l_i-1 is valid and clock variable i minus the clock variable at
iteration i-1 satisfies the timing condition p_i. In addition, if C_j, if j indices of the clock variables is inside those
subset of clock variables, which has to get reset to zero, then when you go from here to here, j entry of those
clock variables should get reset to zero and the rest remain as what is inside x_0. You repeat these recursively
and then you have a valid state run of time automata. What's the role of invariants? Invariants are the only means
to force transition to be taken, meaning that if you're in a location and the time is elapsing, so keep in mind that
you are not forced to take any discrete transition. You can stay in that location. But keep in mind that the
invariance in that location might get violated. The moment the invariance is going to get violated, you're actually
forced to take the transition from that location before the invariance gets violated. That's the main role of the
invariance in a time automata.

Lesson: Timed Automata: Semantics

0:06

So let's look at this example and see if this can be a possible run of this time automata. So in this time automata,
we have four locations and the transition discrete transitions are given with their corresponding if the clocks get
reset and the timing condition, okay? Let's see if this state run can be potentially a run of this time automata,
okay? At time 0, we start from location z0, which is correct. And we have two clock variable, x1 and x2 they're
both 0, so far so good. So under action a, I go to location z1, okay? That can be correct. But then let's look at the
clock variable. The first clock variable is 0, which makes sense. Why? Because if I take this discrete transition
from z0 to z1, the first clock variable gets reset to 0, so that's compatible. And the second clock variable is 2, that
also can be true. Why? Because when I go from z0 to z1, the second clock variable doesn't get reset to 0. So 2
possibly can be the value of the second clock variable, so far so good. So under action b, I go to location z2, still
compatible based on the syntax of the time automata. And then let's look what happens to the clock variable. The
first clock variable is 0.7. I mean, it's possible because when I take this discrete transition, first clock variable
doesn't get reset to 0. And then you see the second clock variable is equal to 0, which is also compatible, because
by taking the discrete transition under b from z1 to z2, second clock variable is actually get reset to 0, okay? So
far so good, this can be a potential, let's say, drawn out this time automotive mode. So, let's see, from z2 under
action c, we go to z3. Is that possible? Yes, and then this is the amount in the clock variable. So the first clock
variable is 0 8. Is that possible? Yes, remember, we can only take this discrete transition if the first clock variable
is less than 1. And here is reported 0 8, it's compatible. And the second clock variable is 0.1. Still possible
because neither first nor the second clock variable get reset to 0 by taking discrete transition from z2 to z3, okay?
And then finally, under action d, we go from location z3 to z0, that's possible. And let's look at the clock
variables. The first clock variable is true. It's quite possible, right? Because going from z3 to z0, there is no
condition over first clock variable. And because the first clock variable has not gotten reset to 0. So then 3 can be
a possible value. What about 2.3? So it's also okay. Why? Because, you see, we take the discrete transition from
z3 to z0 under action d, if the second clock variable is bigger than 2, which here reported 2.3 and we continue
this. So then you see this state run here reported can be a potential state run of this time automata. Let's look at a
realistic example and see which type of scenario we can actually model using time automata. So, time automata
in fact has been used widely in real time system community because they use time automata to model real time
scheduling. So, here is an example. In many safety critical applications, the execution of software tasks need to
be completed in a timely fashion. And this timeliness is typically formulated by equipping each software task
with what is called worst case execution time, denoted by capital C here, a relative deadline, denoted by capital
D. And in the case of periodic task, which is the point of discussion here a period capital T. This formulation
entails that a task becomes active every capital T units of time and its execution must finish no later than
deadline capital D. After becoming active, a scheduler is a special task that decides which of the active tasks
should be executed by the processor. The decision process takes into account the period, relative deadline, and
the fact that the execution may take, in the worst case, C units of time to complete. A set of tasks is said to be
schedulable if it can be executed without violating any of the deadline. Of course, we assume that the worst case
execution time is less than deadline and deadline is less than capital T units of time. So that the task execution
can finish before the relative deadline and before the next activation. We also assume that the task cannot be pre-
empted, meaning that once the execution starts, the task runs to completion. So now, let's see how can we
actually model these scheduler tasks using a time automata? Here, we can actually model this scheduling using a
time automata. So, our time automata has four locations. So first location is called the sleep. So the scheduler is
sleeping and we introduce two clock variable PSI 1 and PSI 2. For now, just ignore about this PSI1.= to 1 and
PSI2.= to 1. This just simply means the clock variables are evolving with the realistic time, right? Continuous
time. So, you see, initially both clock variables are 0, scheduler is a sleeping and the invariance of this location
says clock variable number 1 between 0 and capital T. So, what happens is, okay, the clock variables are both
evolving. And the moment the invariant of this location sleep is going to get violated, when Zygon reached to
capital T, are forced to take this transition and the scheduler gets awake. Remember, the scheduler works
periodically with the period T units of time. So now the scheduler gets active. So in the case zi1 become = to T
and then the scheduler goes to the active location. And the first clock variable gets reset to 0. Why is that?
Because the scheduler works every T units of time, so the period gets activated. So now again, we reset the clock
variables because we want to ensure that the tasks get executed before the period is going to finish.
Play video starting at :8:24 and follow transcript8:24

So now we are in location active. Still the clock variables are running. The first clock variable gets reset to 0. So
you see the invariance of this when the scheduler is active. So look at the invariance of this location says first
clock variable bigger than equal to 0, less than equal to D. So what happens is if we are in the active location and
you see if the first clock variable which got reset 0 here, if it reached to D before the task getting executed. So
that means the deadline has arrived and the task is expired and we go to the error location. Why? Because the
scheduler was not able to execute the task, the deadline arrived and that's an error, right? So you see, if the first
clock variable reached to D and we have not moved to execution task, then the task is expired and we go to the
error location. What if before Psi1 reached to T, the scheduler start executing the task? Okay, now in this case we
assume that Psi1 is definitely less than D. The deadline has not arrived. So we take this transition, right? So now
we set the second clock variable to be equal to 0. Why is that? Because now we need to consider the time it takes
to execute the task and we need to keep in mind that we still have a deadline D that we need to respect. And in
the worst case, the execution of the task can take C units of time. Okay, so the second clock variables, that's the
main role of the second clock variables is take into account how long it takes to execute the task. So we are in
this discrete location called execute and look at the invariance of the execute. Still the first clock variables has to
be between 0 and less than equal to D, right? We still are keeping track of the time that is not reached to the
deadline. Because if Psi1 again is equal to D and we haven't finished executing the task, then that means the task
is expired. We go to the location called error.
Play video starting at :11:11 and follow transcript11:11

If Psi1 hasn't reached to T and Psi2 is between 0 and the worst case execution time. So then the task is actually
completed and we go back, the scheduler goes back to the sleep location and waits for the next period to start.
You see, we were able to use timed automata to model the real time scheduling task.

Play video starting at :11:45 and follow transcript11:45

But then the question we might ask from ourselves is okay, this timed automata syntactically and semantically is
not very similar to the notion of system I introduced in the beginning of this course, right? But at the same time I
also emphasize that almost all the systems around us can be modeled using the notion of system, okay? Timed
automata is also a system modeling. The question is can I model time automata using the notion of system? Can
it be described using the notion of system in this course? Because in the beginning I claim that the notion of
system I introduced in this course is general enough that can be used to model many systems around us, many
cyber-physical systems. Okay, let's see for example this particular timed automata which models scheduling a
task. Can I actually represent this using the notion of system? The answer is yes. Here, this is the system
representation of the timed automata in the previous slide. So I can actually come up with a simple system S
associated with the previous timed automata in which okay, what is the set of state? If you look at the previous
timed automata we have both clock variables which are changing in real numbers, continuously changing. And
we also have four locations, right? So that means my state set is actually a hybrid set. Meaning what? Meaning it
has both a discrete components in it which is the locations in the timed automata and it has continuous variables.
What this notation means, means non negative real numbers to the power 2. Why is that? Because I have two
clock variables which are changing continuously in time and both of them can be any value, any real number
bigger than equal to 0. So that's the reason. This is the second component of my state set which constitute to a
hybrid nature of this set. There is a discrete part, there is a continuous part.

Play video starting at :14:23 and follow transcript14:23

What about the initial state set? Initial state set is the set of those pairs in which the first part translates the
location of the timed automata. So initially the timed automata was in the location sleep. And what about the
XP? XP means the clock variable, okay? In the initial location, the clock variables was inside the invariant of
slip. So that is RX0.

Play video starting at :15: and follow transcript15:00

What about input action?

Play video starting at :15:4 and follow transcript15:04

Okay, this is interesting. So now we also have two types of input, discrete inputs or continuous inputs. So the
discrete part correspond to those name which appear on those transition awake, expire, starting, expired and
finish. So awake, expired, starting and finish. We have four input actions and then I take union with non-negative
real numbers. Again, this notation means non-negative real line. Okay, so you see here input is the union of two
sets. One set is pure, discrete, finite. The other set is continuous, right? Okay, now you will see how this input is
actually being used. Okay, so I already defined what the set x is, what the set x0 is, what the set u is. So now let's
see how the state transition function is defined based on the previous time automata. Here, if you are in location
xa, if the clock variable is xb under input u, you go to location xa primed and the clock variable is xb prime if
and only if one of the following two conditions hold. Okay, so if you look at the time automata, there are two
possibilities. Either we stay in one location and we do not take the discrete jump, or we take the discrete jump,
right? Okay, in the first case, let's assume we are staying within the initial location. We do not change the
location. However, the clock variable is still running, right?

Play video starting at :17:10 and follow transcript17:10

So in this case, u is actually the amount of time that has elapsed since I was in the initial location and I am still in
that location, right? U input in this case denotes how much time has elapsed. That's the reason is a non negative
real number because I do not change the location x a prime is actually equal to xa I am in the same location.
However, the clock variables has changed. Why is that? Because u units of time has elapsed, right? And the
clock variables are continuing in continuous time, right, evolving. And I know that their initial value is xp and u
units of time has passed. What is the new value of the clock variables? It's very simple. So initially they are xp,
right? So you need to solve this simple differential equation. The clocks are changing. So initially it's xp after u
units of time is equal to x prime b, which simply is equal to xp, the vector xp plus. So how many times has
elapsed, u units of time? So then you add a vector with all its entry to be u. So that amount of time you add to the
initial clock variable. That gives you the next value of the clock variables. And as you know, the location has not
changed xa prime is equal to xa because we are still in the same location, but the clock variables is evolving and
I assume the input is equal to u, which means the u units of time has elapsed. So what is the new value of the
clock variable? Is the previous value of the clock variables. And then you add each entry of the vector containing
clock variable. In this case, we have two clock variables. So we add each entries of each of those clock variables
with u units of time and that's our new clock variables.

Play video starting at :19:35 and follow transcript19:35

Okay, the other option is we actually change location. So since in this case we are changing the location, the
input is one of those discrete inputs awake, expired, starting, finished. So in this case, the location changes, right,
based on the input and subsets of the clock variables get reset to zero based on the discrete transition. So that's
how the state transition function f, is defined for the time automotive in the previous slide. And you see, I was
able to actually capture the state runs of the time automotive using a simple system.

Lesson: Hybrid Automata

en

Interactive Transcript - Enable basic transcript mode by pressing the escape key

You may navigate through the transcript using tab. To save a note for a section of text press CTRL + S. To
expand your selection you may use CTRL + arrow key. You may contract your selection using shift + CTRL +
arrow key. For screen readers that are incompatible with using arrow keys for shortcuts, you can replace them
with the H J K L keys. Some screen readers may require using CTRL in conjunction with the alt key

Play video starting at ::6 and follow transcript0:06

So now let's look into actually more general class of hybrid system, for example hybrid automata. So I'm not
going into details of syntax and semantic of hybrid automata. I only provide an example of a bouncing ball and
then I show you how that bouncing ball behavior can be actually be modeled using a hybrid automata. And I also
will explain the types of behavior and phenomena that can happen for this class of systems. So, let's assume we
have a ball and we drop the ball and of course the ball is going to bounce, bounce, bounce until it stays
underground, right? So, okay, let's look at the model of the bouncing ball. So, when the ball is in the air, let's
assume the altitude, the height of the ball is described using this variable x. So then the derivative of x which is
the altitude of the ball, the height of the ball from the ground, its derivative with respect to time is equal to the
velocity of the ball, right? And the velocity of then the derivative of the velocity of the ball is equal to- g, the
gravitational acceleration, right? And because the reason is minus, because the gravitational acceleration is
toward down and we consider the positive direction to be upward direction. And let's assume that the ball at
times t0 or 0 is starting at a fixed height edge and the velocity at that particular edge is 0, right? Because we are
grabbing the ball by hand. So the ball is fixed and then we're dropping it right at time 0, the velocity is 0. So
what happens when the ball hits the ground? So then there is an energy balance, right? The kinetic energy
exactly at the time slightly before the impact is equal to the kinetic energy for a time a little bit after the impact +
a dissipative energy, right? So now how the kinetic energy is computed, kinetic energy is equal to 1/2 times the
mass of the ball, the ball times the square of the velocity. So now in this situation, we assume that the amount of
dissipated energy is in terms of percentage is 100 times- 1- c2. Of course, this constant c depends on the type of
the floor, the material of the ball, and the size of the ball. So we don't go into the details, but let's assume that 1-
c2 percentage of the kinetic energy before the impact gets dissipated, right? So in this case, the velocity of the
ball immediately after impact is -c times velocity of the ball immediately before impact. And the reason we put-
sign because the direction of the ball is changing after impact, right? So now one might decide actually to model
the behavior of the bouncing ball using this simple hybrid automata which has only one location called q0, and
the invariant of the this location it says the height is always bigger than equal to 0 of course. The height of the
ball from the ground cannot be negative because underground is equal to 0 and how this continuous variable is
evolving. So here our continuous variable is the height of the ball from the ground, right? So the variable x,
okay, what the dynamic is in the air. So x.= velocity and the derivative of velocity is = to -g, gravitational
acceleration. And then what happens when the ball hits the ground? So okay, we have this self loop transition x =
0 because the ball is hitting the ground and of course the velocity is still less than equal to 0, right? Because the
ball is going down, it's hitting the ground. So the ground is equal to 0 and the velocity is less than equal to 0.
And when that happened so then the velocity gets reset. So v become minus- cv, it changed the direction and due
to some energy gets dissipated. So the velocity gets- c times the velocity exactly before the impact, okay? So
now the question is, is this mathematical artifact which models bouncing ball, is it even correct? There are
actually some simulator out there that you can simulate the behavior of a hybrid automata. So here we use
Ptolemy two high visual to actually simulate the behavior of this particular hybrid automata. So let's see what
happens. So what we do, we plot the position, the height of the ball as a function of time. So you see the ball is
bouncing and then bouncing, bouncing, the height is reducing, reducing, reducing until it reached to this time
maybe around 27 seconds, and then all of a sudden the height is going to minus infinity. So let's see what's
happening here. So if you look at the number of bounces that the ball is having, so it reached to a time that the
ball is actually facing infinitely many jump within a bounded time horizon which we know in reality that's
impossible, right? So then this is actually called Zeno behavior, meaning that the system makes an infinite
number of jumps in finite time, which we know that's not possible in reality when we drop the ball. So this
means that why does Zeno behavior arise? So look, our model in the previous slide, this model here with one
discrete states and a self loop is a mathematical artifact. So our previous model for the bouncing wall was a
mathematical artifact. So Zeno behavior is actually mathematically possible but it's invisible in the real physical
world. So this actually points to some unrealistic assumption in our model. So what happened was, here I assume
that when the ball hits the ground instantaneously at no time it change position and it start bouncing, whereas
apparently this is not true physically. So what happens is when the ball hits the ground, it stays on the ground for
some units of time before it goes up and it bounce back. So that's the reason. So here, to eliminate the Zeno
behavior which we saw in the previous model, we do some regularization. So here what we do is we add another
discrete location, namely q1. So in location q0, the invariance is still the height of the ball is the height above the
ground is bigger than equal to 0, which makes sense. And while the ball is on the air, it satisfies this simple
Newton's equation. The, [COUGH] derivative of the position of the ball equal to velocity and the derivative of
velocity is equal to minus gravitational acceleration. So when the position of the ball is equal to 0, so that means
the ball hits the ground, right? So in that case, velocity is also less than equal to 0 because the ball is going
downward, right? So what happens is now we have a new continuous variable, which is a clock variable in this
case. So the clock variable gets reset to 0. And now in the location q1, we actually assume that the ball is sitting
on the ground, position 0, velocity also 0. It's sitting on the ground for some units of time before it bounce back
up. And this location is exactly modeling that the ball is sojourning on the ground for some units of time, which
that units of time is modeled using this parameter epsilon. So, okay, when we are in location q1, the invariance
of this location is y less than equal to epsilon. And because the ball is sitting on the ground, so the velocity is 0,
the acceleration is 0, and the clock variable is running normal continuous time. So when the time clock variable
reaches epsilon, then we take a transition and the ball start bouncing back. So the velocity gets reset to- cv. And
again, when the ball is on the air, it follows the normal physical equations, right? So you see, we have two
discrete location. Each location has its own invariance condition and in contrast to time automata, which in each
location the only physical variables was clock and they were actually evolving. And they had this simple
dynamic which was saying the clock variable with respect to time was equal to 1. Here, the evolution of the
physical variable actually can be more complex. Look at this dynamic, right? Look at the derivative of those
variables with respect to time is not anymore xr equal to 1 is actually equal to velocity. This can actually have a
nonlinear behavior as well in some complex scenario. In location q1, the continuous variable is still a clock
variable, the same as time automata, but in location q0 is different. So now, let's see if by adding this new
discrete state to capture the amount of time that the ball sitting on the ground without any movement, does it
solve the Zeno behavior? So this simply says an instantaneous mode change or jump is unrealistic in reality. So,
okay, let's now simulate the behavior of this new hybrid automata for different epsilon and see what happens as
epsilon gets smaller and smaller. Then we choose epsilon to be equal to 0.3, you see, no Zeno behavior is
happening, the ball is bouncing, and eventually the height of the ball gets equal to 0. But if we simulate that
hybrid automata for epsilon equal to 0.15, still we do see a Zeno behavior. See, there is a threshold above which
we don't see a Zeno behavior and below which the Zeno behavior start happening again. And this is enough
explanation and discussion about hybrid automata and we're not going to go more into details of hybrid
automata. If you are interested in studying hybrid automata more, you can actually look at the suggested
textbook for this course, and you will find a lot of discussions about hybrid automata. Formal syntax and
semantics of hybrid automata.