A* Search - YouTube

Second algorithm I'm going to run for

you is the A* search algorithm. This

is also going to return for me the

optimal path but the theory is that you

should do a little less work or even a

lot less work just the fact it's going

to use a heuristic to do an informed

version of the search. Let's have a look

at how this works. As you can see in the

search space now each node in the search

space has a number next to it and that

number is an estimate, a quick compute

estimate, of what the cost is between

that state and one of the goal states. So

the estimate is the between node B and

one of the goals it's going to cost six.

As you can see the actual cost which the

shortest path between D and the goal

state is actually nine so this is an

under estimate and this turns out to be

important. In order for the A* search

algorithm to return the shortest path

you must use a heuristic that never

overestimates the cost. So it either

underestimates or get it gets it entirely

correct. So here I've got heuristic

values that are never over estimating

the cost and therefore what that means

is that A* is going to return the

optimal path for it let's see how this

works. It works in a similar way to

uniform cost search except that we use

the A8 search score that's the cost

of the path so far as we used in uniform

cost search plus we add on to that the

heuristic of the end node of the path so

that gives you an estimate of the total

cost of the path that you're looking at

so far. Let's see how this goes here. We

look at this it's not the goal state

so we're going to expand it we'll add it

to the visited list and we'll also store

it's A*

score so that we know it's A* score if

we find a better one than that and we

know that we need to visit it and this

can happen in the A* search

algorithm. Let's expand it so we can go

to A to B and to D for a cost of five, nine

and six. We have to take the heuristic

measure into account as well the

heuristic measure for A is seven so it

the algorithm thinks it's going to take

seven units of cost to get from A to the

goal state.

From B the heuristic measure is three

and from D the heuristic measure is six.

So the A* score is the cost of the

path so far ,so for this one that's

five plus the cost of the heuristic

measure so that's an estimate of how far

it's still to go to get to the goal

state and that gives you an estimate of

what the total cost of this path is

going to be once it's actually got down

to a goal state. So it's 12 here 9 plus 3

is 12 for this path as well and 6 plus 6

is also 12 for this part so at the

moment the A* search is not

distinguishing between these

possibilities it thinks that each of

these paths is going to cost 12 in the

end. So let's just take them in

alphabetical order as we did before

we'll look at this one first. From A we

can go to B or we can go to G1 so let's

put those up there B and G1 the

heuristic measure for B is 3 and the

heuristic measure for G1 is 0 because

it's a goal state and the heuristic

measure can understand that G1 is a

goal state and therefore it doesn't cost

any units in order to get to a goal

state from there. From A to B that's a

cost of 3, from A to G1 is a cost

of nine so we now calculate the A*

scores so the total cost of the path

along there here is eight, five plus

three, within add in the further three

here and that gets us to 11. So the total

estimated cost of that path is 11 the

eight plus another three. And for this

path it's five plus nine which is 14

plus the zero and that takes us to 14.

And we now mark A as visited and add it

to the visited list with an A* score

of 12. If later on in the search we find

a path to A that has an A* score

of less than 12 then we will look at

that. However if we find later on in the

algorithm a path to A with an A*

score of more than 12 then we can

completely ignore it and prune that part

of the search. Okay so we now continue

we've got four active paths in the tree

and the one with the best A* score

is this one here ending in node B. So

look at node B. From note B we can go to

a for a cost of two or you can go to C for

three. Now if we went to A for a cost of

two then the total A* score of the

path leading to A here would in fact be

twenty, thirteen plus seven,

so we've already visited it to 12 we

don't need to add it back to the tree.

But for the other node B to C we will

add that to the tree. So C has a

heuristic cost before that's the

estimate of how far it is to a goal

state and its cost of one to get there.

So it's now nine along that path plus

the four which makes it 13,

and that one has now been visited so B has now

been visited and it's A* score for

the visit was 11. We've now got four

paths in the tree one for 13 one for 14

and 2 for 12. So we're going to take one

of these two. We'll just take the first.

What B has already been visited for an

A* score of 11 over here so there's

no point in visiting it for an A* score

of 12 so that's a dead end.

Now look at D from D we can go back to S,

we can go to C and to E the route back

to S is not going to be visited because

we've already visited that for A*

score of 5. However we can add in C and

we can add in E the cost is 2 in each

case C has a heuristic value of 4 E has

a heuristic value of 5. Let's calculate

the A* scores. so it's 8 plus 4

that's 12 along that path and along this

path here it's 6 plus 2 that's 8, plus 5 which

brings us to 13 along this path. We now

add that to our visited list so D has

has been visited for an A* score of 12. Let's

look at the remaining active paths in the

tree. Well we've got this one for 13

this one for 14 here's one for 12 and

again C and here's one for 13 ending in

E so it's going to be this one that gets

explored next one ending in E for an

A* score of 12,

that's lining is C for an A* score of

12 rather so let's look where we can go

to from C. Well we can go back to S but

we're not going to do that because it's

A* score when we visit it was 5 and

it's going to be more if we visit this

time, but we can go to G2

and we can go to F so let's put those

into the tree.G2 that has a

heuristics cost of zero and the cost of the

arc is five and to F, F has a heuristic

score,

a heuristic estimate of six and the cost

of the arc is seven. So let's calculate

the new A* scores along these new

branches. So it's eight plus five plus

zero is 13. And 8 plus 7 is 15 15 and 6 is

21 for that branch there so that's our

most expensive branch so far. Good to see

a tick and add it to the visited list so

C has been visited for a cost of 12.

Let's look at the remaining branches.

Well we've got C here for an A* score of

13, G1 A* score 14 G2 for an A*

score 13, F for an A* score 21 and E

for 13. We're just going to we've got

three end in a 13 3 have score of 13 we're

just going to take them in alphabetical

order. So we'll visit this one for the C

for a score of 13 but we already visited

C for an A* score of 12 it's in there

so there's no point in expanding that

note that's a dead end.

Then we go to E for the next one E we can

go to G3 for a cost of 7, G3 here.

We calculate the A* score of this

new path so that six plus two is eight

plus seven is 15, 15 and zero is 15

for this branch E has now been visited

for an A* score of 13. And at this

point we've now got one, two, three, four

active branches 14, 13, 21, and 15 so this

is the best one we look at the node to

see if it's a goal state and it is so we

have now reached the goal and because

the heuristic that we used was an

admissible heuristic we know that this

path here is the optimal path through

the tree. Now I'll mark that for you in red

as before. What we noticed was that the

algorithm the A* algorithm here has

done a fair amount of work, it's visited

a fair number of nodes, and it expanded

quite a lot of the tree. The reason for

this is that the heuristic measure that

we used in the search space wasn't very

accurate. So for example the heuristic is

estimating that it costs 5 to get from S

to a goal state and we now know that the

actual cost is 13. So what I'm going to

ask you to do for the assignment is that

I'm going to ask you to run the search

the A* search again but I'm going to

give you more accurate measures for the

heuristics from each of the node to see

what difference that makes.