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

R. Trejo, J. Galloway, C. Sachar, V. Kreinovich, Chitta Baral, Le Chi Tuan

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)827-837
Number of pages11
JournalInternational Journal of Uncertainty, Fuzziness and Knowlege-Based Systems
Issue number6
StatePublished - Dec 2001


  • Optimal planning
  • Planning

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Artificial Intelligence


Dive into the research topics of 'From planning to searching for the shortest plan: An optimal transition'. Together they form a unique fingerprint.

Cite this