Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal
Authors: Leah Chrestien
Stefan Edelkamp
Antonin Komenda
Tomáš Pevný
Venue: NeurIPS 2023 poster (2023)
Keywords: Learning heuristic functions
deep learning
Immitation learning
planning
A*
best first search
TL;DR: We propose a theoretically sound loss function designed to minimize number of expanded states in best-first search with merit function. The advantage is demostrated on extensive experimental comparison to SOTA.

Abstract: In imitation learning for planning, parameters of heuristic functions are optimized against a set of solved problem instances. This work revisits the necessary and sufficient conditions of strictly optimally efficient heuristics for forward search algorithms, mainly A* and greedy best-first search, which expand only states on the returned optimal path. It then proposes a family of loss functions based on ranking tailored for a given variant of the forward search algorithm. Furthermore, from a learning theory point of view, it discusses why optimizing cost-to-goal h* is unnecessarily difficult. The experimental comparison on a diverse set of problems unequivocally supports the derived theory.

Optimize Planning Heuristics to Rank, not to Estimate Cost-to-Goal
Leah Chrestien
Tomás Pevný
Czech Technical University in Prague leah. chrestien@aic fel. cvut.cz
Czech Technical University in Prague, and Gen Digital, Inc. pevnytom@fel. cvut.
Stefan Edelkamp Czech Technical University Prague edelkste@fel. cvut.cz
Antonín Komenda
Czech Technical University in Prague antonin komendaffel.. cvrtt. cz
Abstract
In imitation learning for planning, parameters of heuristic functions are optimized against a set of solved problem instances. This work revisits the necessary and sufficient conditions of strictly optimally efficient heuristics for forward search algorithms, mainly A and greedy best-first search, which expand only states on the returned optimal path. It then proposes family of loss functions based on ranking tailored for given variant of the forward search algorithm. Furthermore, from learning theory point of view, it discusses why optimizing cost-to-goal ht is unnecessarily difficult. The experimental comparison on a diverse set of problems unequivocally supports the derived theory.
Introduction
Automated planning finds a sequence actions that will reach a goal in a model of the environment provided by the user. It is considered to be one of the core problems in Artificial Intelligence and it is behind some its successful applications [39 27 46). Early analysis of planning tasks [31] indicated that optimizing the heuristic function steering the search for given problem domain towards the goal can dramatically improve the performance of the search. Automated optimization of the heuristic function therefore becomes central request in improving the performance of planners (6 [3].
Learning planning means optimizing heuristic functions from plans of already solved problems and their instances. This definition includes the selection of proper heuristics in a set of pattern databases 17 22 33 selection of planner from a portfolio (55] learning planning operators
from instances 32 56 learning for macro-operators and entanglements 9 29 and learning heuristic
functions by general function approximators (e.g. neural networks) 45
16 5
The majority of research 45 53
16 optimizes the heuristic function to estimate the cost-to-goal, as it is well known that it is an optimal heuristic for many best-first heuristic search algorithms including * or IDA* 21 28 These works optimize the heuristic function to solve regression problems. But even true cost-to-goal h does not guarantee that the forward search will find the optimal solution while expanding the minimal number of states. This paper defines a stricter version of optimally efficiency [T0 24 as follows. Forward search (or its heuristic) is called strictly optimally efficient iff it expands only states one optimal solution path returned by the search, i.e., if this optimal solution path has + states, the search will expand only states.
This work focuses exclusively on a forward search with merit functions. It presents theoretical arguments as why the order (rank) of states provided by the heuristic function more important
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

than the precise estimate of the cost-to-goal and it formalizes the necessary and sufficient condition for strictly optimally efficient search. also argues why learning to rank a simpler problem than regression estimating the cost-to-goal from statistical learning theory point of view. The main motivation of the paper is similar that in (38), but the derived theory and implementation are much simpler. The sufficiency of optimizing the rank has been already recognized in [59] for a beam-search
and in [18) for greedy best-first search (GBFS), though, unlike this work, it cannot guarantee strict optimal efficiency.
We emphasize that this work neither deals with nor questions the existence of strictly optimally efficient heuristic function with the forward search. It is assumed that the space of possible heuristic functions is sufficiently large, such that there exist one that is sufficiently good. The theoretical results are supported by experimental comparisons to the prior art on eight domains.
The contributions of this paper are as follows.
1. We state necessary and sufficient conditions for strictly optimally efficient heuristic functions for forward search algorithms deterministic planning.
2. We show that when optimizing heuristic function, it is better to solve the ranking problem.
3. We argue, why learning rank is casier than regression used in learning the cost-to-goal.
4. We instantiate it for A and GBFS searches leading to two slightly different loss functions.
5. We experimentally demonstrate on eight problems (three grid and five PDDL) that optimizing rank always better.
2 Preliminaries
A search problem instance is defined by directed weighted graph I' = (S, E, w). distinct node 80 E S and a distinct set of nodes S* C S. The nodes S denote all possible states 8 E S of the underlying transition system representing the graph. The set of edges & contains all possible transitions e E 3 between the states in the form = (s, ). so E S is the initial state of the problem instance and S S S is a set of allowed goal states. Problem instance graph weights (alias action costs) are mappings w E + R20
A path (alias plan)
et), e, = (8)-1,8;) E, of length / solves a task r with 8o and S* iff π = ((so. $1). (s1 82).... s() and st E S An optimal path T is defined a path minimizing the cost of a problem instance r, So, its value f w(x*) Ei w(e:). When cost function w(e)
optimal path corresponds the shortest denotes subplan of plan и containing its first i actions. S" = {si) == denotes the set of states from the path π ((00, (21,82), (st-1,8)) and correspondingly S denotes the set of states in subplan π.z-
one. = ((s, $1), ($1, (s:-1, (2), 82),.....
2.1 Forward search algorithm
To align notation, we briefly review the forward search algorithm, of which A and GBFS are special cases. As we apply full duplicate detection in all of our algorithms, there is bijection of search tree nodes to planning states. Forward Search for consistent heuristics, where l((s) - h(s') S w(s 8') for all edges (") in the w--eighted state space graph, mimics the working of Dijkstra's 's shortest-path algorithm [[]] It maintains two sets: the first called Open list, O, contains generated but not expanded nodes; the second called Closed list, C, contains already expanded nodes. Parameters a and B of a merit function fs) = ag(s) + Bh(ss used to sort states in Open list allow to conveniently describe different variants of the algorithm described in detail shortly below. The forward search works as follows.
1. Initialise Open list as O₂ = {5o}.
2. Set g(su) 0
3. Initiate the Closed list empty, i.e. Co 0.
4. For i 1,... until O
(a) Select the state s; arg min, ag(s) + (h(s)
2

---

(b) Remove s, from - {ss}
(c) If s, E S", i.. is goal state, go 5.
(d) Insert the state s; to C,-1, C, C {8:}
(c) Expand the state 8; into states s' for which hold (st, and for each
i. set g(s") = g(s;) + s's,,s))
ii if s' is in the Closed list as Se and g(s') < g(se) then s, is reopened (i.e., moved from the Closed to the Open list), else continue with (e)
ii.
in the Open list as so and g(s") < (55) then so is updated (i.e., removed
from the Open list and re-added in the next step with updated g(-)), else continue with (e)
iv. add 8' into the Open list
5. Walk back retrieve the solution path.
In the above algorithm, g(s) denotes a function assigning an accumulated cost w for moving from the initial state (5o) a given state s. During its execution, it always expands nodes with the lowest ((s) = (g(()) + 3h( s) Different settings of a and 8 give rise to different algorithms: for A*, == = 1; for GBFS a 0 and B 1.
Consistent heuristics, which are of special interest, are called monotone because the estimated cost of a partial solution f(s) g(s) + h(s) is monotonically non-decreasing along the best path to the goal. More than this, f is monotone on all edges (s, s'), if and only if h is consistent as we have f(') g(s') + h(s') 2 g(s) w(s, + h(s) w(s, s') = fs). For the case of consistent heuristics, no reopening (moving back nodes from Closed to Open) in A is needed, as we essentially
traverse a state-space graph with edge weights w(s. + h(s') h(s) 2 0. For the trivial heuristic ho. we have (x) 0 and for perfect heuristic h", we have f()) = f* g(s) + (s)ss) for all nodes s. Both heuristics ho and h² consistent. For GBFS and other variants, reopening usually neglected. Even if the heuristic is not consistent, best-first algorithms without the reopening, remain
complete i.c., they find a plan if there is one. Plans might not be provably optimal but are often good for planning practice [14].
3 Conditions on strictly optimally efficient heuristic
Let O₂ be an Open list in the 7th iteration of the forward search expanding only states on the optimal path æ. Below definition defines perfect ranking heuristic as a heuristic function where state on some optimal path in the Open list, Sh O Or, has always strictly lower merit value than other states in the Open list off the optimal path, Og \ Sha The intersection S O O contains always exactly one state.
Definition 1 (Perfect ranking heuristic). A heuristic function h(s) is perfect ranking in forward search with a merit function f() = ag(ss () + Bh(s) a problem instance I = ((S, &, w), so, S*) and only if there exists an optimal plan π ((s0,8) $1), (81, s2),..., (st-1,, s1)) such that
g(s)) is the cost from so to s in a search-tree created by expanding only states on the optimal path æ;
Vi E (I....,I) and Vs, E O, \ 8 we have f(s)) f(s))-
As an example consider a search-tree in Figure la with an optimal path ((s0, 81), (81, 82), (82. 83)) and states (84, 85, 86, 87) off the optimal path. Then the Open list after expanding so is O₂ (81,84, 85, and that after expanding 81 is O₂ = (82, 84. 86, 86, }7 The set of states on the optimal sub-path are S (so, $1 5 {so, $1, 32 States on the optimal path in the Open lists are STa n O = { and S n O² = {s2). States off the optimal path in the Open lists are ST 85) and O₂ S {sa, 85, 86, s6, 37). Function f is perfectly ranking problem
instance in Figure la iff following inequalities holds:
((s)) < s(44), f(s1) < f(s))
f(x2) < (844,
((x2) < f(a); f(s2) < f(s)).
f(s2) < f(s),
Notice that the heuristic values of states on the optimal path are never compared. This because the forward search expands only states on the optimal path, then its Open list always contains only
3

---

50
8
B
3
84
$1
85
10
B
ST
2
$3
(a) An example of search tree created by expanding only (so: 81, 82, 83). Grey nodes denote states on the optimal path and pink nodes denote states off the optimal path.
(h) Problem instance where perfect heuristic is not strictly optimally efficient with GBFS. Numbers the edges denote cost action and red numbers next to nodes denote the minimal cost-to-goal.
the optimal path
one state from the optimal path. The definition anticipates the presence of multiple optimal solutions and even multiple goals, which requires the heuristic break ties and have perfect rank with respect to one them.
The forward search with merit function f(s) ag((s) + (Bh(s) and a heuristic is strictly optimally efficient on a problem instance ((S, E, w), 80. S*) if and only if h is perfect ranking on
Theorem
Proof. Sufficiency: If the conditions of a perfect ranking heuristic hold, then there exists optimal path such that a state on it that is the Open list always has the strictly lowest hcuristic value. Therefore, forward search will never off the optimal path and is, therefore, strictly optimally efficient.
Necessity: If h is strictly optimally efficient heuristic, then the forward search always selects the state on the optimal path, which means that the state has the lowest heuristic value of all the states in the Open list, which is precisely the condition of perfect ranking heuristic.
Theorem D despite being trivial, allows certifying that the forward search with a given heuristic in given problem instance is strictly optimally efficient. This property has been discussed in [59] for Beam search, but the conditions stated there are different because Beam search prunes states in the Open list. Recall that the complexity class of computing perfect ranking heuristic function is the same as solving the problem because one implies the other. We now remind the reader that the popular cost-to-goad goal does not always lead to strictly optimally efficient forward search.
While cost-to- goag h' is the best possible heuristic for algorithmss like A (up to (e-breaking) in terms of nodes being expanded, for GBFS, h² does not necessarily yield optimal solutions.
Example 1.
See Figure 2 for a counterexample. The complete proof is in the Appendix. Appendix 8.4 also gives an example of a problem instance, where an optimally efficient heuristic for GBFS returning the optimal solution does not exist.
4
Loss functions
4.1
Ranking loss function
Let's now design loss function minimizing the number of violated conditions in Definition forr a problem instance (T, 60, S*) and optimal plan и. Assuming a heuristic function h(s, 0) with parameters 0 E O the number of violated conditions can be counted as
T (h, 1, = Σ Σ
[r(8s, 8,, 0].
s,E8* STE0
where
r(s 8y,0) =a(g(s)) ((3,)) + B(h(s, 0) h(ss, 0))
(2)

---

Oi, S as used in Definition] 1 [III denotes Iverson bracket being one if the argument is true and zero otherwise, and and 3 are parameters controlling the type of search, as introduced above.
In imitation learning, we assume that we have a training set TuD consisting of tuples of problem instances and optimal plans Tum {((S, &i, wt),, S heuristic function (ts, 0), we propose to minimize the number of wrongly ranked states over all the problem instances in the training set,
ma))?==- ; To optimize parameters f of
arg min 8E
Σ Loi (h, .T).
In practice, one often wants to solve problem ② by efficient gradient optimization methods. To do so, the Iverson bracket [-] (also called 0-1 loss) usually replaced by convex surrogate such the hinge-loss or the logistic loss used in the Experimental section below, which case Equation becomes
Σ Σ log(1 + sy.
arg min BEG
(T SLES" SyES'
While optimization of the surrogate loss might look as if one optimizes a different problem, it has been shown that for certain classes of functions, optimization of surrogate losses solves the original problem 3 as the number of training samples approach infinity [50 35
4.2 Regression loss function
For the sake of comparison, we review a loss function used in the majority of works optimizing the cost-to-goal in imitation learning for planning (some notable exceptions are in the related work section). The optimization problem with L2 loss function is defined as
arg min DE
Σ (h(s,, -
(5)
(T.))T7* $LES"
where h" (s:) is the true cost-to-goal. The optimal solution of the optimization is the heuristic function h" What is important for the discussion below is that the L2 loss function uses only states on the optimal path and the heuristic function is optimized to solve the regression problem. Other variants of regression loss, such as asymmetric L, in [51], do not solve issues of regression losses discussed in this paper.
4.3 Advantages and disadvantager of loss functions
Cost-to-goal provides a false sense of optimality It has been already mentioned above that A* with h" is strictly optimally efficient up to resolving states with the same value of g(s) + h" h"(ss. This means that for problems with a large (even exponential) number of optimal solutions of equal cost (see (23 for examples), A will be very inefficient unless some mechanism for breaking ties is used. Moreover, since learning inherently imprecise, a heuristic close but not equal to h" will likely be less efficient than the one close to perfect-ranking heuristic.
Size of the solution set The set of all functions satisfying Equation is likely smaller than that satisfying Equation (3) because the solution set of (3) is invariant to transformations by stricly monotone functions, unlike the solution set of (5). From that, we conjecture that finding the solution of (5) is more difficult. The precise theorem is difficult to prove since the solution of (5) is not a solution of (3) due tie resolution in Definition [
Optimizing cost-to-goal does not utilize states off the solution path Assume a problem instance ((S, &, w), 80, 80,
S*) and an optimal solution path ((s0,8) (81, (21,8))..... (st-1, 1, (1)). Loss function optimized in (5) uses only states {s:]_ on the optimal path. This means that even when the loss is zero, the search can be arbitrarily inefficient if states 87 off the optimal path will have heuristic values smaller than min h(s). The proposed ranking loss (3) uses states on and off the optimal path and therefore, does not suffer from this problem. This issue can be fixed if the training set is extended to contain heuristic values for all states off the optimal path (states {sa, $s, $6, $7 } in Figure Ta}, as has been suggested in 49 With respect to the above definitions, this is equal to adding more problem instances to the training set sharing the same graph I and set of goal states S*, but differing in initial states. Solving all of them to obtain true tost-l greatly increases the cost of creating the training set.
5

---

Heuristic value for dead-end states should be sufficiently high to ensure they are never selected. An infinity the L2 loss would always lead to an infinite gradient in optimization. In practice, the oo is replaced by a sufficiently large value, but too large values can cause large gradients of T.2, which might negatively impact the stability of convergence of gradient-based optimization methods. Proposed ranking losses do not suffer this problem.
Goal-awareness
The drawback of the heuristic function h(s, 0) obtained by optimizing ranking losses is that they are not goal-aware unlike the heuristic optimizing the estimate of cost-to-goal.
Speed of convergence against the size of training set From classical bounds true error [54 and 77. we can derive (see Appendix for details) that the excess error of ranking loss converges
which is slightly faster than that of regression V - vinn, where n, and pp denotes the number of states and state pairs respectively in the training set. But, the number of state pairs in the training set grows quadratically with the number of states; therefore, the excess error of ranking loss for the number of states n, can be expressed as v2ln which would be by ",
to zero at rate Vluny,
Vinn,
_ factor faster than that of regression. Note though that these rates are illustrative since at least v.,
the independency of samples (and sample pairs) is in practice, violated since even samples from the same problem instance are not independent.
Conflicts in training set Unlike regression loss, the proposed family of ranking losses is potentially sensitive to conflicts in the training set, which occur when the training set contains examples of two (or more) different solution paths of the same problem instance. This might prevent achieving zero loss. The effect on the heuristic depends on the composition of the training set. Either solution paths more frequent in the training set will be preferred, or there will be ties, but their resolution do not affect optimally efficiency. Appendix 8.5 provides an illustrative example.
5 Related Work
The closest work to ours is (3) which adjusts heuristic value by a policy estimated from the neural network. The theory therein has the same motivation, to minimize the number of expanded states, though it is more complicated than the theory presented here. For efficiency, (38] needs to modify the GBFS such that search nodes store policy and probability of reaching the node from the start. Moreover, in some variants (used in the experimental comparison below) the neural network has to estimate both heuristic value and policy.
Inspired by statistical surveys of heuristic functions in 57 states preserving order defined by the true cost-to-goal. The formulation therefore valid only for GBFS and not for A search. Ties are not resolved, which means the strict optimal efficiency cannot be guaranteed. Similarly, heuristic values for domains where all actions have zero cost cannot be optimized. Lastly and importantly, the need to know the true cost-to-goal for all states in the training set greatly increases the cost of its construction as discussed above. From Bellman's 's equation [49] arrives at the requirement that the smallest heuristic value of child nodes has to be smaller than that of the parent node. The resulting loss is regularized with L, forcing the value of the heuristic to be close to cost-to-goal.
58
18
proposes to optimize the rank of
In 55, A* is viewed as a Markov Decision Process with the Q-function equal to the number of steps of * reaching the solution. This detaches the heuristic values from the cost-to-goal cost, but it does not solve the problem with dead-ends and ties, since the optimization done by minimizing T.2 loss.
Symmetry of Le (and of Lj) loss are discussed in [51] as it does not promote the admissibility of the heuristic. suggests asymmetric Lj loss with different weights on the left and right parts, but this does not completely solve the problem of estimating cost-to-goal (for example with ties, dead-ends).
Parameters of potential heuristics 41 to meet admissibility constraints while helping the search. On contrary, this work focuses on the efficiency of the search for many problem instances but cannot guarantee admissibility in general.
are optimized by linear programming for each problem instance
Combining neural networks with discrete search algorithms, such that they become an inseparable part of the architecture is proposed in [55] and [60]. The gradient with respect to parameters has to be

---

propagated through the search algorithm which usually requires both approximation and the search algorithm to be executed during every inference.
improves the Monte Carlo Tree Search (MCTS), which has the advantage suppress the noise in estimates of the solution costs. These methods proposed there are exclusive to MCTS and do not apply to variants of the forward search algorithm. Similarly, investigate architectures of neural networks implementing the heuristic function hss, 0), ideally for arbitrary planning problems. We use 45 g to implement h(s, 0), but remind our readers that our interest is the loss function minimized when optimizing A.
A large body of literature 46
20 15 2
a lot of works 45 53 61 19 16
Finally, M proposes to construct a training set similarly to pattern databases [2] by random backward movements from the goal state and to adapt A* for multi-core processors by expanding k >> states in each iteration. These improvements are independent of those proposed here and can be combined.
Experiments
The experimental protocol was designed to compare the loss functions while removing all sources of variability. It therefore uses imitation learning in planning [18 19] and leaves more interesting bootstrap protocol for future work [3]. The goal was not to deliver state-of-the-ard results, therefore the classical solvers were omitted, but their results are in the Appendix for completeness.
The proposed ranking losses are instantiated with the logistic loss function as in Equation 4 for A*
search by setting a B in (2) called L_" and for GBFS, by setting a = 0, B 1 in called L.gss- Lg is used as defined in Equation (5). Since the heuristics used in this paper are not admissible, A search will not provide optimal solutions. It was included in the comparison to demonstrate that heuristics optimized with respect to Libts might be inferior in A search. To observe the advantage of ranking over regression, we defined Let loss function
L (h,
Σ (+)1)1)))
log(1 + exp(h(s,, 0) h(s;-1,0))) 0))
(6)
comparing only states on the optimal trajectory. We also compare to the loss function proposed in 44
defined Loe (h, 1,, T) Exes= max(1 + ming/eN(s) h(s', 0) h(s, 0) 0} + max h (s)s) 0), + max. :(0, h(s, 0) 2h" (s)]. where NV(s) denotes child-nodes of state Furthermore, we compare to the policy-guided heuristic search [38] (denoted as Lí,) with GBFS modified for efficiency as described in the paper while simultaneously adapting the neural network to provide the
policy and heuristic value.
The heuristic function h(s, 0) for given problem domain was optimized on the training set containing problem instances and their solutions, obtained by SymBA* solver (52) for Sokoban and Maze with teleports and [2 for Sliding Tile. Each minibatch in SGD contained states from exactly single problem instance needed to calculate the loss. This means that for Lz, L,t, Lies only states on the solution trajectory were included; for L", Lighs and Lbee there were additional states of distance one (measured by the number of actions) from states on the solution trajectory. Optimized heuristic functions were always evaluated within A* and GBFS forward searches, such that we can analyze how the heuristic functions specialize for a given search. To demonstrate the generality, experiments contained eight problem domains of two types (grid and general PDDL) using two different architectures of neural networks described below.
Neural network for grid domains States in Sokoban, Maze with teleports, and Sliding-uuzze can be easily represented in grid (tensor). The neural network implementing the heuristic function h(s,0) 0) was copied from [8] Seven convolution layers, PI... Py of the same shape 3 x 3 with 64 filters are followed by four CoAT blocks (CoAT block contains a convolution layer followed by a multi-head attention operation with 2 heads and positional encoding layer). Convolution layers in CoAT blocks have size 3 x 3 and have 180 filters. The network to this stage preserves the dimension of the input. The output from the last block is flattened by mean pooling along and y coordinates before being passed onto a fully connected layer (FC) predicting the heuristic. All blocks have skip connections.
runs the "LAMA 2011 configuration" of the planner
7

---

Neural network for PDDL domains For Blocksworld. Ferry, Spanner, N- N-Puzzle, and Elevators, where the state cannot be easily represented as a tensor, we have used Strips-HGN 44 and we refer the reader therein for details. Strips-HGN was implemented in Julia A using PDDL. j1 [6 extending [3).. Importantly, we have used the hyper-graph reduplication proposed in 48 to im- prove computational efficiency. Since we did not know the precise architecture (unlike in the grid domain), we performed a grid-search over the number of hyper-graph convolutions in {1, 2, 3), dimensions of filters in {4, 8, 16), and the use of residual connections between features of vertices. The representation of vertices was reduced by mean and maximum pooling and passed to a two-layer feed-forward layer with hidden dimension equal to the number of filters in hyper-graph convolutions. All non-linne con-linarsttes were of relu type. The best configuration was selected according to the number of solved problems in the validation set. Forward search algorithms were given 5s to solve each problem instance chosen in a manner to emphasize differences between loss functions. All experiments were repeated 3 times. All experiments on the PDDL domains including development took 17724 CPU hours. Optimizing heuristic for a single problem instance took approximately 0.5 CPU/h except Gripper domain, where the training took about 8h due to large branch factors. The rest of this subsection gives further details about domains.
Sokoban The training set for the Sokoban domain contained 20000 mazes of grid size 10 x 10 with single agent and 3 boxes. The testing set contained 200 mazes of the same size 10 10, but with 3, 4, 5, 6, boxes. Assuming the complexity of to be correlated with the number of boxes, we can study generalization to more difficult problems. The problem instances were generated by [40]
Maze with teleports The training set contained 20000 mazes of size 15 x 15 with the agent in the upper-left corner and the goal in the lower-right corner. The testing set contained 200 mazes of size 50 x 50, 55 x 55, and 60 x 60. Therefore, as in the case of Sokoban, the testing set was constructed such that it evaluates the generalization of the heuristic to bigger mazes. The mazes were generated using an open-source maze generator [47], where walls were randomly broken and 4 pairs of teleports were randomly added to the maze structure.
Sliding puzzle The training set contained 20000 puzzles of size 5 5. The testing set contained 200 mazes of size 5 x 5. These puzzles were taken from (37] Furthermore, we tested our approach on puzzles of higher dimensions such 6 x 6 and 7 all of which were generated with [37]. Thus, in total, the testing set contained 200 sliding tile puzzles for each of the three dimensions.
Blocksworld, N-Puzzle, Ferry, Elevators, and Spanner The problem instances were copied from 44 (Blocksworld, N-Puzzle, and Ferry) and from (34) (elevators Sorttcorr---ssstee 0t-sirips). Problem instances of Spanner were generated by [43. Blocksworld contained 732 problem instances of size 3-15, N-Puzzle contained 80, Ferry contained 48, Elevators contained 80, and Spanner contained 440. Table in Appendix shows the fraction of -olved mazes by breadth- first search for calibration of the difficulty. The problem instances were randomly divided into training, validation, and testing sets, each containing 50% 25% / 25% of the whole set of problems. The source code of all experiments is available at https://gghuub.comaacaneeeetee planaeeeeettiiiiiiiiaaainnggg -lanningeeuuurissiiisss-sssss-s Rank with MIT license.
6.1 Experimental results
Table I shows the fraction of solved mazes in percent for all combinations of search algorithms (A* and GBFS) and heuristic functions optimized against compared loss functions. The results match the above theory, as the proposed ranking losses are always better than the 12 regression loss.
For * search, the heuristic function optimized against the L is clearly the best, as it is only once inferior to Lyc and Lbee on the Ferry domain. As expected, heuristic functions optimized with respect to Light behave erratically in A* search, because they were optimized for a very different search.
For GBFS, heuristic functions optimized against the L* or against Lybes behave the best. It can be shown (the proof is provided in Apendix) that since each action has constant and positive cost, the heuristic function optimizing L* optimizes Lybh as well, but the opposite is not true.
Heuristic functions optimized against L2 estimating cost-to-goal deliver most of the time the worst results. Heuristic functions optimized against other ranking losses I, and T frequently perform well, most of the time better than L2, but sometimes (Elevators, Sokoban, Sliding puzzle) are much
8

---

A#
GBFS
problem
complx.
'gbfs
Tyt
1.2
Tbe
1."
'gbis
lyt
1/
Lbc
1ec
Blocks
100
100
100
99
100
100
100
100
100
100
99
Ferry
98
98
100
92
100
98
100
100
100
98
98
N-Puzzle
87
88
83
89
89
89
89
92
88
Spanner
100
89
100
84
92
100
100
100
100
100
100
Elevators
91
85
75
36
66
92
85
79
76
67
58
Sokoban
3 boxes
99
98
96
97
92
98
100
94
95
92
98
4 boxes
89
89
85
81
82
87
91
84
83
84
84
5 boxes
80
75
72
72
73
78
77
74
72
72
73
6 boxes
69
59
51
53
71
56
51
54
64
7 boxes
55
49
47
42
45
51
49
48
4.3
455
49
Maze w.
50
91
87
87
90
89
84
85
89
55 x 55
78
75
73
72
74
74
75
74
72
75
74
60 x 60
49
37
35
32
31
42
48
36
34
32
42
Sliding puzzle
5 x
88
83
84
80
82
86
87
84
84
84
855
6 x 6
51
48
49
45
46
47
49
45
43
46
48
7
39
35
36
32
34
35
36
35
32
34
35
Table 1: Fraction of solved problem instances in percent from the testing set. The top row denotes the type of the search and the second top row denotes the loss function against which the heuristic function was optimized. The complexity is explicitly shown for grid domains. Standard deviations most of the times smaller than one percent and are provided in Table in the Appendix.
stating that optimizing the exact estimate of cost-to-goal is unnecessary, but they also show the advantage including states off the optimal path in the loss function. Finally, the method combining policy and heuristic in GBFS, Lie, (38] performs better that L2, but worse than the proposed ranking losses. Since both approaches are derived from the same motivation, we attribute this to difficulties in training neural networks with two heads. Ranking losses optimize just the heuristic which is directly used in the search, which seems to to be simpler. Additional statistics, namely the average number of expanded states (Table and the average length of plans (Table are provided in the Appendix.
worse than proposed losses. These experiments further confirm the 17 59
7 Conclusion
The motivation of this paper stemmed from the observation that even the cost-to-goal, considered to be an optimal heuristic, fails to guarantee a strictly optimally efficient search. Since a large body of existing research optimizes this quantity, optimized. To fill this gap, we have stated the necessary and sufficient conditions guarantecing the forward search to be strictly optimally efficient. These conditions show that the absolute value of the heuristic is not important, but that the ranking of states in the Open list is what controls the efficiency. Ranking can be optimized by minimizing the ranking loss functions, but its concrete implementation needs to correspond to a variant of the forward search. In case of mismatch, the resulting heuristic can perform poorly, which has been demonstrated when the heuristic optimized for BGFS search was used with A search. The other benefit of ranking losses is that from the point of view of statistical learning theory, they solve simpler problem than ubiquitous regression in estimating the cost-to-goal.
effectively lost with respect to what should be
The experimental comparisons on eight problem domains convincingly support the derived theory. Heuristic functions optimized with respect to ranking loss L instantiated for A search perform almost always the best with A search (except for case where it was the second best). In the case of GBFS, heuristic functions optimizing ranking losses Libis and L instantiated for GBFS and A worked the best. This is caused by the fact that the heuristic optimizing L for A optimizes Libis for GBFS as well.
We do not question the existence of a strictly optimally efficient heuristic. Given our experiments, we believe that if the space of heuristic functions over which the loss is optimized is sufficiently rich, the result will be sufficiently close to the optimal for the needs of the search.

---

7.1 Acknowledgements
This work has been supported by project numbers 22-32620S and 22-30043S from Czech Science Foundation and OP VVV project 17.02.1.01/0.000 matics". This work has also received funding from the European Union's Horizon Europe Research and Innovation program under the grant agreement TUPLES No 101070149.
019/0000765 "Research Center for Infor-
References
[1] Forest Agostinelli, Stephen McAleer, Alexander Shmakov, and Pierre Baldi. Solving the rubik's cube with deep reinforcement learning and search. Nature Machine Intelligence, 188):356-363, 2019.
[2] Thomas Anthony. Zheng Tian, and David Barber. Thinking fast and slow with deep learning and tree search. In Isabelle Guyon, Ulrike Luxburg. Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5360-5370, 2017.
[3] Shahab Jabbari Arfaee, Sandra Zilles, and Robert C Holte. Learning heuristic functions for large state spaces. Artificial Intelligence, 1 (75(1611))200755 17):2075 2011.
[4] Jeff Bezanson, Alan Edelman, Stefan Karpinski, and Viral Shah. Julia: A fresh approach to numerical computing. SIAM review, 59(1):5--9,, 2017.
[5] Mohak Bhardwaj, Sanjiban Choudhury, and Sebastian Scherer. Learning heuristic search via imitation. In Conference on Robot Learning, pages 271-280. PMLR. 2017.
[6] Blai Bonet and Héctor Geffner. Planning heuristic search. Artificial Intelligence. 2001 Jun; 129 (1-2): 5-33., 2001.
[7] Vladimir Cherkassky, Xuhui Shao, Filip M Mulier, and Vladimir N Vapnik. Model complexity control for regression using ve generalization bounds. IEEE transactions on Neural Networks, 1065):1075-108, 1999.
[8] Leah Chrestien, Tomáš Pevný, Antonín Komenda, and Stefan Edelkamp. Heuristic search planning with deep neural network using imitation, attention and curriculum learning. In PRL-IJCAI workshop, 2021.
[9] Lukás Chrpa. Combining learning techniques for classical planning: Macro-operators and entanglements. In ICTAI, pages 79-86. IEEE Computer Society, 2010.
[10] Rina Dechter and Judea Pearl. The optimality A revisited. In Michael R. Genesereth, editor, AAAI, pages 95-99, AAAI Press, 1983.
[11) Edsger W. Dijkstra. A note on two problems in connexion with graphs. Numerische Mathematik, 1:269-22 271, 1959.
[12] Stefan Edelkamp. Automated creation of pattern database search heuristics. Model Checking and Artificial Intelligence, pages 35-50, 2006.
[13] Stefan Edelkamp and Stefan Schrödl. Heuristic Search Theory and Applications. Academic Press, 2012.
[14] Ariel Felner, Uzi Zahavi, Robert Holte, Jonathan Schaeffer, Nathan Sturtevant, and Zhifu Zhang. Inconsistent heuristics in theory and practice. Artificial Intelligence, 17509):1500-1603 201 1.
(15) Dieqiao Feng, Carla P. Gomes, and Bart Selman. Solving hard AI planning instances using curriculum-driven deep reinforcement learning. In Christian Bessiere, editor, Proceedings of the Twetty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020, pages ijcai.org, 2020.
[16] Patrick Ferber, Malte Helmert, and Jörg Hoffmann. Neural network heuristics for classical planning: A study of hyperparameter space. In ECAL, pages 2346-2353. IOS Press, 2020.
10

---

[17] Santiago Franco, Alvaro Torralba, Levi H. S. Lelis, and Mike Barley. On creating complementary pattern databases. In IJCAI, pages 4302-4309, 2017.
[18] Caelan Reed Garrett, Leslie Pack Kaelbling, and Tomás Lozano-Pérez. Learning to rank for synthesizing planning heuristics. page 3089-3095, 2016.
[19] Edward Groshev, Aviv Tamar, Maxwell Goldstein, Siddharth Srivastava, and Pieter Abbeel. Learning generalized reactive policies using deep neural networks. 2018.
[20] Arthur Guez, Théophane Weber, Ioannis Antonoglou, Karen Simonyan, Oriol Vinyals, Daan Wierstra, Rémi Munos, and David Silver. Learning to search with metsnets. In International conference machine learning, pages 8822-1831. PMLR, 2018.
[21] Peter Hart, Nils J Nilsson, and Bertram Raphael. formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics, 4(2):100-107, 1968.
[22] Patrik Haslum, Adi Botea, Malte Helmert, Blai Bonet, and Sven Koenig. Domain-independent construction of pattern database heuristics for cost-optimal planning. In AAAI, pages 1007-1012, 2007.
[23] Malte Helmert and Gabriele Röger. How good is almost perfect? In AAAI, pages 944-949. AAAI Press, 2008
[24] Robert C. Holte and Sandra Zilles. On the optimal efficiency of cost-algebraic A. In The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019, pages 2288-2296 AAAI Press, 2019.
[25] Michael Katz, Shirin Sohrabi, Horst Samulowitz, and Silvan Sievers. Delfi: Online planner selection for cost-optimal planning. IPC-9 planner abstracts, pages 57-64, 2018.
[26] Diederik P Kingma and Jimmy Ba. arXiv:1412.6980, 2014.
Adam: A method for stochastic optimization.
[27] Donald E Knuth and Ronald W Moore. An analysis of alpha-beta pruning. Artificial intelligence. 6(4):293-326, 1975.
[28] Richard E. Korf. Ieeratie-deepennng-AA, An optimal admissible tree search. In IJCAL, pages 1034-1036. Morgan Kaufmann, 1985.
[29] Richard E Korf. Macro-operators: A weak method for learning. Artificial intelligence, 26(1):35- 77, 1985.
[30] Šimon Mandlík, Matěj Račinský, Viliam Lisy, and Tomáš Pevný, Jsongrinder, jl: automated differentiable neural architecture for embedding arbitrary json data. Journal of Machine Learning Research, 23(298):1-5,, 2022.
[31] Drew V. McDermott. A heuristic estimator for means-ends analysis in planning. In AIPS, pages 142-149. AAAI, 1996.
[32] David Ménager, Dongkyu Choi, Mark Roberts, and David W. Aha. Learning planning operators from episodic traces. In 2018 AAAI Spring Symposia. AAAI Press, 2018.
[33] Ionut Moraru, Stefan Edelkamp, Santiago Franco, and Moisés Martínez. Simplifying automated pattern selection for planning with symbolic pattern databases. In KI, pages 249-263, 2019.
[34] Christian Muise. Collection of pddl files of classical problems. https:/giihubbcoo/AllPlaininni classical-domaing 2023.
[35] XuanL.ong Nguyen, Martin Wainwright, and Michael Jordan. On surrogate loss functions and f-divergences. The Annals of Statistics, pages 876-904, 2009.
[36] Laurent Orseau, Levi Lelis, Tor Lattimore, and Théophane Weber. Single-agent policy tree search with guarantees. Advances in Neural Information Processing Systems, 31, 2018.
11

---

[37] Laurent Orseau and Levi HS Lelis. Implementation of the algorithms described in "policy- guided heuristic search with guarantees" by orseau and 1. lelis, published aaai'21. https: /ggthub.coom/eeveiiihh--een 2021.
[38] Laurent Orseau and Levi HS Lelis. Policy-guided heuristic search with guarantees. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12382-12390, 2021.
[39] Arthur L Samuel. Some studies in machine learning using the game of checkers. ii recent progress. IBM Journal of research and development, 11(6):601-617, 1967.
[40] Max-Philipp B. Schrader. gym-sokoban. http://gitibbbcooommgiimmeeegeoo 2018.
[41] Jendrik Seipp, Florian Pommerening, and Malte Helmert. New optimization functions for potential heuristics. In ICAPS, 2015.
[42] Jendrik Seipp and Silvan Sievers. Fast downward stone soup 2023.
[43] Jendrik Seipp. Álvaro Torralba, and Jörg Hoffmann. PDDL generators https://doi.or/1005555 zenodo.6382173. 2022.
[44] William Shen. Strips-hgn. http://gshhaaccco/lllllalsssssss
2021.
[45] William Shen, Felipe Trevizan, and Sylvie Thiébaux. Learning domain-independdnt planning heuristics with hypergraph networks. In ICAPS, volume 30, pages 574 584, 2020.
[46] David Silver, Julian Schrittwieser, Karen Simonyan, loannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, al. Mastering the game of go without human knowledge. nature, 35047666) 2017.
[47] Kristian Smith. Maze creator / solver. http://gtthoooommmaaaaaaaaaaeeee 2022.
[48] Gustav Sourek, Vojtech Aschenbrenner, Filip Zelezny, Steven Schockaert, and Ondrej Kuzelka. Lifted relational neural networks: Efficient learning of latent relational structures. Journal of Artificial Intelligence Research, 62:69-100, 2018.
[49] Simon Ståhlberg, Blai Bonet, and Hector Geffner. Learning general optimal policies with graph neural networks: Expressive power, transparency, and limits. In Akshat Kumar, Sylvie Thiébaux, Pradeep Varakantham, and William Yeoh, editors, Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling, ICAPS 2022, Singapore (virtual), June 13-24, 2022, pages 629-637. AAAI Press, 2022.
[50] Ingo Steinwart. Consistency of support vector machines and other regularized kernel classifiers. IEEE transactions information theory, 51(1):128-142 2005.
[51] Takeshi Takahashi, He Sun, Dong Tian, and Yebin Wang. Learning heuristic functions for mobile robot path planning using deep neural networks. In ICAPS, volume 29, pages 764-772, 2019.
[52] Alvaro Torralba, Vidal Alcázar, Daniel Borrajo, Peter Kissmann, and Stefan Edelkamp. SymBA*: A symbolic bidirectional A planner. In International Planning Competition, pages 108, 2014.
[53] Sam Toyer, Sylvie Thiébaux, Felipe Trevizan, and Lexing Xie. Asnets: Deep learning for generalised planning. Journal of Artificial Intelligence Research, 68:1-68, 2020.
[54] Vladimir Vapnik. Principles of risk minimization for learning theory. Advances in neural information processing systems, 4, 1991.
[55] Marin Vlastelica, Michal Rolinek, and Georg Martius. Neuro-algorithmme policies enable fast combinatorial generalization. In International Conference on Muchine Learning, pages 10575-10585. PMLR, 2021.
12

---

[56] Xuemei Wang. Learning planning operators by observation and practice. In Kristian J. Ham- mond, editor, AIPS. pages 335-340. AAAI, 1994.
[57] Christopher Wilt and Wheeler Ruml. When does weighted A fail? International Symposium on Combinatorial Search, volume 3, 2012.
[58] Christopher Makoto Wilt and Wheeler Ruml. Effective heuristics for suboptimal best-first search. J. Artif. Intell. Res., 57:273-306, 2016.
[59] Yuehua Xu, Alan Fern, and Sungwook Yoon. Learning linear ranking functions for beam search with application to planning. Journal of Machine Learning Research, 10(7), 2009.
[60] Ryo Yonetani, Tatsunori Taniai, Mohammadamin Barekatain, Mai Nishimura, and Asako Kanezaki. Path planning using neural A search. In International Conference on Machine Learning, pages 12029-12039. PMLR, 2021.
[61] Ziqi Zhang and Florian Geißer. Extending graph neural networks for generalized stochastic planning. In Bridging the Gap Between Al Planning and Reinforcement Learning. 2021.
[62] Tan Zhi-Xuan. PDDL jl: An Extensible Interpreter and Compiler Interface for Fast and Flexible Al Planning. PhD thesis, Massachusetts Institute of Technology, 2022.
[63] Juntang Zhuang, Tommy Tang, Yifan Ding, Sekhar C Tatikonda, Nicha Dvornek, Xenophon Papademetris, and James Duncan. Adabelief optimizer: Adapting stepsizes by the belief in observed gradients. Advances in neural information processing systems, 33:18795-18806, 2020.
13

---

8 Appendix
8.1 Speed of convergence against the size of training set:
We use the classical results of statistical learning theory to show that estimating the cost-to-go converges more slowly with respect the size of the training set than estimating the rank.
From Equation (1) in the main text it should be obvious that ranking is in its essence a classification problem if one considers pair of states (s, s') single sample. For classification/ranking problems, a following bound on true error rate [54] holds with probability 7
Re S Re +
1 [
[1+xih
2np K
V np
17
where R. denotes the true loss (Equation (1) in the main text) and Re. its estimate from Up state pairs (8i, 85), and K, the Vapnik-Chervonent
dimension [54) of the hypothesis space.
Optimizing hss, f) with respect to cost-to-goal (Equation (5) in the main text) is regression problem for which different generalization bound on prediction error 7 holds with probability 1 1-1)
R < R
1 In pe) In m
ng
where again R2 is the error of the estimator of cost-to-go and R, is estimate from n, states (Equation (5) in the main text) and [xr] is shorthand for max(0, x).
From the above, can that excess error in the ranking converges to zero rate mp Shg which is slightly faster than that of regression Vay-vlam But, the number of state pairs in the training set grows quadratically with the number of states; therefore, the convergence rate of the ranking problem for the number of states can be expressed as 1/2n which would be by at least nh ym, factor faster than that of regression. We note that bounds are illustrative, since the independency of samples is in practice violated, since samples from the same wroblem-instanee are not independent.
Vinn,
8.2 Suboptimality of perfect heuristic in GBFS
3
B
3
8
2
y
4
C
D
4
Figure 2: Problem instance where perfect heuristic is not strictly optimally efficient with GBFS. Numbers on the edges denote the cost of action and red numbers next to nodes denote the minimal cost-to-go.
Example 2. While cost-to-goal he is the best possible heuristic for algorithms like A (up to tie-breaking) in terms of nodes being expanded, for GBFS, he does necessarily yield optimal solutions.
g()) hs* and some with f(s) f*(()= g(s) + ht (s), so nodes can only be saved with optimal (s) (s)) + (s). In fact, when given
Proof. A explores all the nodes with <
"The formulation in 7 contains constants and but authors argue they can be set to = and hasubve been therefore omitted here.
14

---

haas the heuristic, only nodes s with f(s)= = (s) are expanded. Depending on the strategy of tie-breaking, the solution path can be found in the minimal number of node expansions or take significantly longer (e.g., in lower g-value first exploration of the search frontier). Any heuristic other than h* is either overestimating, and, therefore, may lead to either non-optimal solutions in A*, or weaker than h", leading to more nodes being expanded.
Even if htt is given, GBFS is not guaranteed to be optimal. Consider the following graph with five nodes A, B, C, D, E, and w(A, B) = 8, w E) = 3, w(A C*) = 2, w(C, D) = 4, w wD E) = 4, 0 (see Figure 2}. initial node
and h (A) = 10, h (B) = 3, (C) = 8, h" (D) So = A, goal node E E S The numbers are the actual costs and the red numbers are the exact heuristic function. For finding path from node A to node E. GBFS would return (A, B, E)) following
4, h² (E)
the heuristic function. However, the path (A, D, E)) has cost 10 instead of 11.
8.3 Theory
Below, we prove the claim in made in Experimental section stating that if heuristic h is strictly optimally efficient for A search, then it is also strictly optimally efficient for GBFS.
Theorem 2. Let a heuristic is a perfect ranking for A search on a problem instance r = ((S,E, w)), 80, 80, S*) with a constant non-negative cost of actions ((3c 2 0) (Ve E E) (w(e) = c)). Then is a perfect ranking for GBFS on
(SI-1, st)) be optimal plan such that vi E {l..... 1] and Vaj E {sy ((kk E E A  E S A Sj & STC} } we have g(s,) + h(s)) > g(s:) + h(ss),, where g(s) is the distance from Su to s in search-tree created by expanding only states the optimal path и. We want to proof that if all actions have the same positive costs, then h(s;) > h(s;) as well.
Proof. Let π ((sg.
We carry the proof by induction with respect to the number of expanded states.
At the initialization (step 0) the claim trivially holds as the Open list contains just a root node and the set of inequalities is empty.
Let's now make the induction step and assume the theorem holds for the first - 1 step. We divide the proof to two parts. At first, we prove the claim for (O); \>((s;11) and then we proof the claim for N 1s;-1,, where (s)) denotes child states of the state s.
1) Assume 8j E (O)x \ (s(s)))). Since h is strictly optimally efficient for A#, it holds that g(0,) + Mss)) >g(s)) + h((;))
h(s;) >g(x;) g(5))) + h(ss)
M(s;) >h(s;),
where the last inequality is true because g(s;) - g(o;) 2 0.
Assume (s, (W(ss=)))s; st). Since h is strictly optimall efficient for A ,,, it holds that g(0,) + h(,)) > g(8:) + h(s:).
Since g(3,) w((((-1,,))) w((3_111 9:) = g (s),, ) it holds
h h(s;) > hss),
(8)
which finishes the proof of the theorem.
8.4 Optimally efficient heuristic might not exists for GBFS
Consider the following graph in Figure 3 with four nodes A, C, D., and 1,, w D) = 1, 1, (D) 2
= =
1, w(A, C) = 1, w(A, D) = 9, w (B, C) = 9, and ht (A) - 0, -,, where A is the goal state and is the initial state.
We can see that for GBFS, the perfect heuristic does not exist for D. On expansion, the GBFS algorithm will put and B to the open list with heuristic values h(A) = 0 and h(B) = I. GBFS takes A from the open list and checks if it is goal state. Since A is goal state, GBFS terminates returning
15

---

B
0
A
D
2
9
1
C
Figure 3: Problem instance where optimally efficient heuristic does not exists for GBFS.
path (D,A) as a solution. However, this is not the optimal path as a better (optimal) solution exists (D, B, A). Since the definition of optimal ranking requires the inequalities to hold for this optimal path, in GBFS, the perfect heuristic does not exist for all initial states.
The problem can be fixed if the definition of optimal ranking is changed consider two cases in the merit function fs) ag(s) + Bh(s):: >> 0 and 3 > 0 and a 0 and 3 > 0 In the first case, the optimal ranking should defined with respect to the "optimal path" " (this the A*); ); the latter case, it should be the path with minimal number of expansions. With GBFS, the user simply wants to
find a solution but not care about its optimality. With this change, the heuristic function will exist for
Figure 3
8.5 Training set with multiple solution paths with the same length of the plan
The behavior the learned heuristic function depends on the composition of the training set, which is illustrated below on a simple grid problem. The agent starts at position (4,4) and has to move to the goal position (0,0). There are no obstacles and the agent can only move one tile down or one tile left (the effects on his positions are either (-1,0) (0,-1)). the cost of the action is one. The number of different solutions path grows exponentially with the size of the grid and all solution path has the same cost (for problem of size 5x5, there are 70 solutions). This problem is interesting, since merit function in with optimal heuristic function (cost to goal) constant, equal to 8, for all states.
For the size of the grid (4,4), the heuristic is determined by table with 25 values. Below, these values are determined by minimizing the proposed loss for A algorithm with logistic loss surrogate by BFGS (with all zeros as initial solution). Since the loss function is convex, BFGS finds the solution quickly.
In the first case, the training set contains one solution path ([4, 4], [3, 41, [2, 4), [1, 4). [0, 4], [0, 3]. [0, 2], [O. 11, [0, 0J), where the agent first goes left and then down. The learnt heuristic values is shown in T
y/x
0
2
3
4
-191.53
-131.99
-76.94
-31.25
0.0
3
0.0
31.25
76.94
131.99
191.53
2
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0
0.0
0.0
0.0
0.0
0.0
Table Table showing one solution path.
An A search using these heuristic values will first always take action moving the agent left and then down. When moving down, the agent does not have another choice. Notice that the heuristic values of many states are not affected by the optimization, because they are not needed to effectively solve the problem.
16

---

In the second case, the training set contains two solution paths: the first is in Table 2 and in the second table B
the agent goes first down and then left. The learnt heuristic values are shown in
y/x
0
2
3
-95.76
-66.0
-38,47
80.14 14
3
0.0
15.62
38.47
131.99
80.14
0.0
0.0
0.0
38.47
-38.47
0.0
0.0
0.0
15.62
-66.0
0.0
0.0
0.0
0,0
-95.76
Table 3: Table showing two solution paths.
An A search will now face tic at state (4,4), since states (3,4) and (4,3) have the same heuristic value. But the presence of the tie does not affect the optimal efficiency the search, as will always expand states one of the optimal path from the training set.
Finally let's consider a case, where all 70 possible solutions are in the training set. The learned heuristic values are shown in Table 4
y/x
0
4
3.74
92.62
134.66
163.17
0.0
3
-46.61
2.35
91.93
134.38
163.17
2
-167.96
-47.7
1.94
91.93
134.66
1
-210.03
-168.66
-47.7
2.35
92.62
0 0.0
-210.03
-167.96
-46.61
3.74
Table 4: Table showing multiple solution paths.
Rank of heuristic values "roughly" corresponds to cost to goal. The reason, why some states are preferred over the others despite their true cost-to-goal being the same is that they appear in more solution paths. As shown in Table the A search with learnt heuristic values strictly optimally efficient.
8.6 Baseline Comparison to breadth-first search
The fraction of solved problems for treadth-fistt search (5s time limit as used by solvers in the paper) shown in Table 5
domain
fraction
blocks
0.35
ferry
0.31
npuzzle
0.14
spanner
0.63
elevators
0.32
Table 5: Fraction of solved mazes by breadth-fing search.
8.7 Training Details
For the grid domains, ADAM (26 training algorithm was run for 100 x 20000 steps for the grid domains. The experiments were conducted in the Keras-2.4.3 framework with Tensorflow-2.3., as the backend. While all solvers were always executed on the CPU, the training used an NVIDIA Tesla GPU model V100-SXM2-32GH Forward search algorithms were given 10 mins to solve each problem instance.
For the PDDL domains, the training consumed approximately 100 GPU hours and evaluation consumed 1000 CPU Alurs.All training and evaluation were done on single-core Intel Xeon Silver 4110 CPU 2. 10GHz with memory limit of 128GB. The training algorithm AdaBelief (63 was
17

---

allowed to do 10000 steps on the CPU. We emphasize though, that the training time does not include the cost of creating the training
GBFS
problem
complx.
gbbs
Let
Libe
ggbs
1ut
L
Lbc
Lic
blocks
37
27
137
54
33
28
29
32
32
127
ferry
53
36
339
20
31
20
npuzzle
660
297
311
591
418
spanner
55
S46
53
807
148
elevators
33
52
657
43
115
Sokohan
boxes
14
17
14
14
14
boxes
32
37
35
36
35
boxes
68
63
66
64
hoxes
171
179
180
210
175
179
181
214
174
boxes
643
651
653
755
654
645
641
640
754
655
643
Maze w. t.
34
34
40
35
40
52
60
55
72
75
78
73
77
89
79
84
Sliding puzzle
x 5
1521
1558
1534
1559
1545
1539
1533
1556
1544
1531
2322
2353
2334
2439
2388
2321
2326
2329
2334
2329
2329
7
3343
3375
3347
3431
3421
3356
3449
3512
3448
3379
Table 6:
Average number of expanded states.
18

---

1
1
1:
98 1:
88 5
100 :
58 58
98 +
81 1
73 1
64 +
49 + 3
89 =
74 1
42 :
85 =
48 + 3
35 +
99
Table 7: Average fraction of solved problem instances percent with standard deviation. SBA* and FDSS denotes Fast Downward Stone Soup. They are domain
Libe
100 +
1
1
7
0
67 14
3
54 -
45 2
75 = 3
32 2
84 = 1
1 2
98
92
100
92
84
72
85
66
34
1g
0
+
0
+
1
100 0
76 1
3
+
3
1
512
43 2
72 2 3
34 34
3
84 + 1
43 3
3
12 3
100
100
89
95
83
72
84
32
GBBS
Lyc
0
+
1:
0
10111 1
100 +
79 -
94 +
84 - 4
74
56 -
48 1
89 +
74 = 2
36 -
84 + 0
45 + 2
-
100
100
89
35
Lgbss
1 0
1
1
1:0
85
100
+
91 +
77
+
3
+
+
75 =
48 +
87 1
3
+
100
100
89
100
85
71
49
90
49
100 +
98 1
92 1
100 0
92 =
98 =
87 1 2
78 -
73 1
51 =
89 1 0
74 = 0
42 = 3
86 = 3
=
3
47
35
Lbo
100 +
1
+ 1
6
66 3
+
3
-
53 +
45 +
87 +
74 + 3
31 + 1
82 + 0
46 + 3
34 +
100
89
92
92
82
73
12
1
+
8
1
1
4
84
36 6
0
81
+ 0
11
1
0
+
87
12 3
32 2
10 2
+ 4
3
99
92
83
97
72
51
42
72
80
45
32
Lt
100 + 0
0
100 0
75 8
96 1
85 =
2
2
59 =
47 -
4
88 =
73 1
35 =
84 =
49 2
*
100
88
72
36
gbfs
100 +
1
+
2
+
2
+ 10
0
89 - 1
2
+
- 1
+
3
75 + 4
37 = 0
+ 3
- 3
98
87
89
98
75
69
49
91
83
48
35
85
L
100 0
98 3
89 1
91 2
99 +
+
80 11
76 +
2
55 4
92 0
78 1
49 1
88 +
51 + 2
3
100
FDSS
100
95
89
90
37
100
81
67
49
31
75
50
0
SBA*
100
100
100
100
100
100
100
97
46
92
52
complx.
3 boxes
boxes
boxes
boxes
boxes
50 50
55 x 55
60 60
5 X 5
6 x 6
X 7
independent planners.
problem
blocks
ferry
npuzzle
spanner clevators
Sokoban
Sliding puzzle
Maze w.
19

---

A
GBFS
problem
complx.
L
Lights
Lights
blocks
21.6
22.7
21.4
22.5
22.9
21.8
22.7
22.1
22.5
23.1
34.1
ferry
16.8
16.9
16.7
16.8
16.8
16.8
16.9
16.8
16.8
16.8
16.9
npuzzle
19.2
23.5
18.2
17.5
17.3
37.6
36.4
39.6
35.1
34.1
124.6
spanner
49.2
49.2
49.2
49.1
49.0
49.2
49.1
49.2
49.3
49.1
elevators
16.4
14.7
17.9
15.8
19.4
15.9
18.0
21.4
Sokohan
3
13.8
13.1
13.5
13.2
4 boxes
15.4
15.2
16.1
15.7
16.8
16.7
15.1
16.1
15.6
16.3
15.8
5 boxes
20.1
19.2
21.3
22.1
20.9
19.8
20.4
21.3
22.1
19.9
20.1
boxes
29.6
29.3
27.7
26.8
28.3
28.1
29.6
29.4
29.9
30.1
7 boxes
31.9
31.4
35.4
34.1
30.1
35.2
32.7
35.5
25.3
24.3
24.3
25.4
24.3
24.7
55 x 55
34.1
33.2
35.0
34.2
33.9
33,2
33.1
34.6
34.6
36.5
36.3
60 x 60
41.2
42.9
41.4
43.2
42.8
42.1
43.6
44.2
45.2
45.3
45.1
Sliding puzzle
5 x
150.1
153.7
155.2
154,6
154.5
154.5
153.5
153.9
155.0
151.1
152.1
252.3
254.2
253.8
254.8
254.0
255.9
256.4
255.3
256.2
254.9
256.3
321.1
324.3
322.9
323.4
327.1
323.7
Table 8: Average number of length of the solution.
The average is computed only problem
instances solved by all 11 variants forward search.
20


Reviews:
[{"review_id": "GJBw7DLzxr", "reviewer": "Reviewer_jMYD", "summary": "The paper considers the problem of using imitation learning for obtaining planning heuristics suitable for using variations of best-first search with a weighted sum of h() and g(), covering A* and GBFS. The paper gives both theoretical and empirical arguments for predicting a ranking of actions instead of predicting h*, the optimal distance to the goal. One argument in favour of ranking is that regression is a harder problem than regression. Another one is the observation that even with an optimal heuristic, the search can still expand more nodes than necessary. For that, in the case of symmetries, the proposed algorithm would choose a particular optimal solution among all the possible ones. The empirical results show the proposed approach to perform the best in A* in comparison with the others. A heuristic trained for GBFS performs well.", "questions": "- What happens in the case of symmetry or multiple paths?\n\t- For instance, suppose there are k discrete integer variables, that can be increased and decreased independently. Suppose the goal is to set them to 0. Optimal plans just interleave increasing the variables independently. What would the theoretical analysis and the empirical results look like?\n\t- This example might be unrealistic but it's related to problems with very flexible solutions like the PDDL benchmark Logistics.\n- How sensitive is the method to the distribution of problems and trajectories?\n\t- Is there any reason for it behaving differently across the proposed methods and the others?", "limitations": "The line of work is interesting, and there are certain domains where this method is relevant. The paper might benefit from exploring better those cases, given that the paper admits that there are cases where estimating the value might be better.\n\nIt'd be good to discuss the stability of training for the different algorithms.\n\nThe space used for introducing the search algorithm could be used for further discussion.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Interesting discussion of ranking vs value estimation.\n- Hard-to-achieve goal of expanding strictly nodes along the path.\n- Discussion on the pros and cons of the approach.\n\t- Including an honest commentary on sample complexity.\n- Promising empirical results.", "weaknesses": "- The proposed approach does not account for flexible goals or multiple goals.\n- Limited discussion on the cases of symmetries and multiple optimal paths.\n\t- This is discussed but it could be analyzed further in the experiments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for an interest in our work and great questions.\n\n*What happens if there are multiple solution path with the same length of the plan (number of actions) and cost?** The behavior of the resulting heuristic function depends on the composition of the training set. Let us illustrate the behavior on a simple grid problem. The agent starts at position (4,4) and has to move to the goal position (0,0). There are no obstacles and agent can only move one tile down or one tile right (the effects on his positions are either (-1,0) or (0,-1)), the cost of the action is one.  The number of different solutions path grows exponentially with the size of the grid and all solution path has the same cost (for problem of size 5x5, there are 70 solutions). This problem is interesting, since merit function in A* with optimal heuristic function (cost to goal) is constant, equal to 8, for all states.\n\nFor the size of the grid (4,4), the heuristic is determined by table with 25 values. Below, we learn these values by minizing the proposed loss for A* algorithm with logistic loss surrogate. The minimization is carried by LBFGS (with all zeros as initial solution). Since the loss function is convex, LBFGS finds the solution quickly.\n\nIn the first case, the training set contains one solution path ([4, 4], [3, 4], [2, 4], [1, 4], [0, 4], [0, 3], [0, 2], [0, 1], [0, 0]), where the agent first goes left and then down. The learnt heuristic values $h$ are\n```\n┌─────┬─────────┬─────────┬────────┬────────┬────────┐\n│ y\\x │       0 │       1 │      2 │      3 │      4 │\n├─────┼─────────┼─────────┼────────┼────────┼────────┤\n│  4  │ -191.53 │ -131.99 │ -76.94 │ -31.25 │    0.0 │\n│  3  │     0.0 │   31.25 │  76.94 │ 131.99 │ 191.53 │\n│  2  │     0.0 │     0.0 │    0.0 │    0.0 │    0.0 │\n│  1  │     0.0 │     0.0 │    0.0 │    0.0 │    0.0 │\n│  0  │     0.0 │     0.0 │    0.0 │    0.0 │    0.0 │\n└─────┴─────────┴─────────┴────────┴────────┴────────┘\n ```\nAn A* search using these heuristic values will first always take action moving the agent to left and then down. When moving down, he does not have other choice. Notice that heuristic values of many states are not affected by the optimization, because they are not needed to effectively solve the problem.\n\nIn the second case, the training set will contain two solution path: the first is as above and the second the agent goes first down and then left. The learnt heuristic values are \n```\n┌─────┬────────┬───────┬────────┬────────┬────────┐\n│ y\\x │      0 │     1 │      2 │      3 │      4 │\n├─────┼────────┼───────┼────────┼────────┼────────┤\n│  4  │ -95.76 │ -66.0 │ -38.47 │  80.14 │    0.0 │\n│  3  │    0.0 │ 15.62 │  38.47 │ 131.99 │  80.14 │\n│  2  │    0.0 │   0.0 │    0.0 │  38.47 │ -38.47 │\n│  1  │    0.0 │   0.0 │    0.0 │  15.62 │  -66.0 │\n│  0  │    0.0 │   0.0 │    0.0 │    0.0 │ -95.76 │\n└─────┴────────┴───────┴────────┴────────┴────────┘\n```\nAn A* search will now face ties at state (4,4), since states (3,4) and (4,3) have the same heuristic value. But the presence of the tie does not affect the optimal efficiency of the search, as A* will always expand states on one of the optimal path from the training set.\n\nFinally let's consider a case, where all 70 possible solutions are in the training set. The learnt heuristic values are \n```\n┌─────┬─────────┬─────────┬─────────┬────────┬────────┐\n│     │       0 │       1 │       2 │      3 │      4 │\n├─────┼─────────┼─────────┼─────────┼────────┼────────┤\n│  4  │    3.74 │   92.62 │  134.66 │ 163.17 │    0.0 │\n│  3  │  -46.61 │    2.35 │   91.93 │ 134.38 │ 163.17 │\n│  2  │ -167.96 │   -47.7 │    1.94 │  91.93 │ 134.66 │\n│  1  │ -210.03 │ -168.66 │   -47.7 │   2.35 │  92.62 │\n│  0  │     0.0 │ -210.03 │ -167.96 │ -46.61 │   3.74 │\n└─────┴─────────┴─────────┴─────────┴────────┴────────┘\n```\nRank of heuristic values \"roughly\" corresponds to cost to goal. The reason, why some states are preferred over the others despite their true cost-to-goal is the same is that they appear in more solution path. As above, the A* search with learn heuristic values is strictly optimally efficient. \n\nWe emphasize that heuristic values are learnt such that the state closest cost to goal are expanded, which is a tie-breaking strategy for A* with exact cost to goal heuristic function.\n\nWe hope that the above example clarifies the behavior of the proposed loss in cases, where the training set contains multiple optimal solutions path of the same problem instance. If the learnt heuristic learn ties, they do not affect the efficiency of the resulting search.\n\n*How sensitive is the method to the distribution of problems and trajectories?**The trajectories that are more frequent in the training set will be preferred. This is demonstrated on the above example, where states close to diagonal has smaller heuristic values. But this does not affect the efficiency of the search. \n\nHeuristic values will be good on problems similar to those in the training set, but might be poor on very different problems. But this problem is inherent to most flexible heuristic functions learn by machine learning methods. We emphasize that according to our experimental results, heuristic functions optimizing the proposed loss generalize better.\n\n*Is there any reason for it behaving differently across the proposed methods and the others?* We are not sure, what the reviewer meant by this question. The proposed loss is theoretically correct in the sense it optimizes the efficiency of finding an optimal solution. It is independent of the design of heuristic functions, which we have shown in the paper by learning heuristic functions for grid and relation (PDDL) domains. Furthermore, in the example in rebuttal, the heuristic function was realized by Table. So we do not have a reason to believe it will behave differently."}, {"review_id": "o9s4HQ6MLw", "reviewer": "Reviewer_7xum", "summary": "This paper investigate the computational advantage if a forward-search algorithm utilises ranking rather than optimising cost-to-goal. I think the contribution is good in general.", "questions": "Please explain my comments listed in the weakness block.", "limitations": "I don't think the paper has any negative societal impact. But I do suggest the authors polish their Sec 4.3.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem is formulated well. \n2. The introduction of the contents is suitable. \n3. The experiment section is good.", "weaknesses": "1. The definition of \"optimal ranking\" is so important to this paper that it needs to be presented before first used. The authors should not use \"(definition is below)\" for this term. \n2. I suggest the authors simplify some expressions. For example, at some points where strict rigorousness is not required, \"minimise the number of expanded states\"--> \"efficient\". \n3. I cannot understand line 7 in the supplementary file. Is it grammatically correct? \n4.Line 10 in the supplementary file, it is not \"lastly\". By the way, what is the connection between the Section 2 in the supplementary and the main text? I don't think there is a need to present this section. As long as \"estimating the cost-to-go converges\" is slower than the proposed scheme, the contribution of the main text is valid. Am I correct? \n5.Can the author find a citation for the claim of Example 1? so that there is no need to present it in detail. I think this example broke the reading flow. \n6. Why is the related work section at Sec 5? Why can't it be Sec 2? \n7. I don't think Sec 4.3 presented rigorous statements. All things are subjective. Did the author write \"conclusive remarks\" here? I suggest the authors move them to the conclusion section. Don't be afraid that the algorithm section is too short. \n\nMinor points: \n\n1. I didn't find the definition for the \\wedge symbol in Def.1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*The definition of \"optimal ranking\" is so important to this paper that it needs to be presented before first used. The authors should not use \"(definition is below)\" for this term.*\n\nThis is a good suggestion. We will incorporate the definition to the motivation.\n\n*I suggest the authors simplify some expressions. For example, at some points where strict rigorousness is not required, \"minimise the number of expanded states\"--> \"efficient\".* \n\nWe are totally aware that some wordings are clumsy, but we wanted to be rigorous. Specifically, the planning community consider A* with true cost-to-goal heuristic to be \"efficient\", but it is not without additional tie-breaking rules. We were afraid that if we would not be precise, some readers might be confused. \n\n*I cannot understand line 7 in the supplementary file. Is it grammatically correct?*\nThere seems to be some typos. We wanted to say that making the learnt heuristic function $h$ to be goal-aware can be difficult, when the problem instance contains multiple goals not defined by a single substate.  All heuristic functions defined by neural networks known to use have this problem and we consider it outside of the scope of this paper. Since A* and GBFS planning algorithms do not need the heuristic functions to be goal aware, we do not see this feature to be an issue, but we wanted to be clear.\n\n*Line 10 in the supplementary file, it is not \"lastly\".* \nYes, we will delete this \n\n*By the way, what is the connection between the Section 2 in the supplementary and the main text? I don't think there is a need to present this section. As long as \"estimating the cost-to-go converges\" is slower than the proposed scheme, the contribution of the main text is valid. Am I correct?*\nWe actually believe this to be important, as it is another argument supporting to learn the heuristic function by \"ranking\" instead of by learning to estimate cost-to-goal. In planning by imitation learning, creating the training set is usually done by running a solver, which is expensive. This argument therefore use the statistical learning theory to argue that learning to rank is simpler problem than regression, because it converges faster with respect to the number of samples. This makes it cheaper. Since we have seen this claim in papers about ranking (not in the planning domain) without a proper theoretical justification, we wanted to have a theoretical evidence with references. Section 2 in supplementary therefore fill this gap by composing results of two papers [8] and [54] (citation numbers of the paper), such that the convergence rates can be compared side-by-side. Moreover, this helps to highlight a difference between sample in regression (one state) and sample in ranking (pair of states). Ref. [8] seems to be relatively unknown, judging by fact it has \"just\" 228 citations while being 24 years old.\n\n*Can the author find a citation for the claim of Example 1? so that there is no need to present it in detail. I think this example broke the reading flow.*\nThe example is adopted from Ref. [14] (citation numbers of the paper). We add the example to make the paper more self-contained. If you think it breaks the flow, we would happily remove it.\n   \n*Why is the related work section at Sec 5? Why can't it be Sec 2?*\nThe position of related work is questionable. We had the impression that NEURIPS community typically puts the related to work towards the end of the paper (e.g. [A] below), because the reader is usually eager to read the novel content of the paper. On the other hand moving the related work to Sec. 2 introduces the reader better to the problem. We do not have a strong opinion and would be happy to move it to Sec. 2.\n\n*I don't think Sec 4.3 presented rigorous statements. All things are subjective. Did the author write \"conclusive remarks\" here? I suggest the authors move them to the conclusion section. Don't be afraid that the algorithm section is too short.*\n\nWe very kindly disagree with the reviewer and would like to ask him to identify, which statements are subjective and why. There are following statements:\n1. Size of the solution set\n2. Optimizing cost-to-goal does not utilize states off the solution path\n3. Cost-to-goal provides a false sense of optimality\n4. Heuristic value for dead-end states\n5. Goal-awareness\n6. Speed of convergence against the size of training set\n7. Conflicts in training set\n\nStatements 2,3,4 and 6 are supported by the theory in the paper. Statement 1 might be considered speculation, but it is very likely true (in the paper we have written that we lack the formal proof). Statement 5 is in favor of estimating cost-to-goal, since the proposed heuristic can be made goal-aware only in some cases. Finally, Statement 7 is a statement. We agree this can be moved to discussion.\n\n\n[A] Klissarov, Martin, et al. \"Adaptive Interest for Emphatic Reinforcement Learning.\" Advances in Neural Information Processing Systems 35 (2022): 95-108.\n"}, {"review_id": "Mq6vvrz2Rl", "reviewer": "Reviewer_458p", "summary": "Planning with (possibly learned) heuristic function is important for both planning and learning communities. The paper focuses on the forward search without expanding redundant search states in their forward process. With the development theorem, the authors demonstrated how the proposed concept work in various domains with A* and GBFS algorithms.", "questions": "The paper is very clearly organized, and I can focus on the content. The below items are come comments.\n\n- Learning-based heuristic functions could be promising for their generalization ability. However, sometimes they are argued that the required learning times (or resources) are too large. In the reported times with PDDL domains, it requires 17724 CPU hours. These results may cause some questions about the efficiency of the learning-based heuristic itself.\n    - Do you discuss why the learning-based heuristic is promising, even though the training resource is required?\n    - Can we compare planners without learning and planners with learning (i.e., the proposed method) in terms of total required resources?\n    - Can the two solvers (A* and GBFS) have similar characteristics in terms of learning-based methods? The two solvers can be formulated similarly, as noted in L.93. Can we regard these methods as just variants of search using the function of the form in L.92, or can we have some important findings of these methods through the experiments?\n- Mathematical notation issues:\n    - In Def. 1, some mathematical errors seem to occur in the second condition: see L.111 and L.117 to check the condition of $\\wedge$.\n    - In Eq.(6), the log() is not closed.", "limitations": "I have no explicit concerns about the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The concept of the focusing problem, wheares they seem to be simple, is interesting. The proposed theoretical discussion (e.g., sufficiency and necessity in Theorem 1) is clearly explained; the whole paper is well written and structured.\n- The proposed approach with $L_\\star$ based on the two fundamental search techniques A* and GBFS work efficiently than counterparts.", "weaknesses": "- Although the proposed learning-based approach is promising, it requires much learning time on PDDL domains (e.g., 17724 CPU hours).\n- The scales and variations of compared benchmark domains seem limited (e.g., traditional search problems and mazes).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for an interest in our work.\n\n*Do you discuss why the learning-based heuristic is promising, even though the training resource is required?*\nLet us first clarify the computational complexity. The paper reports the total time of all experiments presented in the paper. This means that 17724 CPU hours is cost of all experiments (training, evaluation, search for hyper-parameters) on five relational domains, six loss functions, and for three repetitions. Moreover, since we have assumed that Neurips welcome reporting the computation time needed for development, these cost include the development (we took it from an audit of SLURM scheduler during period of authors working on this paper). Similarly, 100 GPU hours and 1000 CPU hours is an upper bound (we did not have the logs from the scheduler due to different computation environment) of the training time (GPU cost) and evaluation time (CPU costs) of three repetitions of three grid problems for six loss functions.  **The time to train a neural network took for a single problem and single loss functions** are \n1. approximately 1.85 GPU/h for grid domains;\n2. and usually 0.5 CPU/h for relational domain. The exception is Gripper domain, where the training takes about 8h due to large branch factors. We believe this training time can be reduced by different construction of minibatches, but we consider this to be outside of this paper.\n\nFrom these number we believe the training times are acceptable even for practical use. We emphasize though, that the training time does not include the cost of creating the training set. We will improve the formulation in the main paper, since it seems to be confusing.\n\n*Can we compare planners without learning and planners with learning (i.e., the proposed method) in terms of total required resources?* This might be difficult, because we do not know the development cost of classical planners. Specifically, we do not know, how much CPU time was used for their tuning and testing. The classical planners and those with heuristics realized by NN were executed on the *same* hardware (always only single core CPU) and were given the same time limit (10mins for grid domains, 5 seconds for relational domains), which should make it fair comparison.\n\n*Can the two solvers (A* and GBFS) have similar characteristics in terms of learning-based methods? The two solvers can be formulated similarly, as noted in L.93. Can we have some important findings of these methods through the experiments?* We also believe that the proposed loss functions, the methods are related. The experimental results, where we have observed that NN optimized for A* works well with GBFS (but not the other way around) motivated the formal proof of Statement on line L.350 (the proof is in the appendix). \n\n*Mathematical notation issues*\nWe have checked lines 111 and 117 and believe them to be correct (albeit L.111 contains additional $\\wedge$). $s_k \\in \\mathcal{S}^{\\pi_{:,i-1}}$ says that $s_k$ has to be on a solution path between start and state $s_i$ and $s_j \\notin \\mathcal{S}^{\\pi_{:,i}}$ should be outside of the solution path. Thus $s_j$ is distance one from the solution path. We completely agree with other reviewers that this is part is difficult to read and we will try to improve it.\n\nThan you very much for spotting the missing parentheses in Equation (6).\n"}, {"review_id": "pPnDW7mNwd", "reviewer": "Reviewer_ahr3", "summary": "The paper highlights the limitations of the conventional method for learning heuristics in search algorithms, which involves imitating the optimal cost-to-go function. The authors present an alternative approach that focuses on optimizing the correct ranking of state pairs by the heuristic. Because of that characteristic, the authors argue that the resulting heuristic offers both theoretical and practical advantages compared to the standard approach.", "questions": "In general, I like the idea and the paper, although at this point it may need some improvements. At this point I'm not fully convinced that the improvement you show is due to the theoretical advantages (which should be clarified) or just a fancy heuristic that happens to work better than a certain imitation objective. Below I highlight a few specific comments.\n\n- l.111,117,157 Arguably a central expression, appears in 3 places, and every time is written differently. Correct it (or explain that it's actually not the same).\n\n- l.113-125 This explanation of the notation above is a lifesaver.\n\n- l.131 Does there exist at least one perfect ranging for every problem? Semms that h(s):=[-infty on a fixed optimal path, infty otherwise] works. What happens in quite a common case in which s_0 is not specified and the heuristic should work for any starting state? Does there always exist a perfect ranking in such case?\n\n- l.105-150 While I don't deny the soundness of the theory, it reads a little like explaining quite an intuitive idea (\"the heuristic is strictly optimal iff in every step of the search the next node on a fixed optimal path receives the lowest value\") with very complicated expressions. I'd consider changing the order and starting from intuition, moving to the formalities afterwards. The ultimate conclusion should be the expression in l.111, which I believe is the central object in this section.\n\n- l.161 Quite a strong assumption.\n\n- l.167 The relation between log(1+exp(x)) and [[x>0]] indeed seems loose. On convergence it will have the desired property indeed, but it doesn't exactly optimize the number of violations, rather a sum of violation volumes. How does it relate to your theory? An experimental analysis of the learned function would do.\n\n- l.180 I'd consider rewording the section title. Although after reading the section it makes sense, at first it seems like a general discussion of optimizing neural networks.\n\n- l.181-185 I like the idea, but it's not true that it is easier to learn a function from a bigger class. The core element is the learning signal. In case of cost-to-go, where we have actually a direct supervision, it is of much better quality than in case of a set of inequalities. Consider an example in which we have n states and we want to learn any monotonic function. Although there are much more functions satisfying f(s_{i+1})>f(s_i), learning fixed supervised targets should be faster.\n\n- l.186-196 \"states off the solution path\" -- you mean in the training dataset or in general? As far as I understand, your training dataset consists of solving paths only, so the issue applies to your ranking loss as well, doesn't it? When provided with off-the-path states, standard cost-to-go functions can also utilize them for learning (e.g. bootstrapping for Q-learning). The issue you describe is devoted to the particular training loss you consider, not learning cost-to-go in general.\n\n- l.203-207 I don't understand. Optimizing the proposed losses never considers dead-ends as they don't lie on the optimal paths. Do you consider any hand-modified heuristics? If you are worried about too high gradients, use Huber loss instead of L2. Why should lare values appear in the training? (5) is strictly supervised.\n\n- l.269 That's a shame, it would support your claims well as it makes a middle-ground between (3) and (5).\n\n- l.285 How costly is it to get this dataset? Is your method more efficient than SymBA* afterwards? Gathering optimal paths for training may be very costly, especially in the hardest domains. Thus, can you comment on the applicability of your claims, since you require a costly operation of gathering optimal paths for your training> Can your method, like standard imitation, learn also from sub-optimal data, which is often much easier to get?\n\n- l.286 Why a single problem instance?\n\n- l.322-342 If the test sets are harder than training sets, how does it relate to the theory in which you assume having optimal paths?\n\n- l.343-363 I'm not familiar with the complexity of some instances of the environments. Thus, it would be helpful to see some trivial baselines in the comparison, such as BFS or Dijkstra. Also, to showcase an advantage of your theory-driven approach, I'd consider comparing with a simple objective that learns to output 0 on the solving paths and 1 on other states outside the path. It fits the definition of optimality and doesn't seem to be stable or generalizable (or maybe?). Advantage over such a baseline would highlight the benefit of learning the ranking over heuristics. It's missing now. Yes, I know that you compare already agains many relevant baselines.\n\n- l.343-363 Also, the claims should be supported by some ablations. Is the learned heuristic correct? Does it learn to properly rank states, even in the training domains? What does it converge to, do the values resemble cost-to-go or some other interpretable quantities? What are the mistakes? Does the learned heuristic fit the theory of what it should learn? Are the paths obtained this way optimal? How do they relate to optimal paths in terms of length? How often only states on an optimal path are expanded? Can you learn a useful heuristic for a fixed domain with many possible starting points?\n\n- l.375 I'm not sure whether optimizing set of inequalities is easier than a direct supervision.\n\nAnd a few minors:\n\n- l.31,212,215,271 etc. When you refer to something, either in your paper or in supplementary, refer to the exact section.\n\n- l.40 Do you mean \"state-of-the-art\"?\n\n- l.48 I wouldn't say \"always\", you can demonstrate that it's better \"in those eight environments\".\n\n- l.50-72 I can't find a definition of g(s) or h(s) before you use it to explain your algorithm. Maybe in preliminaries? g(s) is defined below the algorithm, but h(s) is not.\n\n- l.116,135, and others: I feel confused whether \"heuristic\" refers to h or f. Please disambiguate the notation.\n\n- l.305 24000 gradient steps in 100 GPU hours? Seems quite slow, I'd suggest checking it.", "limitations": "The limitations are not clearly stated, there should be a dedicated section for them. Societal impact is not an issue here.", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The paper presents an original idea that indeed can offer a significan advantage for planning methods. The presentation is mostly clear, with only minor problems.", "weaknesses": "In my opinion, the claims formulated in the paper should be supported better. I'm not convinced that the reported results stem from the theory. Clearer discussion of theoretical advantages and disadvantages of various approaches, more detailed experiments including analysis of the learned heuristic, and comparison with some other baselines could be a significant improvement to the paper. Details of my concerns are discussed in the comments.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for valuable commplents. Due to space limit of, we will address his comments in the same order using lines for perfect matching.\n* *l.111,117,157* We seen the expression in lines L.111 and L.117 the same. Can you clarify us, where do you see the difference exactly? The expression on Line L.157 differs in not using and index $j$ for identifying the state, because it was not needed.  We will happily reintroduce state $s_j$ back, if it helps readability.\n\n* *l.113-125* We agree. \n\n* *l.131* On line L.144 we state that the complexity of perfect ranking heuristic is equal to the complexity of solving the problem, because we can solve the problem and then create the heuristic by your construction. Since the initial state $s_0$ is part of the definition of the problem instance, to assert that heuristic is perfect ranking for any initial state, we would need to verify the conditions for all initial states.\n\n* *l.105-150* Changing the order sounds like a good idea.\n\n* *l.161* This assumption seems to be common in papers about imitation learning (e.g. Ref. [9,17,19,20,45,49] in the paper). We prefer this over bootstrapped learning (arguably more realistic) to better expose differences in loss functions while isolating other sources of variability.\n\n* *l.167* We do not see a problem in using this relation, since it is used in majority machine learning methods optimizing parameters by gradient descend.  The relation is loose, since  log(1+exp(x)) upper bounds [[x>0]], but it allows methods scale. We can optimize parameters of NN [[x>0]] using mixed integer program, but this does not scale to interesting problems. The theory is sound  [[x>0]], but log(1+exp(x)) is needed to make it practical.\n\n* *l.180* This is an interesting view, but we prefer to keep it as is, because the proposed loss function can be used with other machine learning methods like support vector machines or gradient-boosted decision trees. One of the motivation for our work stems from the fact a lot of attention is paid to architecture of NNs (or classifiers in general), but loss functions are neglected despite being very important.\n\n* *l.181-185* \"Easy to learn\" is an unfortunate  expression. A better would be that more functions can satisfy the conditions. The quality of cost-to-go is debatable (and we would love to debate it more in discussion). As argued in the paper, search does not care about values, but about their order. For cost-to-go work, you also need to learn its values for states off the optimal path, otherwise it fails as discussed in the paper. A nice example, where cost-to-go gives wrong signal is when all actions have zero cost (but the proposed method still works). \n\n* *l.186-196* We consider L2 loss as is used in imitation learning in planning, which uses exclusively states on the optimal path, because otherwise the cost-to-go is not known. If it uses states off the optimal path, it needs to run solver to get the correct values, which corresponds to solving a new problem. Repeated simulations in Q-learning corresponds to repeatedly running the solver, which is different settings.\n\n* *l.203-207* If you use just cost-to-go on optimal path, in Equation (5), you will never learn about dead-ends. But as [9] has shown, informing NN about dead-ends by giving them high heuristic value in the training set helps. We tried to explain that dead-ends are considered by the proposed loss function without any modification, since they will be among states off the optimal path and heuristic is learnt to avoid those.\n\n* *l.269* We have some initial results for comparison and we can share them with you in discussion phase. The word limit is quite tight.\n\n* *l.285* Obtaining a training dataset is costly, but this step is required by methods optimizing cost-to-go by $L_2$ loss as well. Therefore we do not see this as a problem of the proposed method. We emphasize that experiments on grid domains show that training on simple problems (e.g. Sokoban with 3 boxes) allow to generalize to hard ones and better than learning cost-to-go (GBFS with $L_2$ can solve 42% problems with 7 boxes while A* with L* can solve 55%.\n\n* *l.286* Because all states in minibatch are used in all known inequalities.\n\n* *l.322-342* The relation is through generalization bounds of a learnt classifier. The argument is the same as for learning cost-to-goal by minimizing $L_2$ loss.\n\n* *l.343-363*  We did not did this, because we have not seen it in the prior art (Refs. [9,17,19,20,37,39,45,49,53]), from where we have taken relational problems. The fraction of solved problems for BFS (5s time limit as used by solvers in the paper) is provided below.\n```\nproblem       fraction\n────────────────────\nblocks        0.35\nferry         0.31\nnpuzzle       0.14\nspanner       0.63\nelevators     0.22\n```\nYour example of learning zero on optimal path and one off the optimal path is a realization of the proposed method with regression ($L_2$) loss. It is an interesting experiment.\n\n* *l.343-363* These are allinteresting questions, but it will not fit the page limit. The rebuttal for the reviewer jMYD contains a maze without obstacles, where all solution path are of the same costs. This example answers some of your questions.\n\n* *l.375* When you optimize inequalities, you do not have to be exact and you are not penalized when the estimate of cost-to-goal is perfect. We think that also for humans, it is easier to estimate that something is closer / farther than how far it is exactly (assuming the human is not equipped with smartphone and maps). \n\n* The computation complexity is reported for all experiments including hyper-parameter search and development in case of relational domains. The training time for a single grid domain is under 2 GPU/h, the training time for single relational domain is usually around 1/2 CPU/h except gripper, where it takes about 8 CPU/h (see rebuttal to reviewer 458p).\n"}]

Author rebuttal:

Meta-review: The paper provides an interesting insight regarding the construction of planning heuristics, which, despite being largely theoretical and immediately applicable only to deterministic search problems, may be empirically useful in probabilistic planning or even RL as well. The reviewers and the AC trust that the authors will incorporate the changes that came out of their discussions with the reviewers into the final version.
Decision: Accept (poster)