Can I Really Do That? Verification of Meta-Operators via Stackelberg Planning

1 Introduction

Classical planning deals with the problem of finding a sequence of actions to achieve a goal [Bylander, 1994]. Since the origins of the field, it was noted that reasoning at different levels of abstraction is key for efficient planning on complex domains. One way of introducing such new levels of abstraction is to introduce meta-actions that model effects that can be achieved by some sequence of primitive actions. This idea has been widely explored by using macroactions [Fikes et al., 1972; Korf, 1985; Botea et al., 2005], meta-actions built from a fixed sequence of actions. Macrooperators go one step further, by considering sequences of parameterized operators, which are transferable skills to other instances of the same domain. Plenty of research has considered how to generate useful macro-operators, e.g., by learning them from existing plans [Chrpa, 2010; Chrpa et al., 2014; Chrpa and Vallati, 2022], testing their benefits in combination with planning techniques [Coles and Smith, 2007; Gerevini et al., 2009], by restricting the amount of considered instantiations and/or replacing primitive operators [Chrpa et al., 2019]. They have shown that, despite increasing the amount of actions in the reformulated task, this can be beneficial due to introducing shortcuts in the state space and reducing the length of the solution, before replacing the macroactions by their corresponding sequences or actions.

We introduce the concept of meta-operator, as an operator that is not part of the domain but whose effects can always be achieved on any state satisfying the preconditions by some, not necessarily fixed, sequence of actions. This is a lot more general than macro-operators, as completely different plans are allowed when applying the meta-operator on different states. This generality offers wide opportunities for defining useful behaviours in all kind of domains.

The main challenge is how to determine if a given metaoperator is valid, i.e., for any instantiation of the metaoperator and any reachable state satisfying the precondition, can it always be replaced by some sequence of primitive actions? Macro-operators are valid by construction, as they are derived from a fixed sequence of operators whose preconditions and effects are uniquely defined. However, we turn the problem around, defining meta-operator candidates as useful high-level behaviours and then verifying if they are indeed valid. This seems unfeasible, as it requires to find a plan for exponentially many states in the size of the planning task and exponentially many actions in the number of operator parameters. However, we show that it can be solved by compiling the problem into a single Stackelberg planning task, and leveraging Stackelberg planners [Speicher et al., 2018]. Verifying meta-operators has benefits beyond their use to reformulate planning domains. We show that it generalizes the problem of testing whether actions are undoable [Daum et al., 2016], i.e., whether their effects can be reversed.

After solving the reformulated task, meta-actions are replaced by a corresponding sequence of primitive actions. We propose a simple approach, based on re-planning for the missing parts of the plan. Finally, we extend techniques for deriving macro-operators in order to learn candidate metaoperators. We show that our compilation is effective at checking which candidates are valid, and that using meta-operators can pay off even when considering the time it takes to reconstruct the solution.

2 Background

A STRIPS planning task [Fikes and Nilsson, 1971; Bylander, 1994] is a tuple Π = (F,A, I,G), where F is a finite set of facts, A is a finite set of actions, I ⊆ F is the initial state and G ⊆ F is the goal. Each action a ∈ A has a precondition pre(a) ⊆ F, and effects add(a), del(a) ⊆ F. We assume add(a) ∩ del(a) = ∅.

turn_to (?s ?dn ?dp) :pre (pointing ?s ?dp) :add (pointing ?s ?dn) :del (pointing ?s ?dp) switch_on (?i ?s) :pre (on_board ?i ?s), (power_avail ?s) :add (power_on ?i) :del (calibrated ?i), (power_avail ?s) calibrate (?s ?i ?d) :pre (on_board ?i ?s),(pointing ?s ?d), (calibration_target ?i ?d),(power_on ?i) :add (calibrated ?i))

