Learning to Improve both Efficiency and Quality of Planning

1 Introduction

A considerable amount of planning and learning re­ search has been devoted to improving planning effi­ ciency, also known as "speedup learning" [Minton, 1989; Leckie and Zuckerman, 1993; Estlin and Mooney, 1996; Kambhampati et al., 1996]. These systems construct domain-specific control rules that enable a planner to find solutions more quickly. Another aim of planning and learning research, which has received much less at­ tention, is to improve the quality of plans produced by a planner [Perez, 1996; Iwamoto, 1994]. In this type of learning, control rules guide the planner towards better solutions. Generating high-quality plans is an essential feature for many real-world planning systems, as is gen­ erating these plans efficiently [Chien et al., 1996]. Im­ proving plan quality and planner efficiency can often be accomplished by using similar learning methods. How­ ever, little research has been done in acquiring control knowledge to improve both these metrics.

·This research was supported by the NASA Graduate Stu­ dent Researchers Program, grant number NGT-51332.

To investigate this issue, we employ the ScoPE 1 learn­ ing system, which uses a combination of machine learn­ ing techniques to acquire control rules for a partial-order planner. SCOPE has previously been shown to signifi­ cantly improve efficiency of a version of the well-known UCPOP planner [Estlin and Mooney, 1996]. SCOPE em­ ploys a flexible learning algorithm that can be trained to focus on different evaluation metrics. The primary focus of previous experiments was to avoid backtracking, and thus, improve planning efficiency. However, by using a particlilar training method, SCOPE can be easily modi­ fied to learn rules that guide the planner towards only "high-quality" solutions.

The remainder of this paper is organized as follows. Section 2 further introduces the issue of plan quality and why it is important. Section 3 describes how ScoPE is used to construct control rules, and in Section 4 we discuss how SCOPE was used to learn rules for improving plan quality. Section 5 presents experimental results that show SCOPE can improve both the quality of plans and planner efficiency. Finally, Section 6 discusses related work, Section 7 presents ideas for future research and Section 8 presents our conclusions.

2 Plan Quality

In many real-world planning systems the quality of a plan may be just as important (if not more) than the time it takes to generate the plan. For instance, it may be vital in a manufacturing domain for a planner to pro­ duce plans with low resource consumption, or with the least number of possible steps. There are a variety of no­ tions about what makes a good plan. Some of the more common quality metrics are listed below:

• The length of the plan (or the total number of steps)
• The execution time of the plan
• The resource consumption required
• The robustness of the plan

1 Search Control Optimization of Planning through Experience Depending on the domain, different quality metrics will have varying importance. In this paper, we focus on im­ proving the first quality metric, minimizing the number of plan steps.

3 The SCOPE Learning System

SCOPE was designed to learn search-control rules for planning decisions that might lead to failure (i.e. might be backtracked upon) . Figure 1 illustrates an example from the logistics transportation domain [Veloso, 1992] where control knowledge could be useful. Here, there are two possible refinement candidates for adding a new action to achieve the goal at-obj(pkg1,city2-airport) . Only the first will actually lead to a solution, since in this domain, only planes can be used to transport packages between cities. For each set of refinement candidates, ScoPE learns control rules in the form of selection rules that define when each refinement should be applied. For example, shown next is a selection rule for the first can­ didate (from Figure 1) which contains several control conditions.

This rule states that unload-airplane (?X, ?Y, ?Z) should be selected to add at-obj (?X, ?Z) only when it is ini­ tially true that object ?X starts at a location which is in a different city than ?Z. Learned control information is incorporated into the planner so that attempts to select an inappropriate refinement will immediately fail.

SCOPE is implemented in Prolog, which provides an excellent framework for learning control rules. Search algorithms can be implemented in Prolog in such a way that allows control information to be easily incorporated in the form of clause-selection rules [Cohen, 1990]. For its base planner, SCOPE uses a version of the UCPOP partial-order planning algorithm which has been reim­ plemented in Prolog. 2 Planning decision points are rep­ resented in the planner as clause-selection problems (i.e.

2 The main difference between our planner and UCPOP is

each refinement candidate is formulated as a separate clause).

