1.3.1.1 - Means-End Analysis

A search for a plan may be extensive when working from the start node. Starting at the goal state and reducing the difference between the goal and the start makes the problem more tractable. This technique is referred to as Means-End Analysis and was originally proposed for GPS (General Problem Solver) by Newell and Simon [1972]. This is the most common method used in planning systems.

1.3.1.2 - Inductive Plans

The reversibility of an action is important when generating a plan. If actions can be undone, then plans may be forward searched in the real world. This is because reversible actions make it possible to backtrack from a failed solution. If actions are not reversible, a world model must be used to simulate the effects of actions. Planning in the real world is not desirable, but may become necessary when the world model has randomly changing conditions.

1.3.1.3 - General Comments on Plan Completeness

A search for a plan may be an overwhelming task. Thus, a number of simplifying assumptions are often made in planning,

• there is only one operation to perform at each task,

• operators are costless,

• operator order is costless,

• the world models are limited to the problems only,

• time is not a factor,

• plans are sequential,

• operations are concurrent (not parallel).

These factors tend to simplify the search space. But, even when searching the simplified problem spaces, there are a number of arbitrary decisions that have to be made. These usually arise because of the arbitrary sequence of operator execution, arbitrary choice of alternative operators, and lack of information. In the presence of arbitrary decisions the best plan can be found with the aid of cost estimates [e.g., Tate, 1977]. Lack of information is often dealt with by a least commitment strategy, where decisions are made as late as possible, or not at all [Sacerdoti, 1975, 1977 and Stefik, 1981 a, b].

1.3.2.1 - Non-Hierarchical Planners

When goals are used to directly find operators, the system is referred to as non-hierarchical. This name definition is commonly used to describe all planners which do not fall into the other categories, namely hierarchical, skeletal, and opportunistic planning. One attribute of these planners is that since they consider all of the search space at once, the search must cover a larger number of possible solutions. The common approach is to use a linear search through space. Some descriptions of the more famous planners follow. This includes descriptions of the most popular non-hierarchical planners, NOAH and STRIPS.

STRIPS - described in [Nilsson, 1980], is based on a goal stack. To begin, the goals are pushed on the goal stack. An Operator is found which satisfies the top goal on the stack, and it will also be pushed on the top of the stack. The preconditions for the operator are then also pushed on the stack. The basic process continues as the condition currently at the top of the stack is examined. If the condition of the top of the stack is satisfied (by the world model), it is removed. If an operator is at the top of the stack all its preconditions have been satisfied, the operator is added to the plan, and used to update the world model. If the condition at the top of the stack is unsatisfied, it will be replaced with an operator which will satisfy it (then all of the operators preconditions will also be pushed on the stack). This process continues until the stack is empty, thus indicating a complete plan.

It is possible for strips to become caught in certain situations that involve non-linear plans, and fail to produce a solution. In some cases STRIPS is able to find solutions to hard problems, but still results in inefficient solutions.

HACKER - Sussman’s work on HACKER [1974] used a plan and repair approach. If an existing plan satisfied the goals presented, it was used. Otherwise, a plan was generated by subdividing the goals until they could be matched to operators. The plan could then be examined by a set of daemons (monitor processes) that can detect known problem patterns, and fix them. Afterwards, the plan was simulated, and any existing errors were found. The problems that caused the errors were identified, and fixed with general debugging techniques. The problem patterns were then stored as new daemons for later problem pattern matching. This process continued until the plan was error free.

Sussman’s [1974] examination of this method has become well known because of the failure of HACKER (a linear planner) to perform a certain three block problem. Dubbed the Sussman Anomaly, the problem involved blocks stacked in such a way that two goals had to be combined. This served as an excellent example of the limitations often encountered by the simpler linear planning schemes.

Goal Regression - Waldinger [1977] proposed a planner that would satisfy one goal at a time. The planner would arbitrarily choose one goal as the first and find a plan for it. A second goal would be incorporated into the plan by trying to expand the second goal after the last step in the first plan. If the preconditions of the second goal plan were violated then the attempt would fail and the second goal would be reconsidered before the last step in the first plan. If the second goal could not be expanded there, then it would be moved though the first plan by another step. This regression will continue until the goal is successful, and is expanded, or it fails by reaching the start of the other plan.

Waldingers approach did not discuss many of the detailed issues, and was lacking an implementation to verify his ideas. The planner could fail in some situations because of its inability to violate the precondition constraints. But, he did discuss some of the anticipated side-effects which would occur if the preconditions could be violated (and goals expanded prematurely). He asserted that some previously unsolvable problems could be solved, but he also stated that some problems could arise. For example, it is possible to have a solution which repeatedly does an action and then undoes it. It is also possible to generate inefficient solutions having needless operations.