A STRIPS planning task induces a state space over the set of states S = 2F . Each state s ∈ S is a subset of facts, which are currently true. An action a is applicable on a state s if pre(a) ⊆ s. In that case, the result of applying a to s is s�a� = (s ∪ add(a)) \ del(a). By S[a] we denote the set of states to which a is applicable. The goal states SG = {s ∈ S | G ⊆ s} are the states that satisfy the goal.

An action sequence ⃗a = ⟨a1, . . . , an⟩ can be applied on a state s if there exists a sequence of states s0, . . . , sn, where s0 = s, and for i ∈ [1, n], ai is applicable on si-1 and si = si-1�ai�. The result is the state s�⃗a� = sn. We say that a state s is reachable if there exists a sequence of actions ⃗a such that I�⃗a� = s. By R(Π) we denote the set of states reachable from I. A solution for I is called a plan for Π and is a sequence of actions from the initial state to a goal state. Additionally, we consider a cost function c : A ↦→ N0. The cost of a plan is the sum of all its actions' cost. We use c(⃗a) to denote the cost of the sequence of actions, and c∗ (s, s′ ) to denote the cost of the cheapest path from s to s′ .

Tasks are often specified in lifted form, e.g., in the PDDL language [McDermott, 2000]. A lifted task Πl is a tuple (P, O, C, I, G) where P is a set of (first-order) atomic predicates, O is a set of operators 1 , C is a set of object constants, I is the initial state, and G is the goal. Predicates and action schemas have parameters. Both parameters and objects have types so that a parameter can be substituted by an object in C if their type matches. We denote individual parameters with x, y, z and sets of parameters with X, Y, Z. An operator o[X] is a triple (pre(o), add(o), del(o)), consisting of preconditions, add list, and delete list, all of which are a set of P instantiated with objects in C or parameters in X. I and G are subsets of P, instantiated with objects from C.

A lifted task Πl can be transformed into a STRIPS task ground(Πl ), by instantiating the set of predicates and operators with the set of objects C to obtain the set of facts and actions, respectively [Helmert, 2009]. As an example, consider

1 Operators are also often called action schemas. We follow the convention used in other macro-operator approaches of using "actions" to refer to the grounded level, and operators to the lifted level.

turn_to-switch_on-calibrate (?s ?i ?dn ?dp) :pre (pointing ?s ?dp), (power_avail ?s), (calibration_target ?i ?dn), (on_board ?i ?s) :add (calibrated ?i), (pointing ?s ?dn), (power_on ?i) :del (pointing ?s ?dp), (power_avail ?s)

the Satellite domain [Long and Fox, 2003], where a set of observation tasks must be performed by several satellites, which are equipped with different instruments. Fig. 1 shows three of the action schemas, which are used to prepare instruments so that they can take images. The set of actions of an operator o, Ao[C], contains an action for each valid substitution of the parameters. For example, the instantiations of turn to could include turn to(satellite1, sun, earth), turn to(satellite1, earth, moon), etc.

2.1 Macro-operators

Given two actions a1, a2 ∈ A, the macro-action, M(a1, a2) represents the application of a1 followed from a2 as follows:

• pre(M(a1, a2)) = pre(a1) ∪ (pre(a2) \ add(a1)),
• add(M(a1, a2)) = (add(a1) \ del(a2)) ∪ add(a2), and
• del(M(a1, a2)) = (del(a1) \ add(a2)) ∪ del(a2).

Such a macro-action is valid if del(a1) ∩ pre(a2) = ∅. In that case, in any state s satisfying pre(M(a1, a2)), we can apply a1 followed by a2 to reach s�M(a1, a2)�. Similarly, we can define macro-actions from any sequence of action ⃗a = ⟨a1, . . . , an⟩ asM(⃗a) =M(M(M(a1, a2), a3), . . . , an). Checking whether such macro-action is valid can be done by checking every pair of actions within the recursion.

Macro-operators follow the same idea at a lifted level. We can consider any sequence of operators, along with a unification of their parameters to define a new macro-operator following the same rules as described for macro-actions. In satellite, in order to use an instrument one needs to turn the satellite towards a calibration target, switch on, and calibrate the instrument. Therefore, it may be useful to bundle these operators together into a macro-operator, as shown in Fig. 2.