By analyzing a set of t~aining examples, SCOPE learns refinement-selection rules which are incorporated into the original planner in the form of clause-selection heuristics. As shown in Figure 2, SCOPE's algorithm has three main phases which are are briefly presented in the next few sections. A more detailed description can be found in [Estlin, 1996].

3.1 Example Analysis

In the example analysis phase, training examples are solved using the original planner and two main out­ puts are produced: a set of selection-decision examples and a set of generalized proof trees. A "selection deci­ sion" is a planning subgoal that was solved by apply­ ing a particular plan refinement, such as adding a new action. Selection-decisions record successful and unsuc­ cessful applications of plan refinements. To collect these decisions, a trace of the planning decision process used to solve each training example is stored in a proof tree. Then, SCOPE uses the proof trees to extract examples of correct and incorrect refinement-selection decisions.

The second output of this phase is a set of generalized proof trees. Standard explanation-based generalization (EBG) [Mitchell et al., 1986; DeJong and Mooney, 1986] techniques are used to generalize each training example proof tree. The goal of this generalization is to remove proof elements that are dependent on the specific exam­ ple facts while maintaining the overall proof structure.

that UCPOP normally employs a best-first search strategy while our Prolog planner operates using a depth-first back­ tracking search. As shown in Section 5, our Prolog planner actually performs better than the standard Lisp implementa­ tion of UCPOP on the sample problem sets used to test the learning algorithm.

find-new-op( ( at-obj(X,Loc) ,Aid) ,Steps,Agenda,unload-airplane(X,P,Loc)) :­ find-in it-state( Steps ,In it), member(at-obj(X,Loc2) , lnit), not(member(same-city(Loc,Loc2),1nit)). member(airport(Loc), lnit). fi nd-exist-op( ( at-truck(T, Loc) ,Aid), Steps,Agend a, in it-state)) :­ find-in it-state( Steps,l nit), member-pred( at-truck(T ,Loc) ,I nit), . . not( member( ( Aid2,drive-truck(T ,Loc, Loc2)) ,Steps) ,Aodo;lAod2).

Generalized proofs provide a background context that explains the success of all correct planning decisions. In­ formation from these trees is used in the next phase to construct control rules.

3.2 Control Rule Induction

The goal of the induction phase is to produce an opera­ tional definition of when it is useful to apply a planning refinement. SCOPE employs a version of the FOIL algo­ rithm (Quinlan, 1990] to learn control rules through in­ duction. FOIL attempts to learn a control definition that is composed of a set of Horn clauses. This definition cov­ ers all of the positive examples of when to apply a refine­ ment, and none of the negatives. The selection-decision examples collected in the example analysis phase pro­ vide the sets of positive and negative examples for each refinement.

Individual clause construction is done by using a general-to-specific hill-climbing search. FOIL adds an­ tecedents to the developing clause one at a time. At each step FOIL evaluates all literals that might be added and selects the one which maximizes an information-based gain heuristic. One drawback to FOIL is that the hill­ climbing search for a good antecedent can easily explode, especially when there are numerous background predi­ cates with large numbers of arguments. 3 SCOPE circum­ vents this search problem by utilizing the generalized proofs of training examples. By examining the proof trees, SCOPE identifies a small set of potential literals that could be added as antecedents to the current clause definition. ScoPE also considers several other types of control rule antecedents during induction. These include negated proof tree literals, determinate literals [Muggle­ ton, 1992], variable codesignation constraints, and rela­ tional cliches [Silverstein and Pazzani, 1991].

3.3 Program Specialization Phase

Once refinement selection rules have been learned, they are passed to the program specialization phase which adds this control information into the original planner. The basic approach is to guard each planning re­ finement with the selection information. This forces a refinement application to fail quickly on planning subgoals to which the refinement should not be ap­ plied. Figure 3 shows two learned rules for the logis­ tics transportation domain. The first rule selects the new action unload-airplane(X,P ,Loc) to achieve the goal at-obj (X,Loc) when X is found to be initially located in a different city than the goal location and when the goal lo­ cation is an airport. The second rule uses the initial state to achieve the goal at-truck(T ,Loc) if there does not ex­ ist another action in the plan drive-truck (T, Loc, Loc2) which moves the truck to a new location.

