Efficient Black-Box Planning Using Macro-Actions with Focused Effects

1 Introduction

In classical planning, an agent must select a sequence of deterministic, durationless actions to transition from a known initial state to a state that satisfies the desired goal condition. Planning assumes the agent has access to a model of the effects of its actions, which it uses to reason about potential plans. Usually this model takes the form of a PDDL description or finite-domain representation [Fox and Long, 2003; Helmert, 2009], which specifies the preconditions and effects of each action. However, in black-box planning [Lipovetzky et al., 2015; Jinnai and Fukunaga, 2017], the model is instead defined implicitly by a simulator that the agent can query to generate state transitions.

In general, planning is hard: determining whether a plan exists to reach the goal is PSPACE-complete [Bylander, 1994]. Heuristic search eases this computational burden by guiding the search towards promising solutions. Of course, heuristic search is only useful with a good heuristic. In classical planning, much work has gone into the development of domain-independent methods that automatically construct heuristics to exploit as much problem structure as possible from the formal PDDL problem description [Bonet and Geffner, 2001; Hoffmann and Nebel, 2001; Helmert, 2006; Helmert and Domshlak, 2009; Helmert et al., 2014; Pommerening et al., 2015; Keyder et al., 2014; Domshlak et al., 2015]. However, black-box planners have no formal domain description to exploit, and are therefore limited to less-informed heuristics.

∗The first author was at IBM Research for part of this work. Code repository and supplementary materials for this paper are available at https://github.com/camall3n/focused-macros.

One simple, domain-independent heuristic that is compatible with simulator-based planners is the goal-count heuristic [Fikes and Nilsson, 1970], which counts the number of state variables that differ between a given state and the goal. The two basic assumptions of the goal-count heuristic are: a factored state space (i.e. there are state variables to count), and a known goal condition (i.e. there is a reason to modify variables). A third, more subtle assumption is that the problem can be decomposed into subproblems, where each state variable can be treated as an approximately independent subgoal. Unfortunately, this subgoal independence assumption is invalid for most planning problems of practical interest, and thus the goal-count heuristic is often misleading.

A second domain-independent strategy for improving planning efficiency is to use abstraction in the form of high-level macro-actions. When macro-actions are added to the set of low-level actions, they can reduce search tree depth at the expense of increasing the branching factor. In some cases, this has been shown to improve planning efficiency, particularly when the macro-actions cause the problem's subgoals to become independent [Korf, 1985]. We further explore this idea in the context of black-box planning by constructing macros that are well aligned with the goal-count heuristic.

We begin by examining why goal counting becomes uninformative for certain sets of actions. We show that both goalcount accuracy and planning efficiency are linked to how many state variables actions can modify at once. Our investigation suggests a compelling strategy for improving the usefulness of the goal-count heuristic: learning focused macro-actions that modify as few variables as possible, so as to align with the assumptions made by the goal-count heuristic. This approach also seems well-aligned with human problem solving, for example, among expert Rubik's cube solvers, where focused macros are essential for the most efficient planning strategies.

We describe a method for discovering focused macroactions and test it on several classical planning benchmarks, restricting our attention to quickly finding feasible plans, rather than optimal ones, with the goal of minimizing the number of simulator queries. Our learned macro-actions enable reliable and efficient planning, making dramatically fewer calls to the simulator and improving solve rate on most domains. Our approach is designed to improve the goal-count heuristic, but it is compatible with more sophisticated black-box planning techniques as well-with similar improvement. In some cases, black-box planning with focused macros is even competitive with approaches that have access to much more detailed problem information.

2 Background

We consider the problem of black-box planning [Jinnai and Fukunaga, 2017], where the planning agent does not have access to a declarative action description. Formally, we define a black-box planning domain using the following quantities:

• A set of states S, where each state is represented as a vector v and each element vi is a state variable assignment from some finite domain D(vi);
• An action applicability function A(s) that outputs the set of valid grounded actions for the given state s ∈ S;
• A deterministic 1 simulator function Sim(s, a), which the agent can query to determine the next state s′ after executing the action a ∈ A(s) from state s ∈ S.

Each of the above quantities is fixed for all planning problem instances in the domain. A particular problem instance additionally contains:

• A start state, s0 ∈ S;
• A goal condition G, represented as a list of variable assignments to all (or some subset) of the state variables.

