Planning with Primary Effects: Experiments and Analysis

1 Introduction

Planning with primary effects is an effective approach to reducing search. The underlying idea of this approach is to select primary effects among the effects of each opera­ tor and to use an operator only when we need to achieve one of its primary effects. A primary-effect restricted planner never inserts an operator into a plan in order to achieve any of the side effects of the operator. For exam­ ple, the primary effect oflighting a fireplace is to heat the house. If we have lamps in the house, we view illumina­ tion of the room as a side effect of using the fireplace: we would not use the fireplace just to illuminate the room.

The advantages of using primary effects in planning are well-known. If a planner considers only operators whose primary effects match a current goal and ignores operators with matching side effects, the branching fac­ tor of search can be reduced, which results in an ex­ ponential reduction of running time. For this reason,

·The first author is supported by the Wright Laboratory, Aeronautical Systems Center, Air Force Materiel Command, USAF, and the Advanced Research Projects Agency (ARPA) under grant number F33615-93-1-1330. The second author is supported in part by grants from the Nat ural Sciences and Engineering Research Council of Canada and ITRC.

Qiang Yang*

Computer Science, University of Waterloo Waterloo, Ontario, Canada N213G 1 qyang@logos. uwater loo.ca

primary effects are used by many implemented planning systems, such as SIPE [Wilkins, 1988], PRODIGY [Car­ bonell et al., 1990], and ABTWEAK [Yang and Tenenberg, 1990].

In our previous work, we formalized the notion of plan­ ning with primary effects and developed two algorithms, MARGIE [Fink and Yang, 1992] and Prim-TWEAK [Fink and Yang, 1993], for automatically selecting primary ef­ fects of operators.

The purpose of this paper is to present empirical and analytical evaluation of the efficiency of planning with primary effects and identify the important factors that determine the effectiveness of primary effects in reducing planning time. We describe experiments on automat­ ically selecting and using primary effects in planning; the experiments demonstrate that the use of primary ef­ fects may lead to an exponential efficiency improvement. We then analytically explain the efficiency improvements observed in the experiments. We also describe an appli­ cation of our analysis to predicting the performance of a planner for a given selection of primary effects. This predictive analysis enables us to decide whether the use of primary effects selected by the user improves the effi­ ciency of planning.

2 Planning with Primary Effects

In this section, we describe the use of primary effects in planning, outline an algorithm for automatically se­ lecting primary effects of operators, and discuss possible problems of planning with primary effects and a method for avoiding these problems.

2.1 Motivating Example

Consider a planning domain with a robot, four rooms, and a box (see Table 1). The robot may go between two rooms connected by a door, and it may carry the box. If the robot has an ax, it can break through the wall between two rooms to create a new door.

To describe a current state of the domain, we have to specify the location of the robot and the box, list the pairs of rooms connected by doors, and indicate whether the robot has an ax. We may describe states of the domain with four predicates, robot-in( x ), box-in( x ), door(x , y), and have-ax. Literals describing a current state may be obtained from these predicates by substi­ tuting specific room numbers for x and y. For example, the literal robot-in(!) means that the robot is in Room 1, box-in(l) means that the box is in Room 1, and door(1,2) means that Rooms 1 and 2 are connected by a doorway.

The operations performed by the robot, such as mov­ ing between rooms and carrying the box, are called op­ erators. We describe an operator by a set of precondi­ tions and a set of effects [Fikes and Nilsson, 1971) (see Table 1). The preconditions of an operator are the con­ ditions that must hold before the execution of the oper­ ator and the effects are the results of the execution. If a literal l is an effect of some operator, we say that this operator achieves l.

A plan is a sequence of operators that achieves some desired goal. For example, suppose that the initial state is as shown in Table 1, and we wish to bring the robot to Room 3 and the box to Room 2; this goal may be achieved by the plan (carry-box(1,2), go(2,3)).

In this paper, we measure the quality of a plan by the number of operators in the plan: the fewer operators, the better the plan. The number of operators is called the size of the plan. An optimal plan is a plan of the smallest size that achieves the goal. We may readily extend all our results to more robust definitions of a plan quality [Fink and Yang, 1994); for example, we may assign a real­ valued cost to each operator in a domain and measure the quality of a plan by the total cost of its operators.

