2 Preliminaries

Traditionally, AI planning (in state space) deals with the problem of finding a sequence of actions transforming the world from some initial state to a desired state. State s is a set of predicates that are true in s. Action a is a 3-tuple (p(a), e ⁻(a), e ⁺(a)) of sets of predicates such that p(a) is a set of predicates representing the precondition of action a, e ⁻(a) is a set of negative effects of action a, e ⁺(a) is a set of positive effects of action a. Action a is applicable to state s if p(a) . If action a is applicable to state s, then new state s′ obtained after applying action a is s′ = (s\e ⁻(a)) ∪ e ⁺(a). A planning domain is represented by a set of states and a set of actions. A planning problem is represented by a planning domain, an initial state and a set of goal predicates. A plan is an ordered sequence of actions that lead from the initial state to any goal state containing all of the goal predicates. For a deeper insight in this area, see Ghallab et al. (Reference Ghallab, Nau and Traverso2004).

In this paper, we consider the classical representation of planing problems. This representation allows the definition of planning operators, in which actions are their grounded instances. Our approach supports the Typed STRIPS representation of PDDL (Planning Domain Definition Language).

3 Related works

Macro-operators (macro-actions) represent sequences of primitive operators (actions), but behave as common planning operators (actions). The advantage of using macro-operators is clear—shorter plans are explored to find a solution. However, macro-operators usually have much more instances than primitive operators, which leads to an increased branching factor for search.

One of the oldest approaches, STRIPS (Fikes & Nilsson, Reference Fikes and Nilsson1971), generates macro-actions from all subsequences of plans. It leads to plenty of useless macro-actions. REFLECT (Dawson & Siklóssy, Reference Dawson and Siklóssy1977) builds macro-operators from pairs of primitive operators that are applied successively and share at least one argument. In this case, macro-operators are learned directly from a domain analysis. However, it may lead to the generation of useless macro-operators. FM (McCluskey, Reference McCluskey1987) follows the ideas used by STRIPS, but instead of STRIPS, FM compiles learned sequences of operators into one single operator representing the whole sequence of primitive ones. In addition, FM learns b-chunks that help it with instantiating of macro-actions. Even though FM gained a significant improvement against STRIPS, still it produced many useless and too complex macro-operators. MORRIS (Minton, Reference Minton1985) learns macro-operators for STRIPS from parts of plans appearing frequently or being potentially useful (but having low priority). Macro Problem Solver (MPS), presented in Korf (Reference Korf1985), learns macro-actions only for particular goals. It needs different macro-actions when the problem instances scale or goals are different. MACLEARN (Iba, Reference Iba1989) generates macro-actions that can ‘traverse’ from one peak of a particular heuristic function to another peak. A domain-dependently oriented work (Iba, Reference Iba1985) discusses the usability of macro-operators in puzzle worlds (for instance, Peg Solitaire).

One of the state-of-the-art approaches, MARVIN (Coles & Smith, Reference Coles and Smith2007; Coles et al., Reference Coles, Fox and Smith2007) learns macro-operators online from action sequences that help FF-based planners to escape plateaus. It also learns macro-operators from plans of reduced versions of the given problems. One of the most outstanding works in the area of macro-actions is Macro-FF (Botea et al., Reference Botea, Enzenberger, Muller and Schaeffer2005), a system for generating macro-operators through the analysis of static predicates. In addition, Macro-FF can learn macro-operators from training plans by analyzing successive actions. Macro-FF is produced in two versions. CA-ED version is designed for arbitrary planners where changing their source code is not necessary and SOL-EP version (planner dependent) where a planner (in this case, FF) is enchanted for handling macro-operators. WIZARD (Newton et al., Reference Newton, Levine, Fox and Long2007) learns macro-actions from training plans by genetic algorithms. There are defined several genetic operators working over action sequences appearing in training plans. WIZARD is designed for arbitrary planners. DHG (Armano et al., Reference Armano, Cherch and Vargiu2003, Reference Armano, Cherch and Vargiu2005) is able to learn macro-operators from static domain analysis by exploring a graph of dependencies between operators.

