From planning to searching for the shortest plan: An optimal transition

If we want to find the shortest plan, then usually, we try plans of length 1, 2, . . . , until we find the first length for which such a plan exists. When the planning problem is difficult and the shortest plan is of a reasonable length, this linear search can take a long time; to speed up the process, it has been proposed to use binary search instead. Binary search for the value of a certain parameter χ is optimal when for each tested value χ, we need the same amount of computation time; in planning, the computation time increases with the size of the plan and, as a result, binary search is no longer optimal. We describe an optimal way of combining planning algorithms into a search for the shortest plan -optimal in the sense of worst-case complexity. We also describe an algorithm which is asymptotically optimal in the sense of average complexity.