\section{Introduction}
\noindent In classical planning, an agent must select a sequence of deterministic, durationless actions to transition from a known initial state to a desired goal state. 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 \cite{fox2003pddl2,helmert2009concise}, which specifies the preconditions and effects of each action, or is implicitly defined by a black-box simulator \cite{lipovetzky2015classical,jinnai2017learning} that the agent can query to generate state transitions.

In general, planning is hard: determining whether a plan exists to reach the goal is \textit{PSPACE}-complete \cite{bylander1994computational}. 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 \cite{bonet2001planning,hoffmann2001ff,helmert2006fast,Helmert2009Landmarks,Helmert2014MergeandShrink,Pommerening2015FromNonNegative,Keyder2014ImprovingDelete,Domshlak2015RedBlack}. However, simulator-based black-box planners have no formal domain description to exploit, and are therefore limited to less-informed heuristics. This poses a problem because an informative heuristic is especially important for simulator-based planning, where querying the simulator can be computationally expensive.

One of the simplest domain-independent heuristics compatible with simulator-based planners is the goal-count heuristic \cite{fikes1971strips}, which counts the number of state variables that differ between a given state and the goal. 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 state (i.e. there is a reason to fix 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 \citep{korf1985macro}. 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 the goal-count heuristic becomes uninformative for certain sets of actions. We show that planning efficiency is 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 \textit{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 learning focused macro-actions and test it on several classical planning benchmarks, focusing our attention on 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 for black-box planning with the goal-count heuristic, but it is compatible with---and improves on---more sophisticated heuristic search techniques as well, and is competitive with approaches that have access to much more detailed problem information.

\section{Background}
\subsection{Black-Box Planning}
We consider the problem of black-box planning \citep{jinnai2017learning}, 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:
\begin{itemize}
    \item A set of states $S$, represented as vectors of state variables (or literals), with each variable $v_i$ taking on a finite number of values in some domain $D(v_i)$;
    \item An action function $A(s)$ that outputs the set of valid grounded actions for the given state $s \in S$;
    \item A deterministic\footnote{In general, black-box planning can include probabilistic effects, but we leave this more general case for future work.} simulator function $\textrm{Sim}(s,a)$, which the agent can query to determine the next state $s'$ after executing the action $a \in A(s)$ from state $s \in S$.
\end{itemize}
Each planning problem instance additionally contains:
\begin{itemize}
    \item A start state, $s_0$, represented as a vector of state variables;
    \item A goal $G$, represented as a conjunction of literals.\footnote{Single-state goals can be expressed as conjunctions with one literal per state variable.}
\end{itemize}

\noindent The planner's objective is to find a plan that connects state $s_0$ to a state $s_G$ 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 \textit{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.

\subsection{The Goal-Count Heuristic}
The goal-count heuristic, $\#g$, is defined in terms of the problem-specific goal, $G$. For any goal conjunction $G$, $\#g(s)$ counts the number of literals in $G$ that are not true in state $s$, with $\#g(s)=0$ if and only if $s$ satisfies $G$. Note that if $G$ is a single state, $\#g(s)$ simply counts the number of state variables in $s$ whose values differ from those in $G$.

\subsection{Macro-Actions}
A \textit{macro-action} (or \textit{macro}), is a deterministic sequence of actions,\footnote{If the simulator has probabilistic effects, macro-actions could in principle be generalized to more complex abstract skills that incorporate state information; however such skills are beyond the scope of this work.} typically for the purpose of accomplishing some useful subgoal. To avoid confusion, we often refer to the original non-macro actions as ``primitive'' actions. Macros have parameters, preconditions, and effects, just like the primitive actions, but in black-box planning, we again make the assumption that the planning agent does not have access to such a declarative description. Instead, when an agent is planning with macro-actions, the action function $A(s)$ must output the valid macro-actions $m$ alongside the valid primitive actions $a$ in state $s$, and the simulator function $\textrm{Sim}(s,m)$ must output the final state $s'$ after executing the entire macro-action $m$, starting from state $s$. In this work, we assume the action and simulator functions can easily be modified to support macro-actions in this way.

\section{The Connection Between Effect Size and Planning Efficiency}
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 \citet{korf1985macro}, 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 the goal-count heuristic to be useful, it does not need to be perfect; it simply needs to be \textit{rank correlated} with the distance to the goal: higher true distances should correspond to higher heuristic values. 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:

\textbf{Definition 1.} The \textit{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.

\textbf{Definition 2.} The \textit{effect size of a macro-action} is the maximum number of state variables, measured at the end of macro-action 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.

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.

\subsection{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 which increment a deterministic subset of the dials (modulo $M$), and half which decrement the same dials (see Figure \ref{fig:suitcase-results}). Let $k_i$ denote the effect size of action $a_i$, and $\bar{k}$ denote the mean effect size across all actions. Given a $\bar{k}$, we generate problem instances with different start states, goal states, and sets of actions such that they have mean effect size $\bar{k}$. This allows us to examine action effect size while holding other problem variables fixed.

Regardless of $\bar{k}$, we ensure that every state can always be reached from every other state. Note that if $\bar{k}=N$, or if all actions modify (for example) an even number of state variables, it is not possible to reach every state from every other state. To circumvent this issue, we check that for a given problem instance, the increment and decrement action sets can each be reduced to an $N\times N$ binary matrix with full rank. We repeatedly generate action sets with the desired mean effect size until we find one that satisfies this condition. The resulting action sets are therefore different for each random seed, except when $\bar{k}=1$ where we always use the identity matrix $I$, and when $\bar{k}=(N-1)$ where we use $1-I$ with an extra 1 added to the first diagonal element to break symmetry. The decrement actions are always the negation of the increment actions, and we ignore them for $M=2$.

\begin{figure}[t]
\centering
\begin{subfigure}{.22\textwidth}
  \centering
  \includegraphics[width=.55\textwidth]{images/suitcaselock}
  \caption*{}
\end{subfigure}%
\\
\begin{subfigure}{.23\textwidth}
  \centering
  \includegraphics[width=.95\textwidth]{images/suitcaselock_2ary}
  \caption*{$N=20, M=2$}
\end{subfigure}%
\begin{subfigure}{.23\textwidth}
  \centering
  \includegraphics[width=.95\textwidth]{images/suitcaselock_4ary}
  \caption*{$N=10, M=4$}
\end{subfigure}
\caption{(Top) The Suitcase Lock domain with $N=4$; (Bottom) Generated states vs. effect size for Suitcase Lock}
\label{fig:suitcase-results}
\end{figure}

\subsection{Focused Actions Improve the Goal-Count Heuristic}
We first investigate the accuracy of the goal-count heuristic for two small Suitcase Lock problems: one with $N=10$ and $M=2$; and the other with $N=5$ and $M=4$. For each possible effect size $\bar{k} \in \{1,...,N-1\}$, 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 across 10 random seeds for each $\bar{k}$, and then compute the Pearson correlation and Spearman rank correlation coefficients between heuristic and distance. The results are shown in Table \ref{tab:correlation}, where we see that actions with more focused effects (i.e. lower $\bar{k}$) lead to significantly higher correlation.

\begin{table}[t]
\centering
\begin{tabular}{crrrr}
\toprule
Effect Size  & \multicolumn{2}{c}{\textbf{N=10, M=2}} & \multicolumn{2}{c}{\textbf{N=5, M=4}}\\
$\bar{k}$ & $\rho_P$ & $\rho_S$ & $\rho_P$ & $\rho_S$ \\
\midrule
1 & 1.000 &  1.000 & 0.775 &  0.760 \\
2 & 0.200 &  0.179 & 0.263 &  0.226 \\
3 & 0.110 &  0.092 & 0.046 &  0.018 \\
4 & 0.060 &  0.041 & 0.000 & -0.044 \\
5 & 0.020 &  0.013 & -- & -- \\
6 & 0.000 & -0.007 & -- & -- \\
7 & 0.000 &  0.001 & -- & -- \\
8 & 0.000 & -0.001 & -- & -- \\
9 & 0.000 &  0.005 & -- & -- \\
\bottomrule
\end{tabular}
\caption{Correlation results between the goal-count heuristic and true distance for Suitcase Lock. Actions with smaller effect size ($\bar{k}$) lead to significantly higher Pearson's correlation ($\rho_P$) and Spearman's rank correlation ($\rho_S$) coefficients.}
\label{tab:correlation}
\end{table}


\subsection{Focused Actions Improve Planning Efficiency}
To evaluate planning efficiency, we measure the number of generated states needed to solve each instance of the planning problem. We run two experiments: first with $N=20$ and $M=2$, and second with $N=10$ and $M=4$, with $\bar{k}$ varying in the range $\{1,...,N-1\}$. We use the goal-count heuristic and greedy best-first search, since we care about feasible plans, rather than optimal ones, and we evaluate performance across $100$ different random seeds.

Figure \ref{fig:suitcase-results} shows an approximately exponential relationship between effect size and planning time. Note that the goal-count heuristic is exactly equal to the cost when $M=2$ and $k=1$, and greedy best-first search (GBFS) generates at most ${N}^2$ states. By contrast, when $k=(N-1)$ the heuristic is maximally uninformative, and GBFS may generate $N\cdot 2^{N}$ states in the worst case. This exponential trend appears to hold even when the 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.

\section{Learning Macros with Focused Effects}
We search for macro-actions using best-first search with a simulation budget of $B_M$ state transitions. We start the search at a randomly generated state, and the search heuristic is macro-action effect size (the number of variables modified by the macro-action)---or infinity if the macro-action modifies zero variables---plus the number of primitive actions in the macro. We save the $N_M$ macro-actions with the lowest effect size, and ignore duplicate macro-actions that have the same net effect. To encourage diversity in the macros, we repeat the search $R_M$ 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. This ensures that even if macros have constraining preconditions, we will still find macros that apply in most situations. (See Algorithm \ref{alg:algorithm} for pseudocode.)

\begin{algorithm}[t]
\caption{Learn macro-actions with focused effects}
\label{alg:algorithm}
\textbf{Input}: Starting state $s_0$, number of macro-actions $N_M$, number of repetitions $R_M$, search budget $B_M$\\
\textbf{Output}: List of macro-actions $L_M$\\
\begin{algorithmic}[1]
\STATE \textbf{Define} $g(m) := \mathrm{length}(m) $\\
\STATE \textbf{Define} $h(s) := \left\{
	\begin{array}{ll}
	    |\mathrm{net\_effects}(s-s_0)| & \mbox{if } > 0,\\
		\infty  & \text{otherwise}
	\end{array}
\right.$
\STATE \textbf{Define} $f(s,m) := g(m) + h(s)$\\
where $m$ is the macro (i.e. action sequence) from $s_0$ to $s$\\
\hspace{10px}
\STATE Let $L_M$ be an empty list of macro-actions
\STATE Let $Q$ be a (max) priority queue of size $N_M/R_M$
\FOR{repetition $r$ in $\{1,...,R_M\}$}
\STATE Run best-first search (BFS) from $s_0$ with budget $B_M/R_M$, minimizing heuristic $f(s,m)$
\FOR{each state $s_i$ and macro $m_i$ visited by BFS}
\STATE Store $m_i$ in $Q$, with priority $h(s_i)$\\
// When $Q$ becomes full, the action sequences\\
// with largest $h$-score will get evicted first
\ENDFOR
\STATE Add each unique macro in $Q$ to $L_M$
\STATE Clear $Q$
\STATE $s_0 \gets$ new random state, such that none of the macros in $L_M$ can run
\IF {$s_0$ is None}
\STATE \textbf{break}
\ENDIF
\ENDFOR
\STATE \textbf{return} $L_M$
\end{algorithmic}
\end{algorithm}


\section{Experiments}
We evaluate our method by learning macro-actions in a variety of black-box planning domains and subsequently using them for planning.\footnote{Code at \url{https://github.com/camall3n/skills-for-planning}}
First we use PDDLGym \citep{silver2020pddlgym} to automatically construct black-box simulators from classical PDDL planning problems, then we use two domain-specific simulators (for 15-puzzle and Rubik's cube) that have a different state representation to show the generality of our approach.

We select the domains to give a representative picture of how the method performs on various types of planning problems. For compatibility reasons, we limit the PDDLGym domains to ones that only require \texttt{strips} and \texttt{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 macro-actions 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\footnote{Approximately $4.3 \times 10^{19}$ unique states \citep{rokicki2014gods}} that black-box planning is unable to solve the problem efficiently.

\subsection{Methodology}
For each planning domain, we generate 100 problem instances with unique random starting states and a fixed goal condition.\footnote{We include all problem instances in the code repository for reproducing our results.} The planner has access to the simulator function, the action availability 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 using Algorithm \ref{alg:algorithm} 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 availability functions.\footnote{ For details on how we update the simulator and action availability functions to incorporate the learned macros, see the supplementary materials.} Updating the simulator allows it to execute the learned macros in a single step for improved computational efficiency. The macros are learned once, for the first problem instance, and then reused on all remaining problem instances for that domain. 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.

\begin{table*}[t]
\centering
\begin{tabular}{lrrrrrrrrrrrr}
\toprule
       &    &    &  \multicolumn{2}{c}{GBFS(A)}  &   \multicolumn{2}{c}{GBFS(A+M)}  &   \multicolumn{2}{c}{BFWS(A)}    &    \multicolumn{2}{c}{BFWS(A+M)}   &    \multicolumn{2}{c}{LAMA(A)} \\
\cmidrule(lr){4-7}\cmidrule(lr){8-11}\cmidrule(lr){12-13}
Domain        &  $N_M$  &  $B_M$  &  Gen & Sol  &  Gen & Sol  &   Gen & Sol    &    Gen & Sol   &    Gen & Sol \\

\midrule
Depot    & 8 & 50K  & 58275.9 & \textbf{0.74} & \textbf{55132.4} & 0.60          & 75966.9 & \textbf{0.48} & \textbf{72205.8} & 0.34 &  46620.9 & 1.00 \\
Doors    & 8 & 5K   &  3050.7 & 1.00          &   \textbf{512.6} & 1.00          &  4660.9 & 1.00 & \textbf{3057.3} & 1.00 &    293.0 & 1.00 \\
Ferry    & 8 & 5K   &  1875.8 & 1.00          &  \textbf{1151.4} & 1.00          &  1209.9 & 1.00 & \textbf{1163.5} & 1.00 &    699.8 & 1.00 \\
Gripper  & 8 & 5K   &  7314.8 & 1.00          &  \textbf{6277.0} & 1.00          & 44945.9 & 1.00 & \textbf{6295.9} & 1.00 &   6493.1 & 1.00 \\
Hanoi    & 8 & 100K & 78433.6 & 0.78          &  \textbf{6358.8} & \textbf{1.00} & 63455.2 & 1.00 & \textbf{3365.9} & 1.00 &  65496.4 & 1.00 \\
Miconic  & 8 & 5K   &  7559.4 & 1.00          &  \textbf{1907.1} & 1.00          & 10269.2 & 1.00 & \textbf{1884.3} & 1.00 &   1316.7 & 1.00 \\
\midrule
15-puz  &      1600  &            1M  &  30840.5 & 1.00  & \textbf{3980.4} & 1.00  &  109425.2 & 1.00  &    \textbf{3872.1} & 1.00  &         -- & -- \\
Rubik's    &       576  &            1M  &       $>$2M & 0.00  &   \textbf{171.3K} & \textbf{1.00}  &       $>$2M & 0.00  &  \textbf{163.8K} & \textbf{1.00}  &  9.13M & 1.00 \\
\bottomrule\\
\multicolumn{13}{c}{(A) - primitive actions only; (A+M) - primitive actions + focused macros}\\
\multicolumn{13}{c}{$N_M$ - number of macros; $B_M$ - macro-learning budget; Gen - generated states; Sol - solve rate;}
\end{tabular}
\caption{Planning results for PDDLGym-based simulators (top), and domain-specific simulators (bottom). Adding focused macros improves planning efficiency and solve rate.}
\label{tab:results-all}
\end{table*}

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. Because we customize the simulator to handle the learned macros, each macro application results in just a single generated state. In Table \ref{tab:results-all}, we show the average solve rate and number of generated states (i.e. simulator queries) for each domain. Except in the case of Depot, we see that planning with focused macros increases solve rate and improves planning efficiency up to an order of magnitude versus planning with primitive actions alone.

\subsection{Comparison Against Other Techniques}
In addition to greedy best-first search (GBFS) with the goal-count heuristic, we also evaluate our method in conjunction with Best-First Width Search, or BFWS \citep{lipovetzky2017best}, a family of search algorithms that augment their search heuristic with a novelty metric computed using Iterated Width (IW) search \citep{lipovetzky2012width}. We specifically use the best-performing black-box planning version, BFWS($R^*_G$) \citep{frances2017purely}.

BFWS($R^*_G$) begins with a preprocessing step that runs IW up to two times, with increasing precision, to generate a set $R^*_G$ of goal-relevant atoms. Then during search, the algorithm evaluates each state $s$ based on how many of those 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 $(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 \ref{tab:results-all}). We followed \citet{lipovetzky2017best} and limited the width precision to $w \in \{1, \textrm{\textgreater}1\}$ on Depot and Rubik's cube to save computational resources. In every domain, goal-count based GBFS with our focused macros resulted in fewer generated states than BFWS with primitive actions. Surprisingly, we found that BFWS did not perform significantly better than the primitive-action GBFS baseline. Next, we tried combining BFWS with our previously-learned, focused macros. The macros substantially improved BFWS's planning efficiency as well, despite being designed to complement the goal-count heuristic.

As a benchmark, we also compared against LAMA \cite{richter2010lama}, a planner with full access to a declarative representation of the problem. We ran LAMA\footnote{Implemented in Fast Downward \cite{helmert2006fast}. We use only the first iteration of LAMA, \texttt{--alias lama-first}, since we care about satisficing plans.} on the same problems we used with PDDLGym, as well as a \rm{SAS}$^{+}$ representation of the Rubik's cube, adapted from \citet{buchner2018abstraction}.\footnote{On a different PDDL version of the Rubik's cube, LAMA failed to complete the translation step before using all of its 16GB of memory.} 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 \citet{buchner2018abstraction}, we find that LAMA generates 9.1M states on average, while our approach generates only 171K.

\subsection{Comparison with Random Macros}
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'' macro-actions 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 \ref{tab:results-by-macro-type}, and Figures \ref{fig:npuzzle-planning} and \ref{fig:cube-planning}, where we observe that random actions perform significantly worse than both the primitive actions and the focused macros. For Rubik's cube, focused macros still perform better, even if we account for the additional simulation budget required to learn them. We inspected the random macros for both domains, and found that they consistently had larger effect sizes than the learned, focused macros. Figure \ref{fig:cube-entanglement} shows a visualization of Rubik's cube macro effect size versus macro length. We suspect the higher planning cost with random macros is partly due to their increased effect size.\\

\begin{table}[h]
\centering
\begin{tabular}{lrrr}
\toprule
 & Generated & Remaining & Solve \\
 &  States & Errors & Rate \\
\midrule
\textbf{15-Puzzle}\\
\midrule
Primitives only    &  30840.5 & 0.0 & 1.0 \\
Random macros      & 120764.8 & 0.0 & 1.0 \\
Focused macros     & \textbf{3980.4} & 0.0 & 1.0 \\
\midrule
\midrule
\textbf{Rubik's Cube} &   &  &  \\
\midrule
Primitives only & $>$2M             & 11.8 &  0.0 \\
Random macros   & $>$2M             & 16.4 &  0.0 \\
Focused macros  & \textbf{171331.4} & \textbf{0.0} & \textbf{1.0} \\
\midrule
Expert macros   &  30229.1  & 0.0 & 1.0 \\
\bottomrule
\end{tabular}
\caption{Planning results for 15-puzzle and Rubik's cube comparing different action spaces. Random macros perform significantly worse than both primitive actions and focused macros. Trials with macros also contain the primitive actions.}
\label{tab:results-by-macro-type}
\end{table}

\begin{figure}[t]
  \centering
  \includegraphics[width=.45\textwidth]{images/npuzzle_planning_time}
  \caption{15-puzzle planning efficiency by macro type}
  \label{fig:npuzzle-planning}
\end{figure}

\subsection{Comparison with 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 expert macro-actions to perform various complementary types of permutations.\footnote{We use the following expert macro-actions (expressed in standard cube notation \cite{singmaster1981notes}):\\- Swap three corners: $L'\,B\,L\,F'\,L'\,B'\,L\,F$ (see Fig. \ref{fig:cube-expert})\\
    - Swap three middle edges: $L'\,R\,U\,U\,R'\,L\,F\,F$\\
	- Swap three face edges: $R\,R\,U\,R\,U\,R'\,U'\,R'\,U'\,R'\,U\,R'$\\
	- Rotate two corners: $R\,B'\,R'\,U'\,B'\,U\,F\,U'\,B\,U\,R\,B\,R'\,F'$\\
	- R-permutation: $F\,F\,R'\,F'\,U'\,F'\,U\,F\,R\,F'\,U\,U\,F\,U\,U\,F'\,U'$\\
	- Flip two edges: $L\,R'\,F\,L\,R'\,D\,L\,R'\,B\,L\,R'\,U\,U\,L\,R'\,F\,L\,\\ R'\,D\,L\,R'\,B\,L\,R'$
	}
We visualize one of these macro-actions, which swaps three corner pieces, in Figure \ref{fig:cube-expert}. 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 \ref{fig:cube-entanglement}, 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 note that our learned 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.

\begin{figure}[t]
\centering
\includegraphics[width=.45\textwidth]{images/cube_planning}
\caption{Rubik's cube planning performance by macro type}
\label{fig:cube-planning}
\end{figure}


In Table \ref{tab:results-by-macro-type} and Figure \ref{fig:cube-planning}, 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 observed that the average solution length for focused and expert macro-actions is about an order of magnitude longer than typical human speedsolve solutions (378 and 319 primitive actions, respectively, vs. \texttildelow$55$ \cite{speedsolving2019cfop}), which suggests that there are additional insights to be mined from human strategy beyond just learning focused macro-actions.

\begin{figure}[t]
\centering
\includegraphics[width=.45\textwidth]{images/cube_entanglement}
\caption{Effect size vs. length of Rubik's cube macro-actions, by type. (Some points overlap.)}
\label{fig:cube-entanglement}
\end{figure}

\subsection{Interpretability of Focused Macros}
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 \ref{fig:cube-learned}) swapped three edge-corner pairs while keeping them connected. In Tower of Hanoi, one of the PDDLGym domains, 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.

\begin{figure}[t]
\centering
\begin{subfigure}{.188\textwidth}
  \centering
  \includegraphics[width=.98\textwidth]{images/cube-expert}
  \caption{Expert 3-corner-swap\\\centering$L'\,B\,L\,F'\,L'\,B'\,L\,F$}
  \label{fig:cube-expert}
\end{subfigure}%
\quad\quad
\begin{subfigure}{.232\textwidth}
  \centering
  \includegraphics[width=.794\textwidth]{images/cube-learned}
  \caption{Learned 3-pair-swap \\\centering$F'\,L\,F'\,L'\,F\,F\,R\,U'\,R'\,F'\,U\,F$}
  \label{fig:cube-learned}
\end{subfigure}
\caption{Expert and learned macro-actions (Rubik's cube)}
\label{fig:cube-macros}
\end{figure}

\subsection{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 \ref{tab:alt-goals}).\\

\begin{table}[h]
\centering
\begin{tabular}{llrr}
\toprule
Domain & Goal & Generated & Solve\\
       & Type & States    & Rate \\
\midrule
15-puzzle & Default   & 3980.4 & 1.0 \\
& Random    & 4520.0 & 1.0 \\
\midrule
Rubik's cube & Default  & 171331.4 & 1.0 \\
& Random    & 152503.7 & 1.0 \\
\bottomrule
\end{tabular}
\caption{Average planning efficiency and solve rate vs. goal type, when reusing previously learned focused macros}
\label{tab:alt-goals}
\end{table}

\section{Related Work}
The concept of building macro-actions to improve planning efficiency is not new. \citet{dawson1977role} considered two-action macros and analyzed domain structure to remove macros that were invalid or that had no effect. \poscite{korf1985macro} Macro Problem Solver investigated how to learn macros in problems with decomposable operators and serializable subgoals. \citet{botea2005macro} introduced a method for automatically learning macros, which subsequently ranked and filtered them by usefulness. \citet{newton2007learning} studied using genetic algorithms to maximize macro-action ``fitness" without relying on assumptions about the planner or domain. In each case, the learned macros were found to help with subsequent planning tasks; however, none of these methods explicitly considered the unique challenges of black-box planning.

\citet{lipovetzky2012width} introduced Iterated Width (IW) search, a ``blind'' planner compatible with simulators, and \citet{lipovetzky2015classical} 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) \cite{lipovetzky2017best}, which we include in our experimental evaluation. \citet{jinnai2017learning} 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.

There has also been work on domain-independent approaches to learning planning heuristics, outside the context of learning macros. \citet{virseda2013learning} showed how to automatically learn a weighted combination of existing heuristics to improve planner robustness. \citet{gomoluch2017towards} trained heuristic functions on known solutions for representative problems, and showed that their heuristics generalized to held-out test problems for a small set of domains. \citet{shen2019learning} recently learned domain-independent heuristics from scratch that outperformed existing baseline heuristics.

Recent work by \citet{agostinelli2019solving} 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 $\num{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.

We also note that \citet{openai2019rubiks} demonstrated a robotic hand that could learn to manipulate and solve the Rubik's cube, but they employ an off-the-shelf, domain-specific planner to generate solutions.

\section{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. Our method is competitive with the state-of-the-art LAMA planner, without ever seeing a declarative description of the problem. While our approach is designed to match the assumptions of the goal-count heuristic, we find that incorporating focused macros improves the performance of more sophisticated heuristic search methods as well.

We are encouraged to see that many of the learned macro-actions 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 macro-actions are composed of primitive actions. One extension to bring this method more in line with human-expert techniques would be incorporating several 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.

\section{Acknowledgements}
We thank Yuu Jinnai and Eli Zucker for many helpful discussions, Tom Silver and Rohan Chitnis for help with {PDDLGym}, the anonymous IJCAI-PRICAI reviewers for their excellent feedback on an earlier version of this manuscript, and our colleagues at IBM Research and Brown University for their thoughtful conversations and support

