Artificial
Intelligence

3.7.2 Multiple-Path Pruning

There is often more than one path to a node. If only one path is required, a search algorithm can prune from the frontier any path that leads to a node to which it has already found a path.

Multiple-path pruning can be implemented by keeping a closed list of nodes that have been expanded. When a path is selected at line 13 of Figure 3.4, if its last node is in the closed list, the path can be discarded. Otherwise, its last node is added to the closed list, and the algorithm proceeds as before.

This approach does not necessarily guarantee that the shortest path is not discarded. Something more sophisticated may have to be done to guarantee that an optimal solution is found. To ensure that the search algorithm can still find a lowest-cost path to a goal, one of the following can be done:

• Make sure that the first path found to any node is a lowest-cost path to that node, then prune all subsequent paths found to that node, as discussed earlier.
• If the search algorithm finds a lower-cost path to a node than one already found, it can remove all paths that used the higher-cost path to the node (because these cannot be on an optimal solution). That is, if there is a path p on the frontier ⟨s,...,n,...,m⟩, and a path p' to n is found that is shorter than the portion of the path from s to n in p, then p can be removed from the frontier.
• Whenever the search finds a lower-cost path to a node than a path to that already found, it can incorporate a new initial section on the paths that have extended the initial path. Thus, if there is a path p=⟨s,...,n,...,m⟩ on the frontier, and a path p' to n is found that is shorter than the portion of p from s to n, then p' can replace the initial part of p to n.

The first of these alternatives allows the use of the closed list without losing the ability to find an optimal path. The others require more sophisticated algorithms.

In lowest-cost-first search, the first path found to a node (i.e., when the node is selected from the frontier) is the least-cost path to the node. Pruning subsequent paths to that node cannot remove a lower-cost path to that node, and thus pruning subsequent paths to each node still enables an optimal solution to be found.

As described earlier, A^* does not guarantee that when a path to a node is selected for the first time it is the lowest cost path to that node. Note that the admissibility theorem guarantees this for every path to a goal node but not for every path. To see when pruning subsequent paths to a node can remove the optimal solution, suppose the algorithm has selected a path p to node n for expansion, but there exists a lower-cost path to node n, which it has not found yet. Then there must be a path p' on the frontier that is the initial part of the lower-cost path. Suppose path p' ends at node n'. It must be that f(p) ≤ f(p'), because p was selected before p'. This means that

cost(p) + h(n) ≤ cost(p')+h(n').

If the path to n via p' has a lower cost than the path p,

cost(p') + d(n', n)<cost(p),

where d(n' , n) is the actual cost of the shortest path from node n' to n. From these two equations, we can derive

d(n', n)<cost(p)-cost(p') ≤ h(p') - h(p)= h(n') - h(n).

Thus, we can ensure that the first path found to any node is the lowest-cost path if |h(n')-h(n)| ≤ d(n',n) for any two nodes n and n'. The monotone restriction on h is that |h(n')-h(n)| ≤ d(n',n) for any two nodes n and n'. That is, the difference in the heuristic values for two nodes must be less than or equal to the actual cost of the lowest-cost path between the nodes. It is applicable to, for example, the heuristic function of Euclidean distance (the straight-line distance in an n-dimensional Euclidean space) between two points when the cost function is distance. It is also typically applicable when the heuristic function is a solution to a simplified problem that has shorter solutions.

With the monotone restriction, the f-values on the frontier are monotonically non-decreasing. That is, when the frontier is expanded, the f-values do not get smaller. Thus, with the monotone restriction, subsequent paths to any node can be pruned in A^* search.

Multiple-path pruning subsumes a cycle check, because a cycle is another path to a node and is therefore pruned. Multiple-path pruning can be done in constant time, if the graph is explicitly stored, by setting a bit on each node to which a path has been found. It can be done in logarithmic time (in the number of nodes expanded, as long as it is indexed appropriately), if the graph is dynamically generated, by storing the closed list of all of the nodes that have been expanded. Multiple-path pruning is preferred over cycle checking for breadth-first methods where virtually all of the nodes considered have to be stored anyway. For depth-first search strategies, however, the algorithm does not otherwise have to store all of the nodes already considered. Storing them makes the method exponential in space. Therefore, cycle checking is preferred over multiple-path checking for depth-first methods.