Our method is designed for domain-independent planning and for arbitrary planners like the other systems. Macro-operators can be assembled only from operators that are dependent, in terms that one operator provides a predicate (or predicates) to the other operator. It is similar to existing approaches. Nevertheless, there are some differences between our method and the existing approaches. We are able to detect pairs of actions that can be assembled into macro-actions, but the actions do not have to be necessarily successive in training plans. In addition, we are able to update the training plans in such a way that the updated training plans consider generated macro-operators. Therefore, it is not necessary to run the planners again. This can help us with another issue, the removal of unnecessary primitive operators that can be replaced by generated macro-operators. Despite the potential loss of completeness of some planning problems, planners benefit from the removal of primitive operators and the experiments we made on International Planning Competition (IPC) domains did not reveal any problem that became unsolvable. In addition, our method can reveal a suitable set of macro-operators in very little time. A more thorough comparison of our method with the existing ones is done in Section 8.3 (last paragraph).

4 Action dependencies in plans

Action choice is the key part of planning. Plans often contain sequences with dependencies between actions in the sense that one action provides predicates serving as preconditions for the other actions. In this section, we formally describe this dependency relation and present some of its useful features.

Every action needs some predicates to be true before the action is applicable. These predicates are provided by the initial state or by other actions that were performed before. If we have a plan solving a planning problem, we can identify which actions are providing these predicates to other actions that need them as their precondition. The following definition describes this relation formally.

Definition 1.1. Let 〈a ₁, … , a_n〉 be an ordered sequence of actions. Action a_j is straightly dependent on the effects of action a_i (denoted as a_i → a_j) if and only if i < j (e ⁺(a_i) ∩ p(a_j)) ≠ ∅ and .

Action a_j is dependent on the effect of action a_i if and only if a_i → *a_j where →* is a transitive closure of the relation→.

The relation of straight dependency on the effects of action (hereinafter straight dependency only) means that a_i→a_j holds if some predicate from the precondition of action a_j is provided by action a_i and a_i is the last action before action a_j providing that predicate. Notice that an action may be straightly dependent on more actions (if it has more predicates in the precondition). The relation of dependency on the effects of action (hereinafter dependency only) is a transitive closure of the relation of straight dependency.

Remark 1.2. Negation of the relations of straight dependency and dependency is denoted in the following way:

• • a_i a_j means that a_j is not straightly dependent on a_i (i.e. (a_i → a_j)).

• • a_i * a_j means that a_j is not dependent on a_i (i.e. (a_i → *a_j)).