2.2 Stackelberg Planning

Stackelberg planning is a framework of adversarial planning introduced by Speicher et al. [2018], inspired by Stackelberg security games [Tambe, 2011]. A Stackelberg planning task Πst = (F,AL,AF , I,G) is an extension of a STRIPS task, where there are two agents with separate sets of actions, the leader (AL) and the follower (AF ). The follower's objective is to reach a state that satisfies the goal G, as in STRIPS. But the leader acts first with the objective of maximizing the follower's plan cost. For each state in s ∈ 2F , we define its leader cost L∗ (s) as the cost of a cheapest sequence of actions in AL starting from I and ending in s (or ∞ if no such sequence exists). The follower cost F ∗ (s) is the optimal plan for the follower starting from s, i.e., the solution of a STRIPS task (F, AF , s, G). A state s dominates another s′ if L∗ (s) ≤

L∗ (s′ ), F ∗ (s) ≥ F ∗ (s′ ) and one of the inequalities is strict. The solution of Πst is the set of all leader-reachable nondominated states S∗ ⊆ 2F . For our use case, it is not needed to compute multiple entries with the same leader and follower cost. Therefore, we focus on approaches that compute the Pareto front PF(Πst ){⟨L∗ (s), F ∗ (s)⟩ | s ∈ S∗ } containing all non-dominated pairs of leader and follower cost [Torralba et al., 2021]. Intuitively, a pair ⟨cL, cF ⟩ ∈ PF(Πst ) means that the leader can make the cost of the follower's optimal plan as high as cF by spending as little as a cost of cL.

One can define lifted Stackelberg planning tasks in an analog manner as for STRIPS tasks [Sauer et al., 2023].

3 Meta-Operators

We start by defining meta-actions, as behaviours that can be achieved by arbitrary sequences of actions.

Definition 1 (Meta-action). Let Π = (F,A, I,G) be a STRIPS planning task. An action aM is a valid meta-action for Π if and only if for all reachable states s ∈ R(Π) where pre(aM) ⊆ s, there exists an action sequence ⃗a = ⟨a1, . . . , an⟩ ∈ A such that s�⃗a� = s�aM�.

We remark that this property can refer to any action, and in fact this property is interesting only when aM ̸∈ A. The notion can be naturally extended to the lifted case.

Definition 2 (Meta-operator). An operator oM is a valid meta-operator for a lifted planning task Πl if and only if all instantiations aM ∈ AoM[C] are valid meta-actions for ground (Πl ).

Figure 3 shows an example of a meta-operator. Metaswitch-on-calibrate achieves the same useful effects as the macro-operator in Figure 2, without the side-effect changing the direction the satellite is pointing to. This is beneficial for having more focused meta-actions, that can achieve the desired effect with fewer preconditions and/or side effects.

Meta-operators generalize the standard notion of macrooperator. The key difference is that in the definition of macroaction, the sequence -→a is the same for all states. Similarly, macro-operators require that the sequence -→a can be lifted, i.e., for all instantiations of o the sequence -→o uses the same action schemas and parameter mappings.

Considering the special case of macro-operators has several advantages. First of all, it makes trivial the process of identifying if the meta-operator is valid, as it suffices to check if the precondition of one of the actions in the sequence is contradicted by the effect of a previous action. Second, it is always straightforward to translate a plan that depends on macro-actions to one that only uses primitive operator: as we know in advance for each macro-action exactly what sequence of actions should it be replaced by.

Meta-actions, on the other hand, are hard to validate. Even when considering a meta-action that is applicable only on a single state, if the effect of the meta-action consists of achieving the goal, then validating whether it is valid is as hard as deciding solvability of planning, i.e., PSPACE-hard.

But, the generality of meta-operators has strong advantages too, as it opens widely the space of possible reformulations