If an operator has several effects, we may choose cer­ tain "important" effects among them and insert the op­ erator into a plan only for the sake of these effects. The chosen important effects are called primary and the other effects are called side effects. A planner that adds new operators to a plan only for achieving their primary ef­ fects is called a primary-effect restricted planner.

For example, consider the following selection of pri­ mary effects:

Suppose that the initial state is as shown in Table 1 and the robot must move into Room 3. The robot may achieve this goal by going to Room 3 (through Room 2) or by carrying the box to Room 3; if the robot has an ax, it may also achieve the goal by breaking through the wall between Rooms 1 and 3. Since robot-in is not a primary effect of the operators carry-box and break, the planner will not consider the use of either of these operators, and it will find the plan (go(1,2), go(2,3)).

2.2 Selecting Primary Effects

The utility of planning with primary effects depends cru­ cially on a "good" selection of primary effects. An im­ proper selection may result in the loss of completeness of planning, which happens when a primary-effect re­ stricted planner cannot find a plan for a solvable plan­ ning problem. For example, if we use the primary effects chosen in the end of Section 2.1, a planner cannot find a plan for removing the box from Room 4, since -.box-in is not a primary effect of any operator.

In [Fink and Yang, 1992) we showed that enforcing the following two restrictions usually (although not always) results in preserving completeness of planning:

1. every achievable literal must be a primary effect of some operator,
2. and every operator must have a primary effect .

Restriction 1 guarantees that, if a literal can be achieved at all, then it can be achieved as a primary effect of some operator, and Restriction 2 ensures that the planner can use all operators of the domain. We use the following simple algorithm for selecting primary effects according to the two restrictions:

1. For every literal l in the domain, if there are operators that achieve l,
2. then make l a primary effect of one of these operators.
3. For every operator that does not have primary effects, make one of its effects primary.

Note that there may be several different ways of select­ ing "one of the operators" at Step 1 of the algorithm and "one of the effects" at Step 2; we presented heuris­ tics for making these choices in [Fink and Yang, 1993) and [Fink and Yang, 1994). The algorithm would select the following primary effects in the robot domain:

2.3 Learning Additional Primary Effects

While the use of primary effects chosen by the above al­ gorithm may improve the efficiency of planning, it can also cause two serious problems. First, the resulting se­ lection of primary effects is not immune to the loss of completeness. Second, planning with the selected pri­ mary effects may result in finding a nonoptimal plan. For example, if the robot has an ax, the goal of mov­ ing the robot from Room 1 to Room 4 may be achieved by the operator break(1,4); however, a primary-effect re­ stricted planner will not consider this possibility, since the new position of the robot is not a primary effect of break. Instead, the planner will find the plan (go(1,2), go(2,3), go(3,4)), with a size of 3. In this example, the shortest primary-effect restricted plan is 3 times longer than the optimal plan. We say that 3 is the plan-size increase of the planning problem.

To address the problem of completeness and optimal­ ity, we present an algorithm that tests whether a given choice of primary effects guarantees the completeness of planning and estimates the maximal plan-size increase.

Planning with primary effects is complete if a primary­ effect restricted planner can find a plan for every solvable problem. Completeness is lost when we can achieve a goal as a side effect of some operator, but cannot find a primary-effect restricted plan that achieves this goal. To guarantee completeness, we must ensure that such a situation cannot happen; that is, we have to make sure that, for every operator, there is always a primary-effect restricted plan that achieves its side effects.

Now suppose that a somewhat stronger condition holds: for some constant C, every operator Op can always be replaced by a primary-effect restricted plan whose size is at most C. Then, the plan-size increase due to the use of primary effects is never larger than C. Thus, this stronger condition not only ensures complete­ ness, but also guarantees a limited plan-size increase for all possible problems in a planning domain. Below, we summarize our observations:

Completeness and Limited Plan-Size Increase: Suppose that, for every operator Op and every initial state S satisfying the preconditions of Op, there ex­ ists a primary-effect restricted plan P with the initial state S such that

• ( 1) P achieves the side effects of Op
• and P contains at most C operators.

Then, for every solvable problem in the planning do­ main, there is a primary-effect restricted solution plan at most C times larger than an optimal plan.

