A Historical Review of Artificial Intelligence Planning
One of the fundamental skills of intelligence is planning. Generally, planning is described as finding sequences of actions to satisfy one or more goals. Despite its importance, the process of planning is not well understood, and as a result is underdefined. This has lead to a number of attempts to mimic the planning process with computer based experiments. These Artificial Intelligence planners use various algorithms to approach a fundamental set of planning problems.
By their nature, planning problems are defined using goal states. If there is a single goal, the problem is often simple. Planning for multiple goals is also simple if the goals are completely independent. Some goals must be satisfied in a particular order; this occurs when they are independent but ordered. The most complex case arises when a number of goals must be satisfied simultaneously (this is non-linear planning; all other cases are linear).
To move between a start and goal state, operators are applied. The choices and orders of operators are both major concerns. A great deal of work has been done for selecting operators and choosing their order, but problems of complexity still tend to overwhelm most planning methods.
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.
2.1 Representation of Problem Space
The representation of problem space is primarily split into two main subjects. 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 introduces potential problems when backtracking failed plans.
A list of conditions (predicates) are stored in a list. As conditions in the world change, conditions are added and removed from the list.
2.1.2 The Solution (Plan) Model
Operators are applied which 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.
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.
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.
The representation of plans is important (we will avoid the subject of planning until section 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.
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 - A Triangle Table [Nilsson, 1980, pg. 285]
The plan’s progress may be verified by examining the kernel. As shown in Figure 1, 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 2.
Figure 2 - A Search Tree in Plan Space [Nilsson, 1980, pg. 283]
By treating all plans as sequential, we have assume 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 3 - A Procedural Net (for painting) [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.
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 4.
Figure 4 - Objective Evaluation [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.
Early planners used structured environments that could result in a single plan. Later planners started to deal with the complexity of real world problems. This section discusses a number of approaches to planning, but first, an outline of planning issues is covered.
Exhaustive solutions to planning problems are quite infeasible for any large problem. For example, the large search tree for the simple blocks world problem makes this obvious in Figure 2. Thus, approaches have been formulated to exploit the nature of the planing process, and prune the search tree.
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. This is the most common method used in planning systems.
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.
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,
• the world models are limited to the problems only,
• operations are concurrent (not parallel).
These factors tend to simplify search space. But, even when searching the simplified problem spaces, there are a number of arbitrary decisions which 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].
The complexity of planning is related to the number of viable plans in plan space. Alternate plans can be created by unordered operators, and equivalent operators (they cause branches in the plan search space). A number of approaches have been developed to deal with the complexity issue. In general, these methods focus on dividing or constraining the search, so that the problem becomes tractable.
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 and therefore 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 process 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.
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 which can detect known problem patterns, and fix them. Afterwards, the plan was simulated, and any existing errors were found. The problems which 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 continues until the plan is error free.
Sussman’s examination of this method has become famous 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.
Waldinger [1977] proposed a planner which 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.
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).
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.
3.2.2.2 NOAH, NONLIN and DEVISER
The procedural nets mentioned earlier are important to NOAH [Sacerdoti, 1975, 1977]. If the reader refers to Figure 3 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.
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 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].
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.
The literature makes it obvious that work needs to be done in planning. In particular, planners need to be developed which will deal with complex problems, which have process costs. It is the author’s opinion that as existing planners are applied to more applications, the existing planning techniques will be refined to meet the needs of the real world problems. A few features are listed below which would be desired in a planning system.
• Be able to deal with linear and non-linear plans.
• Produce a plan in a shorter time with a slightly higher cost.
• Produce plans with low costs, having greater computation time.
• Deal with plans involving millions of steps.
• Deal with equivalent operators.
• Be able to backtrack in the event of plan execution failures.
• Be able to perform inductive and deductive reasoning.
• Deal with probabilistic events.
The hierarchical planning approach has performed well on many of these points, suggesting that is an excellent method to consider for future planning research and application.
Cohen, P.R., and Feigenbaum, E.A., 1982, The Handbook of Artificial Intelligence, William Kaufmann, Inc., Vol. 3, pp. 523-562.
Gevarter, W.B., 1985, Intelligent Machines: An Introductory Perspective of Artificial Intelligence and Robotics, Prentice Hall, Inc., pp. 67-81
Green, C., 1969, “Application of Theorem Proving to Problem Solving”, IJCAI, 1969.
Korf, R.E., 1987, “Planning as Search: A Quantitative Approach”, Artificial Intelligence, pp. 65-88.
Nilsson, N.J., 1980, Principles of Artificial Intelligence, Tioga Publishing Co., pp. 282-287.
Rich, E., 1983, Artificial Intelligence, McGraw-Hill Book Company, pp. 247-277.
Sacerdoti, E., 1975, “The Nonlinear Nature of Plans”, International Joint Conference on Artificial Intelligence, pp. 206-214.
Sacerdoti, E., 1977, A Structure for Plans and Behavior, Elsevier North-Holland Inc.
Stefik, M., 1981a, “Planning with Constraints (MOLGEN: Part 1)”, Artificial Intelligence, pp. 111-140.
Stefik, M., 1981b, “Planning and Meta-Planning (MOLGEN: Part 2)”, Artificial Intelligence, pp. 141-170.
Sussman, G.J., 1974, “The Virtuous Nature of Bugs”, Proceedings of the AISB Summer Conference, pp. 224-237.
Tate, A., 1977, “Generating Project Networks”, IJCAI, pp. 888-893
Vere, S.A., 1983, “Planning in Time: Windows and Durations for Activities and Goals”, IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-5, No.3, pp. 246-267.
Waldinger, R., 1977, “Achieving Several Goals Simultaneously”, Machine Intelligence.
Wilensky, R., 1983, Planning and Understanding, Addison-Wesley Publishing Co.