meta-switch-on-calibrate (?s ?i) :pre (on_board ?i ?s) (power_avail ?s) :add (calibrated ?i) (power_on ?i) :del (power_avail ?s)

that can be applied to the planning task. For example, macrooperators have a hard time modelling scenarios where an object needs to traverse multiple locations to reach a final destination. In those cases, to ensure that there is a fixed sequence of actions for all possible instantiations, it is necessary to introduce parameters that model all intermediate locations visited along the way. This is not only cumbersome, but utterly impractical, as the number of instantiations grows exponentially. With meta-operators, we can instead "assume" that the target will be reachable by some sequence of actions. Ensuring validity of the meta-operator will necessarily involve checking this for all pairs of source and destination. Similarly, in our example, we can get rid of certain parameters such as the direction the satellite is pointing to, making the meta-operator more applicable with less instantiations.

4 Validation via Stackelberg Planning

We compile the problem of testing whether a given action schema is a valid meta-action for a given task as a Stackelberg planning task. The idea of the compilation is that the leader can apply any sequence of actions to choose any reachable state s ∈ R(Π) where some instantiation of the operator is applicable, and choose one such action. Then, the goal of the follower will be to go from the resulting state, to a state where the effects of the action have been accomplished.

Definition 3. Let Π = (F,A, I,G) be a STRIPS planning task, AM a set of actions. The meta-action task of Π and AM is the Stackelberg planning task ΠM(Π,AM) = (F st , AL, AF , I st , Gst ) where:

• F st = F ∪ {g p , ok p | p ∈ F} ∪ {turn L}
• I st = I ∪ {turn L} ∪ {ok p | p ∈ F} ∪ {g p | p ∈ I}
• Gst = {ok p | p ∈ F}
• AL = {αL | α ∈ A}∪{passTurnL[aM] | aM ∈ AM}
• AF = {αF | α ∈ A} ∪ {achieveGoalF }

where the actions are defined as shown in Table 1.

For each fact p ∈ F, our compilation includes three different copies: p represents the current value; g p represents whether the follower's goal is to make p true or false; and ok p represents whether the current value of p is the desired one. In other words, the value of ok p can be derived from p and g p , as there is always an invariant such that ok p = (p ↔ g p ). Finally, there is an additional fact turn L indicating when the leader passes the turn to the follower by choosing which action aM should the follower verify from the current state.

The leader has two types of actions, αL, and passTurnL[aM]. αL is a copy of the original actions, and allows the leader to navigate through the state space to reach any reachable state. Through this process, we also update g p so that g p = p. Then, the passTurnL actions allow the leader to pick one action in AM, if the preconditions are satisfied. Note that, due to the fact turn L, only one such action may be applied, and it must be the last action applied by the leader. The action passTurnL[aM] sets the goal for the follower, by applying the effects of aM on the g p facts. Also, it keeps the ok p = (p ↔ g p ) invariant. Note that, after applying aM, the value of g p facts corresponds to the state that would be obtained by applying aM on the current state (so that all facts in add(aM) are true, all facts in del(aM) are false, and all remaining facts should retain the same value).

Then, the follower will apply actions to reach the state that results from applying aM in the current state. This is so, because it must achieve all ok p facts, whose value satisfies the invariant ok p = (p ↔ g p ). As actions αF do not have any effect over g p , the only way is to change the values of the current facts p until they have the same value as g p . Finally, the action achieveGoalF simply forces the leader to end their plan with a passTurnL action, as otherwise it is trivial for the follower agent to reach the goal with a cost of 0.

The formulation of Definition 3 uses some syntactic sugar to define the effects of the αF actions, for the sake of simplifying the presentation. Namely, it uses conditional effects, some of which have negated literals (¬g p ) in the conditions. This can be compiled away into the standard formalism of Stackelberg planning introduced in Section 2.2 by:

