second algorithm I'm going to run for you is the AAR search algorithm this is also going to return for me the optimal path but the theory is that it should do a little less work or even a lot less work due to the fact that 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 to compute estimate of what the cost is between that state and one of the goal States so the estimate is that between node D and one of the goals it's going to cost six as you can see the actual cost the the shortest path between d and a goal state is actually nine so this is an underestimate and this turns out to be important in order for the AAR search algorithm to return the shortest path you must use uh a heuristic that never overestimates the cost so either it underestimates or it gets it entirely correct so here I've got heuristic values that are never overestimating the cost and therefore what that means is that a star is going to to return the optimal path for us let's see how this works it works in a similar way to uniform cost search except that we use the a star score that's the cost of the path so far as we used in uniform cost search plus we add onto that theistic 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 its AAR score so that we know its a star score if we find a better one than that then we know that we need to visit it and this can happen in the AAR search algorithm let's expand it so we can go to A to B and to D for a cost of 5 9 and 6 we have to take theistic measure into account as well theistic measure for a is seven so the algorithm thinks it's going to take um seven units of cost to get from a to the goal state from B theistic measure is three and from D theistic measure is six so the a star score is the cost of the path so far so that 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 + 3 it's 12 for this path as well and 6 + 6 it's also 12 for this path so at the moment the a star 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 theistic measure for B is three and theistic measure for G1 is zero because it's a goal State and theistic measure can understand that G1 is a goal State and therefore it doesn't cost any uh units in order to get to a goal state from there from A to B that's a cost of three from a to G1 is a cost of n so we now calculate the a star scores so the total cost of the path along the here is 8 5 + 3 we then 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 5 + 9 which is 14 plus the 0o and that takes us to 14 and we now Mark a as visited and add it to the visited list with an AAR score of 12 if later on in the search we find a path to a that has an aore a star 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 AAR score of more than 12 then we can completely ignore it and print 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 AAR score is this one here ending in node B so we look at node B from node B we can go to a for a cost of two or we can go to C for three now if we went to a for a cost of two then the total a star score of the path leading to a here would in fact fact be 20 13 + 7 so we've already visited it for 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 of four that's the estimate of how far it is to a goal State and it's 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 star score for the visit was 11 we've now got four paths in the tree one for 13 one for 14 and two for 12 so we're going to take one of these two we'll just take B first well B has already been visited for an a star score of 11 over here so there's no point in visiting it for an AAR 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 root back to S is not going to be visited because we've already visited that for a star score of five however we can add in C and we can add in E the cost is two in each Case C has anistic value of four e has a heuristic value of five let's calculate the a star scores so it's 8 + 4 that's 12 along that path and along this path here it's 6 + 2 that's 8 + 5 which brings us to 13 along this path we now add that to our visited list so D has been visited for an a star score of 12 let's look at the remaining active Parts in the tree well we've got this one for 13 this one for 14 here's one for 12 ending in c and here's one for 13 ending in e so it's going to be this one that gets explored next the one ending in e for an a star score of 12 that's one ending in C for an AAR 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 its a star score when we visited it was five and it's going to be more if we visit it this time but we can go to G2 and we can go to F so let's put those into the tree to G2 that has a heris score 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 AAR scores along these new branches so it's 8 + 5 + 0 is 13 and 8 + 7 is 15 15 and 6 is 21 for that Branch there so that's our most expensive Branch so far give c 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 star score 13 G1 a star score 14 G2 for a star score 13 F for uh a star score 20 one and E for 13 we're just going to we've got three that end in a 13 three that have a score of 13 we're just going to take them in alphabetical order so we'll visit this one for first C for a score of 13 but we already visited C for an a star score of 12 it's in there so there's no point in expanding that node that's a dead end then we go to E for the next one e we can go to to G3 for a cost of s G3 here we calculate the a star score of this new uh path so that's 6 + 2 that's 8 + 7 is 15 15 and Z is 15 for this Branch e has now been visited for an AAR score of 133 and at this point we've now got one 2 3 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 theistic that we used was um an admissible heuristic we know that this path here is the optimal path through the tree and I'll mark that for you in red as before what we noticed was that the algorithm the a star algorithm here has done a fair amount of work it's visited a fair number of nodes and it's expanded quite a lot of the tree the reason for this is that theistic measure that we used in the search space wasn't very accurate so for example theistic is estimating that it costs five 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 AAR search again but I'm going to give you more accurate measures for theistic from each of the node to see what difference that makes