ABSTRACT
It has long been believed that one of the cornerstones of intelligence is the ability to plan, or simulate the future. With this ability a planner can test the usefulness of certain action sequences without exposing itself to the hazards of actually executing those sequences in a real-world environment. Planning here includes such problem-solving activities as that carried out, for example, by Strips systems (Fikes and Nilsson, 1971) or theorem provers (Green, 1969). Such systems take formal descriptions of an external environment and of a problem statement and attempt to compute plans, or sequences of actions, which when executed yield a state of the agent and the environment satisfying the problem statement. The computational costs are the time and space consumed by the planning process. Evidence that planning is expensive is the fact that even though in principle it is possible to solve problems, a guarantee provided by many complete search procedures, there are few practical applications of what has been presented in the planning literature. There are exceptions, such as reported in Vere (1983), Georgeff and Lansky (1987) and Stefik (1981a, 1981b). However, these cases seem unrepresentative of the broad coverage that the completeness property suggests is possible.
