A heuristic is an idea that helps you make a decision, any heuristic might not actually help you get to your goal, that's why it's a heurisitc and not a method or a prodcedure.
Our goal is to develop a domain specfic heuristic function which guesses the cost of getting to a goal state froma node , where if we see then we would guess that it is cheap to get to a goal node from then from . If is a goal state then we define
The heuristic is defined on the state stored in the node, so that if two different nodes have the same state then their heuristic values would be the same.
Greedy Best First
Use a frontier which has a priority queue, where a nodes priority is it's value. Therefore we will always expand nodes by lowest value to attempt to greedily find a low cost solution. Since values don't necessarily have to depend on the cost of a path, then in general it will not produce cost optimal solutions.
f value
One way of trying to fix the above issue with costs, is to incorporate the cost of a given path as we continue. Let's define the following function:
Where is the cost of the path to and is our usual heuristic, let's denote as a evaluation function, and it's individual values as f values, it's purpose is to estimate the cost of getting to the goal from
The purpose of the f-value is to combine our knowledge about the cost of a nodes path and what the heuristic value returns.
A Star
In A* we will define a f-value function, and expand the node with the lowest f-value on the frontier
We'll note that if there is no solution in the graph, and the graph is an infinite number of different states (even with finite branching factor) which are reachable from the initial state, then this algorithm will never terminate.
This is because on every iteration we will be adding more nodes to the frontier, and we only consume one node off the frontier at a time so we will never be able to clear them all, we note that the algorithm only terminates once the frontier is empty.
But if there ar ea finite number of different reachable states and we do path checking or cycle checking, then it will eventually terminate and deduce that there is no solution. If we don't do cycle checking then it would constantly add a node to the fronteir pop it off and add the next node in the cycle, and continue doing that forever.
A* Execution Table
For the following graph where is the start node and is the goal:
Run A* with and without cycle checking, drawing the frontier table for each.
Note that (ACBC, 12) was pruned, because we had already seen a path ending in C, which had cost 8, namely (AC, 8), so there was no need to explore this one.
Complete
We can prove that A* is complete under certain conditions.
A* is Complete
A* will always find a solution if one exists so long as
There exists a maximum branching factor
There exists a global lower bound for all actions
is finite for every node which can be extended to reach a goal node
Since we know a goal state exists, then at any time in the search we know that an ancestor of is on the frontier. Which we can prove by indiction on the number of ancestors of .
Suppose that is an ancestor of on the frontier, then by the second condition, we know that every action has finite cost, and thus the path cost of is also finite, since we know that can be extended to reach a goal node, we know that it has a finite h-value, and thus it's f-value is finite.
As A* continues to run, we claim that the f-value of the nodes on the frontier eventually increase, this is because if we expand some node , then it is removed from the frontier, and a successor is added to the frontier, we know that the g-value of is greater than 's g value, but perhaps the h-value of is smaller than the h-value of , and in that case it may be possible for the f-value of y to be less than x's f-value, suppose x's f value decreased by .
We know that there exists some such that , and thus no matter what after iterations the f-value of any node will exceed the f-value of and so f-values eventually increase (which means there are finitely many nodes on the frontier which have smaller f-value). With that said, since is on the frontier, and eventually f-values increase, then either A* finds a solution in this time, or becomes the node on the frontier with the lowest f-value.
Thus we expand , and if is the immediate ancestor of , then we get and it returns, or it adds another ancestor which is one step closer and by applying the same argument again, we see that eventually expand every ancestor of and then and so it will find the goal node.
Note that the reason we require a global lower bound on our actions, is that suppose there was a sequence of actions with costs , and suppose we have some constant heurstic such that for all nodes, then we note that and so if every other value in the frontier is greater or equal to , then we would continue selecting nodes with these geometric costs, and if there is no goal node then it would do this forever.
We require that the h value is finite, if it can be extended to reach a goal node because if it were infinite, then it's f value would also be infinite, and thus it is greater than all other values, and therefore anything in the frontier will always be expanded before it gets expanded, and the only way it would be expanded is if nothing else is on the frontier, but that's never guarenteed to happen since our graph may be infinite.
Admissible Heuristic
Let be the cost of an optimal path from some node to a goal node (define as otherwise), then a heurstic function is said to be admissible if
A* is Not Cost Optimal if The Heuristic is Not Admissible
Show that A* returns a non cost optimal path if the heuristic is not admissible
Observe the following graph where are goal states, note that is not admissible because the the cost to get from the splitting node to is only , but the heuristic overshoots this value.
If A* is executed on this graph, then when the branching node is expanded both and are added to the frontier, 's f-value is given by and 's f-value is given by , so therefore A* will expand next and terminate because it's a goal state, but has lower cost.
This requires that your heustic estimate is less than or equal to the cost of an optimal path to the goal node, that is to say that your heuristic never over-estimates, it can only under-estmiate the cost of getting to the goal node. This implies that the search won't miss any promising path if it is cheap to get to a goal via ( that is to say that is low and is low), then is also low, and eventually will be expanded off the frontier.
A* Never Expands Large f-values
A* with an admissible heuristic never expands a node with f-value greater than the cost of an optimal solution
Let be the cost of an optimal solution, and be the path taken. We can show by indiction that for each node in the search space that is reachable from our initial node, at every iteration an ancestor of that node is on the frontier.
Therefore let be a node which is reachalbe from the initial state and then let be the ancestors of . So by our previous paragraph at least one of them is always on the frontier. Now observe that
A* is Optimal
If the following assumptions hold true, then A* will find an optimal cost solution:
the branching factor is finite
there is a global lower bound on all actions given by
our heuristic is admissible
if a solution exists then since A* is complete, it will terminate by expanded some goal node , by the above lemma we know that , and since is a goal node we know that therefore so then , but since no solution can have lower cost than the optimal we conclude that which means that A* returns a cost-optimal solution.
Monotone Heuristics
We say that a heuristic function is monotone if it satisfies the triangle inequality, that is for all nodes such that is a successor of and is the action between them: Where denotes the cost of getting from the state of to via action
This means that has to be less than the estimate of plus the cost of actually moving from to . So for example if we know that , and the cost of moving from to is 10, then is at least .
It says that "we don't change our mind", based on a simple transition, so that by taking one action our heuristic isn't going to drastically change.
Monontonicity implies Admissibility
Later Expansions Imply Larger f-values Under Monotonic Heuristic
If a node is expanded after by A* with a monotonic heuristic, then we know that
First Expansion is Minimum Cost Uner Monotonic Heuristic
With a monotone heuristic, the firs ttime A* expands a node , must be a minmum cost solution to .state