Skip to main content
Loading Explore guides…
Real-Time Decision Making · Acedra
Home
Explore
Computer Science
Real-Time Decision Making
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
178 segments
Copy
Hide video
0:00
[HOST] Thank you all for coming for the second session. Uh, our first speaker in the second session is Professor Richard Murre, who is also the second speaker of the session. Second. Yeah. Speaker of the session. So that tells you how his reputation is in the controls community. He's very well known, very, a large body of work. So welcome, Richard. We are looking forward to your [RICHARD M MURRAY] Talk. Great. Thanks for sharing this. Well, it's my pleasure to be here, of course,
0:22
and to tell you a little bit about this area. So let me just say what I hope you get out of this talk. So my goal here is, of course, like the two talks in the morning, to get a little bit of an overview of this area for people who aren't familiar with it, and to talk some about how this might be relevant for applications in real time decision making, and of course quite a broad set of applications that we're thinking about in the context of the real time decision making program, so that's
0:46
a particular challenge. Um, but of course, really all I'm going to do is, you know, hopefully tease you with some ideas about, "Oh, that's interesting. That's a different way to think about it," or, "That's a feature that I see present in my problems, and so maybe control theory can shed some light or provide some tools," or whatever. And so, I hope you'll come find me if something in here you think might relate to things that you're doing And I'd be happy to follow up.
1:09
And so and you know, look at joint project opportunities and other things, so please come find me, and hopefully this will be a teaser for more in-depth interactions throughout the time. Um, I'm here Tuesdays through Thursdays most weeks between now and the end of March. And so find me soon. Uh, and then in April and, and May much less often because I have to teach back down at Caltech. Okay, so let me start by just saying a little bit about what is control.
1:35
So the problem with the word is it's a broad word, it gets used all over the place, it gets used in lots of different ways. So for people doing feedback control theory, what do we mean by control? And sort of the traditional point of view would be something like this. You have some system that you want to control, maybe it's an autonomous vehicle. This is an autonomous vehicle that was entered in the DARPA Grand Challenge, built by a bunch of Caltech undergraduates named Alice.
1:57
Uh, and so among other things, one of the things Alice is supposed to be able to do is drive at a constant speed when commanded, so drive at, you know, 25 miles an hour down the road or down the dirt road or wherever it is. And so, a typical feedback control after doing that would be to sense what the vehicle speed is, compare that to what the desired speed is so compute what you want to do, I want to speed up or I want to slow down, and then to actuate the system, press the gas pedal,
2:20
press the brake whichever it has to be, and to do this in some sort of a feedback loop. And so in a, you know, starting class, we would say, well, control is really about sensing, actuation, and computation in some sort of a feedback loop. And the idea being that now we want that closed loop system to have some desired behavior or something else. And the typical things that we look at are stability that is that I would like that small perturbations either stay small
2:46
or better yet converge back to the desired equilibrium point. Performance, I like that when I command a different speed, so I say go from 25 miles an hour to 35 miles an hour that I do so in a way in which it's smooth And it's relatively quick And it feels good and all of those good things, so we have to have performance measures. And then perhaps most importantly, robustly. Uh, that means that in the face of uncertainty, maybe the tank is full, maybe it's not full,
3:11
maybe the car is one year old, maybe it's 10 years old, maybe it's got two people in it, maybe it's got 10 people in it, I'd like it to operate the same across all of those different conditions. And so the ideas are to look at stability, which is in some sense the easiest of those, performance, but really robust stability and robust performance are the interesting parts. So how do I have those properties be robust with respect to some source of uncertainty?
3:33
So in the traditional view, that's it, and you know, we could spend a lot of time talking about how to do those things. But in fact, the field is changing in a, I think, quite exciting way, and so the emerging point of view is a little bit different. And so, you know, the emerging point of view, we go from the sort of applications on the left, which are, you know, kind of aircraft and building controllers and things like that, to the applications on the right, which are, you know,
3:52
autonomous cars and biological systems the Internet, you know, very large enterprise scale systems. This one is a battle space management system. And we think about control as the collection of tools and techniques for analyzing, designing and implementing complex systems in the presence of uncertainty. So the uncertainty is still there. And it's a combination of thinking about dynamics, so dynamics of the underlying process as well as dynamics of
4:19
the feedback control system, interconnections and feedback and feedforward in particular and communications, computing and software, which is how we implement all of those things. And so I think a more modern view, if you looked at control system, you might see something, and I'll put this up in more detail later and we'll kind of walk through some of the pieces that looks like some relatively complicated block diagram at multiple levels of abstraction with all sorts of things going on.
4:41
And this is sort of what's going on inside of an autonomous car these days in terms of all of the computing that's going on and the different things that have to be managed. And so I'd say a more modern view of control then would be that it's some sort of product, right of dynamics and uncertainty and feedforward and feedback. And so, you know, somebody says, "What's control about?" Well, it's when all of these things come together that's what the field tries to understand.
5:05
And so you can remember this by the acronym DUFF. So if you're a Simpsons fan, just think Duff beer and that will remind you dynamics, uncertainty, feedforward, and feedback. Okay, so there are a couple of key principles that guide the way that we think about control systems. And these have been constant over time, both for the kind of traditional view but also this more modern view, and the first of those is that feedback is a tool for managing uncertainty.
5:30
Uncertainty in your system, but also uncertainty in the environment. So not only may the system be changing, the age of the car, the power of the car, the weight of the car and other things, but the environment might be changing. I might be on a dirt road or I might be on a highway or I might be on something that's bumpy or smooth. And again, I'd like to use feedback as a way of managing that uncertainty. The other thing is that feedback provides us a tool for designing the dynamics of a system.
5:53
Oh, and sorry, let me say, if there's no uncertainty, so if you say, "My system is well known, I-- it's completely characterized," you don't need feedback, right? So don't bother with it. But if it has uncertainty, then feedback is one of the tools. There are others as well. Uh, other principle is that it provides feedback and feedforward provide tools for design of dynamics. That is, that we can design the dynamics to be different than the natural dynamics of the system.
6:16
So for example, an aircraft that might normally be unstable like that one in the lower left, right, the wings are pointed forward. You can imagine if you tilt it up a little bit, right, that it flips over, right? But with feedback, we can make that have desirable properties so that it flies like a regular aircraft, flies like a very stable aircraft, or something like that. So feedback is a mechanism for designing the dynamics of a system to achieve something you want it to achieve,
6:39
and it's a mechanism for handling uncertainty and making something robust with respect to the uncertainty. And the two of these together, designing the dynamics and managing uncertainty, provide, I think, one of the powerful kind of corollaries of these which is that feedback enables modularity and interoperability, right? Modularity because now I can interconnect it to different things, and because it's robust with respect to what it's interconnected to,
7:02
and because the dynamics, right, are something that I designed to do that in face of that robustness, right, I get a module, right, that can be interconnected to different things and operate in the same way. Yeah? [AUDIENCE MEMBER] Are you restricting feedback to just temporal feedback, or do you include, say, other dimensionalities, particularly space? [RICHARD M MURRAY] Yeah, so in some sense I'll try and say, you know, that generally one wants to
7:23
look at all sorts of different types of feedback, right? Sort of temporal feedback, but also potential spatial feedback, so something might happen differently when I move over here versus over there, right, or other types. And I'll try and get into some of the different ways-- --that you can think about them. Okay, so at a very, very high level, control is about this kind of set of things. And there have been some important things that have happened in the last 15 years or so,
7:44
just to keep in the back of your mind about where is this field going, and what are the tools, and what are people doing with it. And so one of these is that just like every other field, the massive increases in the amount of computation we have available have changed what we can do. And so we've gone from implementing controllers on little, you know bespoke analog circuits and things like that, to implementing things in microprocessors and more complicated, you know,
8:10
NVIDIA processors and other things. And so online optimization is something we can do. So what this experiment is showing you is something where we're actually calculating out trajectories for this flight control system. And we are calculating every 10th of a second what to do for the next second or two. And then doing that for a 10th of a second and then re-computing, and then re-computing, and then re-computing, right? And doing so, right, all of this re-computation is a mechanism of feedback.
8:35
This is something called receding horizon control. I'll give you more detail in a minute. But it allows us to deal with highly non-linear systems in very constrained environments and allows for really quite aggressive types of trajectories and other things that can be very robust. And just to say, this is now something from probably a little bit more than 15 years ago. At the time we implemented it, it took 30,000 dollars' worth of computing to implement that, right?
8:59
It's, of course, less than the amount of computing on your cell phone today, right? And so this is the type of thing that is all over the place. Feedback control systems use optimization all the time. Yeah? Can [AUDIENCE MEMBER] You tell me what feedforward, you mentioned it-- I [RICHARD M MURRAY] Will. --but I haven't seen it. Yep, give me, give me a second, I'll get to it. Uh, and so you know, I'll talk about it. Okay, so optimization, advances in computing, big deal.
9:22
Another is just thinking about, you know, computer science and layering and different layers of abstraction. This is showing a video from the DARPA Grand Challenge. This is a Caltech undergraduate team that designed a vehicle that could drive on roads. Here you're seeing it navigating a stop sign intersection. This is from 2007, so about a decade before the sorts of things you see now. It doesn't know exactly where the road is. It's having to take sensory data, make computations and
9:45
do things, but it's doing it at multiple layers of abstraction. It has to worry about staying on the road and driving the right speed, but it also has to worry about what are these cars in front of me? What turn--whose turn is it at the intersection? Should I go now or not, right? And things at a different level of kind of discrete decision making. And so these are very complicated systems, and these complicated systems we break up in the usual way into different layers of abstraction and
10:06
different components and put them together. Another advance has been, again, taking things coming from computer science, using ideas from formal methods. Uh, this is an area where I'm particularly active and taking ideas from computer science about verification and synthesis using temporal logics and other things, and applying these to control systems. I'm gonna run a video over here on the right, and what you're gonna see is a discrete decision-making
10:31
system where I have a bunch of incoming robots and they are supposed to get blocked by the robots down at the bottom. This is sort of like a soccer, you know, you block you and, you know, you tag the, you, this other person type of a setup. And the idea is that there's now a protocol that's running on the bottom that is going to switch assignments, right, by talking to the neighbor on the left and the right. And if I see that I'm going for somebody on this side and you're
10:53
going for somebody on this side, it would make sense for us to switch. All right? And so we're gonna implement a feedback algorithm that is going to talk to each other and somehow figure out whether or not we should switch, and as it does so, it will always resolve out so that there are no crosses and we can always block people before they come down. And we'd like to prove that that works and it's robust with respect to the dynamics of the incoming agents, et cetera.
11:15
But this is now a discrete problem rather than some, you know, what speed should you go, right? It's should I be assigned to prob-- you know, to Agent 1 or Agent 2, right? So it's a different style of problem. And finally, the other big trend has been just moving up in scale. And so Internet of Things types of pictures where we really think about doing enterprise-level control, right? And so certainly one of the early ones of those was just internet congestion control.
11:38
That was an enterprise-level system. But now when you look at supply chains and when you look at battle space management and you look at all of these other very large-scale systems, these are examples where controls are coming in. Okay, so that's kind of at a high level the sorts of things we'd like to think about, and of course what I want to do is dive in and tell you, answer what is feedforward, what is feedback, but also some of the techniques that we're using.
11:59
So here's what I'm gonna try and cover you know, in this first lecture and then after a break in the second one, so I'll try and go through all of this and we'll see how far I get. I'll start by just talking about the kind of standard model for control, what's the control architecture that we think about, and try and give a couple of examples of how that architecture can be applied to real-time decision making. Then talk about some of the standard design patterns that are used in control.
12:22
If you go look inside the hood of a control system, you'll see typically a couple of different design patterns. And then talk about feedback systems, and then feedforward systems, and so what do I mean by those two things, and how do we use them. Uh, and then, as I have time, I'll talk a little bit about now, as we layer the architecture and look at these more complex systems, what does that look like? And then talk some about reactive protocols, these discrete decision-making protocols.
12:44
Okay, so that's what I'm going to try and cover. Uh, please feel free to interrupt me, and I'll try and stop at the end of each slide as I start to do a little bit more technical things and say, "Questions?" All right? And if I don't, just raise your hand or yell something out. Okay, so let's talk about this kind of standard model, right? So physics has a standard model. Here's the control system standard model. So we start with some input-output process, right?
13:05
So you've got some process, it's got inputs and outputs. It might be your car, and the input is your gas and your steering and the output is the speed you're going and your location. It might be a big computer farm, right, and the input is how many computers should I be running, and the output is how much computation can I do? It might be this building, and I can turn on or off the air conditioning or the heating, right? Anything that you can think of that I have some set of inputs
13:30
that will typically change the behavior of the process, and I have something that I can observe about that process. And so we want to look at that class of systems.
13:40
The first thing we need to do is, the things that we observe may or may not be the things that we care about. That is, the system may have internal state, we may care about what that internal state is, but we can only see what we can measure. And so the very first thing we'll do is we'll put an observer on this. And that observer will watch the outputs of the system and infer something about the system. And indeed, some of the scientific applications that we heard about on Monday, right,
14:03
where you want to see a supernova or you want to know where an earthquake occurred, right? I don't know what the input for an earthquake is, right, you know, something down deep in the core, but you're watching a bunch of cell phones shake up and down, right, and you'd like to say, "Did an earthquake happen or not?" Right? And so you want an observer that is trying to watch the signal, which is a bunch of things going up and down, and infer something
14:21
about the underlying process, which is, you know, the San Andreas just erupted, get out of town, or whatever it is.
14:27
So we'll typically have some sort of an observer that we use. And of course, the observation process is complicated by the fact that there's often noise involved, so I don't get a clean measurement right? In addition to not necessarily measuring what I want to measure, there may also be noise on that. So the cell phones were all moving around and jumping up and down and other things, and that's corrupting things, right? We gotta look for the correlations between everything going on.
14:53
Now on the other end, on the input end, we'll typically put our controller. And so the idea of the controller is, I take some sort of a description of the task. I'd like to drive down the road at 25 miles an hour. I'd like to have the building be 30 degrees C or 25 degrees C. Um, and then I'm going to command the inputs. I'm gonna turn on and off the air conditioners, I'm gonna press the gas, I'm going to start up more uh compute servers whatever it happens to be.
15:17
So I have some description of my task, and the controller's job is to take that task description and decide what inputs to apply to the process to somehow get that to satisfy that task. And to some extent, the simplest control system would look just like this. And if I had a perfect model of the process, right, I can just kind of invert it out, right? I can say, okay, I know what the heat capacity of this room is and how much heat you're all generating, I know what the temperature outside is,
15:44
And so I can figure out how much heat do I need to put into this room to keep it at some temperature? How much heat do I need to take out? And then I'll just do that, right? And so if I have all of the information then I can do that. Uh, and we typically call this open-loop control, because I'm not gonna see whether I'm right or not. I'm just going to, right, sort of put something in. You can think about open-loop control lots of different ways.
16:05
Uh, a typical stoplight would be open-loop control if it doesn't use a traffic sensor, right? Just gonna say, "Look, I'm just gonna turn my light cycling, right, every two minutes." Right? I'm gonna give different directions, right, the ability to go probably more often than two minutes And that's it, right? And if you're doing that in a mobility situation, that may or may not optimize the mobility, but it's a pretty simple schedule, right? And so we're not gonna measure anything.
16:27
We're just gonna do that.
16:28
Now, part of the reason that's complicated, of course, is that what you tell the system to do and what the system actually does may be different, so there are some sort of disturbances that come in, right? So I don't really know the temperature outside, or somebody in here is burning a lot more heat, or somebody plugged their laptop in and that's generating more power than I knew. And so these disturbances make it hard to use just open-loop control and get the desired output.
16:51
And so it's at this point that we start using feedback. We say, "Look, but I can measure what the temperature in this room is," or, "I can measure what the traffic is," right? And I can use that to decide whether or not I want to do things. And so the feedback loop, or a closed-loop system, right, comes from taking some output from the observer and then feeding that back and making some decision in the controller that is going to affect the process, which is
17:14
gonna change the output, right, which is then gonna affect the process, and so I'm gonna get some sort of a cycle. And so the idea, of course, is to try and design that in a way that gives the desired performance. And so now, for example, if there are disturbances and I, let's say I'm doing a car controller and I'm trying to hold the speed constant, and I say, "Well, I know for this car that if I push the gas down this much, I should go 35 miles an hour." But now I start going up a slight hill,
17:39
I'll measure that I'm going too slow, right? And I can say, "Oh, well, push the gas a little bit more," and that should speed me up a little bit. I come over the top of the hill, I let it off, right? All of those things. And of course, we have to be careful because this can lead to instability, right? So if I, for example, see that I'm going a little bit too slow, and so I push the gas really hard, well, now I'll go too fast. Now I'm going too fast, so I'll pull back, right?
17:59
We've all, maybe less so now, but probably all been in cars where somebody's not very good at this, right? And they're kind of rrrr, rrrr, and you get really sick really quickly, right? And so, you know, they're not as good a feedback controller as we might like. Nowadays, cruise controllers are really good, right? You set it at 55 miles an hour, you go 55 miles an hour. You go up a hill, you probably won't even see it deviate off of 55 miles an hour, right? Um, I mean, they really
18:21
kind of do the right thing. So that's one way of thinking about feedback, is that we have this process, we have disturbances and noise. We wanna be robust with respect to those disturbances and noise And we have, we'd like to accomplish our task. Now, there's another-- Yeah? I have a question about [AUDIENCE MEMBER] That. Sure. Cruise control and stuff. Are they better because our computation is better or because?
18:44
[RICHARD M MURRAY] Uh, I'd say a little bit of both. So, you know, part of what happens is the sensors got better, so we can sense speed much more accurately. Part of it is that it used to be that, you know, if you look at a really old car, it would be implemented as a mechanical cruise controller. I mean, it was actually an electro-mechanical system, and that had its limitations in what it could do, and modern computation can do more And so we can measure things better.
19:04
And yeah, I'd say that's probably most of it. And you know, everything's electronically controlled now, so you don't have to go through a mechanical process and things like that. Yeah? [AUDIENCE MEMBER] Just about the diagram. Sure. So processing, intermediate processing, you're sort of putting into the group? [RICHARD M MURRAY] Yeah, so I'm gonna, I'm gonna expand on this box and tell you what's inside it. That's where all of the, you know, kind of control theory is happening in some sense.
19:26
Some on the right-hand side as well, for the estimation algorithms and other things. But at a high level, right, lots of things could go in there, absolutely. Including feedforward, feedback, different types of computation, whether it's electromechanical, et cetera, all fit in that little box. Now, there's one other important part that control theory has developed.
19:45
It is traditionally been a very model-based field. That is, you give me a model of the process, you give me a model of what the disturbances and the noise are, usually just bounds on those, right? So I know how much wind there is, so I know what the airplane's going to get moved around by, things like that. And then I will come up with my control law. But one of the things we all know about models is models are always approximations. They're there to answer certain questions and
20:08
they're never going to be exact for every question. And so one of the things that happened early in control theory is that people thought about, what if your model isn't right? And so often you'll see in a control diagram this little extra piece added up on the top that is some sort of uncertainty. And the idea here is that that box up there, just like the other boxes here, might be a dynamic input-output map. That is, it might actually have dynamics in it.
20:36
So, one thing we might think about, for example, is if you're designing a flight controller for an airplane, then of course you design this flight control and you say, "Well, you know, if I want to turn left, I need to kind of, you know, move my flaps around and other things so that I turn left and then fly around," right? And so my process might have those kind of rigid body mechanics in it that give me that with a little bit of the aerodynamics of you know, if I tilt one of the ailerons or
20:59
other things a certain amount, how much force will I get and all of those things. But of course there's a lot of other things going on, right? The wings are actually flexible, they're not rigid, right? So if you look out the w-- if you're sitting in a wing seat, right, and you look outside and you're like in turbulence or something, you can see the wings are moving, right? And so does that matter or not? Right? There's fuel in those wings, and that fuel's sloshing around. It's a liquid, right?
21:22
It has dynamics, right? As you're moving around and getting bucked around, all that fuel sloshing around. Does that matter or not? And so we'll typically put up into that box that I've labeled environment, but really should have probably labeled uncertainty, unmodeled dynamics, right? That is, we know there are dynamics that we're leaving out, and we're going to take that into account in our design. And we're going to bound that, so I'm not saying anything can happen.
21:46
I'm gonna say, "Look, I know that on my wings, you know, if I move my rigid body around a little bit, I could excite those modes," but I've got some model for I don't expect the wings to bend more than a certain amount or to bend, you know, more than, at higher frequencies than something or other. And so I can put bounds on what that unmodeled set of dynamics are. But I'm not gonna assume that I have all of the dynamics; I'm gonna allow for unmodeled dynamics, disturbances, as well as noise.
22:11
So those are the sources of uncertainty.
22:14
Okay, so in this kind of control diagram there are a couple of key elements. So one is there's the process, some sort of an input-output system that has memory or dynamics to it. We care about things where if I make a change now, that will affect me for some period of time. If I turn the heater on, right, it will take some amount of time until the room heats up, and it will take some amount of time before it cools back down. Uh, we also care about the environment,
22:39
and so I've drawn this little line just to sort of say the t-- stuff up on the top is the description of the uncertainty present in the system or its environment, right? So there's some sort of unmodeled dynamics, disturbances, and noise. That's gonna typically be bounded, but not specified directly. I'm not gonna-- The whole point is I'm gonna kind of ignore that from the point of view of the design and then show I'm robust with respect to it later.
23:05
The third piece, of course, is this observer over here on the right, and so we have to estimate the states that we care about, the underlying system state that we care about from what we can measure.
23:15
And then of course, the stuff on the left, right, which is the actual controller that we're going to do, and so this is where we're gonna try and achieve the desired task by taking the data that we get from the observer and the known actions that we can apply to the process. So that's the sort of standard picture for control and of course, the part that we think a lot about in the control theory community, right, is now colored in blue, this feedback part, right?
23:40
So it's a feedback cycle and you have to be careful how you reason about things because, you know, the changes you make in the controller affect the process, which affects what you observe, which affects what you do in the controller, right? So there's this cycle and there are things that could go wrong.
23:54
In particular, implementing feedback systems is often painful, and there are three primary disadvantages I would say. One is it's kinda complicated, okay, because you've got to put in extra sensors and actuators and other things. You have a potential for instability whenever you have feedback, so, you know, a standard one is the microphone. If I turn the gain up too much, it'll squeal, right? That's an instability that's occurring, because it's going around this loop and
24:20
getting amplified and amplified and amplified until we hit the saturation. And then furthermore, even if it's not unstable, you can still amplify the noise. That is, if I have a noisy sensor, all right, then I might try and respond to that noisy sensor, even though that's not really what the system is doing, right? So, if I don't have a very accurate speed controller, for example, and it's drifting around, all I know is that's the speed I'm reading, right? And so I'll follow that.
24:42
So these are not good things to have happen. And so to some extent, if you can avoid using feedback, you should but there are reasons why you might want to use it. And I'd say the two primary advantages are that it provides robustness with respect to uncertainty, 'cause you measure what actually happens, right, not what you think happens. And then it enables, through the design of the dynamics as well as this robustness to uncertainty, modularity and interoperability.
25:09
So you know, every large scale engineering system involves feedback some place, right? Your body involves feedback all over the place. Ecosystems have feedback all over. Everything has you know, all of these things, and part of it is that it's trying to be robust with respect to uncertainty and provide some set of modulator and interoperability. Okay, so this is my, you know, if you talk to somebody in control theory and you draw this diagram, they oughta say, "Yep. Uh, I get it."
25:33
You know, "That's exactly what we study." And the generality is, this process can be the Earth's climate. This process can be discreet decisions that are happening inside of an algorithm that's doing Bitcoin mining. These, that process can be, you know, sort of lots of things, as long as it's got inputs, outputs, and some dynamics to it. Okay, so questions about this, if I haven't lost everybody already? Still high level. I'm gonna go in more detail, but just conceptually, this
25:59
is what we think about as a, as kind of the standard model for control theory.
26:07
Okay. All right, so now let's just look at this a little bit, and I'll try and do just a couple of examples. So let's look at some of the things that we've already heard about and say, "Well, how do they fit in this diagram?" So we heard on Monday about a couple of different things, earthquake detection and supernova detection. Those fit into this diagram, but maybe in a simplified way. There's, to my knowledge, no actuator for supernova, at least not one that we control, all right? Yet.
26:34
The specification, what are we trying to do? Well, we're trying to detect them, right? It's an estimation problem, observer problem, right? And so really it's just this observer only. Earthquakes are a little bit more interesting. You might say, "Well, earthquakes are the same. We're just trying to detect them." But actually we can actuate earthquakes, all right? Fracking actually actuates earthquakes, all right? I mean, this is known. And there's no reason why in principle I
26:54
can't say, "Well, look. We're doing fracking. Maybe we should measure what the seismometers say and right before we see the big one about to happen, all right, maybe we should, you know, do a bunch of fracking in certain spots, right, to try and keep that from happening." Yeah maybe right? So I don't know. For now, right, this is observers only. We're not trying to control earthquakes yet But maybe someday. Okay, so these are, I would put these in
27:17
the class of things that maybe we'll call kind of scientific detection, all right? It is certainly, potentially a real-time decision making problem, but it's one in which mainly we want to detect events, we have sensors and there's an observer. So it fits, but you know, the feedback loop's in there, so control theory is not gonna help very much here, right? Maybe in an auxiliary way.
27:36
Now, we saw yesterday a bunch of applications around the ideas of mobility, right? Urban mobility, bike share, car share, right? These are very interesting 'cause they are feedback control systems, right? So for example, if we look at something like bike share, right? What's the actuator? Well, you get to move the bikes around, right? You gotta go pick them up, right? We're empty, we're gonna go pick them up, right? What's the sensor? Well, I know where the bikes are,
27:57
at least which docks they're in right? I maybe know something about the apps that, you know, somebody says they want to use one or not, right, depending on, and we had this discussion a little bit yesterday. What am I trying to achieve? Well, I want to optimize their location and usage, right? I want to make sure I don't go down to zero. I want to make sure that I've got enough docks to put them in, right? All the stuff we heard about yesterday. And this of course fits in this.
28:18
I would say unless you're doing dynamic management, it's not at the fastest time scale, all right? That is, typically, and the people who talked about this can tell me more, you know, you probably think about having an open loop schedule, right? You know, the truck's gonna drive around, and it's gonna pick up this many bicycles from this place and put it there. And not something that's dynamic. I see that I have too many bicycles here, so let me send the trucks out right now and start
28:39
adjusting them around. But you could do that, right? We could also start, and we talked about this yesterday in some of the questions, incentivizing things, right? "hey, I'll give you five bucks off if you go park your bicycle over there instead of over here." Right? Because what do I want to do? I want to get the closed loop to put the bicycles in the right place at the right time, and my actuator now, right, is probably a list of these other ones incentives, right? So I can use that too.
29:00
So we can think of that as a feedback system, and you know, we saw yesterday some examples of things where there were just horrendous dynamics, right? I mean, really bad, right? 'cause it was going down to zero and it was going all over the place, right? You know, I would argue it's not a very good feedback system, right, in what's implemented. Might be 'cause we don't have good actuators, right? Might be 'cause we don't have good sensors, right?
29:18
Might just be because we haven't actually thought of it as a feedback system and tried to stabilize, right, in a better way what's going on. Okay, so those are I think interesting applications where maybe the ideas from control apply. Certainly there's uncertainty there, right? We don't know exactly who's gonna go where when. We don't know when the bicycles are gonna break, right? You know, if it's ride share, we don't know exactly what the traffic's gonna look like, et cetera, et cetera.
29:41
Okay, so these transportation networks then have things like schedules and incentives as their actuators, some sort of demand measurements and supply measurements perhaps in what they sense. They're trying to optimize some sort of utility function. I think they're open loop at the fast time scales, what happens over the course of minutes or day or hours. They're closed loop at a slower rate. That is, we adjust the number of bicycles that we pre-position, we adjust the number of racks, right?
30:03
So at a weekly time scale, we might have some closed loop stuff.
30:07
Okay, a third one and this is actually what I'll talk about next week in the public lecture if you come on Tuesday is autonomous vehicles, and I already showed you a little bit of that. So here of course you can think about the actuators just as the gas and the steering. The sensors are all sorts of cameras and radars and laser range finders and other things but also measurements of the traffic and other information that we might get from the cloud. What are we trying to do?
30:30
Well, roughly we're trying to get from A to B without hitting anyone, right? And by the way, a smooth ride and, you know, minimize fuel and a bunch of other things, right? But probably the first one is get from A to B without hitting anyone.
30:40
And it's a very interesting, very complex environment. I'll tell you a little bit more about, you know, some of the architectures they used for that. Okay, so these are examples that we saw, at least the top two classes already and we'll see more tomorrow when we hear about the smart grid and other things, right, of examples where there are feedback and uncertainties and other things. And so maybe the tools from control theory can apply.
31:01
Okay, and then I'll just say a little bit about, and, you know, sort of was asked already, what types of systems can one do? And so I'd say there's kind of three broad classes and lots of intersections. One is if we have continuous states, temperature, altitude, speed things like that and we model those with ordinary differential equations or partial differential equations or difference equations, if it's something that's on a discrete time clock.
31:26
And typically the specifications there might be integrated cost over time or space. So we can think about spatial as a, as the free variable. And these are very well studied systems, and there are lots of tools available, particularly for linear time and variant systems. So if I have a linear differential equation, a linear partial differential equation, a linear difference equation then I can apply a lot more mathematics to that and sort of do things.
31:49
So this is sort of the classic area that if you take a class in control theory, you'll almost certainly study this class. Um, one can also think though, and I'll talk more about this at the end, about discrete state systems, right? So now I can turn something on or off, or I can turn left or right. And so I have discrete decisions that I can make. So now the dynamics are gonna be described by some sort of a finite state automata, probably, some sort of an input-output
32:14
finite state automata maybe timed automata, depending on how time comes in there, Petri nets and other types of representations. There are lots of different ways you can represent these discrete state systems. If it's a manufacturing system and I say, how many parts do I have, right? That's a discrete number, right? We can do, as we saw yesterday a little bit, we can do continuous approximations of those. So I can start looking at densities of parts and
32:33
other things and pop them up into my top class, right? By choosing a different model. But some of them really, if I want to turn left or right, it's probably going to be something at this level. And our specifications might be written in some sort of a temporal logic. And again, I'll say a little bit more about that later. Um, and here I'd say there are great tools for doing verification, that is given a design, does it satisfy the specifications, less good tools for doing design and synthesis.
32:55
How do I actually design those and make sure they work?
32:59
Now all of the things that I've said so far have been in some sense a kind of deterministic point of view. And many of the things I particularly work on we use a sort of deterministic point of view. But we can also have a probabilistic point of view, right? So you can say, look, you know, it's a stochastic system. Uh, maybe it's, you know, represented by a stochastic ODE or a Kolmogorov equation or some sort of Markov decision process. And now my specifications are probably things like this,
33:24
but in terms of probabilities, expected moments, right? Things of that sort. Uh, and again it's relatively well studied, especially for things like linear time invariant systems, Markov decision processes. There's lots of tools around. All of these fit, you know, kind of in this picture of things going on. And the same principles apply, that is you want to manage uncertainty and design dynamics, right? And use the feedback to do that.
33:47
All right, so let me say a little about--Well, here's some different types of things. I gave some examples. I'll just pause briefly.
33:55
Questions about the types of things we can model or think of as a control system and the various components of it?
34:04
Yeah?
34:06
You have disturbances and noise and an environment that represents unmodeled dynamics.
34:14
What happens when you have an adversarial environment? Yeah, great question. So you can think about it in a number of different ways. So one is, I would say adversarial can be captured in that little environment box up there, and you can think of it now as a game, right? That is, the environment gets to see what I'm doing. That's the arrow coming into it. It then gets to decide what it's going to do, and it could have a different objective function, keep me from getting to, you know, my point.
34:43
And then it gets to inject something back. If I can put some sort of a bound on what's possible, it fits the theory, right? In other words I can say, look, you know, the other cars that are on the road, let's pretend they're trying to keep me from getting someplace. They still have to satisfy physics, right? If it's two miles away, I don't have to worry about interacting with it in the next 30 seconds, right? Guess, unless I'm going really fast. So
35:05
But anyway so you know, I think you can still put it into that framework. Of course, I have to tell you now that my model of the environment is adversarial and they might be working against you. The things that are coming in as disturbances and noise, we should think of those as more benign. They're not measuring what I'm doing and trying to subvert me. So adversarial stuff would go in that ENV box, right? An adversarial environment. Yeah? [AUDIENCE MEMBER] Sir, you sort of mentioned,
35:30
there are situations say in the driving situation, there's a tight loop for ignition. Yeah. There's a, at the driver level it makes decisions. The fleet management meets once a quarter. Right. And upper management meets once a year to-- Right. --decide how big the fleet should be. So, there's, at least in this case, kind of a nesting. But is, are, is it fruitful to consider there being some kind of an algebra for composing these? [RICHARD M MURRAY] Yeah, that's a great question.
35:55
So, let me first talk about the nesting and then talk about the mathematical structure. So at the nesting level, absolutely. We see this all the time, right? So let's do manufacturing. You know, at the manufacturing level, there's a robot someplace that has very tight loops that are controlling, you know, I'm gonna put this in this position, right? There's something else that's saying, well, I've got to get the parts to where that robot can pick it up.
36:11
That's happening at a slower time scale over the next couple of minutes. There's something that's saying, I've got to ship the parts to the factory so that they get there. There's somebody who's saying, I got to make a new contract with another supplier, right? Every quarter. There's a board that's saying, you know, we're gonna get out of this business or that. These are all feedback loops happening at different scales. Um, we do talk about and I'll show you this
36:30
at least schematically, and I'm happy to talk more about it. How do you do what we call vertical contracts between those, right? Because the bottom one is implementing some desired dynamics. The top one is making some assumptions about that. That is that when the people worrying about shipping are thinking about, you know, are the right parts going to be here, et cetera, they're not worried about the currents going through the motors on the robots that are
36:51
putting those things together, nor should they have to. They should simply know that the robots will put them together at this rate. So there are different abstractions, but I need to make sure that the assumptions that I'm making about what the upper layer is thinking and what I'm doing are consistent. So there is a contract structure, I would say, making that into more of an algebraic structure I think would be interesting to think about and could probably be done.
37:14
I think the hard part would be often the layers of abstraction are using different mathematics. And so now you've got a, you know, I don't know if it's category theory or something weird, right? And you got to get into something where you're really talking about generalized classes of algebras, right? Because if I'm doing discrete variables in one spot and I'm doing continuous variables over time in another and continuous variables over space in another, I could probably connect the
37:35
time and space, but can I connect the discrete? I have to think about it. [AUDIENCE MEMBER] But potentially there could be--consistent notions of deleterious instability-- [RICHARD M MURRAY] Yeah, for example. [AUDIENCE MEMBER] --that you want to not propagate. [RICHARD M MURRAY] Right. Right absolutely. Yeah? [AUDIENCE MEMBER] In computer science so in the morning, we have input, we have functions we want to minimize and optimize, and you get an output, and there's approximation.
37:58
For online algorithm, we have competitive ratio, we have streaming algorithm. But everything you ever objective function. And you, and I say, what is there? How you measure the success of the system, the function, I mean, there is general framework that-- Also in the paper, sometimes there's a solution, but there's no problem. Right. Or maybe the paper is-- [RICHARD M MURRAY] Fantastic. All right, let [AUDIENCE MEMBER] Yes, can I just say, what is optimization Yeah.
38:19
[RICHARD M MURRAY] All right, so good. So let me use that to then introduce the next thing. So what are the specifications that we're trying to satisfy? What's the problem we're trying to solve, right? So let me say a little, and if I don't answer it, ask again. So let me just give you some examples of the types of problems that we're trying to solve. And again, this comes back to the different layers and what you're doing, right? So a very typical one would be a regulation problem.
38:38
That is, I'm trying to regulate the speed of the vehicle or the position of the aircraft or something like that. And for those, we would often do something, and sorry, I'm going to have to use some math that I haven't introduced. But we would do something where we say, "Well, I have an input-output mapping, and this input-output mapping is now going to be written in terms of operators." And so I've got some output Y, that's the thing that I measure,
39:01
I have some input U and some disturbance D, those were the inputs that I had. Uh, and I'm going to assume that there's some relation between these, and here I've written it in terms of a linear system of Laplace transforms, but just think of these as operators, right? I've got some operator PYu that takes some function U and gives me the component the output that would go along with that. Uh, this addition might be a more complicated interconnection, right, th-- uh, besides just addition
39:25
But I've got some disturbance, D. And I need to tell you something about the disturbances. So for example, I might say they're bounded in some way, right? I have a certain amount of energy in the disturbances or something like that. And the problem that we want to solve, if we were writing it as a control theorist, we might write it like this, which is complete Greek, so let me write it in terms of pictures. So for example, we might care about what are the transience to the system?
39:46
That is, if I tell you to change speed from 25 miles an hour to 35 miles an hour, right, how do you respond to that? And so for example, we might talk about that would be one that would be a traditional step response. So I give you some step input, I'd like you to go from, you know, zero to one, and the system will respond, and that system response, if it's a continuous variable and continuous time might, for example, have a little bit of oscillation or something else.
40:11
And you can imagine the specifications would be, well, I don't like the large amount of oscillation. Like, this is unchanging the speed and you go too fast and you slow down and then finally you settle into the right speed. That's not desirable. So we might have things like the rise time, how long does it take to get to the right speed? The overshoot, how much over speed do you go before you come back down? The settling time, that is, how long does it take you
40:31
to get within plus or minus 1% and stay there? So I might get up to the speed, but I overshoot it And then I come down, right? And so these are all the types of metrics that we might use. These are now cost functions, and I can now ask, can I design the controller to give those good characteristics? Another thing that we worry about a lot is not the transience, how do I respond to something changing but the steady state response. So steady state response often comes up when we
40:58
have something where the transience have died out and I'm now into some steady operation, think of this as some cyclical motion that I'm commanding, and so there's some initial transient And then I settle into that cyclical motion. And so often we'll talk about, for example, the frequency response if it's a system in continuous variables where I say, "Well, if I have, let's say, sinusoidal disturbances at some frequency, the wind is blowing, right, and
41:22
it's blowing at some frequency then how much do I amplify or attenuate, right, that blowing?" And so for example, if I'm a bridge and the wind is blowing at a certain speed and it's setting up certain periodic types of forcing, I might say, "Well, if that periodic forcing is at, you know, frequency 10 to the minus one, hertz or radians per second, I get some response," right? There's maybe a little bit of a resonance as I get to a higher forcing frequency, right, and then it dies down.
41:48
So we look at the gain from some input, whether it's my control input or my disturbance to my output then I can write what the gain is and what the phase is, the phase lag in a sinusoidal response, and I want to do this in steady state after the transience have died out. So that would be another specification, and I might give you specifications on these sorts of frequency responses. I don't want any frequency to be amplified more than a certain amount, or I want all frequencies above 100
42:13
hertz to be attenuated by at least a factor of 10, right? So those would be a different type of specifications, and again, we would then try and solve that problem. Now, these are the sorts of specifications you see often at this kind of lowest level, the fastest loops, these regulation loops. We often have things that look a little bit more like what we've seen where we might say, "Well, what if what I really want to do is that kind of open the, just planning, I want
42:36
to get from A to B, right, and I want to maybe minimize some integral cost function plus some terminal cost over some fixed horizon from time zero to T." Right? So I've got some non-linear system, I have some constraints on the states, the input, maybe the noise and I want to minimize some cost function. So these would be more traditional. We saw a lot of these sorts of things, for example yesterday.
42:56
I can also talk about specifications that happen not at the level of these kind of continuous types of variables, but if I have a finite state machine, right, that is describing my input-output system, then I might get something like this. So I'll describe this if I get to it a little bit later, but this is now a temporal logic formula that says something about the properties of the events that occur and the sequences of events that occur, right?
43:19
And so here now, we might have properties that are thought of as safety properties, so for people in computer science, right, what do you have? You have safety properties and liveness properties, right? So safety property, roughly speaking, says, nothing bad should ever happen. I should always stay at least a meter away from all nearby cars, I should never run into the curb, all right? They should never happen. Progress properties or liveness properties
43:39
are things that should eventually happen or should happen in a recurring way. So you should always recharge, you should always get back into your lane if you can, right? Things that, it's not like I should never do this, it's okay to get out transiently, but I should get back right? Something like that. And all of these, right? Are things that we can try and optimize over. And so typically, you'd have to say, "Well, which of these are you trying to optimize, right? And for what reason?
44:01
And then, what are the designs that let you do that?" And so all of these kind of come at the same time. One of the interesting things that I think about control theory, and particularly in the way it's going, is for the most part, these are three different communities, right? This is the sort of optimization community, right? This is the kind of frequency domain operator community coming from controls, right? This is the computer science community, right? So, you know, most people can't
44:25
read everything on the diagram, right? If I said, you know, "Translate this to English," uh, right? You know, it's like, "Okay. Box, diamond something or other", right? You know, "I don't know what the hell that means", right? I'll tell you in a minute, right? Most of you probably read this, but, you know, what norm am I using? What are these operators? What the hell's going on, right? So and I, and again, you know, at a high level though we're
44:44
trying to you know, do these transients, steady state, safety, and liveness properties. Okay, so I don't know if that answers your question about what problem you're trying to solve. Here's four, three problems that you might try and solve, written in a set of mathematics that, if I'm lucky, you understand one of. Uh-- [AUDIENCE MEMBER] You put time, what about-- So it's not just one problem, offline problem, it's in over time, so the specification include over time there?
45:05
[RICHARD M MURRAY] Yeah. So, so for example, you know, this might, I want, I've sort of written it as zero to T, but I might want this to be really little T to capital T. So, over every horizon, minimize this thing, right? In these transients and steady states, time is very much there, right? So I want the rise time when I get an event to within a certain, I wanna respond within a certain period. Can [AUDIENCE MEMBER] You really solve this? I mean, usually as soon as that you find local minima.
45:27
Is it true that, [RICHARD M MURRAY] Oh, so Yeah, I would say like all engineering things, right, local's good if it's good enough, right? So, you know, are they, you know the problems I've wr-- this problem is solvable, it's convex, other things, 'cause I've assumed a lot of structure. This problem is not convex, not necessarily solvable, but they're good algorithms to do it, right? They do good enough. This is roughly the problem that autonomous cars are
45:46
solving over and over again all the time, right? So we trust them, right? I mean, you know, you would go in an autonomous car, right? So you know, they're good enough. [AUDIENCE MEMBER] That's actually--
45:56
Just About your examples, but I notice, I noticed a lot of T and not very much X, Y, and Z. [RICHARD M MURRAY] Yeah. So it's true that I think-- Like partials. And then, yeah. So, so I would say, you know, I've said we can do partial differential equations and spatial temporal things, but I've not said a lot about it. Let me just give you an example of one, which comes from geoengineering.
46:14
So in geoengineering, one of the questions is, can we seed clouds? Right? And really the question is not can we make it rain, but where can we make it rain, and over what time? Right? And so one of the interesting questions that people ask is, if I did cloud seeding types of things, how much can I control the distribution over space of where the rain will occur? Right? Can I make it rain every place where there are fields and farms and other things, or do I not have that much spatial control?
46:40
So that would be one where now you're trying to integrate a cost function over some, you know, it's gonna be high cost over regions in which high cost for no rain in regions in which you have crops, right? So it can be done. Harder, 'cause you gotta do PDEs instead of ODEs and things like that.
46:57
Okay, so let me kind of describe a couple of design patterns. And what I'm gonna do is I'm gonna go into these in detail. So I'm gonna kind of show you what the standard patterns are, and then I'm gonna explain, I hope, what's inside these a little bit more.
47:13
And now this is kind of taking that box that I just labeled C and saying, "Yeah, but what do you do inside that box," in some sense. All right, so here's one standard design pattern. So I apologize, I've reused, well, controller. So here's my process, here's my disturbances and noise. So you recognize that part. And now I'm expanding out a little bit what's inside that C box. So this is the box that I said controller before. And what I'm telling you now is that here,
47:38
what I'm gonna do is I'm gonna take my measured output,
47:41
I'm gonna multiply that by minus one. I'm gonna take some reference. So think of this like the speed I want to go or something like that. I'm going to possibly process that information a little bit. Ignore this for a second. And then what I'm gonna do is I'm gonna compare my reference to my actual speed, and I'm gonna compute an error. You said you wanted to be going 35 miles an hour, you're going 33 miles an hour, you're off by two miles an hour.
48:01
And then what I'm gonna do is I take that error and I'm going to compute on that error, and I'm gonna figure out what input I should apply. You're two miles too slow, press the gas pedal down another quarter of an inch, right? Something like that. So we call this a reactive compensation, because I don't do anything-- Or, so the only way that my control changes is if the output does something different and I react to it, right? So if we assume that the reference is constant, right,
48:27
then I will wait until I see that I have an error before I do anything. So it's a reactive type of a controller. And these reactive controllers are very common. They can work very well.
48:39
The controller is sitting here in some sense. The feedback controller is sitting here. This piece here is usually a reference shaping box. So one way to think about that is, if I tell you I want you to go from 10 miles an hour to 65 miles an hour right now, all right? Then immediately you have a 55 mile an hour error, 'cause there's no way you're speeding up immediately. Now, if you give the controller a 55 mile an hour error, say, "Holy cow, all right? I am not going nearly fast enough.
49:08
Floor it." Right? You just push the gas down as hard as you can. Well, that's a stupid thing to do. What you probably really meant was, if I tell you I want to go 55 miles an hour, I'd like you to ramp up to that speed over the next 10 or 20 seconds or something like that. So it'll be much easier for a reactive controller if you don't try and get it to react to these huge changes, but give it something that's a little bit smoother, right?
49:28
And so we do this pre-shaping of the input in order to do that. So this pre-shaping of the input's very simple. It's usually just, like, a low pass filter, right, that just makes it so that the high frequency stuff doesn't get in there.Okay, So these reactive compensation schemes then they use reference input shaping, they have a feedback that's on the output error between the reference and the output, the compensator dynamics, that's sort of what's sitting
49:51
in here, or what shape the closed loop responds. We have uncertainty in the disturbances noise, and I've left it off, but you know, implicitly, whenever you see a control systems talk, assume that there's a little box around this guy. That's the unmodeled dynamics, 'cause we always think about that in the back of our heads. And here, the goals are the standard goals. We'd like it to be stable, that is that if I get noise or disturbances and those go away, I want to return to my
50:13
initial operating point. Um, I'd like it to have good performance, so for example if I do make a change in the reference, I track that well. And I'd like it to be robust. I'd like it to work even if this model isn't exactly right in presence of noise, in presence of disturbances. So this reactive design pattern is probably the most used design pattern. And to this question earlier about, you know, why are things getting better this reactive design
50:34
pattern made a lot of sense when you had relatively simple electronics and you couldn't do a lot of computation, because you just kind of looked at the error and then you kind of multiplied that by something and then kind of fed it back, and you'll see that in a second.
50:45
A more modern, and more complicated design pattern is this one. You can automatically see it's more complicated. All right, so the process still here, disturbances noise, all looks the same, but now I've really expanded out what I'm doing here. So first off, the observer is here. I had that over on the other side, but you know, I've sort of wrapped it a-- around a little bit. And now what I'm doing is something different. So let's kind of walk through this.
51:04
So this trajectory generation bit is a more sophisticated version of this reference shaping. So what I'm gonna do now is you're gonna give me the task description, and I'm actually gonna compute here's what you should do based on a model of the car, what the road type is, you know, what my current gas prices are, whatever you want, I'm gonna do a pretty sophisticated calculation to optimize one of those cost functions. And then, I'm going to give you two things.
51:31
I'm going to say, "Based on what I saw, here is the state that I think you should be at, right, to follow, to carry out this task, and here is the nominal input that you should apply in order to do that." Then what I'm gonna do is I'm going to take my process, I'm going to observe if, if this has, sorry, if this process has some internal state x, the position, speed, acceleration, whatever is required to describe the state, I'm gonna observe that state, and then I'm gonna say,
51:57
"What is the actual state of the process compared to where I think it should be based on this complex calculation that I did?" And that's gonna form my error. This is not the output error, but the state error. Okay? So the state of the system might be, for example for a car, its position in the lane, its side velocity in the lane, its forward velocity, right? Those three things.
52:15
And then I'm going to put some feedback in here, so this is just like the C of S, but it's on the state error, and I'm going to add that to the nominal input. And so the way to think about this is, if the model were perfect and the trajectory generation module knew that model, then I would exactly know and calculate what input to apply for you to follow that. And I wouldn't need to do anything. But the model's not perfect, and there are disturbances and
52:40
noise, so I also put in this feedback compensation bit, right, that corrects for that. But it doesn't have to correct for everything. And you asking why are these things so much better now, well, part of it is that they can do this feedforward calculation, so we call this a feedforward calculation, FF for feedforward, where it can say, you know, "Look, I know what the engine dynamics are, so I know if I press the gas this hard, right, this is what I can do, and so if you tell me to speed up,
53:04
it will speed up very smoothly and other things." Um, furthermore, I might even say, "Well, I see that I am slowing down and I'm guessing based on my GPS that I'm actually on a hill, right, and so I'll press it down a little bit further." They typically don't do that in cars, they do that in trucks and trains and things like that. That is they pre-compute, right, here's how much input I should apply based on changing speed limits in trains, for example, right? And they save fuel that way.
53:29
So we can do that now, because that's like a small microprocessor's worth of computing, right, that costs a buck, right? You know, not a, you know, $30,000 computer, right, that it used to cost 20 years ago. So this more complex pattern is kind of predictive compensation. It has still a reactive compensation in it, but it's predicting out based on some sort of a model of the system it may have a model of the environment, right, it can have all sorts of things that can come into it.
53:55
And so this is typically what you see. And so here we do explicit computation of trajectories given a model of the process, and potentially a model of the environment. And this is, for example, what an autonomous car does, right? It knows where all the other cars are, it has some estimate of where they're gonna be, it plans out a trajectory and says, "Here's what you should do," right, for some period of time, and then it says, "And here's the amount to turn
54:17
your wheel, assuming I'm right, and here's the amount to press your gas pedal, assuming I'm right." And then if I'm wrong, I don't quite steer the right way, right, because the road was a little slick or I didn't calculate something right, I'll correct for it, right, with this little feedback loop in here.
54:29
And then I'm gonna say more about this later, but just to say there's this little dash line here, 'cause one of the things that you figure out very quickly is, it's not that I want to calculate this out once and then not recalculate it, right, I want to constantly recalculate it, right? So you could imagine saying, "Oh, well, I want to drive from, you know, here to the Berkeley BART Station or something like that, let me just pre-compute, right, ahead of time exactly when I'm
54:49
gonna turn the wheel and how much and all of that stuff." That's a fine thing to do, right, except that as soon as I get out there, I'm gonna find out the roads are wet, right, which wasn't in my calculation right? And so now I know the roads are wet, so I should redo the calculation, right? And redo it and redo it and redo it, right? And so that notion is what we do all the time now. And that works because we have lots of computation.
55:09
Okay, so that's, these two design patterns are the primary ones. What I'm gonna do next is tell you more about what go into these. Um, let me pause and ask whether there are questions at this point and then if there are none, I'll do one more slide, and if there are, then I'll then we'll take a break I'll answer them and take a break.
55:29
Questions on these design patterns or what I've said so far?
55:37
Yeah? [AUDIENCE MEMBER] When you, I may have missed something, when you do the trajectory generation-- It, it seems like there's a lot of knowledge that has to go into picking the trajectory. Like, you might pick a dumb one, or an expensive one. Yep.
55:52
So how do you
55:54
[RICHARD M MURRAY] Yeah. So, I think there's several ways. So one is, you can --If you have good models of what's going on, and you have a cost function that captures what you want, and the problem is either convex Or you've got a good algorithm that can sort of sort through things, then you will, if that model's a good one, solve out a pretty good trajectory, right? And so, you know, if I'm driving on a dry road And I want to know, you know, I need to change lanes
56:17
and things like that, that's a pretty easy problem and I can compute that out.
56:21
For some problems that won't work. If I'm doing supply chain management, I may or may not have a really good model of, if I place an order on Monday, right? How many of these am I going to get? At what time, right? Because I, maybe I don't know what the model is of the production facility that's producing these and other things, right? And so it may be much noisier, and you may have to rely on some reactive thing. Oh, I don't have enough of these, so I better order more of them, right?
56:41
And I really don't have enough now, I better put in an emergency order, right? Things like that. So, all of those are trade-offs. One thing that's changing is that in many situations this trajectory generation bit is being done based on data, right? So for example, if you're doing self-driving cars, you can think about, okay, well, I need to decide how to change lanes. Well, that's complicated because there's some people on the corner over there, and there's some bicycles
57:04
over here, and the person coming up behind me is coming at this speed, right? But I've collected billions of miles of data. Can't I infer, right, the most probable thing a human would have done, right, and then use that trajectory as my nominal trajectory, right? So, you might be able to do something with data. And now I still have a model. My model's my data, right? But I don't have an explicit, say, physics-based model or a computing model of what's going on.
57:28
So but, implicit in this is I have to somehow be able to take my task description and convert it into what I think the system should do based on some representation of some knowledge about the system dynamics.
57:43
That's the point of view.
57:47
Yeah? [AUDIENCE MEMBER] I have a two-part question. It sounds like this feedforward trajectory generation could really be called planning rather than control, is one thing. [RICHARD M MURRAY] Yep. [AUDIENCE MEMBER] And the other is that, if you're looking for pure control, I don't know if you need it. I mean, suppose you just use feedback, and some assume some physical limits, like you cannot press the gas pedal more than so much, or assume, put some bounds on what you're allowed
58:09
to do in response. Right. Can you get rid of feedforward control? [RICHARD M MURRAY] Yeah, it's a great question. So, I agree with you that, you know, it's not strictly speaking feedback control, right, by the name. I think increasingly we think of planning as being part of the broader control problem, in part because of this little dashed line here, which is, in fact, you rarely do planning kind of once way ahead of time and never revisit it. Increasingly, in many of these applications,
58:36
you replan over and over and over. And that's a feedback loop, right? Because I plan, something happens, I see what happened, I replan, right? And so this trajectory generation, I've sort of described it as feedforward, it's kind of open loop, but it's not really when you start closing the loop around this thing. Now, do you need it or not? Can you do a purely reactive thing? Can you use the upper design pattern, for example, or just the part of the design pattern down here?
58:57
Sometimes yes, and if you can, it's much less complicated and you should get away with-- You can do it. It gets hard when the control task involves things that are not right now, right? So think about driving a car, right? You could take a very myopic point of view and say, "Look, you know, I want to change lanes. Is there anybody next to me in the lane or not?" Right? And that's it, because that's all I know is, let's say, the distance to the nearest car.
59:22
That distance is, you know, greater than zero, so I'll move over, right? But, of course, we can all appreciate that what you really want to do is you want to think through, where am I going? What does the road look like ahead? Are there other cars down there? Now you're doing planning, right? So if you're looking at something forward in time, and of course to do that I need a model of what those other agents around me do, right in order to do that.
59:40
So I have just some model of the environment and propagate that model, right? So I would say if you can get away with just this part, you should do it. I had a former student of mine who went and started his own company and he took the controls class that I taught like 20 years ago, and he said, "Richard, you didn't spend nearly enough time talking about this, because that's the way we get all our performance," right? Because increasingly, that's sort of, you know, if I need to,
1:00:04
if I've got, I'll gi-- give you the example he was working on. They were trying to get a satellite that wa-- uh, antenna that was pointing at a satellite on a moving vehicle, right? You can do that in a reactive way, that is that you can just wait and see the signal's going down And so I need to move it back, right? But I know how I'm driving the vehicle, right? And so I can feed forward that information. I'm about to turn, so you better turn the antenna the other way.
1:00:26
How much you turn it, we'll use a model to do that, right? So, I think increasingly as computation has gotten cheaper, we've gone to the second design pattern more and more and more.
1:00:37
Okay, so this is probably a good place to take a break. And you'll tell us when we're coming back. [HOST] Well we should all be back at 3:30, and then we will start with the second session. [RICHARD M MURRAY] Fantastic, and I'm about halfway through my slides.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat