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 x is optimal when for each tested value x, 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.