1.2 PLANNING PROBLEMS

Researchers have embodied the planning problems with a symbolic approach. Thus, the problem is easily described in terms of lists, rules and expressions. This approach was first described by Green [1969] who discussed a planner based on resolution of logical statements.

 

1.2.1 Representation of Problem Space

The representation of problem space is primarily split into two main divisions. Initially the state of the world must be described by a model. As a plan is executed, the world model will evolve through time. If a world model is not used (for simulation) then the operators must be applied to the world directly. This will cause problems when backtracking operations to recover from a failed plan.

1.2.1.1 - The World Model

A list of conditions (predicates) are stored in a list. As conditions in the world change, conditions are added and removed from the list.

1.2.1.2 - The Solution (Plan) Model

Operators are applied that may update a world model. As the model changes, it will form a linear sequence of states over time. This is equivalent to a path through a graph [Korf, 1987]. As a result, the description of planning often takes on the terminology used for search.

1.2.2 Representation of Goals

At any time the world model contains a set of conditions. When some goals are introduced, they must describe the desired state of the world model. Thus, goals are described with a conjunctive expression of all the desired conditions in the world model. Each condition is considered a separate goal.

1.2.3 Operators

To describe actions, operators are used. Traditionally, an operator has a set of preconditions which must exist in the world model before an action can be performed. If the preconditions of an action are satisfied, the results of the action are simulated by deleting and adding conditions to the world model.

It is important to note that this may result in one operator violating the preconditions of other operators.

1.2.4 Plans

The representation of plans is important (we will avoid the subject of planning until section 4.3). Ultimately, all plans must be stored as sequences of serial, concurrent or parallel preconditions and actions. It is also possible to store states after each operation. Including a state representation allows the ability to track plan progress, and to check for failures during execution. These advantages do not come without costs. It is easy to store sequential plans with all of their preconditions. Non-linear plans are much harder to store, because of the non-linear graph structure caused by inherent parallelism.

Korf [1987] described the various plan types and how they may be described with graph search theory. His work proved formally that sequential plan steps are preferable, although not always possible.

1.2.4.1 - Sequential Plans

In its most simple form, a sequential plan is a list of operations. A more sophisticated plan also describes the state of the world model after each operation. One such method for doing this is triangle tables [Nilsson, 1980, pp. 282-286]. These tables store the result of each operation in (selected rows of) the column beneath. The rows selected are determined by which subsequent operations the results are preconditions for.

 

Figure 1.1 A Triangle Table

(Adapted from [Nilsson, 1980, pg. 285])

The plan’s progress may be verified by examining the kernel. As shown in Figure 1.1 A Triangle Table, the kernel (outlined in double lines) for STACK(B, C) is a matrix of conditions. If these conditions match the world model, then the plan is progressing normally at STACK(B, C).

Nilsson also mentions the complete expansion of state space in a tree form [1980, pp. 282-284]. Each node becomes an intermediate plan state, and each arc becomes an operation. This approach is both memory intensive and inefficient, but recovery from plan execution failure is easier. An example of this approach applied to a blocks world problem is shown in Figure 1.2 A Search Tree in Plan Space.

 

Figure 1.2 A Search Tree in Plan Space

Larger Arrows indicate path followed by planner (Adapted from [Nilsson, 1980, pg. 283])

1.2.4.2 - Non-Sequential Plans

By treating all plans as sequential, we have assumed that all operations are ordered, and two events may not happen simultaneously. In actuality, many operations are parallel in nature, and therefore it may be desirable to have plans which are concurrent and only partially ordered. The main disadvantages of unordered plans are that progress checking (and error recovery) will be more difficult, and the scheduling of events must still be specified.

An early planner called NOAH [Sacerdoti, 1975, 1977] used a representation called procedural nets. The nets had a starting point at the left hand side, from which plan execution would begin. During execution concurrent paths could branch and rejoin. Preconditions and operations were located at various positions along the paths. The only drawback to this representation is that conditions that were previously set can not be undone. Tate [1977] discussed an approach based on project networks, and claimed that he overcame the problem with procedural nets. These nets are similar to procedural nets except the goals and preconditions are not separated.

Figure 1.3 A Procedural Net (for painting)

(Adapted from [Sacerdoti, 1977, pg. 10])

Tate discussed finding an order for an unordered plan using Operations Research techniques on a project network. DEVISER [Vere, 1983] was able to generate plan representations with non-sequential operations, using an approach based on Tate’s project networks.

1.2.5 Planning Objectives

A real problem rarely has a unique solution. Typically there are either multiple solutions, or none at all. When there are multiple solutions, a value analysis must be performed to find the greatest valued plan. If there are no solutions, goals must be compromised to reach a solution. A diagram by Gevarter [1985] which he derived from the book by Wilensky [1983] is shown below in Figure 1.4 Objective Evaluation.

Figure 1.4 Objective Evaluation

(Adapted from [Gevarter 1985, pg. 71])

Although, this figure illustrates a comprehensive planning approach, planners commonly find the first solution possible, or quit if none is found.