Skip to main content
Loading Explore guides…
Search in AI · Acedra
Home
Explore
Computer Science
Search in AI
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
189 segments
Copy
Hide video
0:00
PROFESSOR: Okay, we're going to get started.
0:05
So a few announcements, homeworks and projects coming up. You can see the dates up there. Just a quick comment on homework and project 0, which are optional. Why on earth would you do an optional homework assignment? The math is a little heavier in the second half of the course. And so if you want to get a bit of a gauge for what sort of math background and familiarity will be helpful, you can go ahead and do project 0 or homework 0, so that you're not too surprised halfway through the course.
0:58
And the time for the final was listed wrong last time. Sorry about that. But these are the corrected times. 3:00 to 6:00 PM. Any questions on that? Okay, let's get started. So the first topic is search. So last time Cam was talking to you about how a key part of artificial intelligence is trying to accomplish things. There are lots of ways that you can try to do things. And only some of those ways will get you to the outcomes you seek. And so what we're going to be talking about today
1:44
is the most pared down, simplified version of how to search for solutions.
1:53
So today we're going to be talking about agents that plan ahead. We're going to talk about what a search problem is. And then we're going to discuss a few uninformed search methods. And we'll talk a little bit about what uninformed means.
2:14
So here we have an agent thinking about how to accomplish some task of shooting an apple down from a tree. And the scheme is kind of showing-- one thing you might try to do is send your projectile straight at the apple, or you might try to account for what's going to happen to it later. So agents that plan-- and I think I'm skipping ahead a little bit. Agents that plan have to think about not just the very next action but what's going to happen thereafter. So a reflex agent is--
3:01
we'll compare this to a planning agent. A reflex agent chooses an action based on its current percept and maybe its memory, like its perception, its observation of the world. And it may have a memory. It may have memory or a model of the world's current state. But it doesn't consider the future consequences of its actions. It considers how the world is. So can a reflex agent be rational is the first question that I will put to you guys. Any thoughts on that?
3:35
Yeah. STUDENT: I guess. PROFESSOR: You guess. Okay yeah. Any other answers? Tell me more? STUDENT: Because that's what I did. [INDISCERNIBLE]? PROFESSOR: Yes. This is meant to be-- it has to satisfy all these things, not just one. Yeah. STUDENT: I do consider future consequences though, [INDISCERNIBLE]. PROFESSOR: Right. Although, maybe you don't always consider future consequences. So maybe sometimes you act a bit like a reflex agent. But yeah.
4:13
Okay, so sometimes you're a reflex agent. Would you say in those moments that you're rational, that you could be rational. STUDENT: Yeah, based on-- PROFESSOR: Yeah, sometimes reflexes can produce exactly what rationality would produce. It's not a very efficient way to live your life because you can't write down every possible state you could be in and have a table for what you're going to do in that state. So maybe in general, it can't be rational. But maybe in specific circumstances it can be.
4:53
So here is a reflex agent that is going to actually behave quite rationally.
5:07
Is it playing?
5:11
There we go. So the reflex that it is acting according to is if it sees a pellet next to it, it goes there and eats it. And in that circumstance, it does as well as we could hope.
5:33
Here is a video of the same reflex agent in a different setting. And maybe you can try to predict what might happen to it. Let's see, does the arrow work here? No, that skips it.
5:57
Sorry. I can't see if it's going.
6:07
What? Sorry.
6:16
What happened?
6:19
Yeah. STUDENT: [INDISCERNIBLE] PROFESSOR: So at this spot it's acting according to its reflex. And the reflex doesn't really help it figure out that it should turn the corner and see what's going to happen next, or what it could accomplish if it went that way. So planning agents, on the other hand, ask, what if. So it makes its decisions based on the consequences of its actions, or more particularly what it thinks the consequences of its actions will be.
6:59
So it must have a model of how the world evolves in response to its actions. Otherwise, what do you do? And it must have some way of deciding whether some possible future meets a goal. That's the goal test that it has to formulate. So it has to consider how the world would be. And we're going to talk later about a few distinctions in planning, which are optimal planning, complete planning, and planning versus replanning. So here is a video of a replanning agent. So let's watch it first.
7:42
And then we can talk about what's going on. Nope, that's not it. There we go. So right now it's thinking, or the video is not playing.
8:01
It works when you test it.
8:11
Sorry, I don't know.
8:22
This is very strange.
8:34
Okay, there we go.
8:47
So this agent is planning a little ways ahead. And then it's not planning out its whole lifetime trajectory all at once. It's planning a little ways ahead, rethinking what's the best strategy from there, and then repeating that a few times. And here is mastermind Pac-Man that plans once and then executes. So right now it is thinking, precalculating, searching for a path.
9:34
Takes a little while. Takes its time.
9:48
It's figured out the best way to eat all the pellets in the quickest way possible.
10:00
So we're going to talk first about how to search in this way, how you could write the code for that. Okay, now I'm going to go back to presenter mode.
10:18
Yeah. STUDENT: Do the replanning models kind of also [INDISCERNIBLE] because it changes what happens [INDISCERNIBLE]?
10:32
PROFESSOR: So a key feature of a reflex agent is that it doesn't think ahead at all. And so this thinks ahead a little bit. And so I think technically wouldn't meet the definition. But honestly, the boundary is a little fuzzy because the current state does have all the information for how the world is going to evolve. And so you could consider the information that would tell you how the world is going to evolve as part of the current state. And you could look at that part of the state.
11:11
And so it is a little bit fuzzy. And so you could think of the near future as being something you can read out just by looking around you. And so if you're thinking about the difficulty of reading out the future from the present, then you could say that something that's only looking a little bit ahead is a little more like a reflex agent. So it's certainly on the way to that. What was that? STUDENT: Having reflexes isn't necessary the only thing [INDISCERNIBLE]. PROFESSOR: Yeah.
11:41
It's also defined in terms of what it doesn't do.
11:48
So if we're going to be writing algorithms for solving search problems, the first thing we need to get straight is, what information are we going to feed these algorithms? What is the information that the algorithm needs to know to plan a path to a goal?
12:13
Try to think about-- if I were to tell you, come up with a way to snake a door. You'd have some questions for me. What would some of those questions be? Yeah. STUDENT: How will you know if you've successfully done it? PROFESSOR: Yes, how will you know it you have successfully snaked a door? Yep. Any other questions you might have for me? STUDENT: [INDISCERNIBLE] PROFESSOR: Yep, so that's I think that's another way of saying, that the objective is the same as understanding a set of ways
12:59
that you could make the world be such that you have successfully snaked a door. So you need to recognize whether that is something you've done. Other things you might need to know.
13:16
Yeah. STUDENT: What you're able to do? PROFESSOR: What was that? What you're able to do. Yeah exactly. So you need to know what actions are available to you. And any other questions you might have. Yeah. STUDENT: Maybe something to maximize or minimize [INDISCERNIBLE] for a step or amount of time it takes. PROFESSOR: Yes, so that will end up being basically the-- so we brought up, you'll need to know what actions are available to you. What are your options?
13:48
And then, is there some cost associated with those actions? Are some actions better to take than others? And there's one other that I'm thinking of, but I'm happy to move on to it if it doesn't occur to anyone right now because you might take it for granted being that you already know how to navigate the world. Yeah. STUDENT: [INDISCERNIBLE] the door? PROFESSOR: [LAUGHS] Yeah. Yeah, that would end up being helpful. Yeah. STUDENT: Maybe [INDISCERNIBLE].
14:22
PROFESSOR: I think these all end up being ways you might represent your understanding of being able to answer the question, have I successfully snaked a door? Yeah. STUDENT: If or how the world changes based on your actions. PROFESSOR: That's the one I was thinking of. Right. So you need to know what your actions are and then what your actions will accomplish.
14:47
We might have skipped this one. A search problem consists of a set of states that the world can be in. So here's our Pac-Man example. And this is obviously not exhaustive. But here are a bunch of possible ways that the world could look. And you could imagine, if a reflex agent were going to try and write down what they were going to do in every one of these, this would quickly become a very unwieldy. We need a successor function with actions and with costs. So that means we take the state.
15:21
We take the proposed action. And it produces, what's the next state going to be? And how much does that action cost? How bad is that action? So here is an example of an input and output to that function. So it takes in a state. It takes in a proposed action. Here's the cost that comes out. And here's the next state that comes out, north and east for the way that Pac-Man moves.
15:54
We need to start state. Where are you? Of all these states that you could be in, where do you start? And then, how do if you've reached the goal? So a solution to a search problem is a sequence of actions-- that is a plan-- which transforms the start state into a goal state.
16:24
So search problems really never do they actually capture the whole picture of the world. So here's the real world. And here is some model of the world that makes the search problem feasible. So the set of states that the real world can be in is enormous. I mean, it's not necessarily even countable. We don't really know.
17:08
And a lot of the details about how the world is are going to be irrelevant for a problem. If my actions are taking steps forward, and I'm trying to get to that door over there with all these obstacles, the state of the world includes, how many people are in the White House right now? But that's not going to be relevant for me when I'm trying to solve my problem. So this is known as an abstraction. And there really hasn't been a lot of progress in AI in the last 50 years
17:47
about how to do that in a good way. It's a hard problem. People don't really know what they're doing.
17:55
Somehow we get an abstraction. We use our human ingenuity, at least the way we do it today. And we've come up with some abstraction of the world. And then we have a much simpler problem, a much smaller state space. And we can model how the state changes when we act. So here is an example of a very simplified model of a part of the world. This is a road map of Romania. And we are starting in Arad. And we are trying to get to Bucharest. And the successor function is you pick a road to go on.
18:43
And there's the cost that you get for taking that road. And then it outputs the city that you end up in. So rather than the state space being every possible configuration the real world could be in, the state space is just, what city are you in? And then all you need for the successor function is how actions change which city you're in. So the start state, as I mentioned before, is Arad. The goal test is, am I in Bucharest? And now we have everything we need
19:17
to try to come up with a solution, the least cost sequence of actions that will get us to Bucharest.
19:31
So the state space, as I mentioned, is going to be different. The state space for a search problem is generally going to be different from the world state. So the world state includes every last detail of the environment, whereas a search state keeps only the details needed for planning. So here is an example problem, which is pathing. You're not trying to eat all the pellets as you are a normal Pac-Man. In pathing, the state is just the coordinates of where you are.
20:01
The actions are north, south, east, and west. And the successor just updates your location. The goal test is, have I gotten to the end state?
20:13
And you can check. If your goal is to get to the end state, and these are your actions and the way the world evolves, this is all you need to keep track of you. Just need to keep track of your location. For the eat-all-the-dots problem you need to keep track of some more things. You need to keep track of where you are. And you need to keep track of where the dots are. So this dot Boolean means, is there a dot there? Is there a dot there? Is there a dot there? is there a dot there?
20:38
So it's going to be a long string of 1 and 0, depending on whether there is a dot in that location.
20:46
Same actions as before. Successor function updates the location. But it also may be updates the Boolean of dots, the signature for whether there's a dot in any given spot. And the goal test, you ask the question, okay, are all the dots false? Or is there no dot in every spot?
21:13
So let's think a little bit about state space sizes and why it can be helpful to make these smaller, how we can make them smaller. So in the world state for this version of Pac-Man, there are 120-- let's see-- positions the agent can be in. So that's 5 by 6. Is that right? No because it can be in the middle of them. 120 agent positions. There's a 30 different food pellets. There's 12 positions each of the ghosts can be in. And the agent is either facing north, south, east, or west.
22:00
So how many total states are there going to be here?
22:06
STUDENT: [INDISCERNIBLE] PROFESSOR: Yeah, you can express it as an equation rather than a number. STUDENT: [INDISCERNIBLE] multiply all the possibilities. PROFESSOR: Yep, multiply all the possibilities. And there's one that isn't just multiply. So it's not just 120 times 30 times 12 times 4. One of the terms is different. Yeah. STUDENT: [INDISCERNIBLE] PROFESSOR: I think maybe they can be. But yeah, if they couldn't, then it would be 12 times 11. Yeah. STUDENT: 2 to the 30 [INDISCERNIBLE]..
22:38
PROFESSOR: Right. 2 to the power of 30 because there's two options for whether this exists or not, two options for whether this exists or not, two, two, two. So it's 2 to the power of 30 there. That's too many.
22:56
But note, if you're just trying to get from one location to another, the only part of the world state you'd have to keep track of is your position. The rest you could just ignore. So that's a much smaller state space. States for eat-all-the dots, well, you can make it a little smaller, but not much. Sorry, 12 squared, not just 12.
23:24
I didn't say that right the first time.
23:31
Here's a slightly different goal. The problem is eat all the dots and keep the ghosts perma-scared. Does anyone does anyone know how Pac-Man works to explain what keeping the ghosts scared is? Yeah. STUDENT: When you eat the big ones, [INDISCERNIBLE],, but unfortunately they run from you. You can't [INDISCERNIBLE]. PROFESSOR: Yes. And it only lasts a certain amount of time. So what do you need to keep track of in the state if you are going to try and fulfill this goal?
24:03
It's all the same stuff as in the eat-all-the-pellets problem. What else?
24:11
Yeah. STUDENT: How long the scare lasts, like how long [INDISCERNIBLE]. PROFESSOR: Yes, how much time you have left where they're going to be scared, so that you can make sure to eat a big pellet before then. Yeah. STUDENT: [INDISCERNIBLE] PROFESSOR: Yeah, that's right. I think so. Were you going to say something else? Or ask a question? STUDENT: Oh, I was just going to say, you could keep track of how many big dots are left. PROFESSOR: How many big dots are left. Oh yeah.
24:41
Yes, you definitely need to keep track of that and their location.
24:50
There we go.
24:55
So when I showed you the map of Romania, that was a graph of the state space with edges corresponding to your actions. And now we're going to talk about a different kind of graph, which is a search tree, very related. The nodes are still states you can enter. The edges are still actions you can take. But it's organized a little differently. So a state space graph, like the map of Romania, is a mathematical representation of a search problem. The nodes are configurations the worlds can be in.
25:32
That's states in the state space. The arcs represent successors, how you get from one to another. And then some nodes in the graph will be labeled as goal or start. So here's a diagram of a very small part of the state space graph for Pac-Man on this tiny 3-by-3 grid. So you can take the north action. And then this transforms to that. I think there are actually some mistakes in here. But I didn't bother to correct them. It looks more or less like this.
26:10
In the state space graph each state occurs only once. This is going to be different from the search tree. And it's too big to fit in memory usually. Usually, state spaces are quite large. But it's helpful to think about it existing, even if we can't write it down.
26:31
Here is a tiny state space graph for a tiny search problem. Here's our start state. There's our goal state. Here are all the different ways we can move around.
26:50
A search tree has a root. This is called the root of the tree. And then there are arrows down. And there are never any cycles. So it starts at the start state. And then every action gets an edge to a new state.
27:16
And then it goes from there. So these are all the different. This is north, east, and south, and so on. And it keeps branching out from the start to where you can end up. This is a what-if tree. Start date is the root node. Children correspond to successors. And the nodes show states. But really more precisely, each node is a path from the start state to a certain state. And you can kind of follow it back up to see the path that got you there. So there are plans that get you there.
27:57
For most problems, again, we can never build the whole tree. So here's a comparison for that toy problem of the state space graph versus the search tree. And you'll see that some states appear twice in the search tree because there are two ways to get there.
28:21
So each node in the search tree is an entire path in the state space graph. So that's the way of interpreting these is actually different things. This isn't just talking about state G. It's talking about the path s-d-e-r-f-g, whereas this is talking about the path s-e-r-f-g.
28:42
A little quiz. Here is our 4-state graph. How big is the search tree starting from S?
28:56
When I say, how big, how many nodes is it going to have? Yeah. STUDENT: Infinite because there's a cycle. PROFESSOR: Yeah, infinite because there's a cycle. Exactly. So let's start expanding it. We have S. Then the children are a and b. Then the children are b and g, children are a and g. Keep expanding. I made these As and Bs. They'll never end. There's lots of repeated structure here. So right, it's infinite. Now let's actually get to solving search problems.
29:29
Here's our example again, starting in Arad, going to Bucharest. Here's the plan. We use a search tree. But we don't write it down because we can't write it down. So we progressively write down more and more of it. So we expand out potential plans, that is the nodes of the tree that we have written down so far. And we maintain a fringe of partial plans under consideration. So right there's one plan under consideration, which is start at Arad.
30:02
And we will try to expand as few tree nodes as possible. Now we've gotten rid of the plan, start at Arad, in favor of more specific plans. Start at Arad, then go to Sibiu. Start at Arad, then go to Timisoara. Start at Arad and go to Zerind. I have no idea how to pronounce these words. But hopefully that's not too bad.
30:27
Okay, we have to keep going. We haven't gotten to Bucharest. Let's refine this plan, from Arad to Sibiu, to a more refined plan, Arad, Sibiu, back to Arad, or Arad, Sibiu, Fagaras. You get the point. So we keep expanding possible plans. This whole search tree, we can imagine it existing still. And we're just uncovering it bit by bit.
30:59
So here is the general tree search strategy.
31:05
It takes as input a problem and a strategy for doing something that we'll get to later. And it returns either a solution or an admission of failure. So we start with the problem. We input that to the algorithm. And then we do the following on the loop. If there are no candidates for expansion, then the search is failed. Otherwise, we choose a leaf node candidate for expansion according to some strategy. These are the nodes on the fringe.
31:42
If the node is a goal state, then we are done, and we return it. Otherwise, we expand the node and add the resulting nodes to the search tree. So we'll get into an example of this soon. The main question is, okay, how are we picking a node from our set of partial plans to decide which one to roll forward a bit? Any questions from this point? Okay. Let's do an example. So we started at S. Here is our fringe of partial plans. The partial plan is start at S. Okay, that's a good start.
32:26
Now we check if that's the goal state. No, it's not. And now we expand it and cross that off. So now we have new partial plans. Our fringe is the set of clear circles, d, e, and p. So we add those to our fringe. And now using some strategy, an arbitrary one for now, we'll pick one of these to expand. Let's pick S to d. So that's not a goal state. We expand it. We cross it off from our list of partial plans. And we add new ones, new partial plans to our list, SDB, SDC, and SDE.
33:10
So these are paths in our world, in our search problem. Let's pick another one to cross off and expand. Let's cross off SDE, still not a goal state. Let's then cross off SDER, and so on, until we get to the goal. So right now we're kind of just doing this at random. We keep crossing things off and adding new ones on. And eventually we get to a goal. Any questions about how this is kind of maintained and run? Yes. STUDENT: Does this look like DFS [INDISCERNIBLE] heuristics?
34:05
PROFESSOR: This is arbitrary. The next slide is going to be DFS. And heuristics are going to be on Tuesday.
34:15
Yeah. STUDENT: Is there a reason that [INDISCERNIBLE]?? PROFESSOR: There's no reason. This is technically not an algorithm. I mean, this is just someone chose it.
34:27
What makes the algorithm specific is having a set strategy for picking which of these you're going to expand. And so in this example, someone just decided.
34:40
So now let's actually talk about different procedures by which to decide which path to take off the fringe and expand.
34:55
I didn't mention the last step, which is returning the solution.
35:02
So now we're going to talk about depth-first search. And here is a little diagram of it. Here is your search space. And you just start by plowing down. And with that one, we just looked like depth-first search if you reorganize things a bit. So the fringe in depth-first search is a last-in, first-off stack. So what that means is we're keeping track of this fringe of paths that are partly explored, but we're going to need to explore more in the future. We're keeping track of that.
35:43
And when we decide to take one to expand further to look at its children and see what we can do from there, we look at the last one that we added on. So how does this proceed? We have S. So now our fringe is S. Now S is crossed off the fringe. And we have SD, SE, and SP. So the last one added-- I guess we're going right to left here. So first we add SP to the fringe. Then we add SE to the fringe. Then we add SD. So the last one we added was SD. So that's the one we take off and expand.
36:25
So now SD is no longer on the fringe. What's on the fringe are still these two at the beginning and now below them, SBE, and then SDC, and then SDB. So then we take SDB off, put its child on. This is the latest one we added to the fringe. So we evaluate that. But it doesn't have any children. So that's nice. Our fringe is finally starting to get smaller rather than bigger. You can see there's no nowhere to go from here. And so now the last one we added to the fringe actually was added before.
37:01
It's this one, SDC. Again, this is how it proceeds. Finally, found a path to the goal. So you can see why it's called depth-first. You go down until you can't go anymore. You go back up. You try another fork that you bypassed the first time. And you keep going until you reach the goal. So let's talk about how the search algorithm behaves.
37:37
First question-- and this was a property of search algorithms I told you we'd talk about at the beginning. Is it complete? That is, it guaranteed to find a solution if one exists? Have a think about this. And then I'll wait to see five to ten hands if anyone thinks they have an idea about this. Is this algorithm guaranteed to find a solution if one exists?
38:14
Yeah. STUDENT: Yes. PROFESSOR: Yes. Okay. Any explanation for that? STUDENT: Because eventually it will cover all of the possible paths. So if there's a solution that actually exists, [INDISCERNIBLE]. PROFESSOR: Yes. That answer is correct in the example I showed you. But it's possible to write down a search problem where it's not the case. Can anyone think of a search problem where that would fail? Yeah. STUDENT: If there's an infinite loop, [INDISCERNIBLE].. PROFESSOR: Yeah, exactly.
38:50
So if there's an infinite loop, and you keep-- remember that one where it was SAB and then something on the right. You could just keep going back and forth with A and B. You might get lucky and go off the loop. But depending on the order in which you're adding the children of a node onto the tree, you might end up just going down and down and down forever and never stopping and coming back up.
39:20
The next question, is it optimal? That is, is it guaranteed to output the least-cost path? Yeah. STUDENT: No. PROFESSOR: No. As observed in that example, if we suppose that everything has a cost of 1.
39:38
Oh no. Sorry, that one was optimal. But yeah, in general, no, not optimal. It could find a roundabout route. Yeah. STUDENT: Why didn't it start with B when [INDISCERNIBLE]??
39:53
PROFESSOR: What were you expecting? STUDENT: Like, why didn't it start with B first? PROFESSOR: So if we add B-- if we add them to the queue left to right, then we would start with E first because E was the last. Well, in fact, we'd start over here. If we add to the queue left to right, then we'd start over here. Here, we're adding them to the queue right to left. And so we take them off of the queue, last in, first off. So we take them off left to right.
40:23
The order you add them is kind of arbitrary. So this is just in this example. It would have ended up being quicker if we'd done it the other way. But this is uninformed search. You don't know. You can't see ahead when you're deciding which one to expand what's going to be the best strategy. Yeah. STUDENT: [INDISCERNIBLE].
40:51
And also, for past paths, why is there [INDISCERNIBLE]??
40:59
PROFESSOR: Yeah, that's arbitrary.
41:05
In general, when you're adding a node's children to the queue, there isn't really any. The search problem itself doesn't give you a specific order that you should do things in. So in reality, when we were looking at that algorithm, the strategy for taking things off the queue isn't the only thing going on. There's some underlying-- you could think of it as randomness or just an arbitrary choice for how you add them onto the queue. If they were added onto the queue in a different way,
41:38
then depth-first search would proceed in a different way. And so I could show you a slightly different thing and tell you that was an example of depth-first search, even though it looks different. And it would just be determined on the order in which things are added to the queue.
41:57
It doesn't have to proceed left to right. Obviously, it doesn't because there is no concept of left and right in the search problem.
42:12
Time complexity and space complexity. What are time and space complexity, first of all?
42:24
Yeah. You had your hand up, right? STUDENT: Run time and then like memory. PROFESSOR: Yeah, how long the algorithm takes to run and how much memory it uses. And usually that'll depend on attributes of the problem you're trying to solve. So here's a cartoon of the search tree starting at the start state and going down. And then the branching factor is generally how many different actions are available to you in those states. There can be a different number of actions available to you
42:59
at different points in time. So then the number of actions is B, which ends up being how many children each node has. So at the first level, we have one node. At the next level, we have b nodes. At the third level, we have b squared nodes, and so on. This gets out of hand very fast. So at the very bottom if there is a maximum depth of m tiers, then there would be b to the power of m nodes in the last tier. Now there might be solutions at various depths. Even if there's only one goal state,
43:36
there might be multiple ways of getting there. And each node in the search tree corresponds to a way of getting to a state. So let's say that those red circles are two ways of getting to the goal.
43:52
Well, before we talk about how depth-first search proceeds, let's first talk about the number of nodes in the entire tree. So that's going to be 1 plus b plus b squared plus b to the power of m, which is going to be within a constant factor of just b to the power of m. I mean, if b was 10, and this is 1 plus 10 plus 100 plus 1,000 all the way up to a billion, you'd end up with something pretty close to a billion.
44:22
So most of the nodes are in the last layer. So how does DFS proceed in this kind of schematic search tree? Take a moment to just make a prediction.
44:36
It proceeds more or less like this. And this is, again, if the successors from a state are being added left to right, and then you're taking off what was added last, you take off the leftmost first. And so then you proceed along this way. And you can see that that's not the best solution. This would have been a better solution. But, oh, well, at least we got a solution. So this could process the whole tree. If m is finite, then it takes order b to the power of m time
45:11
because each node takes some amount of time to process. How much space does the fringe take? So let's think about what the fringe is. The fringe is the number of paths that we're considering expanding.
45:35
It's only the siblings on the path to root that we're currently at. So let's take a look at this.
45:48
So here's our search tree. And let's imagine we were just going down the leftmost for a ways. You'd have all the siblings down here of this one, all the siblings down here of that one, all the siblings there, and so on, and all these siblings. So you'd be maybe md if m is your maximum depth. And all the b minus 1 siblings that you passed over for the time being would be on the fringe too. So you have to keep track of all of these clear circles. You don't have to keep track of-- is that right?
46:24
No, you do have to keep track of these. So you're keeping track of the fringe.
46:32
Sorry, I got that wrong. You don't have to keep track of these. You don't have to keep track of the ones in gray. Once you've exhausted these, you can just go straight to here. They're not in your fridge. Although, I guess, they are still stored in your tree, so you can return a solution. So in any case, when you go all the way down here, that's a depth of m. And there's b different nodes at each level. So that's a total of b times m that you need to keep track of.
46:59
When you've exhausted this branch, and now you're going down another one, you don't have to keep track of these anymore because you've already determined that they don't lead you to the goal. So as you're proceeding through a tree, you are able to forget large parts of it, which is helpful for memory. Where was I? Here.
47:28
Order b times m memory. Questions about that computation? Yeah. STUDENT: Professor, [INDISCERNIBLE] the average thickness or [INDISCERNIBLE]?? PROFESSOR: Both. STUDENT: [INDISCERNIBLE] PROFESSOR: Both. STUDENT: Both. PROFESSOR: Definitely the worst. Let me just make sure that's right for the average. I mean, you have to define a probability distribution over problems. But for any sensible one, I think it would be dominated by that, by the worst case. Yeah.
47:59
STUDENT: Somebody just said it was incomplete given [INDISCERNIBLE]. PROFESSOR: Yes. So that is definitely correct. This is only if you have a limit of m, a depth m limit. If m is infinite, then you plug-in infinity there. And you get the infinity you're looking for.
48:23
Only complete if we prevent m from being infinite. Is it optimal? No, it finds the kind of left-most solution, regardless of the depth or the cost. Now let's talk about breadth-first search. Question. STUDENT: [INDISCERNIBLE] the detector [INDISCERNIBLE] thinks that it's [INDISCERNIBLE].. How do we know [INDISCERNIBLE]? PROFESSOR: So in the depth-first search I described to you, we don't check for loops. We just terminated after m steps or not. I mean, there's a variant of depth-first search
49:07
where you do check for loops. That will help you even in infinite spaces to terminate successfully. Although, you still can go down an infinite path if your state space is infinite, even without going on a loop. So checking for loops will help you solve some of the cases, not all of the cases. I haven't discussed it yet. If you want to do depth-first search with loop checking, then you need to keep track of-- I think you can still just keep track of the same nodes.
49:42
And then every time you expand a node, you make sure not to add it if it's up and if it's in the history. So it's a sensible thing to do. And anyone doing depth-first search in real life would probably do it. Yes. STUDENT: If you do take that route, where you circle back and make sure that you're not adding things, does that mean that [INDISCERNIBLE]? PROFESSOR: No, not necessarily. If the state space is finite, then yes. If the state space is infinite, then you
50:18
could just follow an infinite path that never cycles, but never goes anywhere. Okay, any other questions before we get on to breadth-first search? Yeah. STUDENT: [INDISCERNIBLE] PROFESSOR: Let's say I'm on a number line. And I can take a step in either direction.
50:44
Breadth-first search. So depth-first search, you expand the node from the fringe that you put on last. Breadth-first search is much fairer. The nodes that have been waiting the longest on the fringe get expanded first. So this is a first-in, first-out queue. It's a real queue. The other one I'd call it a stack.
51:12
So take a second to predict how this is going to look when I zoom through breadth-first search on this tree. Okay, we start in S. And then we expand. Now Imagine that the nodes have been added to the queue left to right. So D gets added first, then E, then P because D was added first, we remove it first. And we add B, C, and E, a new version of E. Now that E has been on the queue longest, so we expand that next. Now P has been on the queue the longest, we expand it next. And we keep going.
51:59
So there are these search tiers. And we do everything from this tier before we go down to that tier.
52:09
This is appealing for the following reasons. It kind of goes-- well, reason, singular, I'll say. It goes top to bottom. Is that not-- why is that not-- oh, that gray shows up much better on my screen.
52:31
Sorry if that was hard to see in the last one, too. This is a little bit darker. So that's how the tree expands for breadth-first search.
52:42
So it processes every node above the shallowest solution.
52:49
So let the shallowest solution have a depth of S. The search time, therefore, takes b to the power of S time.
53:03
And that's the worst case. Depth-first search, the worst case was b to the power of m, which is many times more because b to the m is so much bigger than even m minus 1.
53:19
But how much space does the fringe take? So these are how many partially completed plans were keeping track of, how many paths from the start state were keeping track of as things to return to but not quite yet as we go and expand other nodes. How much space does the fringe take in breadth-first search? Order what?
53:44
Think about it for a minute.
53:48
Yeah. STUDENT: Also b to the S. PROFESSOR: Also b to the S. I think there's going to be an image that shows it better, maybe not. Here, this image will do fine.
54:05
When we are at level S, we have part of the nodes from there and all the nodes from there. So that's going to be somewhere between b to the S minus 1 and n to the S. But in the worst case, that's b to the S. Is it complete? Yes, sorry, I could have given you time to think about that. S must be finite if a solution exists. If there is a way to the solution, there is a number of steps that it takes. And you never need to go beyond that. So that's nice, unlike depth-first search.
54:47
Even if the state space is infinite, even if you're not checking for cycles, you will get to a solution if a solution exists. So that's good. Is it optimal? Is this guaranteed to find an optimal solution? This one I'll give you a chance to answer. I have gotten so many answers from right here. And I want to give other people a chance. Yes. STUDENT: I believe it is optimal. PROFESSOR: Yes, it is optimal. We're not even considering paths of length S plus 1
55:25
because we're considering all possible paths of length S before we move on to any paths of length S plus 1. And so we'll stop before we ever consider any worse paths to the goal than the best path to the goal.
55:42
Sorry, there's that caveat, if all the costs are 1. So if you're just minimizing the number of actions that you're taking. If some actions are way more expensive than others, obviously this algorithm is not doing anything to take that into account.
55:57
So here's a little quiz for when you might prefer depth-first search or breadth-first search. Someone give me an example of either of these.
56:17
Yeah. STUDENT: [INDISCERNIBLE] PROFESSOR: Which will do better? STUDENT: [INDISCERNIBLE] PROFESSOR: Usually, yes. Although, there is a circumstance where the costs are all 1 and depth-first search would still do better. Yeah. STUDENT: [INDISCERNIBLE] PROFESSOR: Yes, if you get lucky. DFS could certainly do better when you get lucky. There are some problems where in the worst case for DFS and the worst case for BFS, the worst case for DFS will be better. Yeah. STUDENT: [INDISCERNIBLE]
57:07
PROFESSOR: Then BFS will definitely do better. Yeah.
57:13
STUDENT: If the graph is not acylic, then BFS will do better? PROFESSOR: If the graph is not acyclic, BFS will do better. Yes, because depth-first search might just never return an answer. Yeah. STUDENT: [INDISCERNIBLE] PROFESSOR: If the branching factor is high, then which is going to do better? STUDENT: BFS. PROFESSOR: BFS. I think I'd disagree with that. So basically the only time you'd want to do depth-first search over breadth-first search
57:45
is if breadth-first search makes your computer crash. If you run out of memory, you can't proceed. So the depth-first search, recall, the memory requirements were b times m rather than b to the power of S. So I guess, if you have to go a little ways down, then b to the S, you can't fit that on your computer. But if you have the time, you can run depth-first search and at least you'll get an answer. Yeah. STUDENT: Is there like an extreme [INDISCERNIBLE] that you can do [INDISCERNIBLE]?
58:23
PROFESSOR: You can do of a mixture where you do breadth-first search until you're almost out of memory and then do depth-first search from all of those different possibilities. That would basically always be preferable to just doing straight depth-first search.
58:46
Unless you're running out of memory, you'll probably want to do breadth-first search. But if you're running out of memory, then you'll want to do depth-first search. So here is a video. It's a good video, but I have to run it. Okay. Here is a maze in water. And I'm going to show you two videos. And then I'll ask you, which was depth-first search? And which was breadth-first search? Now you've seen it. Next one.
59:25
Raise your hand if you think the first one was depth? Put up a 1 or a 2 for which one was depth-first search.
59:38
2, that is right. It just kind of went around, kept going wherever it was until it found the goal. So then I'll show you breadth-first search again. Here, it's looking at all of the kind of close few action nodes and expanding those first before moving on. Yeah. STUDENT: Which was takes longer? PROFESSOR: Which one takes longer? Well, this is pretty much all filled in. So it's visited basically every state, whereas this one visited much less than every state.
1:00:20
So it looks like this one took less time, 5 seconds verses 5.8 seconds. So there you go.
1:00:37
I'll go back to presenter mode.
1:00:50
I like this algorithm. It's called iterative deepening. And I like it because when I was first reading about breadth-first search and depth-first search, I was thinking, why did you waste my time with depth-first search? I mean, unless I'm running out of memory, this is just a dumb algorithm. But it is a component of iterative deepening, which is not a dumb algorithm. So the idea is to get depth-first search's space advantage with breadth-first search's time and shallow solution advantage.
1:01:24
So the idea is you run depth-first search with a limit. First, you run it with a limit of depth 1. Then if you haven't found a solution, then you run it with a limit of depth 2, then depth 3, and so on, until you find a solution. Now this seems like you're duplicating loads of work. Isn't that wastefully redundant? But if you do the math, most of the work happens at the lowest level search. So it's actually not that bad. So let's say our branching factor is 10 and the solution is 5 steps down.
1:01:59
If we're doing breadth-first search, where there are 10 nodes at the first level, 100 at the next level, 1,000 10,000 100,000. We visit a total of 111,110 nodes. Whereas with iterative deepening search, all these nodes at the first level we visit a total of five times because we visit them at depth 1, at depth 2, at depth 3, at depth 4, at depth 5. On the second level, we only visit them 4 times because-- you get it. And so the total number of times, the total cost
1:02:37
from visiting the first level is 50 plus 400 plus 3,000 plus 20,000 plus 100,000. You add them all up, and it's barely worse. So it takes obviously a little more time than breadth-first search. But instead of b to the S memory, it is only b times S memory. I mean, that's night and day. Okay, before we move on, we mentioned last time the attendance code. Here it is. The passcode is vernazza. There's a link to it. I'll give you a minute to do that.
1:03:23
Anyone having trouble getting it on their phone?
1:03:30
There should be a link to it on the website, too, if the QR code is not working or if the electron's blocking it.
1:03:40
Anyone need me to stay on this?
1:03:50
Same question. Anyone need me to stay? Okay.
1:04:00
One more time, we good? Okay, I think we're good. And sorry if I missed anyone. You can find it on the website. But you do have to do it soon before the time cut-off at the end of the lecture.
1:04:16
So we haven't talked about different costs of actions. All the algorithms we've discussed so far are kind of assuming uniform cost. So now let's talk about cost-sensitive search. So breadth-first search finds the shortest path in terms of the number of actions. It does not find the least-cost path. We'll now cover a similar algorithm, which does find the least-cost path.
1:04:43
So here's a little diagram of uniform cost search. This imagines it's a little more costly to dig through that rock. And so we're spending more time searching through areas that are less costly. So now, instead of taking things off of the queue, either depending on whether they were first off, first on, or depending on whether they were last on, now it's a priority queue. And we remove from the queue whichever partial plan, whichever path, has the lowest cost so far.
1:05:21
So now there's numbers on all this. So our fringe consists of S. It has cost 90, which we remove. Obviously, the only thing on the fringe, S, we expand that. And now we add to the fringe S to d, 3, S to e, 9, S to p, 1.
1:05:45
Hold up a 1, 2, or 3 for which one we expand next. 3, yes, the lowest cost one. So we expand that. Now we have 3, 9, and 16. So we expand 3. And note, this is not a 15. It's a 16. It's the total cost to get there, not the cost we've just added. Makes sense. So we just keep going, adding whichever node has the lowest cost.
1:06:24
And something happened there. You might have noticed, okay, we've just added the goal to the fringe, but we keep going. So this goal has a cost of 10. But now we expand this one that has a cost of 9. And now we go to the goal because now 10 is the lowest cost thing. And now we return it. So why did we do that where we kind of waited to return the goal after it had been expanded to the fringe? Well, there could have been a shorter path to the goal
1:07:01
because right now it's only taken us 9 to get to e. Let's say that were an 8, for convenience. Let's say it had only taken us 8 to get to e, and there were a costs that were 1, and it went straight to g. Well, then that would be the path we'd want to return. So there's still a possibility of some other path to the goal getting a shorter path as long as g is not your minimal cost entry on the fringe. So you don't return the goal immediately. You wait to return it until you would have expanded it.
1:07:41
So you can picture this. I don't know if you remember from before, the tiers where each tier was a color. And then you go through the whole tier before you go to the next one. You can draw a similar picture where instead of flat tiers, they are tiers of constant contour. So you do all the red first, then the yellow, then the green, then the blue. And the gray you never have to get to. So here are some properties of uniform cost search. Which nodes does it expand? This is just a schematic.
1:08:21
But you're going down from the top, but not necessarily evenly. And maybe actually-- now we're in a setting, this is actually even though it takes more actions to get there, the actions have lower cost. Yeah. Question? STUDENT: You talked about the previous slide, doesn't p have a cost of 1 [INDISCERNIBLE]?? PROFESSOR: Doesn't p have a cost of 1? So it would be the cheapest.
1:08:52
So you're wondering why it wasn't expanded? STUDENT: Yeah. PROFESSOR: It was. Then we added q to the fringe. And now we cross it off. So once we expand it, we cross it off from the fringe. Yeah, we've done it. Sorry. The fringe is the clear ones. The red are the ones we've done already. Any other questions?
1:09:25
Yeah. STUDENT: Would it go in numerical order unless it's reached the bottom in your goal? PROFESSOR: Yeah, you keep going in numerical order until you would expand the goal state. And if you would expand the goal state, you say, wait, no, we're done. And you return it.
1:09:51
So this process is all nodes with less cost than the cheapest solution. This is an observation that will be useful for figuring out the resource requirements. So if the solution costs C star-- that's the sum of the costs of all the actions on the way to the solution, which minimizes the cost-- and each action has a cost of at least epsilon, then it can't take more than C star over epsilon. So if C star is 100 and epsilon is 1/100, then you can't have a path that costs 100
1:10:24
with more than 10,000 steps because 10,000 steps, each of which costing 1/100, would have a cost of at least 100. So that's the effect of depth, C star over epsilon, which could be pretty bad, actually. But nothing you can do about it really. So this takes time, in the worst case b to the power of C star over epsilon because the depth-- I mean, you could be looking at b different options at each depth. And then it gets exponentially larger as the tree gets bigger.
1:11:02
So how much space does the fringe take? Just take a moment to think.
1:11:10
Same, roughly that of the last year. This is basically breadth-first search with a spin. And so it's the same thing where you're keeping track of this whole uniform cost tier.
1:11:26
And that could get larger and larger and larger as the tree expands.
1:11:36
Is it complete? Is this guaranteed to find a solution if a solution exists? Raise your hand for yes.
1:11:46
Yes, it is.
1:11:56
Assuming there is a minimum arc cost. I mean, if you had actions with costs that were like a half, then a quarter, then an eighth, then a 16th, you could be expanding that forever. But if all of the actions have costs that is bounded below by a positive constant, then you will eventually terminate. Is it optimal? Will this give you the lowest-cost solution? Hands up for no.
1:12:29
It will give you the lowest-cost solution. Question. STUDENT: I might be misunderstanding how it works, but isn't it kind of like [INDISCERNIBLE]??
1:12:45
PROFESSOR: We might have time at the end. But let me just show you a few videos of this. First, just discussing how uniform cost works. It explores increasing cost contours, so it starts with the lowest-cost possibilities. So the good thing is it's complete. It'll guarantee to find an optimal solution. It's complete. It's guaranteed to find a solution. And it's optimal. It's guaranteed to find the optimal solution. The bad is it explores in every direction
1:13:23
equally with no information about the goal location. And that's a problem we're going to have to solve next lecture. And we're going to require more information from the problem set, from the way the problem is posed. So you can think of it as of searching out from the start until it gets to the goal. We might like something that kind of searches more preferentially to the right. That is what we'll call informed search. This is uninformed search. And you can imagine with uninformed search,
1:13:55
you don't have a way of knowing starting from here. Can you see my mouse? You don't have a way of knowing starting from here that you should be preferentially going to the right. So here is a demo of uniform cost search in the Pac-Man maze.
1:14:25
This one, I guess, doesn't really have a goal state. It's just showing how it expands states on the fringe that it's thinking about visiting.
1:14:47
There is uniform cost search.
1:14:52
So this is breadth-first search. If all the costs are 1, then uniform cost search looks like breadth-first search. So here, you can see that all the costs of all the actions are 1. So this is a video of both, breadth-first search and uniform cost search.
1:15:11
Here is a maze where some of the water is deeper and some of the water is shallower. And so the idea is the cost of going through deeper water is more. And I'm going to show you depth-first search, breadth-first search, and uniform cost search. And then at the end, I'll ask you which was which. So here is number one.
1:15:41
Here is number two. Oh, no, you can see the--
1:15:51
Well, maybe some of you missed it. And here is number three.
1:16:00
Okay, so one was depth-first search. One was breadth-first search. And one was uniform cost search. Starting with this one, who can tell me what they think it was? Someone I haven't heard from. Thank you to the-- STUDENT: BFS. PROFESSOR: BFS. Yep. And this one, which was this one.
1:16:27
STUDENT: Uniform cost search. PROFESSOR: Uniform cost search. Yep. And so breadth-first search was the first one.
1:16:40
STUDENT: [INDISCERNIBLE] PROFESSOR: Yeah, because we're almost at the end. One more slide plus an extra one I thought I'd have time for, but we don't. Oh, come on.
1:16:54
I could show it to you at the start of the next lecture. Yeah, what was your question? STUDENT: So do we [INDISCERNIBLE] PROFESSOR: Yeah, exactly. So you could tell that the UCS was UCS as opposed to breadth-first search because it was spending more of its search focus on the shallow water. I'm just going to go through this. You guys can leave if you need to. But just try to do so quietly. All these search algorithms are the same except for their strategy for what they do on the fringe.
1:17:28
So depth-first search is removing the one that was put on last. Breadth-first search is removing the one that was put on first. And uniform cost search is removing whichever one has the lowest cost so far. So the implementation for this is 90% the same. It's just a question of which one you're removing from the fringe. Okay. Thanks guys. And I'll see you on Tuesday. And come up with any questions if you like.
1:20:11
[MUSIC PLAYING]
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