Preliminary Report on a Theory of Plan Synthesis.

摘要

Classical planning problems have the following form: given a set of goals, a set of actions, and a description of the initial state of the world, find a sequence of actions that will transform the world from any state satisfying the initial-state description to one that satisfies the goal description. In principle, a problem of this type may be solved by a very simple procedure: merely enumerate all possible sequences of actions and test each until one is found that achieves the intended goals. By this procedure, we will eventually find a solution if one exists. However, in practice, not only do we want to find a solution, we want to do so expeditiously. Quick and efficient problem solving is desirable primarily for reasons of economy: the less time it takes to solve a problem, the more productive one can be. Furthermore, in some situations, the time it takes can mean the difference between success and failure, as is the case when the problem is part of a scholastic exam or when the problem is to prevent meltdown in a nuclear reactor. Previous work aimed at developing efficient planning techniques has been highly experimental in nature, the standard methodology being to explore ideas by constructing computer programs. For the most part, very little theoretical analysis has been done to determine why the programs work when they are applicable, and whether they can be generalized to solve larger classes of problems.