Uploaded by Linda Bailey on February 13, 2018 at 2:45 am

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

MIT 6.034 Artificial Intelligence, Fall 2010
View the complete course: http://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 http://ocw.mit.edu/terms
More courses at http://ocw.mit.edu

MIT 6.034 Artificial Intelligence, Fall 2010
View the complete course: http://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 http://ocw.mit.edu/terms
More courses at http://ocw.mit.edu

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

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.

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 ?

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?

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

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

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!

nice explanation

there are some more videos for students on artificial intelligent in following link

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

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

What was Eliot's question?

#MIT

https://youtu.be/gGQ-vAmdAOI?t=1951

The late comer in the front row is too tired.

Is that beer?

#DeadHorsePrinciple

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

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.

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 ?

Pause at 38:29

He wrote "Acc dist + admissable height"

Shouldnt it be

"acc dist + airline distance"?I FEEL LIKE I'M IN MIT fyeah

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

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?

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

Ah, yes, the famous German auto bond!

how to calculate airline path for writing a program

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

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

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!

Wouldn't BFS give us shortest path as well?

WHY NO LAPTOPS

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