• Eliminating negative conditions, e.g., using an additional fact per p ∈ F that always has the opposite value than g p . In practice, this is not needed as the Stackelberg planner we use supports negative preconditions.
• Compiling conditional effects away [Nebel, 2000]. In our implementation, we create multiple copies of each action, one per combination of conditional effects [Gazen and Knoblock, 1997]. This is feasible because there are not too many conditional effects, and we can exclude any combination with mutually exclusive conditions.

Action costs are not strictly needed to test validity. However, using costs is convenient because the leader just tests reachability and the distance from the initial state is not relevant. Moreover, as Thm 1 shows, this allows us to obtain what is the maximum cost required for applying the meta-operator.

Theorem1. Let Π = (F,A, I,G) be a STRIPS planning task and AM a set of actions. Then, the solution of ΠM(Π, AM),

Proof. PF(ΠM(Π,AM)) contains a single entry because all leader actions have a cost of 0. By definition of Stackelberg planning, the follower cost of such entry is maxπL minπF c(πF ), where πL and πF range over all possible leader and follower plans, respectively. We need to show that this is equal to cM.

The leader plan πL maximizing the expression necessarily corresponds to a path ⟨αL 1 , . . . , αLm, passTurnL[aM]⟩. The only exception is if no such path is applicable. In that case, the meta-operator is trivially valid due to its preconditions not being met in any reachable state, and cM = 0. Otherwise, as the leader attempts to maximize cM, passTurnL[aM] should be applied (otherwise the follower can reach the goal with cost 0 using achieveGoalF ). And due to turn L, it is necessarily the last action in πL. As there is a direct correspondence between each πL = ⟨αL 1 , . . . , αLm, passTurnL[aM]⟩, and the set of reachable states R(Π) where aM is applicable, it suffices to show that given such a path c∗ (s, s�aM�) = minπF c(aF ), where s = I[πL].

Let πF be the optimal follower plan. Again, there is one such plan for every sequence of actions applicable from s, as the preconditions and effects of each αF over facts p are exactly the same as those of the original actions α. It remains to show that such a path satisfies the follower's goal Gst iff s[πF ] = s[aM]. Gst requires to have all ok p facts, which as explained above keep the invariant ok p = (p ↔ g p ). As passTurnL[aM] sets the g p facts to exactly the set of facts true in s[aM] this is equivalent to reach a state in which p ↔ g p .

However, for testing whether a meta-operator is valid, it is sufficient to run the compilation with unit costs. Indeed, a meta-operator is valid as long as the Pareto front does not contain an entry where the follower cost is ∞.

Corollary 1. Let Π = (F,A, I,G) be a STRIPS planning task and aM an action. Then, aM is a meta-action if and only if PF(ΠM(Π, AM)) does not contain an entry (x,∞).

To test if a candidate operator o is a valid meta-operator on a task Π, we can simply set AM to be all valid instantiations of o on Π. Note that then the actions passTurnL[aM] can also be written as an operator (action schema) in PDDL.

5 Relation to Undoability

The problem of testing whether a meta-operator is valid is related to the notion of undoability [Eiter et al., 2007; Eiter et al., 2008; Daum et al., 2016; Morak et al., 2020], i.e., testing whether the effects of a given action/operator can always be undone. This is the case, if for every reachable state s where a is applicable, c∗ (s�a�, s) < ∞. Daum et al. [2016] showed that the problem of testing whether an action is undoable can be compiled into a contingent planning task. This can also be done with our compilation. For any planning action, we can always define a reverse action, which has the opposite effects. 2 Then, testing whether the action is undoable, is equivalent to testing whether the reverse action is a valid meta-action.

Our Stackelberg compilation is inspired by their compilation to Contingent planning, but also has several advantages. We do not need to approximate the set of reachable states by using state invariants, as our encoding automatically lets the leader enumerate exactly the set of reachable states. Furthermore, in order to test whether an operator is undoable, the contingent planning compilation requires to solve a separate contingent planning task for each action instantiation. Our compilation instead is able to test validity of a meta-operator by solving a single Stackelberg planning task.