A formal proof and discussion of this observation can be found in [Fink and Yang, 1994]. We use this result to de­ sign a learning algorithm that adds new primary effects to a selection to make sure that primary-effect restricted planning is complete and that the plan-size increase is within the user-specified bound. For each operator Op in the domain, the learner generates several states that satisfy the preconditions of Op and checks whether the side effects of Op can be achieved in all these states. If not, the algorithm "promotes" some side effects of Op to primary effects.

Let C be the maximal allowed plan-size increase, spec­ ified by the user. The learning algorithm can be infor­ mally described as follows:

For every operator Op, repeat "several" times:

1. Pick at random a state S

that satisfies the preconditions of Op.

1. Try to find a primary-effect restricted plan P such that o P achieves the side effects of Op from the state S, o and P contains at most C operators.
2. If such a plan is not found,

make one of the side effects of Op be a primary effect .

In [Fink and Yang, 1993] we presented a formal descrip­ tion of this algorithm, described methods for generat­ ing random legal states satisfying the preconditions of a given operator, and estimated the number of differ­ ent states that must be considered for every operator to ensure a high probability of completeness.

As an example, suppose that we apply this learning al­ gorithm to the robot domain, with primary effects shown in the end of Section 2.2 and C = 2. The learner is likely to notice that, if the robot has an ax, the ef­ fect robot-in(4) of the operator break(1,4) cannot be effi­ ciently achieved by a primary-effect restricted plan. Af­ ter noticing it, the algorithm will select an additional primary effect of the break operator, producing the fol­ lowing selection:

3 Search Reduction: Experiments

We now present a series of experiments on planning with primary effects; the experiments demonstrate that the use of primary effects may drastically improve the ef­ ficiency of planning. We · used the ABTWEAK planning system [Yang and Tenenberg, 1990] in the experiments; the primary effects were selected automatically by the learning algorithm outlined in Section 2.3.

3.1 Experiments in a Robot Domain

We first describe experiments in a robot domain, where the robot can move between rooms, open and close doors, carry boxes, and climb tables (with or without boxes). We ran our learning algorithm to select primary effects in this domain, with the plan-size increase C = 1; the time of learning primary effects was 2980 CPU msec. In Table 2, we show the performance of the ABTWEAK plan­ ner without primary effects ("w/o") and with the use of the learned primary effects ( "w / prim") when achieving different goals. The initial state in all cases is as shown in the picture, with both doors being closed. For all prob­ lems, the solution found with the use of primary effects was the same as the solution found without primary ef­ fects. As can be seen from the table, the use of primary effects considerably improves the efficiency of ABTWEAK.

3.2 Experiments in Artificial Domains

We next describe a series of experiments in artificial do­ mains, similar to the domains used in [Barrett and Weld, 1992]. These domains have a number of features that can be varied independently, which enables us to per­ form controlled experiments.

We define a problem by m initial-state literals, init1, .. , initm, and m goal literals, goal1, .. , goalm. We use m operators, Op 1 , .. , 0Pm· Each operator Op; has the single precondition in it; . Op; deletes the literal init;_1 and establishes the goal literals goal; mod m· goal(i+1) mod m· .. , goal(i+k-1) mod m · Thus, each operator has (k + 1) effects: one negative effect and k positive effects. The artificial domains allow us to vary the following problem features:

Goal Size The goal size is the number of goal literals, m. The size of an optimal solution plan changes in proportion to the number of goal literals.

Effect Overlap The effect overlap, k , is the average number of operators establishing the same literal.

We vary these two features in the controlled experiments. Although the domains are artificial, they demonstrate some important characteristics of real-world problems: first , if the goal size increases, the size of the optimal solution plan also increases; second, if the effect overlap increases, then every operator can achieve more goal lit­ erals and the size of the solution decreases.

Varying solution sizes.

First , we demonstrate that the savings in running time grow exponentially with the size of an optimal solution plan. We use domains with effect overlaps k = 2 and k = 4. The results of the experiments are presented in Figure 1: we show the running times of the ABTWEAK planner without primary effects ( "w / o prim") and with the use of the learned primary effects ("with prim") for problems with different optimal-solution sizes; every point on each figure is the average of five different prob­ lems. (Note that the time scale is logarithmic.) These graphs show that the savings in planning time increase exponentially with an increase in the optimal-solution size; a significant improvement is achieved in both cases.