The planner's objective is to find a plan that connects state s0 to any state sG that satisfies G via a sequence of actions. In general, actions can have associated costs, and an optimal plan is one that minimizes the sum of its action costs. Here we are concerned with planning efficiency, so we focus on satisficing solutions-that is, finding a plan as quickly as possible, regardless of cost. We measure planning efficiency in terms of the number of simulator queries (equivalently, the number of generated states) before finding a plan.

2.1 The Goal-Count Heuristic

The goal-count heuristic, #g, is defined in terms of the problem-specific goal, G. For any goal condition G, #g(s) counts the number of variables in state s whose values differ from those specified in G, with #g(s) = 0 if and only if s satisfies G. A well-known downside of the goal-count heuristic is its dependence on the size of G. In the extreme case where |G| = 1, the goal-count heuristic only separates goal states from non-goal ones. Nevertheless, due to the relative lack of information in black-box planning, the goal-count is often the only goal-aware heuristic available. Other planners may add additional components, such as state novelty [Franc`es et al., 2017], but the black-box versions of those planners still rely on goal counting at their core.

1 In general, black-box planning can include probabilistic effects, but we leave this more general case for future work.

2.2 Macro-Actions

A macro-action (or macro), is a deterministic sequence of actions, 2 typically for the purpose of accomplishing some useful subgoal. To avoid confusion, we often refer to the original nonmacro actions as "primitive" actions. Macros have parameters, preconditions, and effects, just like primitive actions, but in black-box planning, we again assume that the planner does not have access to such a declarative description. Instead, when planning with macro-actions, there are two alternatives. Either the action applicability function A(s) and simulator function Sim(s, a) are updated to additionally compute macro-action validity and effects in a single step, or alternatively, each primitive action in the macro must be simulated sequentially, with longer macros requiring more simulator queries.

3 Effect Size and Goal-Count Accuracy

The goal-count heuristic implicitly treats each state variable as an independent subgoal. There are two ways to satisfy this assumption exactly. The first is if each subgoal can be achieved in one step without modifying any other state variable. The second, more general way, explored by Korf [1985], is if each subgoal can be achieved in one step (possibly modifying other state variables) and the subgoals are serializable-i.e. there is an ordering of the state variables that retains previously-solved subgoals when solving new ones.

In general, an action can of course change many state variables, and the problem representation may not allow the subgoals to be serialized-both of which can cause the goal-count heuristic to be uninformative. However, for a heuristic to be useful, it does not need to be perfect; it simply needs to be rank correlated with the distance to the goal: higher true distances should correspond to higher heuristic values [Wilt and Ruml, 2015]. When the heuristic is perfectly rank correlated, there is a monotonic relationship between heuristic and true cost, and best-first search will always expand nodes in order of their true distance from the goal.

We hypothesize that if each action modifies only a small number of state variables, the problem will better match the assumptions of the goal-count heuristic, and thus the heuristic and true goal distance will be more positively rank correlated. We informally say such actions have "focused" effects, and we formalize this idea with the following definitions:

Definition 1. The effect size of an action is the maximum number of state variables whose values change by executing the action, over all states where the action is applicable.

Definition 2. The effect size of a macro-action is the maximum number of state variables, measured at the end of macroaction execution, that are different from their starting values, over all states where the macro-action is applicable, even if additional variables were modified during execution.

2 For simulators with probabilistic effects, macro-actions could in principle be generalized to more complex abstract skills incorporating state information, but that extension is beyond the scope of this work.

If our hypothesis above is correct, we expect the goal-count heuristic to be more accurate for domains where actions have smaller effect size, and we further expect this to lead to an improvement in planning efficiency. In the following experiment, we see better rank correlation between heuristic and true distance for domains whose actions have low average effect size, and we see that this leads to an approximately exponential improvement in planning efficiency.

3.1 The Suitcase Lock Domain

To study the relationship between effect size and planning efficiency, we introduce the Suitcase Lock domain. The Suitcase Lock is a planning problem whose solution requires entering a combination on a lock with N dials, each with M digits, and 2N actions, half of which increment a deterministic subset of the dials (modulo M) and the other half of which decrement the same dials (see Figure 1, top). For each problem instance, a start state, goal state, and (fixed) action set are generated randomly, and a parameter k controls the mean effect size across all actions. This allows us to examine action effect size while holding other problem variables constant. For implementation details, see Appendix A of the supplementary materials.

