5. Search: Optimal, Branch and Bound, A*
ฝัง
- เผยแพร่เมื่อ 6 มิ.ย. 2024
- MIT 6.034 Artificial Intelligence, Fall 2010
View the complete course: ocw.mit.edu/6-034F10
Instructor: Patrick Winston
This lecture covers strategies for finding the shortest path. We discuss branch and bound, which can be refined by using an extended list or an admissible heuristic, or both (known as A*). We end with an example where the heuristic must be consistent.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu
Great lecture. Simulations help a lot to paint a picture about how algorithms work in real scenarios.
I had a little problem with understanding consistency just by reading the book, but this video cleared all my doubts.
Thanks a lot!
I have watched different online videos (courses from Stanford, Course Era...etc.) on AI. This course is by far the best!
So , if someone completes this , what next must he look at or do ?
12345a If you are looking for something technical and mathematical, you can search for Andrew Ng from Stanford.
I was more concerned about its applications
I want to start a company based on some AI application
Do I need someone with a phD in this subject for it?
The art of Teaching, simply awesome.
For me what's awesome is I can attend lecture of MIT sitting in my room in India and learn from this great gentelman. Also I would love if MIT can provide access to program they are using. Peace ☮️
Excellent lecture as usual. One thing that I'm kind of surprised wasn't mentioned. For A*, instead of adding constraints to the heuristic function, another common approach is to add one simple rule to the extend list:
If you find a node that has already been extended but the new travel distance to that node is shorter than the old travel distance to the node, replace the old path with the new one.
So if you work through the last example with this rule you'll see that when visiting C for the second time, the path to C was shorter so it should replace the previous path to C and you would then find the correct solution.
This is how games handle maps with terrain that result in different travel speeds. So that the shortest distance isn't necessarily the fastest path.
I'm not sure about the math and whether this is slightly less efficient, but I know from experience that it works and that it can be very difficult to come up with a heuristic function to estimate the remaining path that satisfies the second constraint.
Soo, Dijkstra's algorithm?
The problem comes is in terms of end condition. Even after a goal node is found, you will need to wait till all possible paths are explored.
What is the difference between enqueued list and extended list ?
Yea, I was wondering the same. But, does this new rule guarantee that you can always find the optimal path with only admissibility being assumed?
I've been wanting to learn AI, but I get bored when reading about it. This information is delivered perfectly for me and so easy to comprehend!!
I'm glad I stumbled upon it.
Loved the Non- Map example that needs consistency to be factored into the algorithm.
there are two more similar courses online, one taught by Peter Norvig and another one taught by Berkeley based on Norvig's book. Materials covered similar in nature, but Prof Winston's teaching method and style is second to none.
I agree that Winston is great - but most comprehensible coverage you will find on Nornig's textbook. By any chance, do you have a link to the classes you mentioned?
These lectures are gem !!
I think it's funny how as the number of lectures increases the number of views decreases.
So it's not everyone's cup of tea. There's nothing wrong with that.
Sopu Nothing wrong with anything...
Why is it funny?
Well, if you skip over to lecture 12, which is about neural networks and back propagation, you see the views spike again. That's probably because it's considered a more interesting topic that those building up to it, and it's something that people would probably directly search for more frequently than, say, branch searching. To that extent, neural networks are the primary reason I want to learn about artificial intelligence. I just think I'd be wise for me to learn some background before-hand.
wjrasmussen666 Primarily a figure of speech. Even so, I actually find it somewhat. Just an example of human-nature when it comes to self-motivation and/or initial interest vs. long-term commitment.
Heh, I'm watching this on my laptop. Such a rebel.
No laptops allowed!
@@WildAnimalChannel True
You may not have taken previous 4 lectures
ikr
Rest in peace, Professor
Well, if you use the definition of consistent heuristic found on wikipedia, changing 100 by 2 will not make it either way. I thought these two definitions of consistency were equivalent but it seems they are not. Any ideas why or am I overlooking something?
such a perfect explanation
Brilliant stuff!
what software is patrick using here to demonstrate the algorithms?
I wish you guys would have posted the homework(lab) solutions as well.
They do some of them on the iTunes U I think
people post their own solutions online. just google it lol
Could we apply to find maximum path if then wht.will be the procedure ,I am not getting the correct ans
Which software is he using to find the shortest path
43:00 why is the estimate distance 0 if the model shows that it's at least 100?
R.I.P Patrick Winston
At 42:00 how was the estimated distance from B to G 0? Why can't a non-map search space be laid out geometrically?
+Thomas Cook consistency is the word you are looking for. In an euclidean space you need the consistency constraint to be true to "lay it out geometrically".
46:27 How to calculate the "actual distance" between node x and y, if the problem is not a map? Use the absolute difference between the accumulated cost from start to x and the accumulated cost from start to y?
list all paths from x to y, take the shortest
40:38 He said 100 was okay as it was less than the actual distance
Can we ever say that actual distance < admissible heuristic ?
And do we measure the actual distance and then look for admissible heuristic ?
Wouldnt that be a waste of time ?
I thought he was trying to explain, when admissible heuristic can go wrong and made up such an example. Not sure...
So when we use admissible heuristic algorithm, how do we know, that the path is actually the shortest? As was said in the previous lecture, heuristics usually work, but not necessarily always. We can think of a simple case when stepping away from the goal would be a better solution, even though the heuristic tells us otherwise (in that case path weights won't correspond to geometrical rules, but that's usually the case in real life problems). But if we stop when potential distances are higher when the one we found, it wouldn't be the optimal path.
So this basically means that there are limitations on the heuristic we use, as it should guarantee that the "airplane distance" that we get is definitely lower than an actual distance
Nvm, he talks about it in the end
At the end he shows the example where A* doesnt work. Wouldn't you just make it so that if you find a shorter path to a node that already been covered you swap it in?
Yes.
is extended list the same as a visited / seen set of nodes ?
Yes, the notion here is if we have a path already extended through this node or not, hence extended. In the visited analogy, it’s the same. Have we visited this node during our traversal?
The last example is not a "Map" but if I change the "100" value to "2" that is "Admisible and Consistent", but it is not a "Map" still?
my understanding is that the meaning of map here is "geographically", or like "euclidian" distance on the edges. Not sure though
what is the software used here?
Pause at 38:29
He wrote "Acc dist + admissable height"
Shouldnt it be *"acc dist + airline distance"* ?
I am late but Airline distance is being referred to as "Admissable Heuristic"
Guys 44:35 ! I couldn't understand : either the situation we're solving is a map or not, the heuristic still doesn't give a value less than the actual distance, then why is the professor considering it admissible (tho it doesn't satisfy the admissibility rule ) ??
Tarek Aloui
6th lesson is completed.. I'm dedicated :))
The Branch & Bound + Extended List Algorithm is basically Dijkstra. Or is there something I miss?
Biabapumpel In this case it is, but you can use branch and bound for more complicated problems, not just pathfinding. Combining with heuristics (im not going to go into detail now) you can split your problem into many smaller ones and eliminate sub-problems based on these heuristics.
i m not that confident in algorithms but dijkstra i think will calculate the shortest distance to any node while this algorithm wont go too far off the central nodes in the graph. when it finds one possible solution "path" it wont go over that distance in other directions right?
Good pickup!
What is the difference between enqueued list and extended list ?
@@aidenigelson9826 An enqueued list is basically an agenda list which helps keep track of which nodes are going to be extended/examined in the future, while an extended list keeps track of nodes that have been already extended. In shortest path problems, since at each iteration we are always extending the shortest path seen so far, if we encounter say node A somewhere after we have already extended it, then extending node A this time will certainly result in a path longer that the one we build from our last extension of A(assuming all paths are positively weighted), and so we just 'prune' the subtree under the second A node. This strategy is well-justified by the optimal substructure of a shortest path(i.e. every subpath of a shortest path is a shortest path up to that point)
As a layperson, I find it very surprising and interesting that Patrick Winston seems to conceive of AI as a branch of human psychology -- he seems to take it that topics like optimal search are sort of parenthetical because "they probably don't describe what's going on in the head". I wonder if other AI practitioners view the field that way...
check out Chomsky.
what specifically does Chomsky say about this?
What is airline distance? Is it just synonym for Euclidean distance?
Yes, also known as heuristic distance
Can somebody please tell me , which software he use to visualize path finding algorithms, i can't find the same software on internet.
Make your own
@@Anonymous-vh6kp What a beast.
He wrote it himself with the help of his colleagues. Since he passed away, i think your best bet is to email someone from his department and ask for source code or may be access to the software since it appears to be cloud based. Or may be you can write your own since he is explaining how the algorithm work XD.
P.S. he mentioned in previous videos that he wrote it in JAVA and that the programs you write yourself does not always work as expected. I think he said it in the "engineer song" video
I can't be the only one who notices how close he gets to the students in the front row. That would make me so uncomfortable!
( ͡° ͜ʖ ͡°)
2014 is 7 years ago... time flies
I was a young rookie then, now I'm an old rookie 👴
at 42:11, why not extend C again since the total distance is less than the previously extended C node?
+qidas123 we only extend a node one time, algorithm actually never says extend if the path is shorter. What we keep in the "Extended List" is only the names of nodes we already extended, nothing about the length of path to those nodes.
He's asking, "why don't we make this simple modification to the algorithm to fix it", not "why doesn't the existing algorithm, as described, compel us to extend C again."
Because that would undermine the purpose of having the admissible heuristic. SO you don't extend C.
I think this consistency matter is there whenever we don't extend the same node twice
-Sure it is true what he said, but I think he should have mentioned/clarified that whenever it is not a map (the distance eq AB+BC>=AC is not necessarily true)
We should check not just whether we've extended this node before or not, but with what cost value????
I mean even if we are not using heuristics this could miss a shorter path (i. e. for example it could be yes we have extended C before but with a longer path, if SC=11 while SA->AC=5+2=7)
.
Or am I missing something here????
the idea here is that node distances are subject to triangle geometry. So in your example, SC shouldn't be 11 , can be max. 7, since in the same line, and have another node B in between.. In real life work, you are right though.
and again in real life, no one would say SC is 11, that wouldn't be considered a regular path. SC would simple mean SB+BC.
10:08 is that a monocular?
yep, he used it in other classes too. this guy looks very interested.
Why is no-one talking about the guy sitting on the right, stiff as a plank
Yeah that dude was totally freaking me out lmfao
May be because everyone is listening to the Lecturer unlike you.
he looks like alien hiding under a human body from men in black movie
The anticipation of a heart attack with all that heavy breathing requires all my attention so I didn't even notice the guy until I read ur comment.
probably trying not to develop of hunchback.
The lectures are really great for foundational understanding of intelligent systems. Also the sleeping guy from last time who has been wearing the same thing to every lecture wasn't there lmaoo
when he is talking about consistency he says if the distance to the goal from A is 2 instead of 100 it will be consistent but I doubt it since according to formula 2-0 < 1 is not correct what are your opinions?
+BangerProductions
What do the 2, 0 and 1 you are using stand for?
+Roland Maio of course the distances
+BangerProductions
|H(x,G) - H(y,G)| Consistency
This means that the heuristic estimate for a node, cannot be greater than the heuristic estimate for a neighbouring node plus the actual distance between the nodes.
With the heuristic estimates used from the start, we get 100-0
+BangerProductions if H(A) = 2, as H(B) = 0 and D(A,B) = 2, then |H(A) = H(B)|
So what does this mean for the search? It is invalid? Or does it now check down that path since it failed the consistency check?
23:00
I FEEL LIKE I'M IN MIT fyeah
so true bro
What is the difference between enqueued list and extended list ?
The enqueued list is for the nodes to be extended (not yet been extended) based on branch and bound. The extended list is, namely, for recording those nodes that have been extended, so that we don't really have to extend them again later.
A node is enqueued does not mean that it is extended. In fact, we can enqueue many times the same node, but with different distence value each time, they are just candidiates for extension. And we just choose the shortest for extension.
"Do you ever want to do just one?" Why do multuple, and how considering modern cache hit costs?
It takes roughly as much time to move an answer from one core to another as 35 cycles.
When he explains consistency, couldn't you use a check for your extended list where instead of checking if a node has already been reached, instead take whichever repeat is the shortest? Therefore although he reaches C through S-B-C and therefore he was hosed when he tried S-A-C, it'd instead take S-A-C because if there's a way between S & C that is less than the others you'd use that path
If you can't guarantee consistency (or monotonicity as it's also known) for your heuristic, then theoretically you could do what you're suggesting. But why use a heuristic at all if you're not going to trust it? Doing what you're suggesting would guarantee optimality but you've lost the maximum efficiency benefits that a good heuristic can result in.
@@conorigoe1213 because sometimes a suboptimal heuristic is the best you can do, and it's still preferable to not using a heuristic.
Can anyone explain to me what real world example could be tied to his last in class example? I'm trying to think when he would ever have to use the A* algorithm on something thats not a map lol
+ranvideogamer You are correct that one wouldn't, but since this is an AI class, he is explaining why one wouldn't, and applying a model in the process.
+ranvideogamer You are correct that one wouldn't, but since this is an AI class, he is explaining why one wouldn't, and applying a model in the process.
+ranvideogamer You may want to split the work into threads and stop one thread if the expected outcome is worse than the already accumulated output by another thread. Not actual real world example but programming related example that is.
+ranvideogamer You could, say you didn't use the cost of the heuristic as distance per se. You could have it as time or something else you know to be admissable and then you could use it for lots of things. Maybe finding files in a search through a directory in a computer, I think that mostly uses some other form of tree search like preorder or something but just an example.
+ranvideogamer I know this was a year old comment but if you are still interested look up the a* 8 puzzle, very interesting... for all I know you might be an expert by now though!
Wouldn't BFS give us shortest path as well?
it'll give you shortest path in terms of number of nodes, however it won't give you the shortest path in terms of actual distance
it'll give you shortest path in terms of number of nodes, however it won't give you the shortest path in terms of actual distance
how to calculate airline path for writing a program
If you're using a Cartesian coordinate system, then the "airline path" heuristic for a position (x0, y0) to a goal position (xG, yG) will just be sqrt( (xG - x0)^2 + (yG - y0)^2 ) from the Pythagorean Theorem
@@conorigoe1213 sqrt is not really necessary (optimization)
11
lmao so many ai people down there . I came here for my dsa endsem. It's a beautiful lecture though . Loved it
26:26 guy in blue shirt with number 10 on it. LMAO.
In a different world
It bothers me that he doesn't use a better example to explain why the algorithms find the optimal path. In our lectures we always had two viable paths of which the one with more nodes had shorter cummulative length to show that fewer nodes doesn't always equal to shortest path. For example S->A would be 6 and S->B->A would be 2+3. That way SBADG would be the optimal path and it would show the difference between informed search vs. uninformed search (BFS would find SADG). This example has very little added value. I mean he explains the algorithms very well, but I'm missing that he doesn't show the true power of the algorithms.
He is basically explaining Dijkstra's algorithm with some heuristics added...
AFAIK A* is a specific version of Dijkstra.
@@EmmanuelMessulam you could say A* is an extension of Dijkstras. Norvig`s AIAMA has a nice table which summarizes this. A* = (path cost + heuristic) whereas Dijkstras = path cost
If you don't trust the oracle, then, it seems that you've hardly save any time, because you end up doing pretty much the same work, so I'm not quite sure what the point of that part of the discussion was...
WHY NO LAPTOPS
From the course FAQ: "We of the staff promise that we will do all we can to make 6.034 an interesting, useful, and inspiring subject. We cannot honor our promise if we are talking to the back of laptops or to people manipulating cell phones or reading newspapers. We find it insulting, and when we are insulted, we are distracted, and when we are distracted, we do less well, and when we do less well, we are less useful to people paying attention, so an open laptop harms other students."
Who is tanya? :P
@17:18 a guy is sleeping in the top left corner
Ah, yes, the famous German auto bond!
omg the white haired guy is.... so hot... does anyone know who this is goddamn
is that you ?
awful taste but he's Jared Leto as the joker