Varying effect overlap.

Next, we consider efficiency improvement for different values of the effect overlap. Recall that the effect overlap k is defined as the average number of operators achiev­ ing the same literal. We vary the effect overlap k from 2 to 6. (If the effect overlap is 1, then all effects must be selected as primary, and primary-effect restricted plan­ ning is equivalent to planning without primary effects.) In Figure 2, we present the running times of ABTWEAK without primary effects ( "w jo prim") and with the use of learned primary effects ("with prim" ) for every effect overlap. The graphs show that the use of primary effects improves performance for all effect overlaps, even though the time savings are smaller for large overlaps.

Effect overlap k equals 4

Figure 1: Dependency of the planning time on the size of an optimal solution plan

4 Analysis of the Search Reduction

We next present an analytical comparison of planning ef­ ficiency with and without the use of primary effects. The purpose of the analysis is to ( 1) explain the exponential efficiency improvement observed in the experiments and (2) identify the factors that determine the efficiency of planning with primary effects. The analysis is an approx­ imation based on several simplifying assumptions about properties of planning domains.

Assumptions of the analysis.

When searching for a solution to a planning problem, a planning algorithm expands a search space, whose nodes correspond to intermediate (possibly incorrect) plans found in the process of planning. The planning time is proportional to the number of nodes in the ex­ panded search space. Total-order planners, such as AB­ STRIPS and PRODIGY, create a new node by inserting a new operator into a plan. Partial-order planners, such as TWEAK and SNLP, create a node by inserting a new operator or by imposing a constraint on the order of exe­ cuting old operators. For simplicity, we assume that the planner expands nodes breadth first.

When inserting a new operator to achieve some literal I, we may use any operator whose primary effect is I. To estimate the number of the matching operators, we assume that, for all literals I, the number of operators achieving I as a primary effect is the same. We define Pas P =Lop #(Prim-Efj{Op)); that is, we count the number of primary effects, #(Prim-Eff( Op )), of each op­ erator Op and define P as the sum of these numbers for all operators. The number of different achievable liter­ als in the domain is denoted by L. Then, the number of operators achieving a particular literal l as a primary effect is estimated as f.

After inserting some operator into a partial-order plan, we may have to impose new constraints on the order of operators in the plan. Let b denote the number of differ­ ent ways of imposing these ordering constraints. Thus, we can create bf different plans by adding an opera­ tor that achieves l and imposing necessary ordering con­ straints. A breadth-first planner considers all these plans and, therefore, the total number of new nodes created af­ ter inserting an operator is bf . This value represents the branching factor of inserting an operator into a primary­ effect restricted plan.

Similarly, we assume that the number of all operators achieving l is the same for all literals and define E by E = L. Op #(Effects( Op)), where #(Effects( Op)) is the number of all effects of Op. Then, the branching factor of inserting an operator by a planner that does not use primary effects is bf. (The effect overlap k, defined in the last section, equals f.)

The notation used in the analysis is summarized in Table 3 (the last three symbols listed in Table 3 are in­ troduced in the next few paragraphs) .

Explaining exponential efficiency improvement.

First , we consider planning without primary effects. As­ sume that an optimal plan that solves a problem contains n operators. The branching factor of inserting an opera tor is bf; thus, the number of nodes with one-operator plans is bf, the number of nodes with two-operator plans is (bf ) 2 , etc. The total number of nodes is

If the maximal plan-size increase is C, then the number of operators in the solution found by a primary-effect re­ stricted planner is at most C · n . Since the branching fac­ tor of inserting an operator in primary-effect restricted planning is bf, the number of nodes in the search space of a primary-effect restricted planner is at most

Let R denote the ratio of running times of planning with and without primary effects. Since the running time is proportional to the number of nodes in the search space, R is determined by the ratio of the search-space sizes:

Let us denote the base of the power in Formula 3 by r:

Then, Formula 3 may be rewritten as R = 0( rn) . This expression explains the experimental results: it demon­ strates that the savings in running time grow exponen­ tially with the size of an optimal plan, n .

