${𝐀}^{\ast }$ search finds a least-cost path and can exploit heuristic information to improve the search. It uses both path cost, as in lowest-cost-first, and a heuristic function, as in greedy best-first search, in its selection of which path to expand. For each path $p$ on the frontier, $A^{\ast }$ uses an estimate of the total path cost from the start node to a goal node that follows $p$ then goes to a goal. It uses $cost(p)$, the cost of the path found, as well as the heuristic function $h(p)$, the estimated path cost from the end of $p$ to the goal.

For any path $p$ on the frontier, define $f(p)=cost(p)+h(p)$. This is an estimate of the total path cost to follow path $p$ then go to a goal node. If $n$ is the node at the end of path $p$, this can be depicted as

If $h(n)$ is an admissible heuristic and so never overestimates the cost from node $n$ to a goal node, then $f(p)$ does not overestimate the path cost of going from the start node to a goal node via $p$.

$A^{\ast }$ is implemented using the generic search algorithm, treating the frontier as a priority queue ordered by $f(p)$.

A search algorithm is admissible if, whenever a solution exists, it returns an optimal solution. To guarantee admissibility, some conditions on the graph and the heuristic must hold. The following theorem gives sufficient conditions for $A^{\ast }$ to be admissible.

It should be noted that the admissibility of $A^{\ast }$ does not ensure that every intermediate node selected from the frontier is on an optimal path from the start node to a goal node. Admissibility ensures that the first solution found will be optimal even in graphs with cycles. It does not ensure that the algorithm will not change its mind about which partial path is the best while it is searching.

To see how the heuristic function improves the efficiency of $A^{\ast }$, suppose $c$ is the cost of a least-cost path from the start node to a goal node. $A^{\ast }$, with an admissible heuristic, expands all paths from the start node in the set

and some of the paths in the set

Increasing $h$ while keeping it admissible can help reduce the size of the first of these sets. Admissibility means that if a path $p$ is in the first set, then so are all of the initial parts of $p$, which means they will all be expanded. If the second set is large, there can be a great variability in the space and time of $A^{\ast }$. The space and time can be sensitive to the tie-breaking mechanism for selecting a path from those with the same $f$-value. It could, for example, select a path with minimal $h$-value or use a first-in, last-out protocol (the same as a depth-first search) for these paths; see Exercise 3.6.

Depth-first branch-and-bound search is a way to combine the space saving of depth-first search with heuristic information for finding optimal paths. It is particularly applicable when there are many paths to a goal. As in $A^{\ast }$ search, the heuristic function $h(n)$ is non-negative and less than or equal to the cost of a lowest-cost path from $n$ to a goal node.

The idea of a branch-and-bound search is to maintain the lowest-cost path to a goal found so far, and its cost. Suppose this cost is $bound$. If the search encounters a path $p$ such that $cost(p)+h(p)\ge bound$, path $p$ can be pruned. If a non-pruned path to a goal is found, it must be better than the previous best path. This new solution is remembered and $bound$ is reduced to the cost of this new solution. The searcher then proceeds to search for a better solution.

Once it has found one solution, branch-and-bound search generates a sequence of ever-improving solutions. The final solution found is the optimal solution.

Branch-and-bound search is typically used with depth-first search, where the space saving of the depth-first search can be achieved. It can be implemented similarly to depth-bounded search, but where the bound is in terms of path cost and reduces as shorter paths are found. The algorithm remembers the lowest-cost path found and returns this path when the search finishes.

The algorithm is shown in Figure 3.14. The internal procedure $cbsearch$, for cost-bounded search, uses the global variables to provide information to the main procedure.

Initially, $bound$ can be set to infinity, but it is often useful to set it to an overestimate, $boun{d}_0$, of the path cost of an optimal solution. This algorithm will return an optimal solution – a lowest-cost path from the start node to a goal node – if there is a solution with cost less than the initial bound $boun{d}_0$.

If the initial bound is slightly above the cost of a lowest-cost path, this algorithm can find an optimal path expanding no more arcs than $A^{\ast }$ search. However, it is rare to know the cost of a lowest-cost path. In general, once it has found an optimal path to the goal, it only explores paths whose $f$-value is lower than the optimal path. These are exactly the paths that $A^{\ast }$ explores to find one solution.

If it returns $\perp$ when $boun{d}_0=\mathrm{\infty }$, there are no solutions. If it returns $\perp$ when $boun{d}_0$ is some finite value, it means no solution exists with cost less than $boun{d}_0$. This algorithm can be combined with iterative deepening to increase the bound until either a solution is found or it can show there is no solution, using a method similar to the use of $hit\mathrm{\_}depth\mathrm{\_}bound$ in Figure 3.11. See Exercise 3.11.

An admissible heuristic is a non-negative function $h$ of nodes, where $h(n)$ is never greater than the actual cost of the shortest path from node $n$ to a goal. The standard way to construct a heuristic function is to find a solution to a simpler problem, one with fewer states or fewer constraints. A problem with fewer constraints is often easier to solve (and sometimes trivial to solve). An optimal solution to the simpler problem cannot have a higher cost than an optimal solution to the full problem because any solution to the full problem is a solution to the simpler problem.

In many spatial problems where the cost is distance and the solution is constrained to go via predefined arcs (e.g., road segments), the straight-line Euclidean distance between two nodes is an admissible heuristic because it is the solution to the simpler problem where the agent is not constrained to go via the arcs.

For many problems one can design a better heuristic function, as in the following examples.

In the above examples, determining the heuristic did not involve search. Once the problem is simplified, it could be solved using search, which should be simpler than the original problem. The simpler search problem typically needs to be solved multiple times, even perhaps for all nodes. It is often useful to cache these results into a pattern database that maps the nodes of the simpler problem into the heuristic value. In the simpler abstract problem, there are often fewer nodes, with multiple original nodes mapped into a single node in the simplified graph, which can make storing the heuristic value for each of these nodes feasible.