Focused Actions Improve the Goal-Count Heuristic

We first investigate the accuracy of the goal-count heuristic for two small Suitcase Lock problems. For each possible effect size, we compute the true distance between all pairs of states, and compare the results with the goal-count, treating the second state of each pair as the goal. We compute the average heuristic value for each true distance, and then compute the Pearson correlation and Spearman rank correlation coefficients between heuristic and distance. The results are shown in Table 1, where we see that actions with more focused effects (i.e. lower ¯ k) lead to significantly higher correlation.

Focused Actions Improve Planning Efficiency

Next, we run two planning experiments using the goal-count heuristic and greedy best-first search (GBFS). To evaluate planning efficiency, we measure the number of generated states needed to solve each instance, since we care about feasibile plans, rather than optimal ones.

Figure 1 (bottom) shows an approximately exponential relationship between effect size and planning time. When M = 2 and k = 1, the goal-count heuristic is exactly equal to the cost, and GBFS can generate at most N 2 states before finding the goal. By contrast, when k = (N - 1) the heuristic is maximally uninformative, and GBFS may generate N · 2N states in the worst case, since it cannot expand any nodes with heurstic value k until it has expanded all nodes with heuristic value < k. This exponential trend appears to hold even when state variables are not binary.

These results on the Suitcase Lock domain suggest that reducing effect size is a viable strategy for improving planning efficiency. To further investigate this idea, we propose a method for learning macro-actions with low effect size.

4 LearningMacros with Focused Effects

We search for macro-actions using best-first search (BFS) with a simulation budget of BM state transitions. We start the search at a randomly generated state, and the search heuristic is macro-action effect size-or infinity if the macro-action modifies zero variables-plus the number of primitive actions in the macro. Technically, we would need to evaluate each macro from every valid state to determine its effect size, which is clearly infeasible. In practice, we simply measure each macro's effect size once and assume it doesn't change (although we could easily relax this assumption by running the macro from multiple states).

We save the NM macro-actions with the lowest effect size, and ignore duplicate macro-actions that have the same net effect. To encourage diversity of macros, we can optionally repeat the search RM times, each time generating a new random starting state in which none of the existing saved macro-actions are valid, or until we fail to find such a starting state. 3 This ensures that we still find macros that apply in most situations, even if there are constraining preconditions.

The pseudocode for this procedure is in Algorithm 1. We use mi to denote the macro whose action sequence generated Algorithm 1 Learn macro-actions with focused effects Input: Starting state s0, number of macro-actions NM, number of repetitions RM, search budget BM

3 Finding such a state may be as hard as planning, unless the simulator can be reset to generate new starting states; however, in practice, a random walk is often sufficient (see appendix, Note B.2.1).

Output: List of macro-actions LM

