Planning in AI has been around since as early as 1963, when [Newell and Simon 63] introduced the General Problem Solver (GPS). In general, an AI planner generates an ordered set of actions that will change the input state into the desired goal state. GPS typifies a non-hierarchical planner, where different sequences of actions, or operators, are tried until the goal state is reached. Although heuristics are usually employed to guide this kind of search, it soon becomes unmanageable in larger systems.
In order to remedy this problem, hierarchical systems such as NOAH [Sacerdoti 77] were created. These systems represent plans in a hierarchy, where higher level plans are abstractions of lower level plans. Planning then becomes the process of finding a sequence of high level plans that fulfill the goal, and then recursively refining those goals until a complete plan is reached. The actual process of finding a sequence of actions at each stage of the hierarchy is the same as in non-hierarchical planning, but the search space is greatly reduced because only the operators at the current level are considered. ``Skeleton'' planning is a type of hierarchical planning where the higher level plans are not actually generated but selected and instantiated from a set of pre-stored plans. The skeleton is then ``filled in'' as above.
The other type of planners relevant to this project are called ``opportunistic'', or ``distributed''. These planners accept inputs from various information sources when the information is needed. They are ``data-driven'', in the sense that processing is controlled by the needs of the data, instead of by an imposed hierarchy. Opportunistic planners will be discussed in more detail below in the context of the DIOGENES text generation system.