Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Authors: Michał Zawalski
Michał Tyrolski
Konrad Czechowski
Tomasz Odrzygóźdź
Damian Stachura
Piotr Piękos
Yuhuai Wu
Łukasz Kuciński
Piotr Miłoś
Venue: ICLR 2023 notable top 5% (2023)
Keywords: search
adaptive horizon
verification
deep learning
hierarchical planning

Abstract: Complex reasoning problems contain states that vary in the computational cost required to determine the right action plan. To take advantage of this property, we propose Adaptive Subgoal Search (AdaSubS), a search method that adaptively adjusts the planning horizon. To this end, AdaSubS generates diverse sets of subgoals at different distances. A verification mechanism is employed to filter out unreachable subgoals swiftly, making it possible to focus on feasible further subgoals. In this way, AdaSubS benefits from the efficiency of planning with longer-term subgoals and the fine control with shorter-term ones, and thus scales well to difficult planning problems. We show that AdaSubS significantly surpasses hierarchical planning algorithms on three complex reasoning tasks: Sokoban, the Rubik’s Cube, and the inequality-proving benchmark INT. 

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
FAST AND PRECISE: ADJUSTING PLANNING HORIZON WITH ADAPTIVE SUBGOAL SEARCH
Michal Zawalski
Michal Tyrolski
Konrad Czechowski University Warsaw
University of Warsaw
University of Warsaw mi cha tyrol @ gmail gmail.com com
m. zawa sk @uw.
k. czechowsk mimuw, edu.pp
Tomasz Odrzygóždı IDEAS NCBR lomaszo@impan p1
Damian Stachura
Piotr Piçkos
Jagiellonian University dami an st stachurale gma 1 com
KAUST
piotrppiekos@gmai com
Yuhuai Wu
Lukasz Kuciński
Piotr Mitoš
Google Research
Polish Academy of Sciences 1kucinski impan. pl
Ideas NCBR,
Stanford University yuhuai@google.
Polish Academy of Sciences, deepsense.al pmi o mmpaa.pl..
ABSTRACT
Complex reasoning problems contain states that vary in the computational cost required to determine the right action plan. To take advantage of this property, we propose Adaptive Subgoal Search (AdaSubS), a search method that adaptively adjusts the planning horizon. To this end, AdaSubS generates diverse sets of sub- goals at different distances. A verification mechanism is employed to filter out unreachable subgoals swiftly, making possible to focus on feasible further sub- goals. In this way, AdaSubS benefits from the efficiency of planning with longer- term subgoals and the fine control with shorter-term ones, and thus scales well to difficult planning problems. We show that AdaSubS significantly surpasses hi- erarchical planning algorithms on three complex reasoning tasks: Sokoban, the Rubik's Cube, and the inequality provving benchmark INT.
INTRODUCTION
When solving hard problems, people often try to decompose them into smaller parts that are typically easier to complete (Hollerman et al. (2000). Similarly, subgoal search methods aim to solve complex tasks by considering intermediate subgoals leading towards the main goal. Besides their intuitive appeal, such approaches offer many practical advantages. Most notably, they enable deeper search within a smaller computational budget and reduce the negative impact approximation errors. Subgoal search methods powered by deep learning have shown promising results for continuous control tasks, such as robotic arm manipulation (Nair & Finn 2020; Jayaraman et al. 2019 Fang al. 2019) and navigation (Kim al. 2019, Savinov et al. 2018). Recently, (Zechowski et al.
22021 showed that the usage of subgoal generator can significantly improve search efficiency on discrete domains with high combinatorial complexity.
This paper uses Czechowski et al. (202I) as a starting point and pushes forward, building upon the following observation: many complex reasoning problems contain states that vary in complexity, measured by the computational cost required to determine the right action plan. To illustrate this, imagine driving car. When traversing narrow, winding street, is crucial to focus on the closest events: the next turn, the next car to avoid, etc. However, after entering straight, empty street, it
"quul contribution; Published as a conference paper at ICLR 2023, notable-top-5%. Work done while the University of Warsaw

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
enough to think about reaching its far end. This suggests that careful balancing of the subgoal distance is desirable: this involves selecting longer-term subgoals, if possible, to advance faster towards the goal, and choosing shorter-term subgoals to power through the harder states. Hence, the question arises whether is possible and, if so, how to incorporate this adaptive subgoal generation procedure into subgoal search methods. In this paper, we answer this question affirmatively.
We propose a novel planning algorithm Adap- tive Subgoal Search (AdaSubS), which adaptively chooses from subgoals with different horizons. Our method benefits both from the efficiency of planning with longer-term subgoals and from the reliability of shorter-term ones. AdaSubS prioritizes further dis- fances, retracting to shorter ranges only when stuck. Additionally, we introduce verifter network, which assesses whether the proposed subgoal is valid and reachable. The verifier makes it possible to efti- ciently discard faulty subgoals. which common and more costly to detect in longer horizons. AdaSubS is a data-driven algorithm whose key com- ponents implemented learnable deep models. In most cases, we use general-purpose trans- former architectures to model subgoal generators and the verifier networks. We train those models on offline data.
An illustrative example of adaptive planning. The planner may choose long-distand distance subgoals in the easier areas (e.g. the left most part) and use short distances in the hard areas (e.g. middle part).
We show the effectiveness of AdaSubS in three challenging domains: Sokoban, Rubik's Cube, and the inequality theorem prover INT (Wu al.) 2021). AdaSubS significantly surpasses hierarchical planning algorithms and sets a new state-of-the-art on INT.
Our main contributions are:
1. We propose Adaptive Subgoal Search (AdaSubS), new algorithm that adjusts the planning horizon to take into account the varying complexity of the state space.
2. We present a comprehensive study of adaptive methods, showing that they outperform similar algorithms without adaptation. Amongst these, AdaSubS is the best choice across environments and planning budgets.
3. We also observe strong indication of cuttr--distribution generalization. AdaSubS trained on the proof of length 15 in INT (longest considered in the literature so far) retains more than 50% of its performance when the proof length increased two-fold.
The code of our method is available at attp://ssshhllcoooooooooooogls/p
RELATED WORK
The combination of planning algorithms with deep learning is an active area of research. It provided impressive results e.g., in automated theorem proving (Polu & Sutskever 2020). chess and Go (Sil- ver et al. (2017). Atari benchmark (Schrittwisser et al. 2019), and video compression (Mandhanc al. 2022).
In the field of hierarchical planning, the majority of deep-learning-basee methods have focused on
visual domains (Kim al. 2019 Pertsch al. 2020a Jayaraman al. 2019 Fang et al. 2019) or
on landmark-basee
navigation methods (Liu et al. [220a]] Gao et al. [201]] 201 ZZang et al. (020) This
body of work often relies on variational autoencoders for the compression visual observations and
uses planning mechanisms suitable for continuous control settings.
There exist many approaches to hierarchical planning utilizing different temporal distances. Kim et al. (2019) and Pertsch et al. (2020b) use hierarchical variational models to learn the temporal structure of tasks by reconstructing the visual state sequences. Pertsch et al. (2020a); Parascandolo et al. (2020); Jurgenson al. (2020) recursively construct plan by generating subgoals in the middle between the existing ones. Allen et al. (021) generate macro-actions that help to speed-up learning to generate subgoals (as opposed to action sequences) and the process is agnostic with respect to the size of the action space. These works have been shown to work domains with limited combinatorial complexity.
the search. This differs from work, as
2

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Recently, Czechowski et al. (2021) has shown how combinatorially complex domains can be treated with a hierarchical planning method. Their approach shares similarities with our Adaptive Subgoal Search; however, it cannot address variable environment complexity. By using the mechanism of adaptive selection of the subgoal generation distance and verifier, we successfully tackle this prob- lem, confirmed by significant performance gains. Our verifier is based on ideas similar to Cobbe it al. (2021); Kurutach et al. (2018); Ahn et al. (2022).
Our approach relates to established search algorithms (Cormen et al. 2009 Russell & Norvig 2010), such as Best First Search or A*. Adaptivity techniques in the classical setup are discussed in Fickert (2022). Koenig & Likhachev (2006) propose an adaptive mechanism to improve A by updating the goal-distance heuristic with local search. AdaSubS instead uses a fixed heuristic and adapts to the local complexity by alternating between subgoal distances. nomain-independern PDDL-bbseed planners (McDermott et al.) 1998) do not use training and attempt to solve problems in a zero-shot manner. Thus, they indicate lower bound on performance. On the other hand, there are domain- specific methods (Kori 1997 Büchner et al. 2022 Muppasani et al. 2022 indicate an upper bound.
Due to their focus, they
AdaSubS relates to multi-queue methods (see Richter & Westphal (2010); Helmert (2006)), which alternate between multiple heuristics. Some of our planners, c.g., IterativeMMxxing or Longest- first, can be viewed through the lens of this approach in the sense that could keep the priority queues for each generator separate (but with the same heuristic being a value function) and have an alterna- tion mechanism between them. The key difference lies in the expansion phase: expand subgoals instead of children and only the generator associated with the currently selected queue is used. !
Different instances of Sokoban, Rubik's s Cube, and INT be viewed tasks with varying degrees of difficulty. Consequently, AdaSubS benefits from sharing data between these instances in manner typical to multitask learning (Caruana| 1998). In particular, we use goal-conditioned policy which is trained similarly as in (Andrychowizz et al. (2020) or Kaelbling (1993). Additionally, the out-of- distribution generalization of AdaSubS hints at strong meta- capabilities of the method (Yu
et al. 2020 Duan et al. 2016 Wang et al. 2016 Hessel et al. 2019).
METHOD
For this work, we propose Adaptive Subgoal Search (AdaSubS), a subgoal-based search algorithm designed solve tasks that can be formulated a search over graph with known transition model. AdaSubS is the best choice stemming from a careful study of methods based on the principle of mixing subgoal distances; see Section 4.4 for their definitions and empirical comparisons.
AdaSubS (see Algorithm D utilizes the following key compo- nents: subgoal generators, verifier, conditional low-level policy (CLLP), and value function. These components are implemented using trained neural networks (see Appendix B). To solve a task, AdaSubS iteratively builds a tree of subgoals reachable from the initial state until the target state is reached or the search budget is depleted. In each iteration, it chooses node in the tree that is expanded by one of the generators. The chosen generator creates few subgoal candidates, i.e., states expected to be few steps closer to the target than the current node. For each of them, we use the verifier and CLLP check whether they are valid and reachable within few steps. For the correct subgoals, we com- pute their value function, place them in the search tree, and the next iteration follows (see Figure
Initial state
smunch LAM
-12.8
-10.9
-6.8
-7.1
verifier CLLP
AdaSubS follows the general structure of Best-First Search (BestFS): thus, the key design decision is how we prioritize nodes to expand and choose generators to produce subgoals. We defer the answer to these questions after providing details of the algo- rithm components (see also Appendix G and the flowchart there).
valoe
Figure 1: An example iteration of
the search performed by AdaSubS.
For search engines using multi queues, see Fast downward ht https: // www. fast downward. org/ Popppk---pppbppoo For PDDI, generators, see https:
LAPKT https::/gt thub. com wttpp//w...........ao.ooeee.ee 7/g wtw.itthbcccmaatb
3

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Subgoal generators. The subgoal generator, or more precisely the k-subgoal generator, takes a state as imput and returns a diverse set of new candidate states expected to be l step closer to the solution. The key trade-off, which AdaSubS needs to address, is that further subgoals, i.., those for higher values of k. advance faster towards the target but are also increasingly harder to generate and verify. We typically use a few (e.g., 3) generators with list of l chosen basing on experiments, namely for INT [3, 2, 1J. Rubik [4, 3, 2] and Sokoban [8, 4, 2]. Note that this is the only component of AdaSubS that outputs a set of predictions.
Conditional low-level policy (CLLP), CLLP returns path of low-level actions between two states (see Algorithm 2) CLLP calls iteratively conditional low-level policy network (PN). PN takes as input the current and target states and returns an action. It is possible that CLLP is not able to reach the target, in which case an empty sequence is returned. The role of CL.LP is two-fold: serves as a mechanism allowing AdaSubS to transition between subgoals, and together with the verifier network, is used in the subgoal verification algorithm (see Algorithm 3
The verifier network is used in the verification algorithm (see Algorithm 3). to answer the following binary classification question: given starting state and a goal state, it possible to reach the latter from the former using conditional low-level policy? Computationally, the evaluation of the verifier network is faster than CLLP. However, since the verifier is a binary classifier, we expect two types of error to occur: accept invalid subgoals reject valid subgoals. The verification algorithm accepts a subgoal if the verifier network values are above a certain threshold (likewise, they are rejected if the value is below another threshold), t1 and thi in Algorithm B In the remaining case, the algorithm falls back on CLLP to decide whether to keep or discard a given subgoal.
Verifier.
Value function. The value function is neural network that estimates the negative distance between the current and goal states. The planner uses this information to select the next node to expand.
Adaptive Subgoal Search. The particular way in which AdaSubS chooses nodes to expand and generator to produce subgoals (see highlighted lines in Algorithm [ implements an adaptive mech- anism that adjusts the planning horizon. The key difficulty to tackle here is that further subgoals, despite being capable of advancing the search faster, are more likely to be faulty. Nevertheless, we assume an optimistic approach prioritizing the longer distances (e-g., higher k). If the search using the long steps gets stuck, the planner retracts and expands the most promising, high-value nodes with closer, more conservative subgoals. The verifier network helps in mitigating the risks of this strategy, as it allows for the efficient rejection of faulty subgoals. This way, by traversing easier parts using fast long-distare -ointdditance subgoals and conservative ones in harder parts, AdaSubS adapts to the variable complexity of the environment.
Algorithm ! presents a simple implementation of this approach. The nodes in the search tree are placed in max- -riioitioitty queue T with keys, being the pairs (k, v) of the next subgoal distance and its estimated value, sorted in lexicographical order. In this way, Algorithm [ Juses the highest l possible, searching with the BestFS strategy over values. If for given k, all generated subgoals are invalid (faulty or unreachable). Algorithm [ will expand for shorter distances. If successful, we go back to generating with the highest value of k. After reaching the target states, AdaSubS reconstructs the path of subgoals and fills it with low-level actions; see function LL PATH in Algorithm
With slight modification, AdaSubS can be guaranteed find a solution any given problem, provided there is large enough computational budget. See Appendix G.I for details.
3.1 TRAINING ORJECTIVES
The components of AdaSubS are trained using a dataset of offline trajectories of subsequent states and actions: (so, ao).... (8n-1, (n,1),,,, 8n. We do not assume that they are perfect; for some of our environments, even randomly generated trajectories may turn out to be sufficient. Details on how the data is collected for each domain can be found in Section 4.1 and Appendix (
Provided with such data, we train the k-generators to map S; onto Si+k- The value function is trained to map 8; onto (i n.). CLLP is trained to map (st, Si+d) onto a, for every d < kiux (kmux. is the maximal distance of the subgoal generators used).
AdaSubS still works, albeit much worse if we disable the verifier network (e.g., by setting tai and ti = in Algorithm 3). However, is a useful setup to gather a dataset of subgoals and their reachability verified by CLL.P. This dataset is used to train the verifier network, see Appendix D
4

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Algorithm Adaptive Subgoal Search
Algorithm Conditional low-level policy
Requires:
C₁
number of nodes value function network subgoal generators
Requires:
C2
steps limit
V
x
conditional low-level
Phat Plom
policy network
SOLVED
predicate of solution
M
model of the environment
function SOLVE(Se)
function GET BET_PAT subgoal)
T 0 D priority queue with lexicographic order parents
step <- 0, <-
action satoonnphhh___ +-
ku...., Am do T.PUSH(((K;; V (Sa)), 8c))
while step < C2
action + x..REDICT(s, subgoal)
seen.ADD(so)
seen is set
while 0 < LEN(T) and Leeen) < C1 do
f BE.NEET_STTATER action)
[k, t T.XXTRAT_MMAA
if subgoal then
subgoals (*)
return action_patti
success
for subgoals do
step f step +
if a' in seen then continue
return
> subgoal is unreachable
if not pootis_AALL VALID then
continue
Algorithm Verification algorithm
seen.ADD(s')
parents(s'] { for in Ao. km do T.PUSH(((k), V(s')), if SOLVED(s') then return I.I__ PATH(s's parenta)
Requires: th upper threshold
verifier network
t1o lower threshold
function VALID(S,
vf, s') th then return True
get low-level path, see Alg.
else if v(s, s') < t1 then return False return GFT [EE__PATH(E,s)) /
return False
For INT and Rubik's s Cube, we transformer models for all the key components. For the Sokoban, we utilize convolutional networks, for details see Appendix
4 EXPERIMENTS
We empirically demonstrate the efficiency of Adaptive Subgoal Search three complex reasoning domains: Sokoban, Rubik's Cube, and the inequality proving benchmark INT (Wu et al. 2021). We demonstrate that AdaSubS is the best choice in family of adaptive methods. Interestingly. even weaker methods in this class also outperform non- adaptite baselines. Finally, we show that AdaSubS has strong out-of-distribution generalization properties on INT.
As the performance metric, we use the success rate, defined as the fraction of solved problem in- stances. The computational budget is defined as the graph size, i.e., the number of nodes visited during the search and evaluated with a neural network (subgoal generator, value function, verifier, or conditional low-level policy). In Appendix C we provide details concerning the number of neural network calls, wall-time evaluations and memory usage.
4.1 EXPERIMENTAL DOMAINS AND DATASETS
Sokoban puzzle which the goal is push boxes on target locations. a popular testing ground for classical planning methods (Lipovetzky & Geffner 2012), and deep-learning approaches (Guez et al., 2019, Milos et al. 2019). Sokoban is considered to be hard (Fern et al. 201 due to its combinatorial complexity. Finding solution for given Sokoban board is an NP-hard problem. In our experiments we used x 12 Sokoban boards with four boxes.
Rubik's Cube is famous 3D puzzle with over 4.3 x 10 possible configurations Korf 1997 Recently Agostinelli et al. (2019); Czechowski et al. (202I) have developed methods for solving Rubik's Cube using neural networks.
INT is a benchmark for automated theorem proving proposed by (Wu et al. 2021). consists of generator of mathematical inequalities and tool for proof verification. An action (proof step) in INT is a string containing an axiom and a specification of its input entities, making the action space effectively infinite and thus challenging search algorithms.
5

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
To collect offline trajectories datasets for Rubik's Cube, we generate random paths of length 20 starting from the solved cube and take them in reversed order. For INT we use the generator provided by Wu et al. (202I). For Sokoban, we use the expert data generated by reinforcement learning agent (Mitoš et al. 2019). Detailed information is contained in Appendix D
4.2 PROTOCOL AND BASELINES
Our protocol consists of three stages. In the first one, an offline dataset is prepared: see Section 4.1
and Appendix D Secondly, we use this dataset to train the learnable components of AdaSubS: the family of subgoal generators, verifier network, and value network, see Section 331] Evaluation the final step in which the algorithm's 's performance is verified. We measure its success rate using 1000 instances of problem for each domain.
As baselines, we use BestFS and kSubS, both with the same models' checkpoints as AdaSubS, The former is a well-known class of search algorithms (including A"), which, among others, performs strongly on problems with high combinatorial complexity (Pearl 1984), achieves state-of-the-ar results in theorem proving (Polu & Sutskever 2020), and strong results on Rubik's 's Cube (Agostinelli et al. 2019 Czechowski et al. 2021). BestFS baseline selects actions with trained policy network.
kSubS the first general learned hierarchical planning algorithm proven to work on complex reason- ing domains (Czechowski et al. 2021 (called BF-kSubS there), attaining good results on Sokoban and Rubik's 's Cube, and INT. kSubS can be view as a non-adaptive version of AdaSubS realized by a
suitable hyperparameters choice: single subgoal generator and inactive verifier (t1. = 0,tm. 1).
For details on the hyperparameter choice for our method and the baselines, see Appendix For a
more detailed description of the baselines, see Appendix E
4.3
MAIN RESULTS: IN- AND OUT- DISTRIBUTION PERFORMANCE
AdaSubs (ours)
kSubS
BestFS
Sokaban
Rubik's Cube
1.0
1.0
0.8
0.5
Success rate
Success rate
167
102
10'
10a
10'
10'
30'
10
Graph size
Graph size
INT (proof length 15)
INT (proof length 20)
1.0
1.0
0.8
0.8
Success re0e
Success rebe
0.0
0.0
10
10
10
10a
Graph size
Graph size
Figure 2: Success rates of AdaSubS, kSubS, and BestFS expressed in terms of graph size. The figure in the bottom right shows the out-of-distributio performance of methods evaluated on INT with proof length 20 but trained length 15. The remaining figures present in-distribution performance. The results were measured on a fixed set of 1000 problems for each domain. Shaded areas indicate 95% confidence intervals.
AdaSubS shows strong in- and out- of distribution performance. The results for the former regime presented in Figure 2 which shows that AdaSubS is able make use of search capacity in the most effective manner, practically dominating other methods across the graph size spectrum. Taking closer look at the low computational budgets, one can observe that AdaSubS achieves significantly
6

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
positive success rates while the competing methods struggle. Perhaps the most striking difference is observed for INT, where at the budget of 50 nodes AdaSubS achieves around 60% success rate, while kSubS has success rate close to zero and BestFS does not exceed 10%. This is particularly impressive since the budget of 50 nodes only slightly larger than three times the considered proof length. To summarize, AdaSubS performs well in low computational regimes, which can be helpful in systems that need to solve search problems under compute or memory constraints.
At the far end of the computational budget spectrum, AdaSubS still performs the best, achieving above 90% performance in each environment (~> 95% for INT, 100% for Rubik's Cube, and 93% for Sokoban). Importantly, when success rates are high, and consequently the absolute differences between methods' results seem to be low, it is instructive to think about failure rates. For instance, in the case of INT (the proof length 15), the failure rate of kSubS is 9%, almost twice the failure rate of AdaSubS. For more results on low and high budgets, see Tables TO 12 Appendix H.4
For the dustr--distribution analysis, we used INT, an environment designed study this phe- nomenon. We investigate how methods trained on the proofs of length 15 perform problems with longer proofs (see Figure 3). The length 15 is the longest considered in the literature (Czechowski er al. 202T). However, we go much further, studying proof lengths up to 28. AdaSubS retains more than 50% of its performance, suffering a relatively slow decay of 3.5% (on average) per one step of the proof. This stands in stark contrast kSubS, which already loses half of its performance length 21. AdaSubS not only outperforms kSub$ at each difficulty level but also achieves the most significant advantage in the hardest problems. Additionally, we provide full profile of the success rate with respect to the graph size for proof length 20; see the bottom right-hand corner of Figure AdaSubS performs much better than the baselines, with the biggest advantage for large budgets. Results for the other environments, namely Sokoban and Rubik, are included in Appendix K
kSubs
INT out-of-distribution generalization
AdaSubS (ours)
1.0
0.956
0.89
0.937
0.88
0.93
0.74
0.779
0.76
0.736
0.61
0.613
0.6
0.50
0.544
Success
0.35
0,25
012
0.0
Proof length
Figure 3: Out-of-distribution performance of AdaSubS and kSuhS for long proofs in INT with budget 5000 nodes. Both methods were trained on proofs of length 15. Error bars correspond to 95% confidence intervals.
The performance boost of AdaSubS over the baselines stems from two components: the verifier and the adaptativeness of subgoal selection. The former makes it possible assign a bigger fraction of computational budget on search by recovering part of it from CL.LP. This, in principle, could already provide significant gain when using the method. However, as shown in Table and Tables 10 12 in Appendix H.4, the verifier helps, but only limited degree. Consequently. the majority of the improvement stems from the algorithmic novelty offered by the adaptive procedure. The adaptivity mechanism in AdaSubS creates this interesting dynamic that incentives the method to be optimistic about choosing subgoal distances while providing a safety net in case this optimism fails. How it works in practice can clearly be seen in Sokoban, where AdaSubS uses 8-subgoals 91.8% of the time, 4-subgoals 7.4% of the time, and 2-subgoals the remaining 0.8% of the time?)
As a final note, Figure 2 can be used infer the computational budget required for achieving certain success rate. Additionally, the ratio of success rate to graph size can measure the efficiency
Additionnlly, the 8-generator, the 4-generator, and the 2-generator generate subgoals that are on average 6.9, 3.9, and 2.0 steps away, respectively. For AdaSubS parameters, see Table Appendix F
7

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
of the chosen budget, while the derivative of the success rate with respect to graph size provides the marginal utility the increase in the budget.
4.4 DEVELOPING ADAPTIVE SEARCH METHODS
In this section, present comprehensive empirical study of four adaptive methods. This ables us to draw two main conclusions: adaptive search methods outperform non-adaptive ones, and Longest-first (on which AdaSubS is based) the most efficient adaptive procedure. We present full results for INT, the hardest environment, and shortened results for Rubik and Sokoban, see Table T The complete set of numerical results with extended discussion can be found in Appendix H
The four adaptive methods presented in this section are implemented using the search method Their adaptivity mechanism is defined by setting the way the subgoals are generated and the order in which the states are processed This happens in two distinguished lines in Algorithm and changing them determines how the search prioritizes various distances.
INT
Rubik (with verilier)
Small hudget (50 nodes)
Large budget (1000 nodes))
400 nodes
6000 modes
with verifier
without
with
without
BesFFS
1.8%
KSubS
28.8%
98. 98.6%
BestFS
1.7%
30.7%
MixSubS
2%
k:
2.2%
0.1
82.4%
83.0%
lterative mixing
50.6%
99.1%
k
1.0%
0.2%
89.6%
90.7%
Strongest-linst
0%
kSubS
k
2.1%
0.5%
89.8%
91.7%
Longest first
58.0%
99.2%
k k 3, 2] 2. [3
0.0%
0.0%
34.7%
46.0%
0.0%
0.0%
94.6%
95.0%
Sokoban (small budget, 100 nodes)
MixSuhS
0.0%
0.0%
92.2%
92.9%
k
17.0%
14.8%
92.2%
93..5%
with verifier
without
iterations
1, !] iterations 24 1]
32.0%
30.1%
87.0%
88:
Beat'S kSubS
45. 95.9%
Iterative mixing
iterations 110, 1.
43.0%
44.8%
95.1%
96.0%
26.0%
4.7%
54.0%
52. 1%
93.6%
95.5%
MixSubS
52.7%
37.7% 37.7%
Iterative mixing
6-1.5%
52.6%
Strongest-fistt
39.5%
10.8%
88.5%
89.8%
Strongest-linst
54.6%
41.9%
Longest-first
59.0%
51.3%
95.7%
95.3%
Longest-first 72.2%
63. 63.4%
Table 1: (left) Results the INT. For each case, unless stated otherwise, the distances subgoal generators
3, 2, 1]. (right) Shortened results for Rubik and Sokoban, for complete results see Table II and Table The results were obtained on 1000 problems each, which yields +3% Bernoulli 95% confidence intervals. Specifically, we designed and tested the following methods: MixSubS, Iterative mixing, Strongest- first, Longext-frrst. Each method uses a set of n generators ( Pk. trained to produce subgoals on different distances Kn < < kn (recall Section 3.1 for training details). A more detailed description of the methods (and pscudocodes) can be found in Appendix H.
are
12
MixSubS is the simplest approach, in which for each processed state we generate one subgoal from each generator Pk. (subgoals + P (s)). In each iteration, MixSubS chooses state with the highest value estimation V(s) to process.
Iterative Mixing is similar to MixSubS and enables for advanced schedules of generators to be used. In the consecutive iterations, the i-th generator is used to expand 4; nodes before switching to the next generator. This allows us to flexibly prioritize the better generators, but at the cost of tuning additional hyperparameters l,,..., In- For these reasons, it is not practical, but useful as reference point.
Strongest-firs uses one generator time (subgoals + (k, (s)), where ky is the longest distance not previously used in In each iteration, Strongest-first chooses state with the highest value estimation V(s) to process.
Longest-first prioritizes long subgoals over the whole search procedure. Only if the queue does not contain any nodes with the highest k, it uses subgoals of lower distances. The nodes are processed in the order of their value estimation (s)).
Adaptivity may also be implemented using the subgoal generator. We considered various approaches in this category, however, they did not perform better than the non-adaptive haseline kSubS, see Appendix [..
We speculate that assessing the state difficulty is a hard learning problem that is casier to handle via search. Forr similar considerations in classical planning, multi-hcuristic best-first search (Helment 2006).
8

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
The high-level empirical conclusion is that the performance of methods is roughly ordered fol- lows: Longest-first > Iterative mixing > MixSubS' > Strongest-first kSubS > BestFS.
In more detail, already the simple MixSubS works better than the non-adaptive baselines. In par- ticular, it can outperform the maximum of performances of kSubS for cach k. This is line with the intuition that mixing mechanism can elicit benefits of various distances while avoiding their drawbacks. We conjecture that whenever a single generator begins to struggle, the search advances with the help of another generator, allowing for stable progress. lterative mixing is able exhibit strong performance; however, needs tedious schedule tuning for each domain.
Strongest-frsst and Longest-first implement bias towards longer distances. Even though they quite similar, they display a large performance difference. We speculate that when Strongest-fing encounters an area with falsely large value estimates, wastes lot of compute to examine it with all subgoal distances. On the other hand, Longest-first first explores other areas before using shorter subgoals and thus is able avoid this problem. We stress that these effects are far from being obvious; however, they occur robustly across our test scenarios.
The verifier beneficial on small budgets, especially when long subgoals are used. For large bud- gets, gains diminish. However, properly tuned verifier never decreases the results significantly.
LIMITATIONS AND FUTURE WORK
Determinism, access to model dynamics Our main focus is combinatorially complex domains. There are many applications of interest in which can assume access underlying dynamics and determinism (for example Automated Theorem Proving). Nevertheless, it is an interesting future direction to adjust our method stochastic domains and learned models.
Reliance on the offline data In our experiments, we need offline datasets of successful trajectories. We leave for future work developing an algorithm based on the expert iteration paradigm.
Path optimization The goal of our algorithm is to find any path leading to the solution. In many real-world problems, it also important find a short path or one with high reward (see Appendix [ for optimality measures for Sokoban).
Completeness and memory constraints Our algorithm is not guaranteed to find solution. We found it is not problematic in practice. If such a property is required, it can be assured by simple change, see Appendix G.T However, since AdaSubS keeps list of visited nodes (see Algorithm [ and caches some computations (sce Algorithm 4 it requires memory proportional to the search budget, which can grow up to the size of the state space when seeking completeness.
Adversarial configuration The performance of AdaSubS can deteriorate when the ability to train its components is reduced and the environment is hard. For example, walk-the-line' environment (with states either lying a unique solving trajectory leading to deadstates) and no training data.
Combine with recursive search methods In some domains, one can generate useful subgoals for long distances and recursively split the problem (Pertsch al. 2020a Parascandolo et al.) 2020 Jurgenson et al. 2020). would be interesting to propose an algorithm that automatically detects when such an approach is possible and combine two ways (our and recursive) of generating subgoals.
6 CONCLUSIONS
We study planning methods that adapt to the local complexity of a solved problem. We concentrate on the adaptive selection of the subgoal distance realized by mixing various subgoal generators. We prove that methods based this principle outperform non-adaptive counterparts They can tackle complex reasoning tasks as demonstrated on Sokoban, the Rubik's 's Cube, and INT. Our main al- gorithm, AdaSubS, is the best of the tested choices across all environments and search budgets. Interestingly. AdaSubS exhibits high -ott----sttibbttoon generalization capability, retaining much of its performance for instances of harder problems INT than it trained for.

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
7 ACKNOWLEDGMENTS AND DISCLOSURE OF FUNDING
The work of Michal Zawalski and Piotr Mitos was supported by the Polish National Science Center grant 202 143/0///66/// This research was supported by the PL-Grid infrastructure. Our exper- iments managed using https: http:://neuuue.eee for providing us access to the team version and technical support.
We would like to thant the Neptune team
REFERENCES
Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 1(8):356-363 2019.
Michael Ahn, Anthony Brohan, Noah Brown, Yevgen Chebotar, Omar Cortes, Byron David, Chelsea Finn, Keerthana Gopalakrishnan, Karol Hausman, Alex Herzog, Daniel Ho, Jasmine Hsu, Ju- lian Ibarz, Brian Ichter, Alex Irpan, Eric Jang, Rosario Jauregui Ruano, Kyle Jeffrey, Sally Jesmonth, Nikhil J Joshi, Ryan Julian, Dmitry Kalashnikov, Yuheng Kuang, Kuang-Huei Lee, Sergey Levine, Yao Lu, Linda Luu, Carolina Parada, Peter Pastor, Jornell Quiambao, Kan- ishka Rao, Jarek Rettinghouse, Diego Reyes, Pierre Sermanet, Nicolas Sievers, Clayton Tan, Alexander Toshev, Vincent Vanhoucke, Fei Xia, Ted Xiao, Peng Xu, Sichun Xu, and Mengyuan Yan. Do can, not say: Grounding language in robotic affordances, 2022. URL https: /ttp///axvvv.// org/ abs/ 2.04.01669
Cameron Allen, Michael Katz, Tim Klinger, George Konidaris, Matthew Riemer, and Gerald Tesauro. Efficient black-box planning using macro-actions with focused effects. IICAI-21, 2021.
Marein Andrychowicz, Anton Raichuk, Piotr Stanezyk, Manu Orsini, Sertan Girgin, Raphaäl Marinier, Léonard Hussenot, Matthieu Geist, Olivier Pietquin, Marcin Michalski, Sylvain Gelly, and Olivier Bachem. What matters in on-policy reinforcement learning? large-scale empirical study. CoRR, abs/2006.05990 2020. URL httpt:t////// http:://axvvvvii org/ wwwpa/wwwww..//////////.//////// abs/2006. 05990
Clemens Büchner, Patrick Ferber, Jendrik Seipp. and Malte Helmert. A comparison of ab- straction heuristics for rubik's cube. In ICAPS 2022 Workshop Heuristics and Search for Domain-independenn Planning, 2022.
Rich Caruana. Multitask learning, Springer, 1998.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers solve math word problems. arXiv preprint 1.Xi::2110.1416. 2021.
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2009.
Konrad Czechowski, Tomasz Odrzygó2dž, Marek Zbysiński, Michal Zawalski, Krzysztof Olejnik, Yuhuai Wu, Łukasz Kuciáski, and Piotr Miloš. Subgoal search for complex reasoning tasks. Advances in Neural Information Processing Systems, 34:624-638, 2021.
Yan Duan, John Schulman, Xi Chen, Peter I. Bartlett, Ilya Sutskever, and Pieter Abbeel. RI.2: Fast reinforcement learning via slow reinforcement learning. arXiv preprint arXiv: 121661102220 .02779, 2016.
Kuan Fang, Yuke Zhu, Animesh Garg, Silvio Savarese, and Li Fei-Fei. Dynamics learning with cascaded variational inference for multi-step manipulation. arXiv preprint arXiv: arXiv:1910.1 1339. 2019.
Alan Fern, Roni Khardon, and Prasad Tadepalli. The first learning track of the international planning competition. Machine Learning, 84(1-2):81-107, 2011.
Maximilian Fickert. Adaptive search techniques in ai planning and heuristic search. 2022.
10

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Wei Gao, David Hsu, Wee Sun Lee, Shengmei Shen, and Karthikk Subramanian. Intention-nes net: Integrating planning and deep learning for goal-directed autonomous navigation. In 1st Annual Conference Robot Learning, CoRL 2017, Mountain View, California, USA. November 13-15, 2017, Proceedings, volume 78 of Proceedings of Machine Learning Research, pp. 185-194. PMLR, 2017.
ml www.:ppessss..ee
html
Arthur Guez, Mchdi Mirza, Karol Gregor, Rishabh Kabra, Sébastien Racanière, Théophane Weber, David Raposo, Adam Santoro, Laurent Orseau, Tom Eccles, et al. An investigation of model-free planning. In International Conference on Machine Learning, pp. 2464-2473. PMLR, 2019.
Malte Helmert. The fast downward planning system. Journal of Artificial Intelligence Research, 26: 191-246, 2006.
Matteo Hessel, Hubert Soyer, Lasse Espeholt, Wojeiech Czarnecki, Simon Schmitt, and Hado van Hasselt. Multi-task deep reinforcement learning with popart. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 3796-3896 2019.
Jeffrey Hollerman, Leon Tremblay, and Wolfram Schultz. Involvement of basal ganglia and orbitofrontal cortex in goal-directed behavior. Progress in brain research, 126:193-2155 2000.
Dinesh Jayaraman, Frederik Ebert, Alexei A. Efros, and Sergey Levine. Time-agnostic pre- diction: Predicting predictable video frames. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL
wttpeeewwwwewweeeeeeeeeeeee http:mmmmdSSyyyyyeeeemmm d=Sy22b3CcFF
Tom Jurgenson, Or Avner, Edward Groshev, and Aviv Tamar. Sub-goal trees framework for goal- based reinforcement learning. In International Conference on Machine Learning, pp. 5020-5030.
PMLR, 2020.
Leslie Pack Kaelbling. Learning to achieve goals. In Ruzena Bajesy (ed.), Proceedings of the 13th International Joint Conference on Artificial Intelligence. Chambéry, France, August 28 September 1993, pp. 1094-1099, Morgan Kaufmann, 1993.
Taesup Kim, Sungjin Ahn, and Yoshua Bengio. Variational temporal abstraction. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alchh-BBu. Emily B. Fox, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 14, 2019, Vancouver, neurips............ cc/ Abb-:44--bbbttrrr Abst .ttml
BC, Canada, pp. 11566-11575. 2019. URL paper 1tsper/2119/aah//55aa0 Battashh/5d3aad9999 00110900000011110000000000000000
Sven Koenig and Maxim Likhachev. Real-time adaptive a. In Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pp. 281-288, 2006.
Richard Korf. Finding optimal solutions to rubik's 's cube using pattern databases. In AAAИ/AАI, pp. 700-705, 1997.
Thanard Kurutach, Aviv Tamar, Ge Yang. Stuart J. Russell, and Picter Abbeel. Learning plannable representations with causal infogan. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 8747-8758, 2018. URL ht///httpps:/prrcceddinng neurips oc//paper/2118/aatt/ (Baccac9t555233955511777771---23 htw.a/eaiee57775tt--taaaaaaaa html
Nir Lipovetzky and Hector Geffner. Width and serialization of classical planning problems. In ECAI 2012, pp. 540-545. IOS Press, 2012.
Kara Liu, Thanard Kurutach, Christine Tung, Pieter Abbeel, and Aviv Tamar. Hallucinative topological memory for zero-shot visual planning. In Proceedings of the 37th International Conference Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event. volume 119 of Proceedings of Machine Learning Research, pp. 6259-6270. PMLR, 2020a. URL http: 7/proceed ing.eddddgg...o ngs ml www.ss/vl1///// /
html]
11

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Yinhan Liu, Jiatao Gu, Naman Goyal, Xian Li, Sergey Edunov, Marjan Ghazvininejad, Mike Lewis, and Luke Zeytlemoyer. Multilingual denoising pre-training for neural machine translation. CoRR, abs/2001.08210, 2020b. JRLttt:a://aaxx org/ abs/ / 2001 08210
Amol Mandhane, Anton Zhernov, Maribeth Rauh, Chenjie Gu, Miaosen Wang, Flora Xue, Wendy Shang, Derek Pang, Rene Claus, Ching-Han Chiang, et al. Muzero with self-competition for rate control in vp9 video compression. arXiv preprint urXiv:2202.06626 2022.
Drew McDermott, Malik Ghallab, Adele Howe, Craig Knoblock, Ashwin Ram, Manuela Veloso, Daniel Weld, and David Wilkins. PDDL - The Planning Domain Definition Language, 1998.
Piotr Mitoš, Lukasz Kuciñski, Konrad Czechowski, Piotr Kozakowski. and Maciek Klimek. Uncertainty-sseniiivve learning and planning with ensembles. arXiv preprint arXiv: 191.,999, 2019.
Bharath Muppasani, Vishal Pallagani, Kausik Lakkaraju, Biplav Srivastava, and Forest Agostinelli. Solving the rubik's 's cube with a pddl planner. 2022.
Suraj Nair and Chelsea Finn. Hierarchical foresight: Self-supervised learning of long-horizon tasks via visual subgoal generation. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.ned 2020. URL https:
//openzeview net/ wtt.:/formmmmmmmmmmme (w22kkggggg22D
Giambattista Parascandolo, Lars Buesing, Josh Merel, Leonard Hasenclever, John Aslanides, Jes- sica B Hamrick, Nicolas Heess, Alexander Neitz, and Theophane Weber. Divide-and-conque monte carlo tree search for goal-directed planning. arXiv preprint arXiv:2004. 14410 2020.
Judea Pearl. Heuristics: intelligent search strategies for computer problem solving. addison-Wesley Longman Publishing Co., Inc., 1984.
Karl Pertsch, Oleh Rybkin, Frederik Ebert, Shenghao Zhou, Dinesh Jayaraman, Chelsea Finn, and Sergey Levine. Long-horizon visual planning with coal-connitioned hierarchical pre- dictors. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Bal- can, and Hsuan-Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020a. URL https://prroceeeinggg wwwrips. cc/ pa2er/202// html
Karl Pertsch, Oleh Rybkin, Jingyun Yang. Shenghao Zhou, Konstantinos G. Derpanis, Kostas Dani- ilidis, Joseph Lim, and Andrew Jaegle. Keyframing the future: Keyframe discovery for visual prediction and planning. In Alexandre M. Bayen, Ali Jadbabaie, George J. Pappas. Pablo A. Par- rilo, Benjamin Recht, Claire Tomlin, and Melanie N. Zeilinger (eds.), Proceedings the 2nd Annual Conference on Learning for Dynamics and Control, L,DC 2020, Online Event, Berkeley, CA. USA, 11-12 June 2020, volume 120 of Proceedings of Machine Learning Research, pp. 969- 979. PMLR, 2020b. URL httt::/pproceeee igg mlr prwss vv///v2/////// http2////ettstt/aaa
html
Stanislas Polu and Ilya Sutskever. Generative language modeling for automated theorem proving. arXiv preprint arXiv:2009.0333
2020.
Silvia Richter and Matthias Westphal, The lama planner: Guiding cost-based anytime planning with landmarks. Journal of Artificial Intelligence Research, 39:127-177. 2010.
Stuart Russell and Peter Norvig. Artificial intelligence: A modern approach. ed. 3. 2010.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. cemi-parametric topological memory for navigation. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL httpttttsss//pp/eeeee
net net/forum?? SygggwGG
Julian Schrittwieser, Ioannis Antonoglou, Thomas Hubert, Karen Simonyan, Laurent Sifre, Simon Schmitt, Arthur Guez, Edward Lockhart, Demis Hassabis, Thore Graepel, Timothy P. Lillicrap, and David Silver. Mastering atari, go, chess and shogi by planning with a learned model. ArXiv, abs/1911.00 1,02665, 2019.
12

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
David Silver, Thomas Hubert, Julian Schrittwieser, Ioannis Antonoglou, Matthew Lai, Arthur Guez, Mare Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, Timothy P. Lillicrap, Karen Simonyan, and Demis Hassabis. Mastering chess and shogi by self-play with a general reinforce- ment learning algorithm. ArXiv, abs/1712.01815, 2017.
Jane X Wang, Zeb Kurth-Nelson, Dhruva Tirumala, Hubert Soyer, Joel Z Leibo, Remi Munos, Charles Blundell, Dharshan Kumaran, and Matt Botvinick. Learning reinforcement learn. arXiv preprint arXiv: 161 1.05763, 2016.
Yuhuai Wu, Albert Q Jiang, Jimmy Ba, and Roger Baker Grosse. INT: inequality benchmark for evaluating generalization theorem proving. 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL https::/cpenzevvew net/ forum? 11==011PddoNNOO
Tianhe Yu, Deirdre Quillen, Zhampeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Conference on robot learning, pp. 1094-1100. PMLR, 2020.
Lunjun Zhang, Ge Yang, and Bradly C. Stadie. World model as graph: Learning latent land- marks for planning. CoRR, abs/2011. 2020. URL/https: / arxiv. wwt.ooorgg/abb1/11111
1241
13

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
A LOW-LEVEL PATH FUNCTION
The low-level path function (see LL_ PATH, Algorithm computes a path from the starting state the goal state in the environment using low-level actions. However, turning the path but also for checking false positive errors of the verifier. Specifically, the verifier can accept an unreachable state in Algorithm B and then wrongly include it in the solution path. Thus, LL PATH has to construct a low-level path and confirm that every step on the way is achievable.
only responsible for
Algorithm 4 Low-level path
function LI. LAT_P,, parents)
parents is the dictionary of parent nodes in the subgoal tree. (S,C) E parents means that C a subgoal for state S
path -
while in parents.KEYS[ do subgoal_path <- PATI(parents($]..)
see Algorithm 2
> In practice, to reduce the number of neural network calls, we cache
the results of the GET_PATH calls in Alg T and reterive them here. mistake of the verifier
if subgoal Baaaggoal_aahhhee_ then return False
path concatenate(subgoal path, path)
s < parents s) return path
14

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
B TRAINING DETAILS
B.1 ARCHITECTURES
INT and Rubik's cube. All components of AdaSubS utilize the same architecture. Specifically, we used mBart, transformer from the HuggingFace library (see (Liu et al. (020b)). To make training of the model and the inference faster we reduced the number of parameters: we used 45M learned parameters instead of 680M in the original implementation. We used 6 layers of encoder and 6 layers of decoder. The dimension the model was set to 512 and the number of attention heads 8. We adjusted the size of the inner layer of position-wise fully connected to 2048. During the inference, we used beam search with width 16 for INT and width 32 for Rubik's s Cube. Our implementation of the model follows (Czechowski et al. 2021 Appendix B.1)
Sokoban. We used four convolutional neural networks: the subgoal generator, conditional low- level policy, value, and the verifier. They all share the same architecture with different last layer, depending on the type of output. Each model had 7 convolutional layers with kernel size (3,3) and 64 channels. Conditional low-level policy and verifier need two Sokoban boards so for these networks we concatenate them (across the last, depth dimension) and we treat two boards as one tensor. For the value function on top of stack of convolutional layers there is fully connected layer with 150 outputs representing 150 distances to the goal or. CLLP has analogous final layers with the one exception that there are only two classes: determining whether is possible to reach subgoal by CLLP or not. The network used for generatiing subgoals returns two outputs: distribution over possible modifications of a given state, and prediction whether modified state is good subgoal. The first output is obtained with fully connected layer, the second with global average pooling followed by a fully connected layer. Generation of single subgoal is realised as sequence of calls to this network. We start from a given state and iteratively apply modifications with high probability assigned by the first head of the network, until the second head predict that no more iterations needed. (see also Appendix G.1
input,
B.2 TRAINING PIPELINE
To ensure fair comparison with (Czechowski et al. (021) we followed their settings for a training pipeline.
INT and Rubik's Cube. To train the models we used the training pipeline from the HuggingFace library (Liu et al. 2020b). We trained our models from scratch without using any pretrained check- points. The size of the training batch was 32, the dropout was set to 0.1, and there was no label smoothing. We used the Adam optimizer with the following parameters: 31 0.9, /3 = 0.999, e e 10 We applied the warm-up learning schedule with 4000 warm-up steps and peak learning rate of 3 10 -4 For inference in INT, we used temperature and for Rubik's ' Cube to 0.5 (the optimal value was chosen experimentally).
Sokoban. To train all networks we used a supervised setting with learning rate 10 10-4 and trained for 200 epochs. We used the Adam optimizer with /81 0.9, B3 0.999 and 10-7
B.3 DATASETS
For dataset used to train all the network see Appendix D
15

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
C COMPUTATIONAL BUDGET ANALYSIS
The default metric the graph size that we use for comparisons counts all the states visited during the search, both high-level subgoals and intermediate states passed by the CLLP. Is good estimate of the number of steps the algorithm takes to solve the given problem. For completeness, in this section, we analyze the total number of calls every learned component of the pipeline for AdaSubS and the baseline kSubS.
Since all of the main components are deep neural networks, their evaluation time dominates the computational budget. Tables 3 and 4 the average number of calls to each component in 1000 test episodes, fixed for all the methods. That indicates which component consumes the largest part of the computational budget. The results are presented for different numbers of beams (see Appendix [ used for sampling predictions from the subgoal generators, the only component that outputs set of predictions. The default number of beams was 16 for Sokoban and INT, and 32 for the Rubik's ' Cube (see Appendix for the complete list of the parameters).
As the tables show, not only does AdaSubS solve more problems within smaller search graphs but also calls each component fewer times, which results in faster inference.
In the Rubik's Cube, the calls to the generators dominate the computations. However, when using smaller beams, this number can significantly reduced while preserving the high success rate. In all the environments, AdaSubS is less sensitive to reducing the number of beams than kSubS in terms of performance. This is the case since AdaSubS every single generator creates fewer subgoal candidates (see Tables 9), and thus does not require wide beam search. Therefore, by reducing the number of beams, AdaSubS can provide strong results within a much shorter time.
In Rubik's Cube and Sokoban, using the verifier in AdaSubS significantly reduces the number of calls to the low-level policy. However, in INT this is not the case. In most cases when kSubS fails find solution, some point it cannot create any valid subgoal, and thus the search ends early. AdaSubS does not suffer from this issue, since it uses more generators. Thus, it counts the calls even from hard instances that require much larger graphs.
As shown in Table 5) if we count the calls only for the tasks solved by both methods, AdaSubS provides an advantage. Therefore, AdaSubS indeed provides better results within a smaller compu- tational budget compared to kSubS.
Environment
Rubik's 's Cube
Variant
kSubS (32 beams)
kSubS (4 beams)
AdaSubS (32 beams)
AdaSubS (8 beams)
AdaSubS
AdaSubS (2 beams)
(4 beams)
Success rate
98.8
97.1
99.2
99.2
99
98.5
Generator calls
6085
852
8872
2205
1244
680
Verifier calls
0
0
277
275
311
340
Policy calls
1330
1526
352
350
395
446
Value calls
259
285
163
162
181
197
Total calls
7675
2664
9666
2994
2133
1665
Wall-time
86.3 sec
49.9 sec
96.1 sec
49.2 sec
47.3 sec
37.3 sec
Table 2: Comparison of the average number of calls to the generator, verifier, policy, and value networks for different numbers of beams (width of beam search in subgoal generation)) and the average wall time. Results were obtained using fixed 1000 instances of Rubik's Cube
C.I MEMORY USAGE
AdaSubS keeps track of the search tree composed of high-level nodes. Thus, the amount of required memory grows linearly with the search budget. However, if we use longer subgoals, the tree is sparse because do not store the nodes visited by the low-level policy.
Note that the BestFS baseline, which uses only low-level steps, usually requires much larger memory because it must record every step. In practice, when evaluating the BestFS baseline in the INT
16

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
environment, often had problems with experiments crashing because of exceeding the memory limit on the machine. We never observed similar issues when running AdaSubS.
Environment
Sokoban
Variant
kSubS (16 beams)
kSubS
kSubS (4 beams)
AdaSubS
AdaSubS (8 beams)
AdaSubS
(8 beams)
(16 beams)
(4 beams)
Success rate
84.4
84.6
82.3
94
94
94.1
Generator calls
2500
1281
746
3389
1692
848
Verifier calls
0
0
0
211
211
212
Policy calls
4576
4693
5554
248
247
247
Value calls
183
187
216
82
82
82
Total calls
7260
6161
6301
3931
2233
1391
Wall-time
48.7 sec
36.6 sec
33.6
54.4
39.3 sec
30.6 sec
Comparison of the average number of calls to generator, verifier, policy, and value networks for different number of beams (width of beam search in subgoal generation)) and the average wall-time. Results were obtained using fixed 1000 instances of Sokoban
Table 3:
Environment
INT
Variant
kSubS beams)
kSubS beams)
AdaSubS (16 beams)
AdaSubS (8 beams)
AdaSub$
beams)
Success rate
90.7
89.7
96
96
95.3
Generator calls
107
26.0
362
166
76.3
Verifier calls
0
0
67.9
62.2
57.2
Policy calls
378
366
801
738
659
Value calls
6.9
6.6
14.0
13.0
11.9
Total calls
492
399
1245
974
805
Wall-time
15.3 sec
12.1 sec
43.8 sec
31.9 sec
31.1 sec
Table 4: Comparison the average number calls to generator, verifier, policy, and value networks for different number of beams (width beam search subgoal generation)) the average wall-time, Results were obtained using fixed 1000 instances of INT problems.
Environment
INT
Variant
kSubS
AdaSubS
Generator calls
93.4
102
Verifier calls
0
19
Policy calls
328
300
Value calls
6.2
5.6
Total calls
428
427
Table 5: Comparison of the average number calls to generator, verifier, policy, and value networks for problems solved by both methods for INT environment.
17

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
D DATASETS AND DATA PROCESSING
Sokoban. To collect offline data for Sokoban we used an MCTS-based RL agent from (Milos et al, 2019). In effect, the dataset consisted of all successful trajectories obtained by the agent: 154000 trajectories for 12x12 12 boards with four boxes. We use 15% of states from each trajectory to create the training dataset D. We performed the split of dataset D into two parts of equal size: D1 and D2. The former was used to train the subgoal generators and conditional low-level policy, while the latter was used to train the verifier network. This split mitigates the possibility of the verifier's over-optimism concerning the probability of achieving subgoals by CLLPP
INT. We represent both states and actions as strings. For states, we used an internal INT tool for such representation. For actions, we concatenate one token representing the axiom and the arguments for this axiom (tokenized mathematical expressions) following (Czechowski et al. 2021).
To generate the dataset of successful trajectories we used the configurable generator of inequalities from the INT benchmark (see (Wu et al., 202T)). We adjusted construct trajectories of length 15 with all available axioms. The dataset used for experiments consisted of 10 trajectories.
Rubik's ' Cube. To construct a single successful trajectory we performed 20 random permutations on an initially solved Rubik's Cube and took the reverse of this sequence, replacing each move with its reverse. Using this procedure we collected 10 trajectories. Such solutions are usually sub-optimal, since random moves are not guaranteed to increase the distance from the solution. They can even make loops in the trajectories.
D.1 DATASET FOR VERIFIER
The verifier answers the question of whether given subgoal is reachable by the CLLP. Thus, the dataset for training this component cannot be simply extracted from the offline trajectories.
To get the training samples for the Rubik's Cube and INT, we run AdaSubS without the verifier. In other words, we set t.: 1 and t1. = 0, which essentially means that the reachability of all the subgoal candidates is checked solely by CL..P. During the searching, the generators create subgoal candidates, which are then verified by CLLP. Therefore, after working on some problem instances, we obtain a reach dataset of valid and not valid subgoals, marked by CLLP.
For the experiments in Sokoban, the limitation of the size of the offline dataset is important factor for the final performance. Therefore, to ensure a fair comparison of AdaSubS with baselines, we do not generate additional solutions. Instead, we split the dataset described above into Dj and D: and used only D2 to generate data for the verifier. From every trajectory in D2, we sample some root states. For every such state, CLLP checks the validity of each of them and we include them in the verifier training dataset.
the subgoal generators to predict subgoal candidates. Then,
After collection, it is essential to balance the dataset. Easy instances with short solutions provide fewer datapoints than hard tasks that require a deep search. Thus, it may happen that a substantial fraction of data collected this way comes from single instance, reducing the diversity of the dataset. We have observed such issues. particularly in the INT environment. To prevent this, during the collection of the data for INT, we limit the datapoints that can be collected from single problem instance to at most 100. This way, we collected about 5 106 training samples for the verifier for each domain.
18

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
E BASELINES
As baselines, we use BestFS and BF-kSubS.
BestFSS is well-known class of search algorithms (including A"), which, among others, performs well on problems with high combinatorial complexity (Pearl) 1984), achieves state-of-the-art results in theorem proving (Polu & Sutskever 2020), and strong results Rubik's Cube (Agostinelli al. 2019
Czechowski et al.) 2021).
Similarly AdaSubS. BestFS iteratively expands the graph of visited states by choosing nodes with the highest value and adding its children to the priority queue. However, instead of using children from the subgoal tree, it uses direct neighbors the environment space. other words, we use single policy network to generate neighbor subgoals in the distance of action from given node and treat it as a new subgoal. One can implement BestFS by replacing the call a subgoal generator Ok in Algorithm| 1 with pRFs.
The implementation of pBFS differs slightly between environments. Rubik's Cube, PBFS for each action estimates the probability that it leads to the solution. In every iteration, we take the top 3 predictions. Sokoban, we use the same training objective, but instead of taking a fixed number of actions, we take the smallest subset of actions with estimated probabilities summing to least 98%. For INT, we use beam search to generate high-probability actions. This is necessary since in INT the actions represented as sequences.
Algorithm 5 BestFS
Requires:
V
value function network
PBFS SOLVED
policy predicate of solution
function SOLVE(S;)
T (
priority queue
parents f- {
(PS))
seen.ADD(so)
seen is set
while < LEN(T) and LEN(seen) < C₁ do
8 T.EXTRACT_MAX(
actions + PBFs(s)) for a in actions do
s' + ENV_ SRVVSTTEPSS,8 if s' in seen then continue
not IS VALID(S, s') then
continue seen.ADD(s') parenta + (V if SOLVED(s') then
return LL__PAAT(SS pL__eat((s,pareetts))
D> get low-level path, see Alg
return False
BF-kSubS the first, according to our knowledge, general learned hierarchical planning algorithm shown to work on complex reasoning domains (Czechowski et al. 2021). attaining strong results
on Sokoban and Rubik's 's Cube and state-of-the-art results on INT. BF-kSubS special case of
AdaSubS with the following hyperparameters choice: single subgoal generator and inactive verifier
(with tio and tx = 1) Algorithm 3
19

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
F HYPERPARAMETERS
Environment
Sokoban
Rubik's Cube
INT
learning rate
10
3 10 10-4
3 10
learning rate warmup steps
4000
4000
batch size
32
32
32
kernel size
[3, 3]
weight decay
10-1
dropout
0.1
0.1
Table Hyperparameters used training.
Environment
Sokoban
Method
kSubS
MixSubS
AdaSubS (ours)
number of subgoals
4
number of beams
16
16
beam search temperature k- A-generators number of steps to check (C2)
1
8
[8, 4, 2]
[8, 4, 2]
10
[10, 6, 4]
[10, 6, 4]
max steps in solution check max nodes in search tree (C1)
5000
5000
5000
acceptance threshold of verifier (txs) rejection threshold of verifier (Ni.)
0.99
0.99
0.1
0.1
Table 7: Hyperparameters used for evaluation in the Sokoban environment.
Environment
the Rubik's 's Cube
Method
kSubS
MixSubS
AdaSubS (ours)
number of subgoals
1
number of beams
32
32
32
beam search temperature
0.5
0.5
0.5
k-generators
4
[4, 3]
[4, 3, 2]
number of steps to check (C2)
[4,
[4, 2]
max steps in solution check
4
max nodes search tree (Ci)
5000
5000
5000
acceptance threshold of verifier (laa) rejection threshold of verifier (t1o)
0.995
0.995
0.0005
0.0005
Table 8: Hyperparameters used for evaluation in the Rubik's 's Cube environment.
Most of the hyperparameters, both for training and evaluation, are either default or have little impact on the performance of the algorithms. The values are in line with (Czechowski et al. 202I) which ensures fair comparison.
The parameter C1 (see Algorithm I controls the number of high-level nodes in the search tree. It is lower than the actual graph size that we use for comparisons since it counts neither the intermediate states visited by CL.LP nor the subgoals that turned out to be invalid. That hyperparameter was chosen enable the algorithms evaluated to reach the graph size values used for comparison in Figure 2 and others in Section
F.1 TUNING THE HYPERPARAMETER
The most important training hyperparameter that has to be tuned is the learning rate. To do this, compared the prediction accuracy for ten training runs corresponding ten learning rates in
20

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Environment
INT
Method
kSub$
MixSuhS
AdaSubS (ours)
number of subgoals
4
3 16
number beams
16
beam search temperature
1
k- d-generators
[3, 2, 1]
[3, 2, 1]
number of steps to check (C2)
[3, 1]
[3, 2,
max steps in solution check
5
nodes in search tree (C1)
400
400
400
acceptance threshold of verifier (44s) rejection threshold of verifier (f1o)
1
0.1
0.1
Table 9: Hyperparameters used for evaluation in the INT environment.
the range [10-5; 10-3). We shared the training hyperparameters across all the components for each environment, they share the same network architecture.
In evaluation, the most important hyperparameter of AdaSubS the set of k-generators. select the set for Sokoban, we started with small values of & (e.g.. I or 2) and increased k multiplicatively, doubling it as long as the new set generators performed better. We used similar procedure in Rubik's 's Cube and INT, but due to the bounds the optimal path length (at most 26 and 15, respectively), we increased & additively (incrementing k by one). This way, we have chosen A: = [8, 2, for Sokoban, set of generators, we also need to set the number of subgoals each generator should output. Thus, each time tried three different values ((1, 2, 3) for Rubik's Cube and Sokoban, {2, 3, 4] for INT) and used the one that resulted in the highest success rate. We ran the evaluation pipeline 15 times to tune that parameter. The other parameters have rather minor impact on the results, and thus did not tune them extensively.
[4, 2] for Rubik's Cube, and
[3. 2, 1] for INT. When evaluating
For kSubS, we took the values of used in (Czechowski al. 2021) for Rubik's Cube and INT. For Sokoban, we use l: = 8 since it outperforms k = proposed in this work.
In the case of the verifier thresholds, we want high precision and high recall (see discussion in Section 4.5). While "loose" thresholds increase the processing speed, "tight" thresholds usually result higher solved rates. To solve this trade-off, we propose to set the thresholds giving roughly 99% recall for the lower threshold and 99% precision for the upper. After estimating the parameters of the verifiers, it turned out that in the case of Sokoban, Rubik's Cube, and INT, the thresholds should be in the intervals [0; 0.1] and [0.9; 1]. The final values were determined by rumning grid search over five values in each interval. That required running the evaluation about 25 times. Note that since the verifier is used increase the processing speed, is enough tune the thresholds only for the final version of the pipeline.
We train INT and Rubik's ss Cube components single GPU for about three days. The components for Sokoban are trained on CPUs for about a day. The evaluations in all the environments were also performed this project. Therefore, to properly tune the parameters, requires ten training runs on GPU and 40 evaluations on CPU nodes for each environment.
CPU nodes. See Appendix for the details of the actual infrastructure used in
21

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
G COMPONENTS OF ADASUBS
G.1 SUBGOAL GENERATORS
The main purpose of the subgoal generator is to propose subgoal candidates in every iteration of the planner loop. That is, given the current state of the environment it should output other states that are a few steps closer to goal g.
We train a k-generator by extracting training data from successful trajectories. Let 80, . 8n be a trajectory that leads to the goal 8n. For every state 5; we train the k-generator network to output the state 8 exactly k steps ahead. Provided with dataset of trajectories, this is a supervised objective. Clearly, a state that is l steps ahead does not need to be exactly steps closer to the solution, especially if the trajectories include noise or exploration. However, it is guaranteed to be at most l steps closer, which enables reliable limits to be set for checking reachability.
In a simple approach, & is hyperparameter that needs to be fixed, as proposed by (Czechowski let al.] (022). However, this is a strong limitation if the environment exhibits a variable complex- ity problem. Therefore, AdaSubS instead uses k. This way, the planner can adjust the expansion to match the local complexity of the problem. Additionally, training set of generators can be easily parallelized.
of generators, trained for different values of
For our generators, we use the transformer architecture. The input state is encoded as a sequence of tokens, as described in (Czechowski et al.) [02T, Appendix C). The network produces another sequence of tokens on the output, which is then decoded to subgoal state. The output sequence optimized for the highest joint probability with beam search: the consecutive tokens are sampled iteratively and fixed number of locally best sequences passes to the next iteration. This way, the generator enables sampling of a diverse set of subgoals by adjusting the beam width and sampling temperature. The exact number of the subgoals that the generators output are given in Appendix F
As noted Section 3.1 for the Sokoban environment instead of transformers we use simple con- volutional networks. In this domain, the subgoal is created by a sequence of changes to the input state. The generator network is trained to predict the probability of changing every pixel. Then, the subgoals are obtained as a sequence of modifications that maximize joint probability. For simplicity, in AdaSubS we use beam search for all domains, including Sokoban.
During the inference, the generators output limited set of subgoals to explore. Thus, if the genera- tors are not trained well enough, even with an infinite computational budget, the search may fail to find a solution the given problem, even if one exists. However, with slight modification, Ada- SubS can be guaranteed to find a solution to any given problem (or correctly report that the solution does not exist). We achieve that by adding an exhaustive single-step policy as the last generator. would populate an empty queue with all children of the highest valued but not yet expanded node. Note that such modification never decreases the score since the dummy generator only used when a search is about to fail. In practice, this type of modification is not necessary to obtain strong results.
G.2 CONDITIONAL LOW-LEVEL POLICY (CLLP)
If we want to add a subgoal candidate to our search tree, we need to check whether it is reachable from the current state. This can be done using CLLP a mapping that given a state and a subgoal produces a sequence of actions that connects those configurations, or claims that there is no such configuration. Specifically, the policy network, given the state and subgoal, iteratively selects the best action and executes it until the subgoal is reached threshold number of steps is exceeded, as shown in Algorithm 2
CLLP is trained to imitate the policy that collected the training data. For every pair of states 8;, that are located at most d steps from each other, it is trained to predict action a, taken in state s;- Such action may not be optimal but usually it leads closer to sy. The threshold d controls the range of the policy, as it is trained to connect states that are at most d steps away. Thus, it is essential to set the hyperparameter d to a value that is greater than the distances of all the generators used.
22

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
It is essential that the policy successfully reach the correct subgoals, as it is necessary condition for adding them to the search tree. The training metrics show that in all our environments the policy can reach more than 95% of correct subgoals. This percentage is even higher for short distances.
G.3 VERIFIER
To check whether a k-subgoal is reachable with the conditional policy, we need to call it up to times. If decide to generators with long horizons, it becomes significant computational cost. To mitigate this issue, we use the verifier that estimates the validity of a subgoal candidate in single call. During the search, the generated subgoal candidates are evaluated by the verifier. For each of them, it estimates whether they are valid and outputs its confidence. If the returned confidence exceeds a fixed threshold, we do not run the costly check with the conditional policy. We perform such a check only in case the verifier is uncertain (see Algorithm 3
At the end the search, when a solving trajectory found, we need to find the paths between all the pairs of consecutive subgoals that were omitted due to the verifier (see Algorithm J). Since the length of the final trajectory is usually much smaller than the search tree, that final check requires much less computations.
should be noted that the verifier estimates validity with respect to the conditional policy that is used. In case valid subgoal is generated but the policy cannot reach it for some reason, it cannot be used to build the search tree anyway, for no solution that uses can be generated in the final phase. Thus, the verifier should be trained to predict whether the CLLP that is used can reach the subgoal, rather than whether it is reachable by an optimal policy.
To train the verifier, the generators are validated with CLLP. This way, eventually we obtain a dataset of reachable and unreachable subgoal candidates. We train the verifier network to fit that data. Unlike the other components, training the verifier does not require access to any trajectories, only to a number of problem instances.
our pipeline on some problem instances. All the subgoals created by
G.4 VALUE FUNCTION.
The value function V S + I estimates the negative distance between the current state s and the goal state g. During the search, this information used to select the most promising nodes to expand. For every trajectory so,..., 8n in the dataset it is trained to output given 8,. We opted for a simple training objective but any value function can be used the algorithm.
G.5 QUALITY OF ADASUBS COMPONENTS
The effectiveness of AdaSubS depends on the quality of its trainable components: below we present an analysis of generators and verifiers.
k-trade
1.0
Success rabe
Generator:
& trade-off. The quality of generators dete-
0.6
riorates when & is increased. In Sokoban, nearly 90%
of subgoals created with the 4-generator are valid (ac- cording CLLP). However at the same time for the 16-
0.4
AdeSuls (nurs)
generator, this figure drops to 50%. Similarly, in Rubik's Cube, about 82% of subgoals proposed by the 4-generator are valid, while the 3-generator has over 99% accuracy. On the other hand, longer distances are beneficial to the search as they make it possible to build sparser search trees and achieve a solution faster. It turns out that the optimal choice of & depends on the search budget. It pays to be optimistic (i.e., choose long distances) for small budgets, while more prudent choices have the upper hand when more compute is available. Crucially, AdaSubS with multiple generators successfully resolves the trade-off, outperforming every single generator, see Figure
16 generrrator
penerater
0.0
4-gememtrr
10F
Graph size
Figure 4: Comparison of success rates for different subgoal generators for Sokoban. AdaSubS-k describes using single generator with distance k.
23

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Verifier: precision and recall For each subgoal, the verifier outputs classification probability p, which used to accept the subgoal (if > fns). reject the subgoal (if < (to) or to pass to the further verification (if p [ti.. twil) by CLLP. For the acceptance task, require high precision, as one false positive can lead to the failure of the whole search procedure. This leads to a high value for the corresponding parameter tui (e.g. for Sokoban ti 0.99, which corresponds a precision rate of 97%). For the rejection task, we do not wish to reject true positives. In other words, we aim for high recall. In this case, errors usually increase the search cost; the corresponding parameter to is set to tto = 0.1 for Sokoban (this gives the recall of 99%). Additionally, for the verifier to be useful, we need to avoid passing subgoals to the further verification p [tt. the). It turns that for the thresholds selected, the verifier is able to assess 70% states without the assistance of CLLP.
G.6 ADAPTIVE SUBGOAL SEARCH FLOWCIARR
Adaptive subgoal search
Initialize piority queue
Start
queue empty of budget exceeded?
Yes
Problem unsolved
No max from the queue, generate subgoals s' from s with corresponding generator
AdaSubS priority queue of states with key being distance value pair (k, v). sorted lexicographical order.
extracting node, we use the corresponding k-generator to generate subgoals.
For valid s', we estimate its value add queue once for each geneator distance k., i.e. once each key (K, v)
Is any s' a terminal state?
Yes
Problem solved
No
Add each valid (according verifier CLLP) and unseen to the queue
24

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
H DEVELOPING ADAPTIVE SEARCH METHODS
There are many natural ways to incorporate adaptivity into the subgoal search pipeline. We exper- imented with several designs to find one that gives strong results in any domain. Here we provide detailed description of all the variants tested and the numerical results of their evaluation in our environments. Their implementations can found Section H.2
An adaptive algorithm should adjust the complexity of the proposed subgoals to the local complexity of the environment in the neighbourhood of the processed state. This can be realized using the following two approaches:
Use an adaptive planner that provides list of k-generators, the most promising node in every step selects and generator to expand
Use an adaptive subgoal generator that instead of proposing fixed-distance subgoals learns to automatically adjust the distance.
H.1 ADAPTIVE PLANNERS
When implementing adaptivity with the planner, we need specify list of k-generators P In every iteration, the algorithm will select a node to expand and generators from the list that will create the new subgoals. This way, can directly control the complexity of the subgoals and adapt to the current state and progress of the search.
MixSubS. Given a list of trained k-generators, simple approach to call all of them each time node is expanded. In every iteration, we choose the node with the highest value in the tree and add subgoals proposed by each generator Pkg to Pk... See @ the implementation.
Observe that in the easy areas of the environment the search will progress fast, since the furthest subgoal will most likely have the highest value, so it will be chosen as the next node to expand. On the other hand, in the hard parts the shortest generators are more likely to provide subgoals that advance towards the target at least a step.
This method already achieve superior results compared to single generators, both on small and large budget. the Rubik environment, it even reaches 100% solved cubes. MixSubS provides the advantage of planning with different horizons, but at the same time, it produces many unnecessary nodes in the easy areas, while taking only long steps is sufficient to solve the task. Additionally, one may want to prioritize the generators that perform better, which cannot be done with this method.
Iterative mixing. In this approach, we specify a number of iterations 4 for each generator Pk. We use Pkg expand the highest-valued nodes in the first iterations. Then, we use Pk, to expand the best nodes in the following I iterations and the procedure follows for the consecutive genera- tors. After finishing with the last one, we start again from the beginning. See Algorithm 7 for the implementation.
This algorithm offers the flexibility of specifying the exact number of iterations for each genera- tor, which forms an explicit prioritization. It can resemble some of the listed algorithms for care- fully chosen 4, However, tuning the number of iterations requires much more effort than the other parameter-free algorithms do. Therefore, we experimented with another two mixing approaches that select the generator automatically in every iteration.
Strongest-firs Another natural implementation of the planner is to choose the node with the high- est value and expand it with the longest generator that was not used there yet. See Algorithm for the implementation. While this greedy approach maintain clear advantage over single generators, it outperformed by most of the mixing methods, even the simple mixes. We hypothesize that this method is more sensitive to the errors of the value function if the search enters area that the value function estimates too optimistically, spends too much time trying to exploit it.
longest-first (used by AdaSubS). This method in every iteration selects the longest generator that has at least one node to expand and highest-valued node for that generator in the queue. This way, it explicitly prioritizes using the longest generators and turns to the shorter only when the search is stuck. See Algorithm 9 for the implementation. As shown in the tables below, this method outperforms all other designs, in all the environments and within all budget constraints. It prioritizes
25

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
the better generators, but does not require any additional hyperparameters to by specified. Therefore, we consider the best mixing algorithm and use in AdaSubS as the default planner.
H.2 ADAPTIVE PLANNERS IMPLEMENTATIONS
this section we provide the implementations of the planners. The lines highlighted in blue indicate the differences with the AdaSubS code. All the methods require specifying the list of generators Pko..... Pk. The Iterative mixing planner additionally requires a list iterations t0 ......... 4m
Algorithm 6 MixSubS
Algorithm Iterative mixing
function SOLVE((a)
function SOLVE(S:)
T 0
priority queue
Tx, f parents +
priority queues
parents
T.PUSH( (S))),
A: ko. ...,. km do TL.PUSH((V(EO)) 50)
seen.ADD(so)
while 0 < LEN(T) and LEN(n) < C1 do
seen.ADD(sa)
-: T.EXTRACT_MAXX
cnt +
> Iterations counter b Current generator id
subgoals {pk, (B).....
.h.....P.... Ph. (8)}
id 4- 0
for s' in subgoals do
while 0 I.E((T) and (SN(seen) C1 do
if a' in seen then continue
if cnt = 445 or LEN(TRal = then
if not is VALID(s, s') then
id < (id + 1)%6(m + 1). cnt +-
continue sDDnss parents(s'] ( + (V if SOLVED(s") then
cnt + cnt +1
+ EXTRACT (AXTRACT_MAX() MAX()
subgoals + (s. for in aubgoals do
if s' seen then continue not IS VALID s') then
return I.I._ PATH(S',
p parents)
return False
continue
seen.ADD(s))
parents for k in ka.......................... km do (L. if SOLVED(s") then return LL__PATH(S' p parents)
return False
Algorithm Strongest-firs
Algorithm Longest-first
function SOLVE(8.)
function SOLVE(ss)
T D priority queue with lexicographic order parents + O
>> priority queue with lexicographic order parents + 0 for & in ko...., km do T.PUSH((K, ((oo)) so)) seen.ADD(sa)
for & in ko...., km do
T.P sc))
seen.ADD(s.)
while 0 LEN(T) and LEN(Seen) C1 do
while 0 LEN(T) and LEN(seen) C1 do
(. k), T.EXTRACT MMXX) subgoals + (s(s)
(k: _._ a + T.XTRACT_MAAX subgoals pu(())
for s' in subgoals do if s' in seen then continue if not VALID then
for in subgoals do s in seen then continue not IS_ VALID(S, s') then
continue
continue
seen.ADD(s')
seen.ADD(s")
parents(s") for in Ko, ... Km do (VV)))(((V(E))))) SOLVED(s') then
parenta(s") for k in ko...., ki do T.PUSH(((K: V(s')),
SOLVED(S') then return LL. PATH(S', parents)
return LL PATH(S', parents)
return False
return False
26

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
H.3 ADAPTIVE GENERATORS
A k-generator is trained to propose subgoals that should be exactly ht steps ahead. However, instead opt for long subgoals when the next steps are clear and short
of matching a fixed distance, when difficulties appear, or both if is not certain.
Implementing this idea requires changing the training the generator. Given a training trajectory, for each state we need to select the target state Sa(i) that should be the output of the generator. We tested few methods that select this target.
Longest-reachable We use the low-level conditional policy to estimate the local complexity around
s,. Specifically, we choose St(s) to be the furthest state on the trajectory such that is reachable from with the CLLP and so do all its predecessors. In other words, we check whether CLLP starting 8; can reach 8;+1, 8,4-, etc. When we find the first state 8j that is not reachable, we set t(t) to be j
Intuitively, this approach makes the generator learn output subgoals as distant as possible, but still reachable for CLLP. However, this way the targets are selected on the borderline of reachability, which may lead to too hard subgoals some cases.
reachalee To make target state selection more robust, we modify reachability verifica- tion. Instead of greedily following the best action determined by CLLP probabilities, in every step more likely to take suboptimal actions, so the selected target
sample the action. This way, should be reachable with higher confidence.
Becondary-reaccabble Another method of making more robust selection is to follow the action with the lowest probability that exceeds fixed threshold, e.g. 25%. Intuitively, we follow the action that CLLP considers be good, but is less certain than in the case of the highest-ranked. Therefore, subgoal reached in this way should be reachable with even higher confidence when following the greedy actions.
Our experiments show that the adaptive generators trained according to those designs perform well in the environments Sokoban. However, none of them provide better results than the kSubS baseline. Therefore in this work we focus on planner-based based adaptivity and leave tuning the adaptive generators pipeline for future work.
consider. For instance, all the methods nearly reach 90% solve rate on
H.4 BENCHMARKING RESULTS
Tables 10 12
show the numerical results achieved by the adaptive planners described in section H.] compared baselines: BestFS and kSubS. For some of the methods few variants provided. In each table, the longest-firy first, strongest-fing first and iterative mixing methods use the same set of generators: [3,2, 1] for INT, [4,3, for Rubik, and [8, 4, 2] for Sokoban. Our main algorithm, Adaptive Subgoal Search, uses the longest-first planner and the verifier network.
27

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
INT
Small budget (50 nodes)
Large budget (1000 nodes)
with verifier
without
with verifier
without
BestFS
1.7%
36.7%
k=4
2.2%
0.1%
82.4%
83.0%
k=3
4.0%
0.2%
89.6%
90.7%
kSubS
k=2
2.1%
0.5%
89.8%
91.7%
k=1
0.0%
0.0%
34.7%
46.0%
k=[4,3,]
0.0%
0.0%
94.6%
95.0%
MixSubS
k=
0.0%
0.0%
92.2%
92.9%
k=[3,2]
17.0%
14.8%
92.2%
93.5%
[teration==(1..1]]
32.0%
30.1%
87.0%
88.6%
Iterative mixing
[tcratios=[10.1.]]
43.0%
44.8%
95.1%
96.0%
[terations:4.2.1]]
54.0%
52.1%
93.6%
95.5%
Strongest-first
39.5%
40.8%
88.5%
89.8%
Longest-fing (AdaSubS)
59.0%
51.5%
95.7%
95.5%
Table 10: INT benchmark
Rubik
Small budget (400 nodes)
Large budget (6000 nodes)
with verifier
without
with verifier
without
BestFS
0.0%
1.8%
k=4
28.8%
24.5%
98.6%
98.8%
k=3
19.3%
18.6%
95.6%
95.4%
kSubS
k=2
8.2%
4.5%
99.0%
95.8%
k=1
0.5%
0.5%
76.5%
76.5%
k=[4,3,]
29.1%
20.9%
99.1%
100.0%
MixSubS
k=[4,3]
49.1%
45.1%
99.2%
100.0%
[1111
33.5%
23.0%
99.2%
100.0%
Iterative mixing
Porations=[10,1]]]
50.6%
43.6%
99.1%
99.9%
itrratons=[4.2.1]
48.4%
41.2%
99.2%
100.0%
Strongest-first
33.4%
27.1%
99.0%
99.9%
Longest-first (AdaSubS)
58.0%
52.4%
99.2%
100.0%
Table
Rubik benchmark
28

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
Sokoban
Small budget (100 nodes)
Large budget (5000 nodes)
with verifier
without
with verifier
without
BestFS
45.9%
82.6%
k=16
13.7%
5.1%
60.5%
63.5%
k=8
26.0%
4.7%
85.6%
84.4%
kSubS
k=4
8.2%
2.6%
68.1%
65.5%
k=2
1.4%
0.7%
40.0%
38.3%
k=[8,4,2]
52.7%
37.7%
91.7%
90.2%
MixSubS
k=[16,8,4]
55.6%
44.9%
89.1%
89.0%
[1,11]
52.7%
37.7%
91.7%
90.2%
Iterative mixing
fteratios=(11.1.11
68.3%
58.6%
92.5%
92.1%
sterations(442.1]]
64.5%
52.6%
93.5%
93.2%
Strongest-firy
54.6%
41.9%
92.0%
90.8%
Longest-first (AdaSubS)
72.2%
63.4%
93.4%
93.6%
Table 12: Sokoban benchmark
29

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
I OPTIMALITY OF SOLUTIONS FOR SOKOBAN
We did an additional experiment for Sokoban: we used simple BFS to find the optimal path, and compared its length with the outcome of AdaSubS. The results are follows (tested on 600 Sokoban boards):
For 7% of boards, AdaSubS found the optimal solution.
The average difference between the length of the AdaSubS solution and the optimal solu- tion is 15 steps.
On average, the AdaSubS solution is 38% longer than the optimal one.
30

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
J INFRASTRUCTURE USED
We performed experiments using two types of hardware: with and without access to GPUs. In the former, used nodes equipped with single Nvidia V V100 32GB card Nvidia RTX 2080Ti 11GB card. Each such node had CPU cores and 168GB of RAM. In the latter, we used nodes equipped with Intel Xeon E5-2697 2.60GHz CPU with 28 cores and 128GB RAM.
Each transformer model was trained on a single GPU node for days. Sokoban models were trained on CPU nodes (due the small size of the models).
31

---

Fast and Precise: Adjusting Planning Horizon with Adaptive Subgoal Search
K OUT-OF-DISTRIBUTION ANALYSIS
In Rubik's Cube, we trained the generators on very short trajectories, obtained by applying only 10 random moves to the ordered cube (that covers about 7 10 configurations, compared to 4 10Ss in total), Even with such limited data, AdaSubS succeeded in solving 99% of the fully scrambled cubes tested.
In Sokoban, we check that AdaSubS trained on boards with 4 boxes can tackle instances with 5, 6, and 7 boxes. Specifically, solves 87%, 82%, and 74% of cases, respectively, while kSubS only solves 74%, 67%, and 56%, respectively. 'he results are presented in Figure 5 Note that exactly like the case of INT, AdaSubS consistently has half the failure rate of that of kSubS on OOD instances.
kSubs
Sokoban out-of-distribution generalization
0.93
0.84
0.87
0.82
0.8
0.74
0.74
.
1
0.56
__
0.4
02
Number of boxes board
Figure 5: Out-of-distribation performance of AdaSubS and kSubS for Sokoban boards with more boxes, with budget 5000 nodes. Both methods were trained on instances with 4 boxes. bars correspond to 95% confidence intervals.
32


Reviews:
[{"review_id": "wZfCTgytRe", "reviewer": "Reviewer_1Tzk", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors proposed an algorithm for planning that uses learned components for generating subgoals (states up to k steps away), generating one low-level action between two states (conditional low-level policy, CLLP), verifying whether CLLP can find an action between two states, and predicting the distance between current state and goal state. The novelty from previous work (kSubS) is that multiple subgoal generators are used to adapt the planning horizon based on states. The modules are trained on offline datasets of puzzles with a large state space. Experiment results show that their algorithm is able to solve the problem of visiting fewer states. ", "summary_of_the_review": "Overall it's an exciting paper, tackling hard planning problems with a novel learning-based algorithm. With more details provided about their evaluation, it would make a very strong submission.", "strength_and_weaknesses": "The idea of learned subgoal generators with adaptive planning horizons is novel. The authors performed large-scale experiments on hard planning problems, comparing their methods both with baselines and also on out-of-distribution problems. That's very good efforts.\n\nBefore authors' rebuttal, the paper lacks important details in the main text for understanding. Though the authors stated the size of their training dataset. It's unclear how many problems were used for the results from Figure 2 and Figure 3. It would be helpful to state that in section 4.1 to make the results more convincing. It's also unclear whether the total wall time in Table 2-4 in the Appendix is from solving one problem or multiple problems, and how they compare to BestFS baseline. Without context, 3-26 hours seems too long for the title of the paper to be called \"fast and precise.\" ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "qUy5eJMbfO", "reviewer": "Reviewer_1BT4", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents Adaptive Subgoal Search (AdaSubS), an approach to learning-driven search that uses proposed subgoals and a novel \"verifier\" network to make more direct and rapid progress towards the target state. The approach builds upon recent progress in this space, notably the BF-kSubS, by proposing subgoals thought to be reachable a distance \"k\" from the current state towards the goal (for multiple values of k). Combining this multi-distance subgoal generation with a verifier network to prune subgoal not expected to be easily reachable, the approach makes faster progress towards the goal and is more successful at solving state-space search problems than competitive baselines. The authors study a Sokoban and Rubik's Cube domain and \"INT\" a theorem proving domain.", "summary_of_the_review": "This is a solid paper with a somewhat small theoretical contribution bolstered by impressive results in a challenging domain and clear and comprehensive analysis. There are still a few open questions that I believe the paper should address pertaining to the importance of a few of the components and comparison to baselines.\n", "strength_and_weaknesses": "High-level comments\n- [strong] The paper improves upon the state of the art. Search finds the goal in problem challenging problem instances including longer INT problems than are feasible for other approaches in this space. The results are solid and the analysis is comprehensive. This is a central strength of the paper.\n- [strong] The choice of experiments is good and appropriate for the work.\n- [weak] There is no discussion of optimal paths and the quality of the generated paths between the different approaches. For the INT domain, this is perhaps not possible, but for the other two domains, it would be very helpful to understand if the proposed approach improves success at the expense of plan quality, and the extent to which this tradeoff is made. While I do not believe inclusion of this discussion is essential, the paper would be improved by the inclusion of such a discussion.\n- [weak] Sec. 4.5 (analyzing the quality of individual components) seems to omit a key piece of analysis: how well AdaSubS will perform without the verifier or how well the kSubS baseline will perform with the addition of the verifier. The central distinctions between the two strategies are (1) one versus multiple subgoal generators and (2) the inclusion of the verifier network. I do not believe there are any experiments that seek to understand how impactful the verifier. It could therefore be the case that the low level policy network is not particularly capable and that all of the performance improvement comes from the addition of the verifier, which bypasses that process. Some discussion or additional experiments (or a pointer to where these experiments exist) would be incredibly helpful for understanding.\n\nSmaller comments, questions, and typos:\n- Abstract: Though the abstract makes sense after having read the paper, the first couple sentences are not particularly clear on their own. Consider revising those to provide a clearer picture of what the central, unique insight is.\n- Sec. 1: The figure in the introduction, while informative, is perhaps somewhat misleading, since robot motion is not studied in this work. Perhaps it would be more appropriate to use the Sokoban domain instead.\n- Sec. 2: Typo (I believe) \"variable environment variable complexity\".\n- In Sec. 3, the discussion of the thresholds could be clearer; it was not clear to me until later on that there were two thresholds.\n- Algorithm 1: The 'return' statement may not find a path, in which (I believe) the procedure is to keep looping through paths if a feasible path is not found.\n- Algorithm 1: Also, the first 'for' loop that pushes elements into T appears erroneous. There are not yet multiple values of 'k', since the subgoal network has not been queried; should this simply use k=0 and push the starting state into T?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "kw0WeUmb3q", "reviewer": "Reviewer_EUhR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper introduces a new algorithm Adaptive Subgoal Search (AdaSubS), which aims to generate the prospective sub-goals iteratively to generate a good action plan. The system has innovative components of a subgoal generator, Conditional low-level policy (CLLP) to find action steps and a verification algorithm to swiftly prune the faulty sub-goals obtained.\n\nThe authors present comprehensive results to show that adaptive methods work.\n", "summary_of_the_review": "The paper introduces a new algorithm called Adaptive Subgoal Search (AdaSubS). It covers related work and provides extensive experimental results provided which give an overall insight into the performance of the algorithm on the different problems chosen. However, the paper needs to add details justifying the need for multiple blocks for sub-goal verification and contextualize the properties of the planner. The entire flow of the algorithm needs to be summarized in a flow chart format. The memory and time usage details of the algorithm needs to be mentioned.\n\nThe paper should also connect with well known results in search-based planning on adaptive action selection and heuristic selection. Otherwise, it is re-discovering known behaviors in a new setting.", "strength_and_weaknesses": "Strengths:\n● The paper is well-structured and easy to read.\n● Introduction of novel search algorithm benefiting from both the planning and\nlearning methods.\n● The experimental section is very well organized and provides good insights into\nthe complexity of the domains considered.\n● State-of-the-art results on inequality theorem prover INT.\n\nWeakness:\n- Although the paper shows advancement in learning-based planning, the results are not surprising given that there is a large body of work in search-based planning to show that adaptive action selection / heuristic selection is beneficial in planning. See work like \"Real-Time Adaptive A*\" or historical perspective in a planning book like Ghallab et al. See also recent dissertation titled \"Adaptive Search Techniques in AI Planning and Heuristic Search\" by Maximilian Fickert. \n- A problem with this like of work is that the algos are not complete. They are not guaranteed to  always produce a plan even if such a plan exists. This point should be highlighted. \n* A system architecture diagram depicting the flow of the algorithm would have\nbeen more comprehensible. It is hard to understand if all the chosen sub-goals\nat a given node are being explored.\n● It is mentioned that the verifier network is a binary classification model, and\nif the network fails to predict the feasibility of the sub-goal, the algorithm\nfalls back on to CLLP to decide whether to keep or discard a given subgoal. But\nit is not clear how CLLP is used for this purpose as it generates an action\nplan between two given states. Does an empty sequence from CLLP mean the\nsub-goal is being rejected?\n● The authors commented on the out-of-distribution generalizability of the\ninequality theorem prover INT, however, it could have been interesting to see\nthe status of the other domains.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QsAV8oSPRy7", "reviewer": "Reviewer_Kkdv", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents an algorithm –AdaSubS– that can be trained and configured to solve deterministic search problems. The key idea is to consider multiple lookaheads that would be explored with lower-level policy. The ablation study confirms the effectiveness of the idea in challenging domains.\n", "summary_of_the_review": "The ideas are novel, the components of the algorithm are well-studied to understand their role, and the benchmarks are appropriate.\n\nI recommend acceptance, but I might lower my scores depending on the answer to my questions.", "strength_and_weaknesses": "# Strengths\n\nI'll be short here. See discussion below on my interpretation of the results.\n\n- The paper is mostly well-organized and well written\n- The ablation study confirms the role of the specific modules. \n\t- I appreciated the detailed algorithms in the appendix\n- The conclusions are very clear, at least for the domains and conditions where it was tested.\n\n# Weaknesses\n\n- Scholarship: I think that Czechowski et al. (2021) should be mentioned as a starting point. The manuscript seems timid about it. I think a stronger paper would make that clear. Here is two key quotes:\n\t- > \"kSubS is the first general learned hierarchical planning algorithm shown to work on complex reasoning domains Czechowski et al. (2021) (called BF-kSubS there), attaining strong results on Sokoban and Rubik’s Cube, and INT. kSubS can be **viewED** as a non-adaptive version of AdaSubS realized by a suitable hyperparameters choice: a single subgoal generator and inactive verifier (t lo = 0,t hi = 1).\"\n\t- > \"Most of the hyperparameters, both for training and evaluation, follow from Czechowski et al. (2021). The most important parameter of AdaSubS is the set of k-generators to use and the number of subgoals each of them generate.\n\t- Czechowski et al. (2021) introduced the idea of a search to achieve the goal in k steps. The paper has multiple references on how they used the same parameter.\n- Scholarship: the paper does not review the state of the art on this problem. If the state of the art is not in the same scope, then related work should be discussed anyway.\n\t- For instance, see Cameron et al, IJCAI 2021, below.\n- BestFS is not explained well enough\n\t- (See before my comment on contrib 2 below)\n\t- Given this is the most important baseline, the paper must make sure that the algorithms was properly tuned.\n\t- It seems it's a simple modification respect to the others, but perhaps there are hyperparameters that would work better for BestFS in comparison with AdaSubS\n- No limitations are discussed (see my first question below as an instance)\n\n# Questions: PLEASE ANSWER THESE ONES\n\n- Does the algorithm keep a list of close nodes?\n\t- Do you cache the result of evaluations in Alg 1 or Alg 2?\n\t- It seems Alg 2 migh run predictions multiple times on the same nodes.\n\t- If a node is visited with k = 8, would it also be visited by GET_PATH with k = 2?\n- How would AdaSubS behave in the following case?\n\t- Suppose a degenerated search space where \n\t\t- There are two action applicable actions in each state, but at least one of them always leads to a dead end.\n\t\t- Suppose further that there is actually only one path to the goal.\n\t\t- For a state in the path to the goal, there are two childs: one to the next state in the plan, the other one child that leads to a dead end by a short binary subtree, all of the deadends.\n\t- Suppose the same list of k used in Sokoban: [8, 4, 2]\n\t- Suppose that all the models are not very good. They choose uniformly over their options. Let's disable the verifier.\n\t- It seems that AdaSubS would expand multiple times the nodes in the subtrees that lead to deadends? Moreover, Alg 2, GET_PATH doesn't seem to have any memory. So, if the models are expensive this could grow quickly.\n\t- (If this example doesn't work, please attempt to provide another example where AdaSubS might deteriorate)\n- Would you comment on the following paper published in IJCAI 2021?\n\t- Efficient Black-Box Planning Using Macro-Actions with Focused Effects. Cameron Allen, Michael Katz, Tim Klinger, George Konidaris, Matthew Riemer, Gerald Tesauro. https://arxiv.org/abs/2004.13242\n\t- Macro-actions are sequences of low-level actions. They create them by attempting to change a few variables in the problem.\n\t- They test in Rubik's cube.\n\t- They tested reusing macros in the same domain.\n- Why does the evaluation support the 2nd main contribution?\n\t- End of sect 1 says: \"We present a comprehensive study of adaptive methods, showing that they typically outperform non-adaptive ones\". But given the lack of comments about other potential algorithms, this might not be true in general. \n\t- I'd accept something like \"they outperform similar algorithms without the adaptation\". It seems that the argument is that given that BestFS and the studied algorithms share common elements, then the value of the contributions is justified.\n- How were the hyperparameters set? \n\t- I see the values in appendix F, but I don't see how they were set. Page 19:\n\t\t- > Based on experimental results, we have chosen generators of 8, 4, and 2 steps for Sokoban, 4, 3, and 2 steps for the Rubik’s Cube, and 4, 3, 2, and 1 step for INT. In the first two domains, the longest generator match the one used for kSubS.\n\t- Explaining that would help readers to understand the effort of using the algorithms in another setting.\n\t- Please clarify the computation cost of arriving at these hyperparameter values? For instance, how expensive is to realize that a set of hyperparameter values are not the most adequate?\n- Are the hyper-parameters of BestFS set in the best possible way?\n- Would you mention the multi-queue algorithms in a revised version of the paper? Where? (See that in my section \"Scholarship on search and planning\")\n\n# Other changes\n\n- Please mention the number of subgoals generators and the values of k early in the paper. \n\t- Table 1 shows that the list k is one of the most important factors for performance.\n\t- The number of goals generated changes fundamentally the search space. \n- In the main body, it should say that BestFS with a trained policy, and how it's implemented. (See my comment on contribution 2)\n\n# Minor questions or comments\n\n- Page 5: > Rubik’s Cube is a celebrated 3D puzzle with over 4.3 × 10 18possible configurations.\n\t- Please cite Korf's paper\n- Page 9. Verifier: precision and recall\n\t- I’d say the verifier increase accuracy only in a small budget in INT.\n- Page 6: \"Shaded areas indicate 95% confidence intervals.\" How many trials?\n- Page 15, Sect \"Computational budget analysis\" \n\t- says: Tables 3, 2 and 4 present the number of calls to each component per 1000 episodes.\n\t- Is this testing or during training?\n\t- Are those 1000 instances the same for all the algorithms?\n\t- Is that the total number for 1000 episodes? The common practice in deterministic search is to report numbers per episode.\n- page 17:\n\t- > Rubik’s Cube. To construct a single successful trajectory we performed 20 random permutations on an initially solved Rubik’s Cube and took the reverse of this sequence. Using this procedure we collected 10 7trajectories\"\n\t- are there symmetric movements? Are these optimals path? See comment by Clemens et al.\n- Page 18: \n\t- > \"ρ BFSworks in the following way. First, it uses a trained policy network to generate actions to investigate. Specifically, for INT we use beam search to generate high probability actions (it is necessary as for INT we represent actions as sequences, following Czechowski et al. (2021)). Then, it uses these actions to get a state that follows a given action (note that all our environments are deterministic). Finally, we treat returned states as our new subgoals, which are easily found in one step by the low-level policy.\"\n\t - It's not clear what happens in other domains. \n- page 15: please say this in the main body, not just in the appendix:\n\t- > used for sampling predictions from the subgoal generators – the only component that outputs a set of predictions.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-5%