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

3.5.3 Lowest-Cost-First Search

When a non-unit cost is associated with arcs, we often want to find the solution that minimizes the total cost of the path. For example, for a delivery robot, costs may be distances and we may want a solution that gives the minimum total distance. Costs for a delivery robot may be resources required by the robot to carry out the action represented by the arc. The cost for a tutoring system may be the time and effort required by the students. In each of these cases, the searcher should try to minimize the total cost of the path found to reach the goal.

The search algorithms considered thus far are not guaranteed to find the minimum-cost paths; they have not used the arc cost information at all. Breadth-first search finds a solution with the fewest arcs first, but the distribution of arc costs may be such that a path of fewest arcs is not one of minimal cost.

The simplest search method that is guaranteed to find a minimum cost path is similar to breadth-first search; however, instead of expanding a path with the fewest number of arcs, it selects a path with the minimum cost. This is implemented by treating the frontier as a priority queue ordered by the cost function.

Example 3.11: Consider a lowest-cost-first search from o103 in the graph given in Figure 3.2. The only goal node is r123. In this example, paths are denoted by the end node of the path. A subscript shows the cost of the path.

Initially, the frontier is [o1030]. At the next stage it is [b34,ts8,o10912]. The path to b3 is selected, with the resulting frontier

[b18,ts8,b411,o10912].

The path to b1 is then selected, resulting in frontier

[ts8,c211,b411,o10912,b214].

Then the path to ts is selected, and the resulting frontier is

[c211,b411,o10912,mail14,b214].

Then c2 is selected, and so forth. Note how the lowest-cost-first search grows many paths incrementally, always expanding the path with lowest cost.

If the costs of the arcs are bounded below by a positive constant and the branching factor is finite, the lowest-cost-first search is guaranteed to find an optimal solution - a solution with lowest path cost - if a solution exists. Moreover, the first path to a goal that is found is a path with least cost. Such a solution is optimal, because the algorithm generates paths from the start in order of path cost. If a better path existed than the first solution found, it would have been selected from the frontier earlier.

The bounded arc cost is used to guarantee the lowest-cost search will find an optimal solution. Without such a bound there can be infinite paths with a finite cost. For example, there could be nodes n0,n1,n2,... with an arc ⟨ni-1,ni⟩ for each i>0 with cost 1/2i. Infinitely many paths of the form ⟨n0,n1,n2,...,nk⟩ exist, all of which have a cost of less than 1. If there is an arc from n0 to a goal node with a cost greater than or equal to 1, it will never be selected. This is the basis of Zeno's paradoxes that Aristotle wrote about more than 2,300 years ago.

Like breadth-first search, lowest-cost-first search is typically exponential in both space and time. It generates all paths from the start that have a cost less than the cost of the solution.