6 Learning and UsingMeta-Operators

Following previous work on macro-operators, our approach is based on learning a set of meta-operators on a set of training instances, for which we already have found a plan. Then, to solve a new planning task, we reformulate the domain PDDL file by introducing our meta-operators. Finally, after finding a plan on the reformulated task we replace any meta-action in the plan by a sequence of actions achieving the same effects.

6.1 Generate Meta-Operator Candidates

We base our approach to generate candidates on previous macro-operator approaches. Specifically, we start from a set of selected macro-operators and generate more compact meta-operators that can get similar effects, but reducing the amount of parameters and preconditions. This increases the applicability of the meta-actions and reduces the amount of instantiations that are needed. We generate candidates by applying three types of modifications to the macro-operators.

Remove precondition parameters (Cpre) Our first method, removes parameters that are absent in the effect of the macro. This aims at obtaining meta-operators that are improved versions of the original macro-operators, with the same useful effects of macros while reducing the number of parameters. When a parameter is removed, all predicates containing this parameter are removed from the action precondition as well. If this causes a parameter to not be mentioned anymore in the precondition and/or effect of the macro, we remove it as well. Given a macro-operator, we attempt to remove the parameters one by one. Note that removing preconditions of an invalid candidate can never cause it to become a valid meta-operator, as this only increases the amount of instantiations and reachable states where they are applicable. Therefore, we only consider removing additional parameters over successful candidates.

2 This may require considering multiple actions, e.g. if some added facts could already be true.

Remove effect parameters (Ceff ) A limitation of the Cpre method, is that in many cases there is no parameter that is not mentioned at all in the effects. In our running example, turn to-switch on-calibrate, all parameters are mentioned in the effect, so Cpre is not applicable. However, often only some effects are useful, whereas others are side effects. In our running example, the effects modifying the direction the satellite is pointing to are not essential.

Our second method, Ceff , eliminates a parameter appearing in the effects, removing any precondition and/or effect that depends on it. This may cause other parameters to be removed as well. In contrast to Cpre, we could in principle remove additional parameters even if intermediate results were not valid candidates. However, this leads to too many candidates so we stick with removing a single parameter.

Remove additional effects (Cinv ) Removing effect parameters might cause the resulting candidates to be automatically invalid, whenever they do not comply with the state-invariants. For example, removing ?d new from turn to-switch on-calibrate results in a metaoperator that deletes (pointing ?s ?d prev) without adding a new direction. This meta-operator is invalid, as it contradicts the state-invariant that a satellite always points in a direction. In principle, it is possible to automatically extract lifted mutex groups [Helmert, 2009; Fiˇser, 2020]. Here, we just approximate this by observing that many lifted invariants refer to the same predicate. Therefore, we take the Ceff candidates, and remove other preconditions and effects with the same predicate as the ones removed by the Ceff method. In our running example, we remove preconditions and effects with calibration target and pointing. The result is the meta-operator from Fig. 3, which does not violate any invariant and is in fact valid.

6.2 Solving New Instances

Once we have collected a set of meta-operator candidates, we use our compilation from Section 4 on the set of training instances. We then extend the domain with a set of metaoperators that were valid on all training instances, so that any classical planner can be called on the reformulated domain. When a new instance arrives, we do not validate the meta-operators again, as that would be prohibitive. Instead, we rely on the training instances being representative of the entire domain, which is a common assumption in learning and/or generalized planning approaches. Note that the behaviour described by valid meta-operators was doable for all instantiations of the operator on all states of the training task, so a few training instances suffice to obtain a strong evidence that this behaviour is always doable in the domain.

After solving the instance on the reformulated domain, we obtain a plan which may contain one or more meta-actions. The next step is to reconstruct a plan composed only of primitive actions. This was easy for macro-actions as they correspond to fixed action sequences. For meta-actions, however, one needs to find a specific plan for the state in which they are applied. In principle, the validation process may give hints about the structure of such plans. However, transferring this from the training instances to the new instance is an open problem. Instead, we follow a very simple approach: calling a classical planner for each meta-action on the original domain to find a plan from the current state to the exact state that results from applying the meta-action.