Let us define the complementary notion of action independency. The motivation behind this notion is that two independent actions being adjacent can be swapped in the action sequence without influencing the plan (lemma 1.4 (see below) which has been formally proved in Chrpa and Bartak (Reference Chrpa and Bartak2008b).

Definition 1.3. Let 〈a ₁, … ,a_n〉 be an ordered sequence of actions. Actions a_i and a_j (without loss of generality, we assume that i < j) are independent on the effects (denoted as a_i a_j) if and only if a_i *a_j, p(a_i) ∩ e ⁻(a_j) = ∅ and e ⁺(a_j) ∩ e ⁻(a_i) = ∅.

Lemma 1.4. Let π = 〈a ₁, … ,a_{i− 1},a_i, a_{i+ 1},a_{i+ 2}, …, a_n〉 be a plan solving planning problem P and a_i a_{i + 1}. Then plan π′ = 〈a ₁, …, a_{i− 1}, a_{i+ 1},a_i, a_{i+ 2}, …, a_n〉 also solves planning problem P.

The symbol for relation of independency on the effects (hereinafter independency only) evokes a symmetrical relation even though, according to Definition 1.3, the relation of independency does not have to be necessarily symmetrical. The reason for using the symmetrical symbol is hidden in the previously mentioned property of the independency relation (lemma 1.4).

Remark 1.5. Since the relations of dependency and independency are not complementary, we define the following symbol:

• • a_i↔a_j means that a_j is not independent on a_i (i.e. (a_i a_j)).

Computation of the relation of straight dependency is quite straightforward. The idea is based on storing of indices of the last actions that created the particular predicates. Concretely, each predicate p is annotated by d(p), which refers to the last action that created it. We simulate execution of the plan and when action a_i is executed, we find the dependent actions by exploring d(p) for all predicates p in the precondition of a_i. The relation of straight dependency can be naturally represented as a directed acyclic graph, so the relation of dependency is obtained as a transitive closure of the graph Mehlhorn (Reference Mehlhorn1984). The relation of independency can be easily computed by checking every pair of actions a_i and a_j (i < j) on satisfaction of the conditions from Definition 1.3. It is straightforward that the time complexity in the worst case is O(n ²) where n represents the length of the sequence of actions (plan).

5 Identifying actions that can be assembled

We obtain a new macro-action by assembling two primitive actions. The result of applying a macro-action to some state is identical to the result of applying the primitive actions in the given order to the same state. A macro-action obtained by assembling of actions a_i and a_j (in this order) will be denoted as a_i,j, formally:

• • p(a_{i, j}) = p(a_i) ∪ (p(a_j)\ e ⁺(a_i))

• • e ⁻(a_{i, j}) = (e ⁻(a_i) ∪ e ⁻(a_j))\ e ⁺(a_j)

• • e ⁺(a_{i, j}) = (e ⁺(a_i) ∪ e ⁺(a_j))\ e ⁻(a_j)

This approach can be easily extended for more actions; see Chrpa et al. (Reference Chrpa, Surynek and Vyskocil2007).

It is clear that we have to decide which actions can be assembled. We can analyze several previously found plans (training plans), where we focus on actions (instances of operators) that are (or can be) often successive. We can analyze the plans by looking for successive actions only. However, in such a case, we may miss many pairs of actions that can be performed successively, but in the plans, there are some other actions placed between them. If the intermediate actions can be moved before or behind the chosen pair of actions without losing plan validity, then we can assemble even non-successive actions. We use the main property of independent actions (can be swapped if adjacent) for detection if a pair of actions can be assembled (we can make them adjacent). To get more insight regarding permutations in plans, see Fox and Long (Reference Fox and Long1999). Figure 1 shows four different situations (actually two situations and their mirror alternatives) for moving the intermediate actions. Clearly, if the intermediate action is adjacent and independent on the boundary action, we can move this action before or behind one of the boundary actions (according to lemma 1.4). If the intermediate action is not independent on one of the boundary actions, then we have to move it only before or behind the other boundary action, which means that this intermediate action must be independent on all actions in between (including the boundary action).

Figure 1

Four different situations for moving the intermediate actions (gray-filled) before or behind one of the boundary actions (black-filled)

The algorithm (Figure 2) is based on repeated application of the above steps. If all intermediate actions are moved before or behind the boundary actions, then the boundary actions can be assembled (become adjacent). If some intermediate actions remain and none of the steps can be performed, then the boundary actions cannot be assembled. Anyway, if the algorithm returns true (i.e. actions can be assembled), we also obtain lists of action indices representing (intermediate) actions that must be moved before (respectively behind) actions a_i and a_j. Usage of these lists will be explained in the following section.

Figure 2

Algorithm for detecting pairs of actions that can be assembled

6 Generating macro-operators

As mentioned earlier, planning domains include planning operators rather than ground actions. Assembling operators rather than actions is more advantageous, because macro-operators can be more easily converted into more complex problems than macro-actions. The idea of detecting such operators, which can be assembled, is based on the investigation of training plans, where we explore pairs of actions (instances of operators) that can be assembled more times.

Definition. 2.1. Let M be a square matrix where both rows and columns represent all planning operators in the given planning domain. If field M(k, l) contains a pair 〈N, V〉 such that:

• • N is a number of such pairs of actions a_i, a_j that are instances of k-th and l-th planning operator (in order), a_i → a_j and both actions a_i and a_j can be assembled in some example plan. In addition, a_i (resp. a_j) cannot be in such a pair with the other instances of l-th (resp. k-th) operator.

• • V is a set of variables shared by k-th and l-th planning operators.

Then M is a matrix of candidates.

In other words, the matrix of candidates contains proper pairs of actions (instances of planning operators) for assembling (or becoming macro-actions). The algorithm (Figure 3) constructs the matrix of candidates from the given set of training plans solving the planning problems in the same domain. Computation of the sets of variables that operators share needs to be clarified. For example, in a variant of a well-known BlockWorld domain, there are operators PICK (box, hoist and surface) and DROP (box, hoist and surface). If we decide to make a macro-operator PICK-DROP (consisting of PICK and DROP operators in this order), then we can also see that the box and hoist are always the same (we are picking and dropping the same box with the same hoist in time), and only the surface may differ. Generally, we observe which parameters (objects) are shared by actions and select such parameters that are shared by all pairs of actions (instances of the given operators) that can be assembled.

Figure 3

Algorithm for creating the matrix of candidates for assemblage

Now, we explain the purpose of lists L and R that are generated in function DETECT-IF-CAN-ASSEMBLE. If we have to update plans by replacing selected actions by macro-actions (instances of generated macro-operators), then we must also reorder other actions to keep the (training) plans valid. The following approach shows how to reorder actions in plan π=〈a ₁ , … , a_n〉, if a pair of selected actions a_i, a_j is assembled into macro-action a_{i, j}:

• • actions a ₁, … a_{i− 1} remain in their positions

• • actions listed in L are moved (in order) to positions i, …, +|L|−1

• • macro-action a_{i, j} is added to i+|L|-th position

• • actions listed in R are moved (in order) to positions i+|L|+1, …, j−1

• • actions a_{j + 1}, …, a_n are moved one position back (to positions j, …, n−1)

To generate macro-operators from training plans (in the given domain), we can use the following approach (formally in Figure 5). We create macro-operators repeatedly until no other macro-operator can be created. At first, we have to compute the matrix of candidates from all the training plans (CREATE-MATRIX). Then we select a proper candidate for creating macro-operators (SELECT-CANDIDATE), which means that such a candidate must satisfy certain conditions (which will be explained later). To ensure the soundness of the generated macro-operators, we have to assign inequality constraints for macro-operator arguments. It prevents a possible instantiation of invalid macro-actions if these arguments are set as equal. In Figure 4, we can see an example of the PICKUP-STACK macro-operator. If the arguments are set as equal, we can simply see that such an instance is applicable, but invalid (when unfolded). Inequality constraints can be easily detected by simulation of performance of the operators that are going to be assembled. After a creation of the macro-operator from the selected candidate, we must update all training plans (UPDATE-PLANS), which means that we replace particular pairs of actions by the corresponding instances of the new macro-operator. UPDATE-PLANS procedure can be easily implemented by application of the previously described approach (reordering actions after assembling) on every pair of actions (instances of the selected operators) in every plan.

Figure 4

Example of PICKUP-STACK macro-operator

Last but not least, the remaining unexplained issue is the function for selecting the proper candidate for assemblage (SELECT-CANDIDATE). We suggested selecting such a candidate that satisfies the following conditions (let f(O) represent the frequency of operator O (how many instances of operator O occur in all the training plans), a(O) represent the arity of operator O (number of arguments of O), N_i,j represent the number N in field M_i,j of the matrix of candidates and V_i,j represent the set of variables shared by i-th and j-th operator):

(6.1)

(6.2)

(6.3)

Condition 6.1 says that we are looking for such operators whose instances usually appear (or can appear) successively. Constant b∈〈0; 1〉 represents a pre-defined bound that prevents selecting such operators whose instances do not appear successively so often. It is clear that if the bound is too small, many operators may be assembled. It usually causes that generated macro-operators are representing almost the whole training plans, which does not bring any contribution to planners. On the other hand, if the bound is too big, almost no operators may be assembled, which means that the domains may remain unchanged. However, in some cases we are not able to prevent the generation of such macro-operators representing a huge part of some training plan, even though b is set quite big. The reason for this rests in the fact that sometimes only one (or a very few) instances of some operator occur in all the training plans. Almost always, we can find some other action that can be assembled with this instance, because the ratio between the number of candidates (stored in the matrix of candidates) and the frequency of the operator becomes 1. It means that the operator will be certainly selected for assemblage. To prevent this unwanted selection, we can add condition 6.2 allowing only the selection of such operators whose ratio between the number of instances being able to be assembled (stored in N_{i, j}) and the number of all actions from all the training plans reaches a predefined constant c.

Another problem we are facing rests in the fact that many planners use grounding. It means that the planners generate all possible instances of operators that are used during planning. However, macro-operators usually have more parameters than primitive operators, which means that macro-operators may have much more instances than primitive operators. To avoid troubles with planners regarding grounding, we should limit the maximum number of parameters for each macro-operator by a pre-defined constant d (condition 6.3). If there are more candidates satisfying all the conditions, then we prefer the candidate with the maximum value of the expression listed in condition 6.1.

We must also decide which macro-operators can be added to the domain and which primitive operators can be removed from the domain. Here, we decided to add every macro-operator whose frequency in the updated training plans is non-zero. Similarly, we decided to remove every primitive operator whose frequency in the updated training plans becomes zero. It is clear that it may cause a possible failure when solving non-training problems. Fortunately, in IPC benchmarks, it does not happen (we did not experience any such problem during the experiments). If for some problem planners fail to find a solution, then it is possible to bring the removed primitive operators back to the domain and run the planners again.

7 Soundness and complexity discussion

We assume that all plans used for analysis by our algorithms are valid. To ensure the validity of the plans, we can simply extend the algorithm for computing the relation of straight dependency by checking the satisfiability of action preconditions. It is quite straightforward that the algorithms for computing the relations of (straight) dependency and independency (sketches of the algorithms are discussed at the end of Section 3) are sound and can be computed in O(n ²) steps (in the worst case), where n represents the length of the input plan. Soundness and time complexity of the other presented algorithms are justified in more detail.

Proposition 3.1. The algorithm DETECT-IF-CAN-ASSEMBLE ( Figure 2) is sound and can be computed in the worst case in O(l ²) steps where l is the number of intermediate actions (actions between a_i and a_j).

Proof. The idea of the algorithm is based on moving intermediate actions before or behind defined actions. It is clear that a pair of adjacent actions can be assembled into a macro-action (we must follow their order) without loss of validity of the examined plan. The moving of intermediate actions can be done in the four cases (Figure 1), where two of them are a mirror of the other two. Without loss of generality, we prove the soundness and complexity only in two cases (on the left-hand side on Figure 1), because the soundness and complexity of the other cases can be proved analogically. First, if a_i a_{i + 1}, then by applying lemma 1.4, we can move a_{i + 1} before a_i without loss of the plan’s validity and it takes a constant time (i.e. O(1)). Second, assume that a_i ↔ a_k, k < j and k is the greatest possible value. If a_k a_l ∀l:k < l < j, then by repetitively applying lemma 1.4, we can move a_k behind a_j also without loss of the plan’s validity. It can take at most O(l) steps. The algorithm always terminates because in each run of the loop we remove at least one intermediate action. When no intermediate action remains, the loop ends. It means that the cycle is performed at most l times. Hence, in the worst case the algorithm requires O(l ²) steps to perform. □

Proposition 3.2. The algorithm CREATE-MATRIX ( Figure 3) is sound and can be computed in the worst case in O(n ⁴) steps where n is the total length of all the training plans.

Proof. For each training plan, the algorithm explores each pair of actions being in the relation of straight dependency by the algorithm DETECT-IF-CAN-ASSEMBLE (Figure 2), which is sound (proposition 3.1). It is clear that by using this approach, we can build the matrix of candidates consistent with the previously stated conditions. It is also clear that in the worst case we can have O(n ²) relations of straight dependency and the algorithm DETECT-IF-CAN-ASSEMBLE in the worst case can be performed in O(n ²) steps (proposition 3.1—considering that l can be close to n). Summarized, it gives us the time complexity O(n ⁴) in the worst case. □

Theorem 3.3. The algorithm GENERATE-MACRO (Figure 5) is sound and can be computed in the worst case in O(n ⁵) steps, where n is the total length of all the training plans.

Figure 5

Algorithm for generation of macro-operators

Proof. From the soundness of the algorithms DETECT-IF-CAN-ASSEMBLE (proposition 3.1) and CREATE-MATRIX (proposition 3.2), we know that each candidate for assemblage represents a pair of actions that can be assembled without loss of the plan’s validity. If we generalize it and consider the inequality constraints, then we can simply see that each macro-operator produced by this algorithm is valid. The algorithm also always terminates because in each step of the loop the length of the training plans decreases at least by one, which means that the loop can be performed in the worst case n−1 times. Together with the complexity of the algorithm CREATE-MATRIX (proposition 3.2), it gives us the time complexity O(n ⁵) in the worst case. □

It is well known that if we add a generated macro-operator into the domain, then the domain remains valid. We can also remove the primitive operators fully replaced by the generated macro-operators. It brings us an improvement of the performance of the planners. However, it may cause an insolvability of some problems that were solvable in original domains. Hopefully, in all tested cases it did not happen as we can see in the experiments (Section 8). Despite the high time complexity of our method (in the worst case), the experiments showed that our method is fast (tenths of a second for one run of the GENERATE-MACRO procedure).

8 Experimental evaluation

In this section, we present the experimental evaluation of our method. We compare the performance of the given planners between the original domains and the domains updated by our method. The planning domains and planning problems that we used here are well known from the IPC. We have done the evaluation in the following steps:

• • Generate several simpler training plans as an input for our method.

• • Generate macro-operators by our method and add them to the domains. Remove such primitive operators that no longer appear in the updated training plans.

• • Compare running times for more complex problems between the original domains and the updated domains. The time limit was set to 600 seconds.

We used SATPLAN 2006 (Kautz et al., Reference Kautz, Selman and Hoffmann2006) and SGPLAN 5.22 (Hsu et al., Reference Hsu, Wah, Huang and Chen2007) both for the generation of the training plans (for the learning phase) and for the comparison of the running times and quality of plans. We also used LAMA (Richter & Westphal, Reference Richter and Westphal2008), Filtering and Decomposition for Planning (FDP) (Grandcolas & Pain-Barre, Reference Grandcolas and Pain-Barre2007) and LPG-td (Gerevini & Serina, Reference Gerevini and Serina2002) for the comparison of running times and quality of plans (not for the learning phase).Footnote 1 The choice of the planners was motivated by great results that the planners achieved on the (several last) IPCs. Since SATPLAN and FDP cannot handle negative preconditions (which are necessary for representation of inequality constraints), we used a tool called ADL2STRIPSFootnote 2 that can produce grounded STRIPS domain from ADL domain.

For the evaluation, we used IPC domains Blocks, Depots, Zenotravel, Rovers, Gripper, Satellite and Goldminer.Footnote 3

8.1 Generating macro-operators and updating the domains

As mentioned earlier, the generation of macro-operators depends on pre-defined bounds b, c and d (conditions 6.1, 6.2 and 6.3). The number of training plans for each domain differs from 3 to 6 with respect to their lengths. The average time taken by both SGPLAN and SATPLAN to generate a training plan was (mostly) within tenths of a second.Footnote 4 Despite the high (worst-case) time complexity O(n ⁵) (Theorem 3.3), the average time taken by one run of our method (GENERATE-MACRO procedure) was within tenths of a second.Footnote 5

We used different settings of bounds b, c and d and two different planners (SATPLAN 2006, SGPLAN 5.22) for the generation of the training plans. First, bound d was set to N+1 (except for the Satellite domain and Gripper domain for SATPLAN’s training plans), where N represents the greatest number of arguments of operators in the particular domain, because we did not want to generate too complicated macro-operators. If bound b was set too low, then many useless macro-operators were generated. We found out that a reasonable value of bound b can be almost in all cases 0.8; only in the Gripper domain (for SATPLAN’s training plans), we lowered it to 0.6. Setting bound c was not as definite as setting the other bounds. Usually, the reasonable value was between 0.1 and 0.05, but in the Gripper domain it was set to 0.03. The reason for keeping bound c low (0.03–0.05) rested in the fact that in the Blocks and Gripped domains, all the primitive operators were replaced by generated macro-operators. The choice of a planner for the generation of training plans brought several differences—only in the Blocks domain, it resulted in the same result. In the Depots domain, we were not able to remove some primitive operators when SATPLAN’s training plans were used as we did when SGPLAN’s training plans were used. In the Zenotravel and Rovers domains, we were not able to learn any suitable set of macro-operators when SATPLAN’s training plans were used. Likewise, in the Satellite domain, when SGPLAN’s training plans were used. In the Gripper domain, the results of learning differed with respect to planners’ strategies—SATPLAN prefers to carry balls in both robotic hands, SGPLAN prefers to carry balls just in one robotic hand. In the Gold Miner domain, the planners preferred different operators, which resulted in slightly different results of learning.

The results of learning (best for the particular domains) are showed in Table 1. We stated only such alternatives that provided the best results in the running times and quality of plans comparison for the particular domains.

Table 1

Suggestion of our method—the best results for the particular domains

8.2 Comparison of running times and quality of plans

In this evaluation, we used SGPLAN 5.22, an absolute winner of the IPC 5, SATPLAN 2006, co-winner of optimal track in the IPC 5, LAMA, winner of the IPC 6 suboptimal track and FDP, participant of the IPC 5 and LPG-td, awarded on the IPC 4. The benchmarks ran on XEON 2.4 GHz, 1GB RAM and Ubuntu Linux. The results are presented in Tables 2 and 3. We chose such problems (in most domains) that were neither so easy nor so hard for the particular planners, because the evaluation of these problems usually tells us the most about the particular domains. The less complex problems were solved in the updated domains almost as fast as or a bit slower than in the original ones (except for the Rovers domain in SATPLAN’s evaluation). The hardest problems (both original and updated) were not solved within the time limit of 600 seconds.

Table 2

Comparison of running times and plans lengths (we assume that macro-actions are unfolded into primitive actions) for SGPLAN (left-hand side) and SATPLAN (right-hand side)

Table 3

Comparison of running times and plans lengths (we assume that macro-actions are unfolded into primitive actions) for LAMA (left-hand side) and FDP (right-hand side)

SGPLAN performed well in the original domains on almost all the tested problems except Blocks problems, some Depots problems and Gold Miner problems. Running times in the updated domains were always better except in the Gripper domain, where the running times were slightly worse, and the Satellite domain where the results were significantly worse. The quality of the plansFootnote 6 generated in the updated domains was not much worse, however; sometimes, the quality was slightly better and, surprisingly, in one Blocks problem it was more than twice better. The best results SGPLAN were reached in the Blocks domain where the speed-up was quite impressive. The possible reason may rest in the fact that SGPLAN’s heuristics (FF-based) do not handle well problems like Blocks or Depots, because the plan quality was significantly better in the updated problems as well. SGPLAN’s behavior in the Gold Miner domain was weird, because for all more complex (original) problems, SGPLAN terminated without throwing any error message after about 3 minutes of running.

SATPLAN, unfortunately, did not benefit often from our method. In the Blocks domain, SATPLAN was able to generate plans faster, but at the price of significantly worse quality of plans. However, SATPLAN produced very good results in the updated Gripper domain, where the problems normally unsolvable (in 600 seconds) were solved in a couple of seconds (for the domain updated on the basis of SATPLAN’s training plans) or in hundreds of a second (for the domain updated on the basis of SGPLAN’s training plans). The reason for that rests in the fact that SATPLAN uses a Planning Graph and each tested problem in the updated Gripper domain can be solved in only two layers. SATPLAN also gained quite good results in the Satellite and Gold Miner domains. Errors thrown by SATPLAN were caused by insufficient memory or a large domain file (produced by the ADL2STRIPS tool).

FDP is a planner based on CSP techniques that guarantees optimal plans. Even though FDP seems to be an ideal candidate for generating training plans for the learning phase, it fails to find a reasonable number of training plans in reasonable time. However, the experiments showed that the performance on the updated domains significantly increased in most of the tested problems. Using macro-operators reduced the depth of the search, which expectedly increased FDP’s performance. The worse results gained in the Zenotravel domain was caused by the fact that no macro-action was used in the solutions of the updated problems (except zeno-2-6). An absence of results on the Rovers and Gold Miner domains is caused by the inability of FDP to process the domains descriptions (both for the original and updated ones) correctly.

LAMA is a planner that combines the Causal Graph heuristic and FF-based heuristics. In the Depots, Blocks and Gold Miner domains, the quality of plans was significantly better in updated domains. In addition, the time comparison for the Depots domain showed a significant increase in performance. The results correlate a bit with the results achieved by SGPLAN, because SGPLAN uses FF-based heuristics as well.

We also made experiments with the LPG-td (Gerevini & Serina, Reference Gerevini and Serina2002) planner. LPG is based on local search techniques. Our experiments showed significantly worse performance in the Blocks and Depots domains; in the other domains, LPG performed almost the same. However, the results of LPG had huge discrepancies (both the running times and the quality of plans) with respect to the selected random seed.