1.3.2.2 - Hierarchical Planners

A more efficient approach to planning involves least commitment examination of the various hierarchies of detail. In other words, the planning should begin at an abstract high level [abstractions are discussed in Korf, 1987]. As planning progresses, the abstract goals should be expanded into more detailed sub-goals. Planning becomes a task of examining a small search space, pruning the search, then expanding the new pruned search space. This makes problems with a large search space tractable (e.g., non-linear plans).

ABSTRIPS - a simple approach to hierarchical planning was based on STRIPS [Nilsson, 1980]. This new planner was called ABSTRIPS [described in Cohen and Feigenbaum, 1982], and only involved the addition of priorities to the preconditions already used in STRIPS. The planning techniques were similar to STRIPS, except that all of the first stage of planning was done with the highest priority conditions. After a complete high level plan was pushed on the stack, it was expanded at a lower priority level. The effect was a greatly reduced search space which could allow solutions of much greater complexity.

In terms of abilities, ABSTRIPS has all the features of STRIPS, but is much more efficient at solving large problems.

NOAH, NONLIN and DEVISER - the procedural nets mentioned earlier are important to NOAH [Sacerdoti, 1975, 1977]. If the reader refers to Figure 1.3 A Procedural Net (for painting) they will note the square nodes. These are used to represent both goals and sub-goals. At each iteration of the search, the square nodes are expanded into sub-plans. After this, three constructive critics are applied to resolve conflicts, eliminate redundant preconditions, and deal with unbound variables. Resolving conflicts involves ordering unordered operations to avoid precondition violations. If preconditions are specified more than once, they should be recognized and the redundant ones eliminated. Unbound variables can occur because of the general form of operation definitions. This can lead to problems assigning them. The critics approach is to bind them to a formal variable or to an instance. The least commitment strategy dictates that the formal variables (or unbound variables) should only be bound to an instance when no other alternatives exist.

Tate [1977] indicates that Sacerdoti’s approach has problems because it is unable to backtrack and undo failed plan steps. Therefore, Tate developed NONLIN, which is like NOAH except that it keeps lists of all decisions made (and all goals achieved) so that backtracking is possible in planning (as well as execution checking). If a plan cannot be found, NONLIN backtracks and tries a new solution.

Vere [1983] states that both NOAH and NONLIN assume that tasks are concurrent, thus trivializing the time planning problem. DEVISER [Vere, 1983] was based upon NONLIN, and can consider parallel tasks with critical execution times. The planner was able to plan device operation plans for a fly by of an interplanetary satellite. The significant difference between NONLIN and DEVISER is the addition of time windows in the consideration of conflict resolution.

MOLGEN [Stefik, 1981a, b] - uses a less general approach to planning. Three layers of abstraction are used: the strategy, design and planning spaces. Goal relations are considered and manipulated in strategy space. Details of the plan are generated in the planning space. In the design space, constraints are considered. The interesting feature of MOLGEN is its use of constraints. Details of each operation include constraints. As operations are specified, the constraints are formulated, and propagated to be considered against constraints from other parts of the plan. MOLGEN then chooses objects to satisfy the constraints of the operations. If a plan is formulated at the strategy level, but the constraints cannot be satisfied at the design level, then the strategy level will replan.

This planner was successful with the complex problem of planning molecular genetics experiments, and shows promise for other more sophisticated problems.

1.3.2.3 - Skeletal Planners

The technique of skeletal planning is variant, not generative as the previous methods are. If a successful plan template is available from earlier planning sessions (or elsewhere) it is stored in a plan database. Before planning begins, the goals are compared against the skeletal plans. If plans are found to satisfy the goal pattern, they are then checked for their success with the current world model. Any remaining plans will be examined for suitability, and the best will be chosen. A successful implementation of this technique was demonstrated with MOLGEN [as described in Cohen and Feigenbaum, 1982, pp. 557-562].

1.3.2.4 - Opportunistic Planning

In his book Gevarter [1985] describes an approach to planning which is opportunistic. This only refers to a technical report (by Hayes-Roth and Hayes-Roth), but suggests that plans may be developed in two stages. First, parts of a plan may be devised with backtracking. Secondly, the parts may be liked together, added to, and enlarged as opportunities become available. Gevarter asserts that this is a more human like approach to planning.