5. Search: Optimal, Branch and Bound, A*

Поделиться
HTML-код
  • Опубликовано: 5 ноя 2024

Комментарии • 167

  • @MrFurano
    @MrFurano 7 лет назад +23

    I have watched different online videos (courses from Stanford, Course Era...etc.) on AI. This course is by far the best!

    • @Leon-pn6rb
      @Leon-pn6rb 7 лет назад

      So , if someone completes this , what next must he look at or do ?

    • @MrFurano
      @MrFurano 7 лет назад +2

      12345a If you are looking for something technical and mathematical, you can search for Andrew Ng from Stanford.

    • @Leon-pn6rb
      @Leon-pn6rb 7 лет назад

      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?

  • @LampCord99
    @LampCord99 7 лет назад +39

    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.

    • @EmmanuelMess
      @EmmanuelMess 6 лет назад +3

      Soo, Dijkstra's algorithm?

    • @saiprasad8311
      @saiprasad8311 5 лет назад +1

      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.

    • @aidenigelson9826
      @aidenigelson9826 3 года назад

      What is the difference between enqueued list and extended list ?

    • @hanxiaodu9935
      @hanxiaodu9935 3 года назад

      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?

  • @L2buildrobots
    @L2buildrobots 10 лет назад +181

    I think it's funny how as the number of lectures increases the number of views decreases.

    • @InebriatedEscapist
      @InebriatedEscapist 10 лет назад +13

      So it's not everyone's cup of tea. There's nothing wrong with that.

    • @L2buildrobots
      @L2buildrobots 10 лет назад +4

      Sopu Nothing wrong with anything...

    • @wjrasmussen666
      @wjrasmussen666 10 лет назад

      Why is it funny?

    • @TheLazyKey
      @TheLazyKey 10 лет назад +25

      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.

    • @TheLazyKey
      @TheLazyKey 10 лет назад +5

      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.

  • @WahranRai
    @WahranRai 9 месяцев назад +3

    Rest in peace, Professor

  • @SomenathChakraborty
    @SomenathChakraborty 5 лет назад +5

    The art of Teaching, simply awesome.

  • @dipmodi844
    @dipmodi844 3 года назад +7

    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 ☮️

  • @GoogleUser-ee8ro
    @GoogleUser-ee8ro 5 лет назад +2

    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.

    • @zenicv
      @zenicv 3 года назад +1

      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?

  • @djhal7961
    @djhal7961 2 года назад +2

    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.

  • @yooos3
    @yooos3 8 лет назад +1

    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!

  • @VivaLaPanda9800
    @VivaLaPanda9800 7 лет назад +53

    Heh, I'm watching this on my laptop. Such a rebel.

  • @ShivangiSingh-wc3gk
    @ShivangiSingh-wc3gk 6 лет назад

    Loved the Non- Map example that needs consistency to be factored into the algorithm.

  • @rohitdas475
    @rohitdas475 3 года назад +1

    These lectures are gem !!

  • @xXxBladeStormxXx
    @xXxBladeStormxXx 8 лет назад +11

    I wish you guys would have posted the homework(lab) solutions as well.

    • @lilalfyalien
      @lilalfyalien 7 лет назад

      They do some of them on the iTunes U I think

    • @studywithjosh5109
      @studywithjosh5109 4 года назад

      people post their own solutions online. just google it lol

  • @WepixGames
    @WepixGames 5 лет назад +5

    R.I.P Patrick Winston

  • @masteryehudi7031
    @masteryehudi7031 9 лет назад +2

    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...

  • @cat3079
    @cat3079 8 лет назад +45

    Why is no-one talking about the guy sitting on the right, stiff as a plank

    • @Apollys
      @Apollys 7 лет назад +2

      Yeah that dude was totally freaking me out lmfao

    • @vijayabhaskar-j
      @vijayabhaskar-j 7 лет назад +8

      May be because everyone is listening to the Lecturer unlike you.

    • @VikramSoni2
      @VikramSoni2 7 лет назад +3

      he looks like alien hiding under a human body from men in black movie

    • @SnoopingDope
      @SnoopingDope 7 лет назад +5

      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.

    • @WildAnimalChannel
      @WildAnimalChannel 5 лет назад +2

      probably trying not to develop of hunchback.

  • @Biabapumpel
    @Biabapumpel 9 лет назад +7

    The Branch & Bound + Extended List Algorithm is basically Dijkstra. Or is there something I miss?

    • @IndieMarkus
      @IndieMarkus 9 лет назад +8

      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.

    • @tw6428
      @tw6428 6 лет назад

      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?

    • @elliott8175
      @elliott8175 4 года назад

      Good pickup!

    • @aidenigelson9826
      @aidenigelson9826 3 года назад

      What is the difference between enqueued list and extended list ?

    • @mikechen3174
      @mikechen3174 2 года назад

      ​@@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)

  • @maxsun1443
    @maxsun1443 3 года назад +1

    2014 is 7 years ago... time flies

    • @jonathanpopham5483
      @jonathanpopham5483 3 года назад

      I was a young rookie then, now I'm an old rookie 👴

  • @Leon-pn6rb
    @Leon-pn6rb 7 лет назад +1

    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 ?

    • @rahulraviprasad
      @rahulraviprasad 6 лет назад

      I thought he was trying to explain, when admissible heuristic can go wrong and made up such an example. Not sure...

  • @DanielOMGz
    @DanielOMGz 7 лет назад +2

    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?

  • @hslyu
    @hslyu 3 года назад

    such a perfect explanation

  • @Leon-pn6rb
    @Leon-pn6rb 7 лет назад +1

    Pause at 38:29
    He wrote "Acc dist + admissable height"
    Shouldnt it be *"acc dist + airline distance"* ?

    • @AnjaliSharma-uw4bg
      @AnjaliSharma-uw4bg 5 лет назад

      I am late but Airline distance is being referred to as "Admissable Heuristic"

  • @masstranwastaken
    @masstranwastaken 5 лет назад

    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

  • @donotreportmebro
    @donotreportmebro Год назад +2

    is extended list the same as a visited / seen set of nodes ?

    • @_brown_
      @_brown_ 8 месяцев назад

      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?

  • @TarekAlouiGeek
    @TarekAlouiGeek 8 лет назад

    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 ) ??

  • @mehmetaliozer2403
    @mehmetaliozer2403 4 года назад +3

    6th lesson is completed.. I'm dedicated :))

  • @shymaaarafat1342
    @shymaaarafat1342 5 лет назад

    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????

    • @fatihtas88
      @fatihtas88 4 года назад

      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.

    • @fatihtas88
      @fatihtas88 4 года назад

      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.

  • @qidas123
    @qidas123 8 лет назад +1

    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.

    • @yessopie
      @yessopie 8 лет назад +2

      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."

    • @rubiskelter
      @rubiskelter 8 лет назад +1

      Because that would undermine the purpose of having the admissible heuristic. SO you don't extend C.

  • @Leon-pn6rb
    @Leon-pn6rb 7 лет назад +12

    I FEEL LIKE I'M IN MIT fyeah

  • @bangerproductions1584
    @bangerproductions1584 9 лет назад +1

    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?

    • @rolandmaio930
      @rolandmaio930 9 лет назад

      +BangerProductions
      What do the 2, 0 and 1 you are using stand for?

    • @bangerproductions1584
      @bangerproductions1584 9 лет назад

      +Roland Maio of course the distances

    • @mestanonym
      @mestanonym 9 лет назад +1

      +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

    • @kurodoakabane
      @kurodoakabane 8 лет назад

      +BangerProductions if H(A) = 2, as H(B) = 0 and D(A,B) = 2, then |H(A) = H(B)|

    • @Jorran0septem
      @Jorran0septem 8 лет назад

      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?

  • @algebra5766
    @algebra5766 8 лет назад

    Brilliant stuff!

  • @michaelwong6004
    @michaelwong6004 4 года назад

    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?

    • @calcifer7776
      @calcifer7776 4 года назад

      list all paths from x to y, take the shortest

  • @ivantarnyagin
    @ivantarnyagin 3 года назад

    43:00 why is the estimate distance 0 if the model shows that it's at least 100?

  • @thomascook8570
    @thomascook8570 9 лет назад

    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 лет назад +1

      +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".

  • @areeshahkhan3512
    @areeshahkhan3512 5 лет назад

    Could we apply to find maximum path if then wht.will be the procedure ,I am not getting the correct ans

  • @utxeee
    @utxeee 6 лет назад

    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?

  • @joshbenner2784
    @joshbenner2784 8 лет назад +1

    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

    • @conorigoe1213
      @conorigoe1213 8 лет назад

      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.

    • @batlin
      @batlin Год назад

      @@conorigoe1213 because sometimes a suboptimal heuristic is the best you can do, and it's still preferable to not using a heuristic.

  • @dariofernandovelasquezorte4499
    @dariofernandovelasquezorte4499 6 лет назад

    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?

    • @albusdumbledore6578
      @albusdumbledore6578 5 лет назад

      my understanding is that the meaning of map here is "geographically", or like "euclidian" distance on the edges. Not sure though

  • @Gavinnnnnnnnnnnnnnn
    @Gavinnnnnnnnnnnnnnn 3 года назад

    What is airline distance? Is it just synonym for Euclidean distance?

  • @allyourcode
    @allyourcode 3 года назад

    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...

  • @LucGendrot
    @LucGendrot 9 лет назад +11

    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!

  • @BudBreaker
    @BudBreaker 4 года назад

    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.

  • @AlekseiMaide
    @AlekseiMaide 7 лет назад +3

    He is basically explaining Dijkstra's algorithm with some heuristics added...

    • @EmmanuelMess
      @EmmanuelMess 6 лет назад +2

      AFAIK A* is a specific version of Dijkstra.

    • @zenicv
      @zenicv 3 года назад

      ​@@EmmanuelMess 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

  • @chidam333
    @chidam333 Год назад

    lmao so many ai people down there . I came here for my dsa endsem. It's a beautiful lecture though . Loved it

  • @aidenigelson9826
    @aidenigelson9826 3 года назад

    What is the difference between enqueued list and extended list ?

    • @hanxiaodu9935
      @hanxiaodu9935 3 года назад

      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.

    • @aliasziken7847
      @aliasziken7847 2 года назад +1

      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.

  • @sachetansabhahit6235
    @sachetansabhahit6235 5 лет назад

    Which software is he using to find the shortest path

  • @jhogrute
    @jhogrute 3 года назад

    what software is patrick using here to demonstrate the algorithms?

  • @coffle1
    @coffle1 10 лет назад +1

    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

    • @faisalwho
      @faisalwho 8 лет назад +2

      +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.

    • @faisalwho
      @faisalwho 8 лет назад

      +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.

    • @benjaminkrarup3673
      @benjaminkrarup3673 8 лет назад +2

      +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.

    • @benjaminkrarup3673
      @benjaminkrarup3673 8 лет назад

      +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!

  • @vinittyagi1702
    @vinittyagi1702 4 года назад +1

    Can somebody please tell me , which software he use to visualize path finding algorithms, i can't find the same software on internet.

    • @Anonymous-vh6kp
      @Anonymous-vh6kp 3 года назад

      Make your own

    • @hanxiaodu9935
      @hanxiaodu9935 3 года назад +1

      @@Anonymous-vh6kp What a beast.

    • @youtubeusername1489
      @youtubeusername1489 3 года назад

      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

  • @ZeusMcKraken
    @ZeusMcKraken 7 лет назад +2

    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

  • @morthim
    @morthim 4 года назад

    "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.

  • @abhishekbhan6410
    @abhishekbhan6410 8 лет назад

    Wouldn't BFS give us shortest path as well?

    • @TarekAlouiGeek
      @TarekAlouiGeek 8 лет назад +6

      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

    • @TarekAlouiGeek
      @TarekAlouiGeek 8 лет назад

      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

  • @kaushikn9510
    @kaushikn9510 Год назад

    @17:18 a guy is sleeping in the top left corner

  • @pratikkhadtale
    @pratikkhadtale 8 лет назад

    how to calculate airline path for writing a program

    • @conorigoe1213
      @conorigoe1213 8 лет назад +5

      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

    • @donotreportmebro
      @donotreportmebro Год назад

      @@conorigoe1213 sqrt is not really necessary (optimization)

  • @kalinduSekara
    @kalinduSekara 3 года назад

    what is the software used here?

  • @repme
    @repme 6 лет назад

    10:08 is that a monocular?

    • @bernardoabreu4910
      @bernardoabreu4910 5 лет назад

      yep, he used it in other classes too. this guy looks very interested.

  • @cynidee
    @cynidee 3 года назад

    11

  • @vincystriling3942
    @vincystriling3942 8 лет назад +3

    WHY NO LAPTOPS

    • @mitocw
      @mitocw  8 лет назад +66

      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."

  • @TP-gx8qs
    @TP-gx8qs 6 лет назад +1

    26:26 guy in blue shirt with number 10 on it. LMAO.

    • @2slimj
      @2slimj 6 лет назад

      In a different world

  • @GoatzAreEpic
    @GoatzAreEpic 5 лет назад

    23:00

  • @azharhussian4326
    @azharhussian4326 6 лет назад

    Who is tanya? :P

  • @Theraisinkiller
    @Theraisinkiller 4 года назад

    omg the white haired guy is.... so hot... does anyone know who this is goddamn

    • @kj7767
      @kj7767 2 года назад

      is that you ?

    • @iamyouu
      @iamyouu Год назад

      awful taste but he's Jared Leto as the joker

  • @kaptenadhoc
    @kaptenadhoc 7 лет назад +2

    Ah, yes, the famous German auto bond!