3 When selecting each new clause antecedent, FOIL tries all possible variable combinations for all predicates before making its choice. . This search grows exponentially as the number of predicate arguments increases.

4 Focusing SCOPE on Plan Quality

By learning rules which avoid search paths that lead to backtracking, ScoPE has been shown to significantly im­ proving the efficiency of a planner [Estlin and Mooney, 1996]. However, by modifying the method used to col­ lect training data, it can easily improve other planning metrics as well.

In order to improve plan quality, we trained ScoPE on only high-quality solutions. To improve plan lengths, ScoPE was given the shortest solution plans for all train­ ing problems. This causes SCOPE to collect positive and negative examples of when to apply a plan refinement based on finding the optimal plan. Thus, it learns rules that not only avoid dead-end paths, but also that avoid paths that lead to sub-optimal solutions.

In order to train ScoPE on high-quality solutions, the search method of depth-first iterative deepening (DFID) [Korf, 1985] was employed to solve the training prob­ lems. This method ensured that the shortest possible solutions were always returned. To improve upon other quality metrics, different training methods may have to be employed that return optimal (or near-optimal) solu­ tions based on other evaluation functions.

5 Evaluation

5.1 Experimental Setup

The logistics transportation domain [Veloso, 1992] was used to evaluate ScoPE's ability to improve both qual­ ity and efficiency. In this domain, packages must be delivered to different locations in several cities. Trucks are used to transport packages within a city, and planes are used to transport packages between different cities. Training and test problems were produced by generat­ ing random initial and final states. Problems contained one and two packages, two trucks and two planes, which were distributed among two cities.

As explained above, depth-first iterative deepening was used to solve the training problems. SCOPE was trained on separate example sets of increasing size. Five trials were run for each training set size, after which re­ sults were averaged.

For each trial, a test set of 100 independently gener­ ated problems was used to evaluate performance. No time limit was used during testing, but a depth bound was given that ensured all test problems could be solved. For comparison purposes we used several different search methods to solve the test examples. These include depth-first search, depth-first search + learned control information, depth-first iterative deepening search, and best-first search. The best-first search tests were done using the standard Lisp implementation of UCPOP [Bar­ rett et al., 1995]. To utilize all of these search methods, only test problems with solutions under a certain length were used. This ensured all problems could be solved by all methods in a reasonable amount of time.

5.2 Experimental Results

Figure 4 shows improvement in planning efficiency. The times shown represent the number of seconds required to solve the problems in the test sets after SCOPE was trained on a given number of examples. The best per­ formance occurred when the planner utilized the learned control information. In these tests, SCOPE was able to produce a new planner that was an average of 28 times faster than the original depth-first planner. Depth-first iterative deepening performs better than depth-first but not nearly as well as ScoPE. Best-first search, on the other hand, performed worse than depth-first. 4

Figure 5 represents how SCOPE improved final plan quality. The lengths shown in the graph represent the average solution lengths returned for the test problems. The depth-first iterative deepening line shows the average length of all optimal solutions. In this experiment, SCOPE was able to produce a new planner that returned optimal solutions, and returned significantly shorter so­ lutions than those returned by depth-first alone. Best­ first search also generated near-optimal solutions.

4 Note that the best-first tests were done using the Lisp implementation of UCPOP. Thus this result could be par­ tially due to implementation differences between Prolog and Lisp.

Overall, these results indicate that is it possible to learn control rules that improve both planning efficiency and plan quality. By using depth-first iterative deepen­ ing to solve the training problems, ScOPE can be trained on optimal solutions. ScoPE can then learn control rules that not only help the planner find solutions quickly, but that also lead to high quality solutions.

5.3 Scalability

One other set of experiments was performed to test how ScoPE performed on harder problems. Using depth-first iterative deepening, SCOPE was trained on 100 training problems from the same distribution explained above. Four different test sets of increasing complexity were then used to evaluate SCOPE's performance. During testing, a time limit of 500 seconds was used. No lim­ its on solutions length were imposed on test problems in these experiments, however, a depth bound was used that ensured all test problems could be solved. Five trials were run for these tests, after which results were averaged.