At first glance, this solution reconstruction procedure may look completely unfeasible: solving multiple classical planning problems which could be as hard as the original one. Indeed, in some domains the overhead is noticeable. However, there are several reasons why this can still pay off. First, the goal is fully specified, which tends to make heuristics more informed. Second, if a meta-operator could be validated, then it was possible to find plans that work for all states in the state-space of the training instance. Thus, one can expect these plans to not be too long, nor particularly difficult to find.

7 Experiments

We evaluate meta-operators on a standard set of IPC benchmarks. All experiments were conducted on a cluster of Intel Xeon CPU E5-2660 with 2.20GHz using Downward Lab [Seipp et al., 2017]. Each run had a time limit of 1800 seconds and a memory limit of 4 GB. The code and data are publicly available [Pham and Torralba, 2023].

7.1 Learning and VerifyingMeta-Operators

First, we analyze the set of meta-operators that can be learned by our approach. For this, we use a small set of 5 instances per domain generated with the publicly available random generators of these IPC domains. As a seed to our method we use macro-operators generated with the Planning Task Transformer (PTT) tool, which implements multiple generation methods: exploiting action dependencies in plans [Chrpa, 2010], MUM [Chrpa et al., 2014], and using inner entanglements [Chrpa et al., 2019]. We learn macros with all three configurations and take the union (which we denote PTT) as a basis for generating meta-operator candidates. Henceforth, we focus on domains for which the PTT set is not empty.

As a sanity check, we ran our validation tool on the set of PTT macro-operators. Interestingly, despite being valid by construction, our tool reported a few cases invalid. As the tool provides the leader plan, this can be used to analyze in what kind of states and instantiations lies the issue. In this case, two parameters were being instantiated by the same object, so that the resulting action had the same fact on the add and delete effects. We fix this by introducing an additional precondition requiring both parameters to be different. This shows that our validation tool can have uses beyond learning meta-actions, like finding bugs during domain modelling.

We validate the candidates by using our meta-operator compilation into a single Stackelberg planning tasks. As Stackelberg planner, we use the symbolic leader search algorithm [Torralba et al., 2021]. We use two configurations that differ on whether the plans computed for the follower are optimal or not. The SLS-opt configuration, used by Torralba et al. [2021], is an optimal symbolic search configuration [Torralba et al., 2017]. The SLS-sat configuration, Total time Search time

100

102

Time GBFS+FF top 2 (s)

uns.

Figure 4: Left: Runtime of optimal and satisficing Stackelberg planners for validating meta-actions/operators. Right: Total and search (excluding plan reconstruction) time with/without meta-operators.

on the other hand, uses Greedy Best-First Search with the FF heuristic [Hoffmann and Nebel, 2001]. In the SLS-sat configuration, we also modify the symbolic leader search algorithm by initializing the initial follower cost to a large constant (105 ). This indicates that the exact follower cost is irrelevant, as we are mainly interested in whether the metaoperator is valid (has a cost lower than ∞) or not. We consider both the problem of validating the entire meta-operator, as well as validating a single meta-action (i.e., a specific instantiation of the operator). For the latter, we sampled 10 instantiations for each instance and meta-operator candidate.

Fig. 4 (left) compares both configurations in terms of runtime. Overall, SLS-sat solves more cases, which is not surprising given that it is a satisficing configuration. But the plot shows that in many cases, we can find the maximum cost required to emulate such behaviour on a specific planning task. Table 2 gives an overview of the number of candidates created by our three methods and how many of them were validated. A meta-operator is validated if either SLS-opt and/or SLS-sat is able to prove that is valid on all 5 training instances. We also considered validated two candidates in the transport domain, where the meta-operator compilation ran out of memory but all sampled instantiations were validated by the meta-action compilation. For most of the rejected candidates, they were shown to not be valid in at least one of the instances. The set of learned meta-operators contains all validated candidates except those that were subsumed either by another candidate, an operator of the domain, or a macrooperator in the PTT set. Here, we consider a meta-operator to be subsumed if it has the same effect and the same or more preconditions, up to renaming of the parameters.