The value of r in the robot domain (Section 3.1) is 0.9 and, thus, the ratio R of running times of planning with and without primary effects is approximately 0.9n, where n is the size of an optimal solution; the value of r in the artificial domains Section 3.2 varies from 0.6 to 0.8.

Factors that determine the search reduction.

The use of primary effects improves the efficiency of plan­ ning only if r < 1, which means that fb . ( P£b)C < 1. Solving this inequality with respect to the plan-size in­ crease C, we conclude that primary effects improve per­ formance when

We can draw some other conclusions from the expres­ sion for r (Formula 4). The base of the power in this expression, PLb, is the branching factor of the primary­ effect restricted search and, therefore, it is at least 1. Since r = fb · ( PLb )c, we conclude that r increases with an increase of C, which implies that the time savings in­ crease with a decrease of the plan-size increase C . Also, r increases with an increase of P and, therefore, the time savings increase with a decrease of the number of pri­ mary effects P .

However, there is a tradeoff between the number of pri­ mary effects P and the plan-size increase C: as we select more primary effects, P increases, whereas C decreases. To minimize r, we have to strike the right balance be­ tween C and P, which may be done by a modified version of the learner outlined in Section 2.3; we described this modified version in [Fink and Yang, 1994].

5 Predicting Savings in Planning Time

We next describe an application of the analysis to de­ termining whether the use of a given selection of pri­ mary effects improves the efficiency of planning. The key component of this predictive analysis is estimating the plan-size increase C for given primary effects.

To describe our method for estimating the plan-size in­ crease, we introduce the notion of a primary-effect cover of an operator. We say that operators Op 1 , .. , Opn form a primary-effect cover of an operator Op if every side effect of Op is a primary effect of at least one of the operators Op 1 , .. , Opn.

To estimate the plan-size increase, we generate a primary-effect cover with as few operators as possible for every operator Op in the planning domain. We use the number of operators in the primary-effect cover of Op as an estimate of the size of a primary-effect restricted plan P that achieves the side effects of Op.

We use a greedy algorithm to generate a small primary-effect cover of every operator in the domain. The algorithm for finding a cover of a given operator, Op, may be informally described as follows:

Set Uncovered-Eff = Side -Eff(Op) and Cover= 0. While Uncovered-Eff is not empty, repeat:

1. Select an operator whose primary effects cover the maximal number of predicates in Uncovered-Eff.
2. Add this operator to Cover.
3. Remove newly covered predicates from Uncovered-Eff.

After generating a cover of every operator in the planning domain, we count the number of operators, #(Cover( Op)), in the cover of every operator Op; we use the maximum of these numbers as an estimate of C:

We substitute this estimate of C into Formula 5 to determine whether the use of primary effects improves the efficiency of planning. We may also use Formula 3 to estimate the savings in planning time.

For example, suppose that we apply this predictive analysis to the robot domain i"n Table 1 (Section 2.1), with primary effects shown in the end of Section 2.3. The cover size of every operator in this domain is 0 or 1 and, thus, we estimate the plan-size increase as C ~ 1. We next note that the total number of primary effects of operators in this domain is P = 6 and the total number of all effects is E = 9. Substituting these values into Formula 5, we find out that the inequality of Formula 5 is satisfied and, therefore, the use of primary effects im­ proves the efficiency of planning.

As another example, consider a fireplace domain, men­ tioned in Section 1. We show a formal description of this domain in Table 4, where x can be substituted with dif­ ferent rooms. In this domain, P = 2, E = 3, and the cost increase is estimated as C ~ 1. Using Formula 5, we again conclude that primary effects improve efficiency.

6 Conclusions

We have presented an empirical and analytical eval­ uation of planning with primary effects and demon­ strated that the use of primary effects considerably

·

reduces the planning time, but an improper selection of primary effects may lead to generating nonoptimal plans and increasing the planning time. The crucial factor is the plan-size increase C, which determines the optimality of plans based on primary effects and the ef­ ficiency of planning.

The experimental and analytical results show that good selections of primary effects result in considerable efficiency improvement and that the savings in planning time grow exponentially with the problem complexity.

Acknowledgements

The authors would like to thank Manuela Veloso, Steven Minton, Yury Smirnov, Alicia Perez, Alissa Kaplounova, Constantine Domashnev, and Robert Monroe for helpful comments and discussions.