The results are shown in Table 1. The first two columns of the table show the percentage of test prob­ lems that could be solved within the time limit (using depth-first search) before and after learning. The next set of columns report the planning time required. The last two sets of columns contain results on plan quality. In the first set, we show the average solution lengths of all solved test problems before and after learning. In the last set, we show the average solution lengths (and opti­ mal solution lengths) for problems that could be solved by the original planner (without rules). This last set of columns show any improvements made in solution length by the learned rules.

For all four test sets, SCOPE was able to improve plan­ ning efficiency, and when possible, increase the percent­ age of problems solved. For instance, on the first set of problems (containing 1 goal) , SCOPE was able to create a new planner that was an average of 800 times faster than the original. Unfortunately, it was difficult to gather data on whether plan quality was improved in all test sets. For many examples, the original planner could not find a solution under the time limit, and thus we were of­ ten not able to compare solution lengths. (Additionally, neither DFID or best-first search could find solutions for any problems in the two larger test sets.) For the first test set, SCOPE was able to significantly improve final solution quality and always generated optimal solutions. For the second test set, only 18 problems could originally be solved under the time limit and these solutions were already at optimal length.

6 Related Work

Most systems that learn control knowledge for planning have been directed at improving planning efficiency. In this regard, the most closely, related system to ScoPE is UCPOP+EBL [Kambhampati et al., 1996]. In con­ trast to SCOPE, which uses a combination of EBL and induction, UCPOP+EBL uses a purely explanation­ based approach to construct control rules in response to planning failures. This system has been shown to improve planning efficiency, however, SCOPE has out­ performed UCPOP+EBL in previous experiments us­ ing the blocksworld domain [Estlin and Mooney, 1996). Most other research on learning control rules to im­ prove planning efficiency has been conducted on lin­ ear, state-based planners. [Minton, 1989; Etzioni, 1993; Leckie and Zuckerman, 1993; Bhatnagar and Mostow, 1994].

Very little research has been done in learning rules that improve plan quality. One learning mechanism for improving the quality of plans was introduced by [Perez, 1996) and is built on top of the PRODIGY nonlinear planner [Carbonell and et al., 1992). It uses EBL and an input quality evaluation function to explain why a higher quality solution is better than a lower quality one and converts this information into control knowledge. This method has been successfully used to improve solu­ tion quality in the process planning domain [Gil, 1991). In contrast, SCOPE uses a combination of learning tech­ niques to learn control rules that cover good planning decisions and rule out bad ones. Also, SCOPE has been focused on improving both quality and efficiency.

Another learning method for improving quality, which was also runs on the PRODIGY nonlinear planner, was developed by [Iwamoto, 1994) . This technique uses EBL to acquire control rules for near-optimal solutions in LSI design. This method is similar to the one employed by Perez, however it does not make use of the quality eval­ uation function to build the explanation.

Most other work in plan quality has concentrated on adding features to the plan algorithm itself that prefer least-cost plans [Hayes, 1990; Williamson and Hanks, 1994) or on examining goal interactions and how they relate to solution quality [Wilensky, 1983; Foulser et al., 1992).

7 Future Directions

There are several issues we hope to address in future research. First, we would like to experiment with differ­ ent types of quality metrics. We are currently working on implementing a version of the logistics domain where actions have different execution costs. In this way, we can measure plan quality in terms of plan execution cost as well as plan length. We would also like to experiment with the Truckworld domain utilized by [Williamson and Hanks, 1994) where resource consumption is important, and the process planning domain [Gil, 1991), where a number of quality metrics would be applicable.

Einally, we would like to devise a method for incremen­ tal learning and training for ScoPE. ScoPE could use learned control information for smaller problems to help generate training examples for more complex problems. This type of incremental approach could help ScoPE scale up more effectively to solve harder problems.

8 Conclusion

This paper describes experimental results from learning control knowledge to improve both planning efficiency and plan quality. Most planning and learning research has concentrated on improving efficiency. Another im­ portant learning goal is to improve the quality of the final solution. However, little research has been done in learning rules that improve both these metrics. In this paper, we have presented results utilizing the SCOPE learning system that show both of these metrics can be improved simultaneously by focusing the learning system on avoiding both dead-end paths and paths that lead to sub-optimal solutions.