3.5 Uninformed Search Strategies

3.5.4 Lowest-Cost-First Search

For many domains, arcs have non-unit costs, and the aim is to find an optimal solution, a solution such that no other solution has a lower total cost. For example, for a delivery robot, the cost of an arc may be resources (e.g., time, energy) required by the robot to carry out the action represented by the arc, and the aim is for the robot to solve a given goal using fewest resources. The cost for a tutoring system may be the time and effort required by a student. In each of these cases, the searcher should try to minimize the total cost of the path found to a 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 with the fewest arcs is not one of minimal cost.

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

Example 3.12.

Consider a lowest-cost-first search from o103 to r123 in the graph given in Figure 3.2. In this example, the frontier is shown as a list of paths in order of cost, where paths are denoted by the node at the end of the path, with a subscript showing the cost of the path.

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

[b18,𝑡𝑠8,b411,o10912].

The path to b1 is then selected, resulting in frontier

[𝑡𝑠8,c211,b411,o10912,b214].

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

[c211,b411,o10912,𝑚𝑎𝑖𝑙14,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 all greater than a positive constant (bounded arc costs) 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 expanded is a path with lowest cost. Such a solution is optimal, because the algorithm expands paths from the start node in order of path cost. If a better path to a goal existed than the first solution found, it would have been expanded from the frontier earlier.

The bounded arc cost is used to guarantee the lowest-cost search will find a solution, when one exists, in graphs with finite branching factor. 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 all have a cost of less than 1. If there is an arc from n0 to a goal node with a cost equal to 1, it will never be selected. This is the basis of Zeno’s paradox that Aristotle wrote about more than 2300 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 a solution.