3 Searching for Solutions

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

3.6 Heuristic Search

The search methods in the preceding section are uninformed (or blind) in that they do not take the goal into account until they expand a path that leads to a node that satisfies the goal. Heuristic information about which nodes are most promising can guide the search by changing which node is selected in line 13 of the generic search algorithm in Figure 3.4.

A heuristic function h⁢(n), takes a node n and returns a non-negative real number that is an estimate of the cost of the least-cost path from node n to a goal node. The function h⁢(n) is an admissible heuristic if h⁢(n) is always less than or equal to the actual cost of a lowest-cost path from node n to a goal.

There is nothing magical about a heuristic function. It must use only information that can be readily obtained about a node. Typically there is a trade-off between the amount of work it takes to compute a heuristic value for a node and the accuracy of the heuristic value.

A standard way to derive a heuristic function is to solve a simpler problem and to use the cost to the goal in the simplified problem as the heuristic function of the original problem [see Section 3.6.2].

Example 3.13.

For the graph of Figure 3.2, if the cost is the distance traveled, the straight-line distance between the node and its closest goal can be used as the heuristic function.

The examples that follow assume the following heuristic function:

h⁢(𝑚𝑎𝑖𝑙)=26h⁢(𝑡𝑠)=23h⁢(o⁢103)=21h⁢(o⁢109)=24h⁢(o⁢111)=27h⁢(o⁢119)=11h⁢(o⁢123)=4h⁢(o⁢125)=6h⁢(r⁢123)=0h⁢(b⁢1)=13h⁢(b⁢2)=15h⁢(b⁢3)=17h⁢(b⁢4)=18h⁢(c⁢1)=6h⁢(c⁢2)=10h⁢(c⁢3)=12h⁢(𝑠𝑡𝑜𝑟𝑎𝑔𝑒)=12

This h function is an admissible heuristic because the h value is less than or equal to the exact cost of a lowest-cost path from the node to a goal. It is the exact cost for node o⁢123. It is very much an underestimate of the cost to the goal for node b⁢1, which seems to be close, but there is only a long route to the goal. It is very misleading for c⁢1, which also seems close to the goal, but it has no path to the goal.

The h function can be extended to be applicable to paths by making the heuristic value of a path equal to the heuristic value of the node at the end of the path. That is:

h⁢(⟨no,…,nk⟩)=h⁢(nk)

A simple use of a heuristic function in depth-first search is to order the neighbors that are added to the stack representing the frontier. The neighbors can be added to the frontier so that the best neighbor is selected first. This is known as heuristic depth-first search. This search selects the locally best path, but it explores all paths from the selected path before it selects another path. Although it is often used, it suffers from the problems of depth-first search, and is not guaranteed to find a solution and may not find an optimal solution.

Another way to use a heuristic function is to always select a path on the frontier with the lowest heuristic value. This is called greedy best-first search. This method sometimes works well. However, it can follow paths that look promising because they appear (according to the heuristic function) close to the goal, but the path explored may keep getting longer.

Figure 3.9: A graph that is bad for greedy best-first search
Example 3.14.

Consider the graph shown in Figure 3.9, drawn to scale, where the cost of an arc is its length. The aim is to find the shortest path from s to g. Suppose the Euclidean straight line distance to the goal g is used as the heuristic function. A heuristic depth-first search will select the node below s and will never terminate. Similarly, because all of the nodes below s look good, a greedy best-first search will cycle between them, never trying an alternate route from s.