• 1: Define g(m) := length(m)
• 2: Define h(s) := { |net effects(s - s0)| if > 0, ∞ otherwise
• 3: Define f(s,m) := g(m) +h(s) where m is the macro (i.e. action sequence) from s0 to s
• 4: Let LM be an empty list of macro-actions
• 5: Let Q be a (max) priority queue of size NM/RM
• 6: for repetition r in {1, ...,RM} do
• 7: Run best-first search (BFS) from s0 with budget BM /RM , minimizing heuristic f (s, m)
• 8: for each state si and macro mi visited by BFS do
• 9: Store mi in Q, with priority h(si) // When Q becomes full, the action sequences // with largest h-score will get evicted first
• 10: end for
• 11: Add each unique macro in Q to LM
• 12: Clear Q
• 13: s0 ←new random state, such that none of the macros in LM can run
• 14: if s0 is None then
• 15: break
• 16: end if
• 17: end for
• 18: return LM

state si. Consider an example with two primitive actions a1 and a2, where BFS starts at state s0. Expanding s0, the action a1 generates s1, and a2 generates s2. Expanding s1, a1 generates s3, and a2 generates s4. Thus macro m4, corresponding to state s4, would be the action-sequence [a1, a2], and we would evaluate its net effect by comparing s4 with s0.

5 Experiments

We evaluate our method by learning macro-actions in a variety of black-box planning domains and subsequently using them for planning. We use PDDLGym [Silver and Chitnis, 2020] to automatically construct black-box simulators from classical PDDL planning problems. Additionally, we use two domainspecific simulators (for 15-puzzle and Rubik's cube) that have a different state representation to show the generality of our approach. See the appendix for implementation details and a discussion of how we selected the various macro-learning hyperparameters (sections B and E, respectively).

We select the domains to give a representative picture of how the method performs on various types of planning problems. For PDDLGym compatibility reasons, we restrict the domains to those requiring only strips and typing. For the domain-specific simulators, we select 15-puzzle and Rubik's cube in particular, because they present opposing challenges for our macro-learning approach. In 15-puzzle, primitive actions have very focused effects (each modifies only the blank space and one numbered tile), but naively chosen macroactions tend to have much larger effect sizes, and both primitive actions and macros have state-dependent preconditions. In Rubik's cube, actions and macros have no preconditions, but primitive actions are highly non-focused (each modifies 20 of the simulator's 48 state variables) and the state space is so large (∼4.3×1019 unique states [Rokicki, 2014]) that black-box planning is unable to solve the problem efficiently.

5.1 Methodology

For each planning domain, we generate 100 problem instances with unique random starting states and a fixed goal condition. 4 All problem instances share the same state space, and the planner has access to the simulator function, the action applicability function, a vector of state information, and the goal condition. We emphasize that although the PDDLGym domains are specified using PDDL, the planner never sees the PDDL during either macro search or planning.

We learn focused macro-actions as described in Sec. 4 and add them to the set of primitive actions, which ensures that the same set of states can still be reached. These macros are then used to update the simulator and action applicability function, allowing the learned macros to execute in a single step for improved computational efficiency. 5 Note that updating the simulator in this way does not reduce search effort, only time. Even if the primitive actions in a macro were simulated oneby-one, the intermediate states are neither stored nor explored, and hence do not count towards the number of generated states.

The macros are learned once, for the first problem instance, and then reused on all remaining problem instances for that domain. In general, it can be challenging to incorporate macros into any planning algorithm, since one must weigh their search benefits against the increased branching factor. For simplicity, our experiments fixed the number of macros NM (see Table 2), but in principle NM could be chosen automatically based on which macros reduce the problem's average effect size.

To solve each planning problem, we use greedy best-first search (GBFS) with the goal-count heuristic and compare performance with the additional learned macro-actions versus with primitive actions alone. We measure planning efficiency as the number of simulator queries that the planner makes before finding a plan. This choice of performance metric is the most natural fit for black-box planning, and it allows for fair comparisons of algorithms across different implementation languages and hardware configurations.

In Table 2, we show the average solve rate and number of generated states (i.e. simulator queries) for each domain. Since we only pay the macro-learning cost BM for the first problem instance, we can in principle amortize this cost over the total number of problem instances. (Note that the BM values reported in the table are non-amortized and are separate from the number of generated states.) Except in the case of Depot, we see that planning with focused macros increases solve rate and improves planning efficiency by up to an order of magnitude versus planning with primitive actions alone. In Rubik's cube, focused macros still perform better, even if we account for the entire macro-learning budget.

4 All problem instances are included in the code repository.

5 See Appendix C for details on how we update the simulator and action applicability function to incorporate the learned macros.

5.2 Comparisons with Other Planners

In addition to greedy best-first search (GBFS) with the goalcount heuristic, we also evaluate our method in conjunction with Best-First Width Search, or BFWS [Lipovetzky and Geffner, 2017], a family of search algorithms that augment their search heuristic with a novelty metric computed using Iterated Width (IW) search [Lipovetzky and Geffner, 2012].

We specifically use the best-performing black-box planning version of BFWS: BFWS(R∗G) [Franc`es et al., 2017]. This version starts by running IW up to two times, with increasing precision, to generate a set R∗G of goal-relevant atoms. During search, each state s is evaluated based on how many relevant atoms were satisfied at some point along the path to s. This forms a relevance count #r(s), which is combined with the goal-count #g(s) to compute the novelty width metric w#r,#g. The algorithm runs GBFS using heuristic (w, #g, c), evaluating nodes first by width, breaking ties with #g, and then breaking further ties with c, the cost to reach the node.

We ran BFWS on each domain and measured its planning efficiency (see Table 2). We followed Lipovetzky and Geffner [2017] and limited the width precision to w ∈ {1,>1} on Depot and Rubik's cube to save computational resources.

Again we find that focused macros substantially improve planning efficiency, likely because the heuristic still uses goal counting at its core. Surprisingly, we found that BFWS did not perform significantly better than the primitive-action GBFS baseline. In fact, comparing against GBFS, we observe that focused macros alone are more beneficial for planning than the more sophisticated novelty-based heuristic.

As a point of reference, we also compared against LAMA [Richter and Westphal, 2010] which has full access to a declarative representation of the problem-information far beyond what is available to black-box planners. We ran the first iteration of LAMA on the same problems we used with PDDLGym, as well as a SAS+ representation of the Rubik's cube, adapted from B¨uchner [2018]. On a different PDDL version of Rubik's cube, LAMA failed to complete the translation step before running out of memory (16GB). We find our method is competitive with LAMA, across the majority of domains, despite the fact that LAMA has access to more information. On the 100 hardest Rubik's cube problems from B¨uchner [2018], which neither primitive-action baseline can solve, LAMA generates 9.1 million states on average, whereas our approach generates only 171 thousand.

5.3 Comparison with RandomMacros

One might wonder whether the improvements in planning efficiency are due to the macros' focused effects, or simply the fact that we are using macros at all. To isolate the source of the improvement, we conducted a second experiment using 15-puzzle and Rubik's cube. Here we compared the focused macro-actions against an equal number of "random" macroactions of the same length, which were generated (for each random seed) by selecting actions uniformly at random from the valid actions at each state.

We present the results in Table 3, as well as Figures 2a and 2b, where we observe that random macros perform significantly worse than both the primitive actions and the learned focused macros. In both domains, randommacros also consistently had larger effect sizes than focused macros. Figure 2c shows a visualization of Rubik's cube macro effect size versus macro length. We suspect the higher planning cost of random macros is partly due to their increased effect size.

5.4 Examining Expert Macros in Rubik's Cube

Expert human "speedcubers" use macro-actions to help them manage the Rubik's cube's highly non-focused actions. In speedcubing, the goal is to solve the cube as quickly as possible, without necessarily finding an optimal plan. Most speedcubers learn a collection of macro-actions (called "algorithms" in Rubik's cube parlance) and then employ a strategy for sequencing those macro-actions to solve the cube. Expert macro-actions tend to affect only a small number of state variables, and proper sequencing enables speedcubers to preserve previously-solved parts of the cube while solving the remainder. Common solution methods typically involve multiple levels of hierarchical subgoals and produce plans approximately twice as long as optimal.

As a benchmark, we consider a simplification of the most common expert strategy, where macros are composed of just primitive actions. We select a set of six hand-coded, expert macro-actions to perform various complementary types of permutations. 6 We visualize one of these macro-actions, which swaps three corner pieces, in Figure 3a. Since our simulator uses a fixed cube orientation, we consider all 96 possible variations of each macro (to account for orientation, mirror-flips, and inverses), resulting in 576 total macros-the same number used for the random macro and focused macro trials.

In Figure 2c, we plot the effect size and length of each macro, labeled by macro type. We can see that the focused macros have significantly smaller effect size than primitive actions or random macros, and begin to approach the effect size of the expert macro-actions. We also note that the focused macros are somewhat shorter on average than the expert macros, and we suspect that increasing the search budget would result in learning macros with even smaller effects.

In Table 3 and Figure 2b, we compare planning with the expert macros against the other macro types and see that while planning with the expert macros is the most efficient, the learned, focused macros are not far behind. By contrast, the random macros and primitive actions never solved the problem within the simulation budget. We also found that the average solution length for focused and expert macro-actions was about an order of magnitude longer than typical human speedsolve solutions (378 and 319 primitive actions, respectively, vs. ~60 [Speedsolving Wiki, 2021]), which suggests that there are additional insights to be mined from human strategy beyond just learning focused macro-actions.

6 Macro-action sequences are included in Appendix D.

5.5 Interpretability of FocusedMacros

We examined the learned focused macros for several domains and found that in addition to having low effect size, they were also frequently easy to interpret. In 15-Puzzle, one type of macro swapped the blank space with a central tile; another type exchanged three tiles without moving the blank space. In Rubik's cube, one macro (Figure 3b) swapped three edgecorner pairs while keeping them connected. In Tower of Hanoi, macros moved stacks of disks at a time from one peg to another. We remark that this is quite similar to the interpretability of the human expert macros in Rubik's cube.

5.6 Generalizing to Novel Goal States

Since our macro-generation step is goal-independent, we can reuse previously learned macros to solve problems with novel goal states. To demonstrate this, we generate 100 random goal states for 15-puzzle and Rubik's cube and then solve the puzzles again. In both domains, we find that planning time and solve rate remain effectively unchanged for novel goal states (see Table 4).

(a) Expert 3-corner-swap

(b) Learned 3-pair-swap

Figure 3: Expert and learned macro-actions (Rubik's cube).

6 RelatedWork

The concept of building macro-actions to improve planning efficiency is not new. Dawson and Siklossy [1977] considered two-action macros and analyzed domain structure to remove macros that were invalid or that had no effect. Korf's [1985] Macro Problem Solver investigated how to learn macros in problems with decomposable operators and serializable subgoals. Macro-FF [Botea et al., 2005] and MUM [Chrpa et al., 2014] learned macros from training problem instances and later used them to improve the planning efficiency of testing instances. The macros we discover in Sections 4 and 5 can similarly be reused across problem instances; however, our macro discovery procedure requires neither goal information nor training instances. Our method is perhaps most similar to MARVIN [Coles and Smith, 2007], which used macros to escape plateaus during heuristic search, and CAP [Asai and Fukunaga, 2015], which decomposed planning problems into subgoals and then found macros to achieve those subgoals. In all of the prior approaches, the learned macros were found to be beneficial for planning, but they also required an explicit model of the domain. Our method is more general than these methods, as it is designed to handle the unique challenges of black-box planning without an explicit model.

Lipovetzky and Geffner [2012] introduced Iterated Width (IW) search, a "blind" planner compatible with black-box simulators, and Lipovetzky et al. [2015] subsequently applied it to planning in Atari video game simulators without known goal states. This work led to the goal-informed Best-First Width Search (BFWS) [Lipovetzky and Geffner, 2017; Franc`es et al., 2017], which we include in our experimental evaluation. Jinnai and Fukunaga [2017] formalized black-box planning and described a method for pruning primitive actions and short macros to avoid generating duplicate states; however their approach did not incorporate goal information.

Recent work by Agostinelli et al. [2019] investigated how to train black-box planning heuristics with neural networks and dynamic programming by strategically resetting the simulator to states near the goal state. Their approach learned heuristics for several domains, including 15-puzzle and Rubik's cube, that supported fast, near-optimal planning. However, training their neural network requires more than 1000 times the simulation budget of our approach, and results in a heuristic that is only informative for a single goal state, whereas ours works for arbitrary goal states.

7 Discussion and Conclusion

We have described a method of learning focused macro-actions that enables reliable and efficient black-box planning across a variety of classical planning domains. While our approach is designed to match the assumptions of the goal-count heuristic, we find that it also improves the performance of more sophisticated black-box planners. Moreover, our method is even competitive with a state-of-the-art LAMA planner, despite the latter having access to a declarative description of the problem.

We are encouraged to see that many of the learned macroactions had intuitive, interpretable meaning in the task domain. This suggests that our method may be useful for improving explainability in addition to planning efficiency.

This work employed a two-level hierarchy where macroactions are composed of primitive actions. One extension to bring this method more in line with human-expert techniques would be incorporating additional levels of action hierarchy (i.e. macros composed of other macros), or macros that permit side-effects to certain unsolved variables, combined with macros to subsequently solve those remaining variables. We leave an exploration of these ideas for future work.

Acknowledgements

We thank Yuu Jinnai and Eli Zucker for many insightful discussions, Tom Silver and Rohan Chitnis for their help with PDDLGym, the anonymous IJCAI'20, AAAI'21, IJCAI'21, and ICAPS'21 HSDIP reviewers for their excellent feedback on earlier versions of this paper, and our colleagues at IBMResearch and Brown University for their thoughtful conversations and support. This research was supported in part by the ONR under the PERISCOPE MURI Contract N00014-17-1-2699.