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!
@dipmodi8443 жыл бұрын
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 ☮️
@MrFurano7 жыл бұрын
I have watched different online videos (courses from Stanford, Course Era...etc.) on AI. This course is by far the best!
@Leon-pn6rb7 жыл бұрын
So , if someone completes this , what next must he look at or do ?
@MrFurano7 жыл бұрын
12345a If you are looking for something technical and mathematical, you can search for Andrew Ng from Stanford.
@Leon-pn6rb7 жыл бұрын
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?
@ShivangiSingh-wc3gk6 жыл бұрын
Loved the Non- Map example that needs consistency to be factored into the algorithm.
@L2buildrobots10 жыл бұрын
I think it's funny how as the number of lectures increases the number of views decreases.
@InebriatedEscapist10 жыл бұрын
So it's not everyone's cup of tea. There's nothing wrong with that.
@L2buildrobots10 жыл бұрын
Sopu Nothing wrong with anything...
@wjrasmussen6669 жыл бұрын
Why is it funny?
@TheLazyKey9 жыл бұрын
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.
@TheLazyKey9 жыл бұрын
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.
@SomenathChakraborty5 жыл бұрын
The art of Teaching, simply awesome.
@LampCord997 жыл бұрын
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.
@EmmanuelMessulam6 жыл бұрын
Soo, Dijkstra's algorithm?
@saiprasad83115 жыл бұрын
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.
@aidenigelson98263 жыл бұрын
What is the difference between enqueued list and extended list ?
@hanxiaodu99353 жыл бұрын
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?
@djhal79612 жыл бұрын
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.
@GoogleUser-ee8ro5 жыл бұрын
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.
@zenicv3 жыл бұрын
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?
@WahranRai6 ай бұрын
Rest in peace, Professor
@rohitdas4752 жыл бұрын
These lectures are gem !!
@VivaLaPanda98007 жыл бұрын
Heh, I'm watching this on my laptop. Such a rebel.
@WildAnimalChannel5 жыл бұрын
No laptops allowed!
@harwinderkarwal3 жыл бұрын
@@WildAnimalChannel True
@harwinderkarwal3 жыл бұрын
You may not have taken previous 4 lectures
@ehza2 жыл бұрын
ikr
@hslyu3 жыл бұрын
such a perfect explanation
@algebra57668 жыл бұрын
Brilliant stuff!
@areeshahkhan35125 жыл бұрын
Could we apply to find maximum path if then wht.will be the procedure ,I am not getting the correct ans
@utxeee6 жыл бұрын
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?
@xXxBladeStormxXx8 жыл бұрын
I wish you guys would have posted the homework(lab) solutions as well.
@lilalfyalien6 жыл бұрын
They do some of them on the iTunes U I think
@studywithjosh51093 жыл бұрын
people post their own solutions online. just google it lol
@ivantarnyagin3 жыл бұрын
43:00 why is the estimate distance 0 if the model shows that it's at least 100?
@michaelwong60043 жыл бұрын
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?
@calcifer77763 жыл бұрын
list all paths from x to y, take the shortest
@masstranwastaken5 жыл бұрын
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
@masstranwastaken5 жыл бұрын
Nvm, he talks about it in the end
@Leon-pn6rb7 жыл бұрын
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 ?
@rahulraviprasad6 жыл бұрын
I thought he was trying to explain, when admissible heuristic can go wrong and made up such an example. Not sure...
@LucGendrot9 жыл бұрын
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!
@Sagolel47976 жыл бұрын
( ͡° ͜ʖ ͡°)
@DanielOMGz7 жыл бұрын
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?
@batlin10 ай бұрын
Yes.
@WepixGames4 жыл бұрын
R.I.P Patrick Winston
@masteryehudi70319 жыл бұрын
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...
@asparwhite867 жыл бұрын
check out Chomsky.
@masteryehudi70316 жыл бұрын
what specifically does Chomsky say about this?
@thomascook85708 жыл бұрын
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?
8 жыл бұрын
+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".
@TarekAlouiGeek8 жыл бұрын
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 ) ??
@yuitocheng89196 жыл бұрын
Tarek Aloui
@Leon-pn6rb7 жыл бұрын
Pause at 38:29 He wrote "Acc dist + admissable height" Shouldnt it be *"acc dist + airline distance"* ?
@AnjaliSharma-uw4bg5 жыл бұрын
I am late but Airline distance is being referred to as "Admissable Heuristic"
@Biabapumpel9 жыл бұрын
The Branch & Bound + Extended List Algorithm is basically Dijkstra. Or is there something I miss?
@IndieMarkus9 жыл бұрын
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.
@tw64285 жыл бұрын
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?
@elliott81753 жыл бұрын
Good pickup!
@aidenigelson98263 жыл бұрын
What is the difference between enqueued list and extended list ?
@mikechen31742 жыл бұрын
@@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)
@mehmetaliozer24034 жыл бұрын
6th lesson is completed.. I'm dedicated :))
@dariofernandovelasquezorte44995 жыл бұрын
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?
@albusdumbledore65785 жыл бұрын
my understanding is that the meaning of map here is "geographically", or like "euclidian" distance on the edges. Not sure though
@sachetansabhahit62355 жыл бұрын
Which software is he using to find the shortest path
@shymaaarafat13425 жыл бұрын
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????
@fatihtas884 жыл бұрын
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.
@fatihtas884 жыл бұрын
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.
@igorborovkov701110 ай бұрын
is extended list the same as a visited / seen set of nodes ?
@_brown_5 ай бұрын
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?
@qidas1238 жыл бұрын
at 42:11, why not extend C again since the total distance is less than the previously extended C node?
8 жыл бұрын
+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.
@yessopie8 жыл бұрын
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."
@rubiskelter8 жыл бұрын
Because that would undermine the purpose of having the admissible heuristic. SO you don't extend C.
@maxsun14433 жыл бұрын
2014 is 7 years ago... time flies
@jonathanpopham54833 жыл бұрын
I was a young rookie then, now I'm an old rookie 👴
@morthim4 жыл бұрын
"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.
@jhogrute2 жыл бұрын
what software is patrick using here to demonstrate the algorithms?
@bangerproductions15849 жыл бұрын
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?
@rolandmaio9309 жыл бұрын
+BangerProductions What do the 2, 0 and 1 you are using stand for?
@bangerproductions15849 жыл бұрын
+Roland Maio of course the distances
@mestanonym9 жыл бұрын
+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
@kurodoakabane8 жыл бұрын
+BangerProductions if H(A) = 2, as H(B) = 0 and D(A,B) = 2, then |H(A) = H(B)|
@Jorran0septem8 жыл бұрын
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?
@vinittyagi17024 жыл бұрын
Can somebody please tell me , which software he use to visualize path finding algorithms, i can't find the same software on internet.
@Anonymous-vh6kp3 жыл бұрын
Make your own
@hanxiaodu99353 жыл бұрын
@@Anonymous-vh6kp What a beast.
@youtubeusername14893 жыл бұрын
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
@joshbenner27848 жыл бұрын
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
@conorigoe12137 жыл бұрын
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.
@batlin10 ай бұрын
@@conorigoe1213 because sometimes a suboptimal heuristic is the best you can do, and it's still preferable to not using a heuristic.
@ZeusMcKraken6 жыл бұрын
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
@Gavinnnnnnnnnnnnnnn3 жыл бұрын
What is airline distance? Is it just synonym for Euclidean distance?
@aidenigelson98263 жыл бұрын
Yes, also known as heuristic distance
@cat30798 жыл бұрын
Why is no-one talking about the guy sitting on the right, stiff as a plank
@Apollys7 жыл бұрын
Yeah that dude was totally freaking me out lmfao
@vijayabhaskar-j7 жыл бұрын
May be because everyone is listening to the Lecturer unlike you.
@VikramSoni26 жыл бұрын
he looks like alien hiding under a human body from men in black movie
@SnoopingDope6 жыл бұрын
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.
@WildAnimalChannel5 жыл бұрын
probably trying not to develop of hunchback.
@coffle19 жыл бұрын
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
@faisalwho8 жыл бұрын
+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.
@faisalwho8 жыл бұрын
+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.
8 жыл бұрын
+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.
@benjaminkrarup36738 жыл бұрын
+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.
@benjaminkrarup36738 жыл бұрын
+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!
@kalinduSekara2 жыл бұрын
what is the software used here?
@Leon-pn6rb7 жыл бұрын
I FEEL LIKE I'M IN MIT fyeah
@pratikdhargalkar48764 жыл бұрын
so true bro
@aidenigelson98263 жыл бұрын
What is the difference between enqueued list and extended list ?
@hanxiaodu99353 жыл бұрын
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.
@aliasziken78472 жыл бұрын
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.
@GoatzAreEpic5 жыл бұрын
23:00
@pratikkhadtale7 жыл бұрын
how to calculate airline path for writing a program
@conorigoe12137 жыл бұрын
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
@igorborovkov701110 ай бұрын
@@conorigoe1213 sqrt is not really necessary (optimization)
@repme5 жыл бұрын
10:08 is that a monocular?
@bernardoabreu49105 жыл бұрын
yep, he used it in other classes too. this guy looks very interested.
@TP-gx8qs6 жыл бұрын
26:26 guy in blue shirt with number 10 on it. LMAO.
@2slimj6 жыл бұрын
In a different world
@chidam333 Жыл бұрын
lmao so many ai people down there . I came here for my dsa endsem. It's a beautiful lecture though . Loved it
@abhishekbhan64108 жыл бұрын
Wouldn't BFS give us shortest path as well?
@TarekAlouiGeek8 жыл бұрын
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
@TarekAlouiGeek8 жыл бұрын
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
@cynidee2 жыл бұрын
11
@AlekseiMaide7 жыл бұрын
He is basically explaining Dijkstra's algorithm with some heuristics added...
@EmmanuelMessulam6 жыл бұрын
AFAIK A* is a specific version of Dijkstra.
@zenicv3 жыл бұрын
@@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
@BudBreaker4 жыл бұрын
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.
@allyourcode3 жыл бұрын
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...
@vincystriling39428 жыл бұрын
WHY NO LAPTOPS
@mitocw8 жыл бұрын
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."
@kaushikn9510 Жыл бұрын
@17:18 a guy is sleeping in the top left corner
@azharhussian43265 жыл бұрын
Who is tanya? :P
@filiphaglund78177 жыл бұрын
Ah, yes, the famous German auto bond!
@Theraisinkiller4 жыл бұрын
omg the white haired guy is.... so hot... does anyone know who this is goddamn