In most domains, we learned meta-operators that describe the effects of the macro-operators in a more succinct way. Our three criteria are very complementary, finding interesting meta-operators in different domains. While many metaoperators have a low cost, meaning that they can be replaced by short sequences of primitive operators, there are also a significant number of cases where the behaviour described by the meta-operator is non-trivial, i.e., at least in some cases it requires more than a handful of primitive actions.

7.2 Planning withMeta-Operators

Our next experiment evaluates whether meta-operators can enhance satisficing planners. We compare the performance

Time GBFS+FF (s)

uns.

102

100

of two planners, implemented in the Fast Downward planning system [Helmert, 2006]: GBFS with the FF heuristic, which is a standard baseline for satisficing planning; and LAMA [Richter and Westphal, 2008], which is a state-ofthe-art satisficing planner. We use the same configuration for finding the plan on the reformulated domain, as well as for reconstructing the plan with only primitive operators. We evaluate on the instances from the IPC, which were not used for learning or validating the meta-operator candidates.

We used three sets of meta-operators. The first set includes all meta-operators validated in the previous phase. Then, we identified the most useful meta-operators by solving a separate set of validation instances, distinct both from the training and the evaluation set. We solve those with multiple domain files: one with all meta-operators, as well as variants with exactly one meta-operator added. Our second set, rel, selects any meta-operator used by any of the plans found. This filters any irrelevant meta-operator that will not be used in plans anyway. Finally, to focus on useful meta-operators, we select only the top 2 (tp2) according to the performance of configurations including exactly one meta-operator on the validation instances. We pick the two that lead to highest coverage, and among those, the ones with lowest total runtime, including the time to find a plan as well as the repair time.

Fig. 4 (right) shows the runtime on IPC instances of the top 2 configuration. Meta-operators are not always helpful, specially on easy instances solved in less than 100s by the baseline. But despite the overhead, there are a number of instances that are solved up to two orders of magnitude faster with meta-operators. This is also reflected in the coverage results of Table 3. Meta-operators improve the coverage on the baseline and, even though they are outperformed when using LAMA, coverage still improves in specific domains like depots or nomystery. This shows that meta-operators have a huge potential to reduce search effort on hard planning tasks.

Regarding the overhead, this is partially due to adding too many additional actions, which explains why using all metaoperators may be detrimental. We alleviated this by using only the top 2 meta-operators, but there is still margin of improvement, e.g. using known enhancements on macrooperators such as outer-entanglements [Chrpa et al., 2018]. On the other hand, the overhead of plan reconstruction can be observed by comparing search and total time in Fig. 4. This is a bottleneck on easy instances, where meta-operators were not too helpful. But when meta-operators significantly reduce search effort on hard instances, it still pays off in total time.

8 Conclusions

Combining multiple primitive operations into macrooperators is a well-known method to reformulate planning problems and plan at a more abstract level. We introduce meta-operators, which define behaviours that can always be accomplished in any state satisfying their precondition, possibly with very different action sequences for different states. This allows for more compact high-level actions with fewer parameters and more focused on useful effects.

We show how to validate whether any invented, or userprovided, meta-operator is valid or not. This requires to check whether there exists any reachable state and instantiation of the meta-operator in which the preconditions are met but achieving the effects is not possible. This can be done efficiently by leveraging Stackelberg planners. This is a powerful tool, that opens many opportunities such as new ways of domain debugging, analyzing properties like undoability, or finding new reformulations for the planning task.

Our experimental results show the potential for using metaoperators as a reformulation technique. Using meta-operators can pay off on hard instances, even when considering the nontrivial plan reconstruction process.