This is the best explanation / visualisation of A* I have come across on TH-cam - you use clear language and a clear example - Thank you Pieter Abbeel!
That's the one perfect explanation that I've been looking for! Explain from all aspects and the most important thing is explaining why. I will keep following.
Thanks for the video. It's really informing. I have a question about the consistency and optimality though. I was taught that if H is admissible but not consistent, we still get the optimal solution, and it's just we need to expand more nodes. Am I right?
Is this algorithm good for finding optimal travel route from city A to city B with transfers by train and bus, which have static route and schedule? I think because of heuristic this algorithm is more suitable than Dijkstra
I wanted to ask, if the next lowest node's f value to be expand happens to be the goal node, then it reached the solution? An awesome explanation of A* btw :D
In real-world application of A*, indeed, a big part of the challenge will be to come up with a good heuristic function. For this video, there is no real-world application behind it, it's just illustrating the execution of A* for a given search problem and heuristic function.
It's specific to each problem, you decide. For example, if the application was google maps suggesting routes, it may factor in the speed limits in each section, so whilst route a might be shorter, you may have to drive slow for a long period.
+imalive Certainly! Our complete course is available here: ai.berkeley.edu. Under "Lectures" -> "Lecture 3: Informed Search" has several examples of how to come up with heuristics.
That's the heuristic value. Assume that you have the entire map with you, then you can calculate an approximate distance between any 2 locations. It could be point-to-point for example.
He didnt estimate that s is 7. The formula to calculate f(n) is g(n) + h(n) and since S's g(n) is 0 (i.e. distance away from starting node since it is the starting node itself) and h(n) is 7 so f(n) is 0 + 7 i.e. 7. Hope I am not too late.
+pratosh kumar Great question! The A* algorithm itself is very general, and applies to a wide range of problems without change. But for each specific domain an expert would have to come up with the heuristic function --- keeping in mind to choose a consistent heuristic to ensure optimality. For example, if finding routes on a road network, you could pick h = straight line distance to the destination.
+pratosh kumar Great question! The A* algorithm itself is very general, and applies to a wide range of problems without change. But for each specific domain an expert would have to come up with the heuristic function --- keeping in mind to choose a consistent heuristic to ensure optimality. For example, if finding routes on a road network, you could pick h = straight line distance to the destination.
Thank you for this video. But there is two errors here : the first one is that you explore nodes in closed list and the second one is the inadmissible Heuristic function that you use. If you don't explore nodes in closed list then with this heuristic you will not find the shortest path
Hi Rayhan, thanks for your clarifying comment! This video illustrates A* Tree Search and A* Graph Search---as algorithms, in the context of CS188 at Berkeley (for which you can find all materials online). Sounds like you are most familiar with A* Graph Search, which indeed has a closed list and doesn't expand nodes in the closed list. A* Tree Search on the other hand doesn't keep around a closed list, it's a slightly different algorithm. Regarding properties of the heuristic function: Indeed, an admissible heuristic is required for A* Tree Search to be guaranteed to be optimal, and a consistent heuristic is required for A* Graph Search to be guaranteed to be optimal. However, even when those properties don't hold both algorithms are still perfectly well defined, and part of the point of these video is exactly to illustrate what happens when those properties do not hold.
5 was obtained as follows: backward cost s - a - b, which equals 1+2 = 3 PLUS forward cost estimate provided by the heuristic at b, which equals 2, together equalling 5
This is the best explanation / visualisation of A* I have come across on TH-cam - you use clear language and a clear example - Thank you Pieter Abbeel!
:)
I watched 4 A* related videos and I was able to understand the best with this video! Thank you, Professor Abbeel!
I liked how you expanded each node in a tree structure, makes a world of difference!
That's the one perfect explanation that I've been looking for! Explain from all aspects and the most important thing is explaining why. I will keep following.
That was a really, really good explanation. Went into just the right amount of repetitions of the working out for it to really sink in.
You are the man Mr.Pieter , Thank you so much and carry on please
Thank you, thank you brother pieter!! , I was struggling figuring out this on internet will all those complex maths till I found your video.
this is the most clearest one on youtube the hand writing pattern here is very neat and easy to use.
Simply amazing !!!
Keep on posting such tutorials.
@Zechariah Justice yeah for me as well thanks
excellent tutorial sir! thanks a lot. I had spent so much time on this topic before watching this, you taught it extremely well.
You made it look easy. :-) . Thank you. Keep it up.
Made simple and easy to understand. Right before my exam :D Thank you
This video help me before mid test exam, thanks and nice explanation :) LIKED
Dude you are great. I tried so much but got it only after seeing your video.
I have loved this, sir. Thanks
Great tutorial.
Thanks a ton
8:22 priority queue
13:07 graph search
awesome explanation! thank you very much!
very clear and detailed explanation, thank you :)
Very clear explanation :) Thank you sir
Thanks for the video. It's really informing. I have a question about the consistency and optimality though. I was taught that if H is admissible but not consistent, we still get the optimal solution, and it's just we need to expand more nodes. Am I right?
awesome tutorial!
thank you so much i dont have any question for this video, its really helpful
How do you know if you have a consistent heuristic or not? I didn't understand that part.
This gave me a better understanding of A* search. Thanks!
very well explained. thank you
Thank you! Your video help me a lot for understand the algorithm. Like
Is this algorithm good for finding optimal travel route from city A to city B with transfers by train and bus, which have static route and schedule? I think because of heuristic this algorithm is more suitable than Dijkstra
Thank you so much!!
good explanation!!!! Thanks
If the graph is not directed, what happens? Will it just explore all the paths avoiding already visites vertices/nodes?
Thanks Pieter. The lecture I was given on this was shit but this helped a lot.
Best and clear explanation
Interesting video :) Thanks
Clearly explained. Thanks :)
Which heuristic function did you use?
Very clear explanation! Thank you!
Thanks!
Is there an equation to calculate the Historic value
great explanation ! Thanks :)
Thank you 😃, it help a lot .
Very useful, thank you very much
will it be wrong if i choose to expand s-b-c before s-a
do you have any pseudo code for this algorithm?
how you get the table values?
I wanted to ask, if the next lowest node's f value to be expand happens to be the goal node, then it reached the solution?
An awesome explanation of A* btw :D
THANKS..it is very clear .
That was an awesome explanation,, better than any MIT professor.
+simarpreet singh Thanks!
when h become admissible ?
and is there 2 way to solve A* algo ??
Thank u so much...☺️
Thank you very much sir...
good video.
would you like to introduce about branch and bound finding clique?
tanks before.
how did you did get the value of H in the table???????????
In real-world application of A*, indeed, a big part of the challenge will be to come up with a good heuristic function. For this video, there is no real-world application behind it, it's just illustrating the execution of A* for a given search problem and heuristic function.
thank you so much for illustrating
Awesome :) Thanks So Much
awesome sir very nice
great video. thanks!
great illustration
Thanks a lot
how do you get heuristic value?
Yeah how did you get it?
It's specific to each problem, you decide. For example, if the application was google maps suggesting routes, it may factor in the speed limits in each section, so whilst route a might be shorter, you may have to drive slow for a long period.
thank you a lot!
Professor could you please post a lecture on calculating heuristics? Thanks for an awesome explaination here
+imalive Certainly! Our complete course is available here: ai.berkeley.edu. Under "Lectures" -> "Lecture 3: Informed Search" has several examples of how to come up with heuristics.
+RLLberkeley Thank You :)
what does it mean admissible
please how did you estimate the S to be 7....i'm a bit confused
That's the heuristic value. Assume that you have the entire map with you, then you can calculate an approximate distance between any 2 locations. It could be point-to-point for example.
He didnt estimate that s is 7. The formula to calculate f(n) is g(n) + h(n) and since S's g(n) is 0 (i.e. distance away from starting node since it is the starting node itself) and h(n) is 7 so f(n) is 0 + 7 i.e. 7. Hope I am not too late.
Thx friend
thank you ..
thank you
sir, what if we are not given the heuristic values??
+pratosh kumar Great question! The A* algorithm itself is very general, and applies to a wide range of problems without change. But for each specific domain an expert would have to come up with the heuristic function --- keeping in mind to choose a consistent heuristic to ensure optimality. For example, if finding routes on a road network, you could pick h = straight line distance to the destination.
+pratosh kumar Great question! The A* algorithm itself is very general, and applies to a wide range of problems without change. But for each specific domain an expert would have to come up with the heuristic function --- keeping in mind to choose a consistent heuristic to ensure optimality. For example, if finding routes on a road network, you could pick h = straight line distance to the destination.
Thank you sir.. appreciate ur work..
Good
thank you ^_^
Thank you for this video. But there is two errors here : the first one is that you explore nodes in closed list and the second one is the inadmissible Heuristic function that you use. If you don't explore nodes in closed list then with this heuristic you will not find the shortest path
Hi Rayhan, thanks for your clarifying comment! This video illustrates A* Tree Search and A* Graph Search---as algorithms, in the context of CS188 at Berkeley (for which you can find all materials online). Sounds like you are most familiar with A* Graph Search, which indeed has a closed list and doesn't expand nodes in the closed list. A* Tree Search on the other hand doesn't keep around a closed list, it's a slightly different algorithm. Regarding properties of the heuristic function: Indeed, an admissible heuristic is required for A* Tree Search to be guaranteed to be optimal, and a consistent heuristic is required for A* Graph Search to be guaranteed to be optimal. However, even when those properties don't hold both algorithms are still perfectly well defined, and part of the point of these video is exactly to illustrate what happens when those properties do not hold.
Hi, I think your H values are wrongly designed because H needs to satisfy that H(n)
untrue, admissible implies optimal solution
proof: if h(n) is admissible, A* using Tree-Search is
optimal.
help me!!
2:58 you have written the value of s- a - b = 5 instead of 4
5 was obtained as follows: backward cost s - a - b, which equals 1+2 = 3 PLUS forward cost estimate provided by the heuristic at b, which equals 2, together equalling 5
yeah , got it , but in video you have written it as (1+2)+1
rajan lad Ha, thanks, that handwriting could indeed have been clearer...
what a mess man
Who cares about A* when you have Deep RL?
lol