Informed Search

Heuristics

Heuristics are estimations of how close a state is to the goal. They are problem dependant, for example finding the shortest route from Arad to Bucharest may use Euclidean/Manhattan Distance (Straight line/Grid distance) as the heuristic. However, it should not use a heuristic such as population in cities. The heuristic function of a goal state will always evaluate to 0.

Heuristics can be created by relaxing the problem (removing constraints on actions), for example, if the roads did not exist and one can travel as the crow flies, Euclidean distance will be a heuristic for a route finding problem. Heuristics that evaluate to higher numbers dominate other heuristics and should be used instead (as long as they are admissible). If one has a list of heuristics that are all admissible, but none of them dominate the others, then you can create a new heuristic function, which takes the max of all the heuristics. This will be the dominant heuristic and will be admissible.

Greedy Best First Search

This algorithm chooses the node that it believes to be closest to the goal based on the heuristic function. It does not consider the actual cost of the actions. i.e. it will always choose the node in the frontier with the smallest heuristic cost.

Greedy best first search is complete in a finite state space, but it is not optimal. Its Time and Space Complexity is O(number of stages), however with a good heuristic this can be reduced substantially to O(bm).

A* Search

A* Search is like a combination of Best First Search and Uniform Cost, taking the optimality of Uniform Cost, while retaining the speed of Best First. It works by choosing the node in the frontier with the smallest actual cost + smallest heuristic cost. i.e. the evaluation function f(n) = g(n) + h(n) where g is the cost of an action and h is the heuristic cost. The node with the smallest evaluation function is the one that is chosen.

A* Search is complete. However, A* Tree Search is only optimal if the heuristic is admissible. Admissible heuristics mean those that do not overestimate the actual cost to reach the goal. For example, if a node A has an actual cost of 5km to goal node B, then h(A) ≤ 5. Euclidean Distance is always admissible for route finding problems.

For A* Graph Search to be optimal, the heuristic must be consistent. Consistent heuristics are admissible heuristics that satisfy the triangle inequality for all nodes in the graph - that is to say, h(n) ≤ g(n') + h(n') where n is a node and n' is a successor node of n. Euclidean Distance is also always consistent for route finding problems.

A* Search is optimally efficient, which means that any search algorithm with the same heuristic must expand all nodes that are expanded by A*. However, for most problems, the complexity is still exponential.