Guiding GBFS through Learned Pairwise Rankings

1 Introduction

Greedy Best-First Search (GBFS) is one of the most widely used algorithms in satisfying planning. GBFS uses a heuristic function to estimate the cost to reach the goal from a given node. The nodes are put in a priority queue based on their heuristic values, and the node with the lowest heuristic value is expanded next. This strategy will return a plan if one exists, but may result in suboptimal solutions. Many researchers have made significant efforts to design informative heuristics to guide GBFS [Bonet et al., 1997; Hoffmann and Nebel, 2001; Richter and Westphal, 2010], however the efficiency of the search depends on properties of the heuristic function which are not yet completely understood [Wilt and Ruml, 2016; Cohen and Beck, 2018].

Therefore, in recent years, the possibility of exploring the space of heuristic functions using machine learning has raised increasing attention [Arfaee et al., 2011; Shen et al., 2020; Ferber et al., 2020; Karia and Srivastava, 2021; St˚ahlberg et al., 2022; Heller et al., 2022; Chen et al., 2024]. These approaches try to learn or improve a heuristic function for a planning domain or, occasionally, a single large problem instance. They typically formulate the learning problem as one of regression, and train models using pre-computed statevalue pairs extracted from (often optimal) plans generated by off-the-shelf planners for small problem instances.

However, labelling states with informative values and attempting to learn accurate values for the heuristic is expensive and unnecessary for the purpose of learning to guide GBFS. This is because the choice of node expansion by GBFS is not determined by the actual numerical values of the heuristic but by the relative ordering over nodes they induce [R¨oger and Helmert, 2010]. Therefore, regression models, which attempt to learn precise heuristic values, artificially restrict the target hypothesis space and the training dataset one can learn from. They also introduce issues such as the difficulty of distinguishing between states that have close heuristic values. In fact, for GBFS to find the optimal plan, it suffices for the heuristic to order the states on the optimal path as preferable to those off it. This is called the perfect ranking heuristic in [Chrestien et al., 2023] as it also minimises search effort.

These considerations motivate an alternative framing of the problem as one of learning to rank pairs of states, building on the active research on learning to rank in information retrieval and relevance analysis [Burges, 2010; Damke and H¨ullermeier, 2021; Li, 2022]. Garrett et al. (2016) were the first to approach this problem for planning by using a statistical machine learning model, namely RankSVM [Joachims, 2002], hand-crafted domain-independent features, and a loss function measuring the normalised difference between the number of correctly and incorrectly classified pairs.

In contrast, this paper explores pairwise ranking with modern deep-learning methods. We propose a novel framework combining a Direct Ranker [K¨oppel et al., 2020b] with any existing neural network regression model for learning heuristics, which are trained end-to-end in order to learn a total quasi-order, i.e. a total, transitive, and reflexive relation over pairs of states. This framework does not require complex loss functions, and exploits the transitivity of the ordering relation to learn a ranking just slightly stronger than the perfect ranking, from an order of magnitude less data than alternative approaches. Moreover, it supports efficient batched evaluation to speed up training.

We evaluate our approach on the learning track of the 2023 international planning competition, using the recent STRIPSHGN [Shen et al., 2020] and GOOSE [Chen et al., 2024]

domain-independent graph neural network architectures, as the underlying regression model. We show that our ranking approach considerably improves the coverage of both these models and expands their ability to generalise to larger problems than those trained on, whilst preserving their plan quality and time to convergence. We also compare our approach with the recently and independently developed work from Chrestien et al. (2023). We show that our framework requires less training data and generalises better to unseen problems.

2 Background

We start by introducing the necessary background on planning, greedy best-first search, and learning to rank. We use �n� to denote {1, 2, ..., n}.

2.1 Planning

We consider classical planning problems described by a tuple P = ⟨S, s0, G, A,C⟩ where S is a finite and discrete set of states, s0 is the initial state, G ⊆ S \ {s0} is the set of goal states, A is the set of actions of which As is the subset applicable in state s, and an action a ∈ As is a deterministic transition function, which takes state s as input and outputs the successor state s′ . In the following, we write Ns for the set of successors of a state s: it consists of all states s′ such that there exists an applicable action a ∈ As with s′ := a(s). The cost function C(a) returns the non-negative cost of applying action a. A unit-cost problem is one for which all actions have cost 1. A plan for P is a sequence of actions a1, . . . , an that induces a sequence of states (a path) s0, s1, ..., sn where ai ∈ Asi-1 , si := ai(si-1) for i ∈ �n�, and sn ∈ G. A plan is optimal if its cost ∑i∈�n� C(ai) is minimal. In the unit-cost case, optimal plans are plans of minimal length.

Greedy Best-First Search (GBFS) is the most commonly used algorithm for satisficing planning. In order to guide the search towards the goal, GBFS relies on a heuristic function h : S → R returning an estimate h(s) of the cost to reach the goal from a given state s, and always expands the state with the lowest heuristic value on the search frontier. As shown in Algorithm 1, GBFS maintains two lists of nodes 1 : the open list (O) - a priority queue ordered by increasing h value, containing the nodes that have been generated but not yet expanded, and a closed list (C) containing previously expanded nodes which is used to avoid revisiting the same state twice and creating loops. At each iteration, the node at the front of the open list - the node with the lowest h value - is transferred to the closed list and expanded by generating its successors. The search stops if a successor is a goal state. Otherwise, any unvisited successor is added to the open list.

GBFS is guaranteed to find a plan if one exists, but the plan may not be optimal. In fact, even when guided with the h∗ heuristic which returns the optimal cost to reach the goal, GBFS is only guaranteed to return the optimal plan for unit cost problems. In the following, we assume that problems have unit cost.

1 In the interest of readability, Algorithm 1 identifies nodes with states, whereas nodes additionally record the h value of the state, the parent node, and the action applied at the parent.

Algorithm 1 GBFS Algorithm

Input: problem P, heuristic function h

Output: Plan π or unsolvable 1: O := {s0} 2: C := ∅ 3: while O ̸= ∅ do 4: s := argmins′∈O h(s′ ) 5: O := O \ {s} 6: C := C ∪ {s} 7: for all s′ ∈ Ns do 8: if s′ ∈ G then 9: return Extract-Solution(s′ ) 10: end if 11: if s′ ̸∈ C ∪O then 12: O := O ∪ {s′ } 13: end if 14: end for 15: end while 16: return unsolvable

2.2 Learning to Rank

Learning-to-rank is a well-studied field in machine learning [Liu and others, 2009; Li, 2022]. Given a set of objects, in our case a set of states, B = {s1, . . . , sk}, it aims to learn an order ⪯ that results in the ranking si1 ⪯ si2 ⪯ . . . ⪯ sik , where i1, . . . , ik is a permutation of �k�. In this work, we further require the order to have the following properties:

Definition 1 (Total Quasi-Order ⪯). A total quasi-order ⪯ over a set X is a binary relation with the following properties

• Totality: ∀a, b ∈ X a ⪯ b ∨ b ⪯ a;
• Transitivity: ∀a, b, c ∈ X a ⪯ b ∧ b ⪯ c ⇒ a ⪯ c.

Moreover, totality implies

• Reflexivity: ∀a ∈ X a ⪯ a.

We define the strict order ≺ in the obvious way: a ≺ b iff a ⪯ b and b ̸⪯ a. Note that transitivity also holds for the strict order ≺: ∀a, b, c ∈ X a ≺ b ∧ b ≺ c ⇒ a ≺ c.

There are several different approaches to solving the learning-to-rank problem, such as SVM [Shashua and Levin, 2002; Herbrich et al., 1999], Boosting [Freund et al., 2003; Wu et al., 2010] and Neural Networks [Burges et al., 2005; K¨oppel et al., 2020b]. Based on how the order is represented, learning-to-rank approaches are divided into three groups: pointwise, pairwise and listwise [Li, 2022]. Listwise approaches learn to sort a list of objects to match a desired total order. For planning, this approach is infeasible since we do not know a priori the list of states we need to sort.

The pointwise approach represents the total quasi-order by a ranking function r : B → R which takes in one object and returns a numerical score [Li, 2022]. This numerical score is then used to sort B. Note that GBFS uses the heuristic h as a pointwise ranking function: the set of open states O is sorted according to their h values (Line 4 of Algorithm 1). Similarly, learning a heuristic function can be seen as learning a pointwise ranking function with extra constraints imposed by the definition of a heuristic function, e.g., h(s) ≥ 0 for all s, h(g) = 0 for all g ∈ G, or even admissibility or consistency.

Lastly, a pairwise ranking function takes a pair of elements as input and it outputs the ordering between the two objects. Formally, a pairwise ranking function r(si, sj) ∈ {-1, 0, 1} represents whether si ≺ sj, si = sj or sj ≺ si, respectively [K¨oppel et al., 2020b]. While learning a pointwise ranking function is a regression problem, learning a pairwise ranking is a classification problem, i.e., given two states si and sj , we need to assign it either -1, 0, or 1. As we show in the next section, this difference has a large impact on learning a ranking for planning in comparison to learning a heuristic.

3 Rank-based GBFS

In the context of GBFS, the heuristic function h is used solely for sorting states in the priority queue as shown in Line 4 of Algorithm 1. This means h is being used only as a total quasiorder over the states S. This fact has been exploited by others, for instance, by using functions other than the cost-to-goal to order states in GBFS [Ferber et al., 2022] and to analyse what makes a good heuristic for GBFS [Wilt and Ruml, 2016]. For this reason, we extend GBFS to use a ranking instead of a heuristic. Formally, given a total quasi-order ⪯, rank-based GBFS is the algorithm obtained by replacing Line 4 in Algorithm 1 with: choose s such that s ⪯ t for all t ∈ O. We relate the two versions of GBFS with the lemma below.

Definition 2 (⪯h). Given a heuristic h, the total quasi-order ⪯h associated with it is so that s ⪯h s′ ⇔ h(s) ≤ h(s′ ).

Lemma 1 (Rank-based GBFS equivalence). Given a problem P, a heuristic h, GBFS using h is equivalent to rank-based GBFS using ⪯h for the same tie-breaking method.

It is easy to see that Lemma 1 holds based on the definition of ⪯h. Lemma 1 also explains why any monotonic non-decreasing function f applied to the heuristic h, i.e., h′ (s) = f(h(s)), does not change the solution found by GBFS: f preserves order, and therefore the total quasi-order ⪯h and ⪯f(h) are the same. We close this section by looking at what ranking function we should aim to learn.

An intuitive ranking to learn is the ranking induced by h∗ , i.e., ⪯h∗ since GBFS is guaranteed to find the optimal solution using h∗ under unit-cost actions. However, for usage with GBFS, ⪯h∗ orders more states than are necessary to find the optimal solution. To see this, consider the example in Figure 1. The total quasi-order ⪯h∗ imposes an ordering between any pair of states in the example, including between siblings of states on the optimal path, i.e., ti,j ⪯h∗ ti′ ,j ′ ⇔ h∗ (ti,j) ≤ h∗ (ti′ ,j ′). However, the ordering among siblings is not needed, i.e., it is sufficient to know that si ≺ tj,m for j ∈ �i� and m ∈ �ki�. We exploit this fact to define an optimal ranking as:

Definition 3 (Optimal Ranking ⪯∗ ). Given a problem P and an optimal plan π∗ = [s0, s1, ..., sn] for P, the optimal ranking ⪯∗ is a total quasi-order such that si ≺∗ si-1 for all i ∈ �n� and si ≺∗ t ∀t ∈ Nsi-1 and ∀i ∈ �n�.

Notice that Definition 3 only relates a state si in the optimal plan with its parent si-1 and its siblings t. Since it does not enforce an ordering between the siblings t of si, the optimal ranking is still a total quasi-order. Moreover, due to the transitivity property of total quasi-orders, we have that si ≺∗ t′ for all t′ ∈ ∪i-1 j=0Nsj , i.e., si is ranked strictly better than any of its ancestors and their siblings. Next, we prove that GBFS finds the optimal solution when using an optimal ranking.

Theorem 1. For a solvable problem P with unit costs, given an optimal ranking ⪯∗ , the plan returned by the rank-based GBFS is optimal.

Proof. Consider a problem P with unit costs, with an optimal solution π∗ = [s0, s1, ..., sn] and optimal ranking ⪯∗ . We prove by induction that si-1 is expanded at the ith iteration of the algorithm and that after expansion, the open list is Oi = ∪i-1 j=0Nsj \∪i-1 j=0 {sj} for all i ∈ �n�. For readability, given a state s and set of states X, we abbreviate ∀t ∈ X, s ≺∗ t with s ≺∗ X. For the base case: initially, the open list of GBFS only contains s0 (Line 1 of Algorithm 1), which is always expanded at the first iteration of the while loop in Line 3, leading to O1 =Ns0 \ {s0}. For the induction step: assume the property holds, we show that si is expanded next and Oi+1 = ∪ij=0Nsj \∪ij=0 sj. According to the definition of the optimal ranking we have: si ≺∗ Nsi-1 (a) and si ≺∗ si-1 (b). Because si-1 was expanded in the last iteration, we have si-1 ≺∗ ∪i-2 j=0Nsj \∪i-2 j=0 {sj} (c). Since ≺∗ is transitive, (b) and (c) lead to si ≺∗ ∪i-2 j=0Nsj \∪i-2 j=0 {sj} (d). Finally, the union of (a) and (d) gives si ≺∗ ∪i-1 j=0Nsj \∪i-1 j=0 {sj}. In other words, si is ranked at the top of the open list Oi and will be expanded in iteration i+1. After expansion the queue will be Oi+1 = Oi ∪ (Nsi \∪ij=0 {sj})=∪ij=0Nsj \∪ij=0 {sj}.

A key difference between optimal rankings and ⪯h∗ is that there are several total quasi-orders that are optimal rankings while ⪯h∗ is unique. This makes learning an optimal ranking potentially easier than learning ⪯h∗ or even h∗ itself, since h∗ is also unique. We exploit this in the next section where we introduce our framework to learn an optimal ranking.

4 Learning an Optimal Ranking

In this section, we introduce a new framework capable of leveraging any neural network regression model to learn an optimal ranking function. We also show how to efficiently integrate the ranking computations into GBFS and how to extract more data from the optimal plans for training while still efficiently handling this extra data through batching.

4.1 DirectRanker

Our approach for learning an optimal ranking through pairwise classification uses DirectRanker [K¨oppel et al., 2020b].

DirectRanker is a general model for pairwise ranking that is designed to learn total quasi-orders. Its structure is shown in Figure 2. The model consists of two parts: feature computation and ranking computation. The first part receives two objects (in our case, states) si and sj to be ranked and generates the embedding vectors embsi and embsj , both in Rn , through the neural networks nni and nnj. The structure of the neural networks nni and nnj is not restricted; the only requirement is that both nni and nnj have the same structure and share weights, i.e., they must be identical.

The second part of the model, ranking computation, computes the element-wise difference of the two embedding vectors and passes it through a single neuron τ with zero bias. Formally, this second part computes p = σ(w(embsi - embsj )) where w ∈ R1×n are the weights and σ is the activation function of τ. The activation function σ must be odd and sign-preserving, i.e., σ(-x) = -σ(x) and sign(σ(x)) = sign(x). The input states si and sj are classified as si ≺∗ sj, si = sj, or sj ≺∗ si if p is less than, equal to, or greater than 0, respectively. Under these assumptions, DirectRanker is guaranteed to return a total quasi-order [K¨oppel et al., 2020b, Theorem 1]. Besides the activation function σ, the loss function used by DirectRanker is also a parameter of the framework and we use the same parametrisation as in K¨oppel et al. (2020b) experiments: activation function σ(x) = (1 + e-x )-1 - 0.5 and mean squared error (MSE) as the loss function [K¨oppel et al., 2020a].

4.2 Efficient Integration with GBFS

Once we learn the shared weights for nn1 and nn2 as well as w for the ranking computation, we need to integrate it into GBFS. Let D(s, t) ∈ {-1, 0, 1} represent the result of the DirectRanker for s and t. In order to insert a new state s into the priority queue O, we need to compare s with states already in O since we have learned a pairwise ranking. However, the amortised computational complexity of insertion is O(k log |O|), where k is the time needed to evaluate D(s, t) for a single comparison.

Since the ranking computation part of DirectRanker is a single-layer, unbiased neural network, we can transform our learned pairwise ranking into a point-wise representation to improve the insertion efficiency in the priority queue. This transformation is formalised in Lemma 2 and lets us represent the learned D(s, t) as the point-wise ranking r(s) ∈ R. As a result, the priority queue in GBFS can now be sorted by r(s) resulting in an amortised insertion time of O(k′ + log |O|) where k′ is the time required to evaluate r(s). With this transformation, only a single neural network evaluation is needed instead of log |O| when using the pairwise ranking function D(s, t). Although r(s) is being used as a heuristic in GBFS, it is important to note that it is not a heuristic in the traditional sense, for instance, r(s) can be negative. Moreover, since we are learning an optimal ranking, it is possible that r(t) ≤ r(t′ ) even though h∗ (t) > h∗ (t′ ) for states t and t′ outside the optimal plan.

Lemma 2. Given a DirectRanker model with weights w representing the total quasi-order ⪯, we can extract a point-wise ranking function r : S → R representing ⪯.

Proof. Given two states si, sj ∈ S, without loss of generality, we assume si ⪯ sj. Then from the definition of the DirectRanker, we have p = σ(w · (nn1(si) -nn2(sj ))) ≤ 0. Since nn1 and nn2 are identical and σ is sign-preserving, we have that p ≤ 0 ⇔ w · (nn(si) - nn(sj)) ≤ 0. Because the right-hand side is a linear transformation, it is equivalent to w · nn(si) ≤ w · nn(sj). Defining r(s) as w · nn(s), we have that p ≤ 0 ⇔ r(si) ≤ r(sj ) and therefore si ⪯ sj ⇔ r(si) ≤ r(sj).

4.3 Efficient Training

Another key difference of our framework lies in the training methodology. Unlike when learning a heuristic, where a specific value is required for each state, we train our DirectRanker D(si, sj) to learn the optimal ranking through classification and then extract the point-wise ranking function r(s). Thus, given a pair of states si and sj, it is sufficient to determine their relative optimal ranking, i.e., whether si ⪯∗ sj or sj ⪯∗ si, without assigning specific values to each state. This allows us to use siblings of states in optimal plans in the training process without the need to compute any information about them. Thus, for a problem with a constant branching factor b, an optimal plan π∗ of size n encodes O(bn) optimal ranking pairs for training. This contrasts with methods that directly learn a heuristic function (e.g., STRIPS-HGN [Shen et al., 2020] and GOOSE [Chen et al., 2024]), which can only extract n pairs in the form (s, h∗ (s)) from π∗ . Note that it is computationally expensive to compute h∗ (s′ ) for any s′ ̸∈ π∗ since it requires optimally solving the problem from s′ .

Another advantage of our framework is that we can efficiently handle this extra training data by batching the pairs si ≺ t for all siblings t of si and also t = si-1 for each si ∈ π∗ [Damke and H¨ullermeier, 2021]. The performance gains come from the fact that the embedding embsi is computed only once as opposed to |Nsi-1 | times, i.e., once for each pair involving si. Formally, let Bsi = {si-1} ∪ (Nsi-1 \ {si}), i.e., the set consisting of the siblings of si and its parent. We compute the embeddings for all states in Bsi resulting in the matrix Er ∈ Rm×n where m = |Bsi | and the j-th row of Er is the vector embedding of the j-th element in Bsi . Next, we compute the embedding embsi and stack m copies of it to create the matrix El ∈ Rm×n . Then we compute p = σ((El - Er)w) ∈ Rm where the j-th row of p is the output of τ comparing si and the j-th element in Bsi . Thus, we compute p by generating only |Bsi | + 1 embeddings as opposed to 2|Bsi | embeddings. This difference is important since computing each embedding in our experiments requires evaluating an expensive neural network architecture.

5 RelatedWork

The closest work to ours is [Chrestien et al., 2023] which learns a heuristic function using a pointwise ranking as the target, as opposed to h∗ . As with other approaches that learn a heuristic function, e.g., STRIPS-HGN [Shen et al., 2020] and GOOSE [Chen et al., 2024], their learned heuristics can be used with A∗ . However, all these approaches cannot guarantee that the solution found is optimal since the learned heuristic may not be admissible. For this reason, our work focuses on GBFS which allows us to remove the restriction that the learned ranking must also be a heuristic.

What makes the approach by Chrestien et al. (2023) different from all previous works on learning heuristics is that their target is a perfect ranking, a concept they introduced. A perfect ranking orders a pair of states s and t as s ≺ t for all s on the optimal path and t ∈ O when s is popped from the GBFS queue. It is equivalent to an optimal ranking without transitivity nor the requirement that si ≺ si-1 for two consecutive states si-1 and si in π∗ . To see the benefits of using an optimal ranking as the target instead of a perfect ranking, consider a problem with a constant branching factor b and an optimal plan π∗ = [s0, s1, ..., sn]. The number of ordered pairs s ≺ t encoded in the optimal plan is ∑ni=1 ib = b(n2 + n)/2. To learn a perfect ranking, Chrestien et al. (2023) use all pairs encoded in the optimal plan with the exception of the pairs si ≺ sj for si, sj ∈ π∗ and i < j, resulting in (b-1)(n2 +n)/2 total pairs. Alternatively, due to transitivity and the requirement that si ≺ si-1 for si ∈ π∗ imposed by our optimal ranking, we can encode all the b(n2 + n)/2 pairs using only bn pairs. Therefore, our training data scales linearly instead of quadratically with |π| while representing all ordered pairs considered by [Chrestien et al., 2023]. As our experiments will show, this has a large empirical effect on training efficiency and generalisation.

Our approach also differs in how the target ranking is learned. We learn a pairwise ranking function using classification through the DirectRanker architecture that is later converted to a pointwise ranking to be efficiently used with GBFS. The heuristic learned by [Chrestien et al., 2023] follows an approach in which a pointwise ranking function is learned using the 0-1 loss for an implicit pairwise ranking function. Their loss function is later relaxed to a logistic loss in order to use gradient optimisation.

Another work based on ranking is [Garrett et al., 2016]. They learn a pairwise ranking by training a Rank Support Vector Machine model [Joachims, 2002] using a convex relaxation of the Kendall rank correlation coefficient. This coefficient measures the degree of similarity between two rankings by computing the difference between the number of concordant and discordant pairs as a proportion of the total number of possible pairs. One main difference between our approaches is that we allow the use of any neural network for computing features while they use hand-crafted features extracted from the graph implicitly built by the FF heuristic [Hoffmann and Nebel, 2001]. Another key difference is that they use as data only the pairs within a suboptimal plan π, that is, they do not use the states outside of π.

6 Experiments

In this section, we empirically compare our ranking framework to Chrestien et al. 2023's framework using GBFS. For both frameworks, we consider two state-of-the-art neural network regression models, namely STRIPS-HGN [Shen et al., 2020] and GOOSE-LLG [Chen et al., 2024], for internal feature computation. To verify that learning a ranking is beneficial, we consider STRIPS-HGN and GOOSE by themselves, i.e., trained using h∗ as the learning target. As a baseline, we also consider the hff heuristic [Hoffmann and Nebel, 2001].

6.1 Dataset

We use the 10 domains from the 2023 International Planning Competition Learning Track (IPC23-LT) [Segovia and Seipp, 2023]. Each domain provides 100 training problems and 90 testing problems. We first solve the training problems using the Scorpion planner [Seipp et al., 2020] with a 30-minute time limit. Only problems solved optimally by Scorpion are used for training, but this still results in a dataset of sufficient size for our experiments. The training problems are randomly split between the training set (90%) and the validation set (10%). The problems in the validation set are used only to monitor convergence and control learning rates.

The testing set is divided into "easy", "medium" and "hard" subsets per domain, based on problem size, with 30 problems per subset. In contrast the training set only contains "easy" problems. Details of the dataset are shown in Table 1.

6.2 Training Settings

The two graph neural network regression models we use are GOOSE Lifted Learning Graph (LLG) [Chen et al., 2024] and STRIPS-HGN [Shen et al., 2020]. The former encodes the full planning problem and domain in a lifted form, whereas the latter encodes the problem delete relaxation in a grounded form. Both models can learn domain-independent heuristics and our framework inherits this property. However, our experiments are restricted to domain-specific rankings.

For both regression models, we used the code provided by their authors with all ReLU activations replaced by LeakyReLUs, except in their last layer. The ReLU function is suitable for learning heuristics because its values are non-negative; however, this restriction is not needed for learning a ranking and we observed that it results in slower convergence. For consistency, the same model parameters are used across our experiments: 4 message-passing layers and hidden dimension m = 64. For our framework, we use the output from the second-last hidden layer of the underlying regression model as the embedding vector, thus embs ∈ R64 .

For each domain, we compare GBFS using the following configurations for the heuristic/ranking:

GOOSE and HGN. The original GOOSE-LLG and STRIPS-HGN regression models trained using h∗ as target and their original loss function. The training dataset consists of all state-value pairs (s, h∗ (s)) for s in the optimal plan.

OptRank(GOOSE) and OptRank(HGN). Our optimal ranking framework combined with the respective regression models. The training dataset is the set of all ordered pairs s ≺ t for s in the optimal plan and t ∈ Ns′ ∪ {s′ } where s′ precedes s in the optimal plan.

PerfRank(GOOSE) and PerfRank(HGN). Chrestien et al. (2023)'s framework to learn a perfect ranking heuristic combined with each model. The loss function associated with the perfect ranking definition is also used. The training dataset consists of all ordered pairs s ≺ t for s in the optimal plan and t ∈ O when s is popped from the GBFS queue.

We use the Adam optimiser and an initial learning rate of 10-3 . The learning rate is reduced by a factor of 10 if the accuracy on the validation set does not improve for 10 consecutive epochs. Training is stopped when the learning rate reaches 10-6 or after 500 epochs.

For each configuration, we solve the problems in the testing set with Fast-Downward using eager-GBFS [Helmert, 2006], a time limit of 30 min per problem, and 8 GB of memory. All experiments are run on an Intel Xeon 2.1GHz CPU and NVIDIA A6000 GPU with 64GB of memory. The experiments were repeated three times and the average results are reported. The source code can be found at [Hao et al., 2024a] and an extended set of results in [Hao et al., 2024b].

6.3 Results

Total Coverage. Table 2 shows the coverage of each configuration on each domain, i.e., the number of problems it solves for this domain. Overall, using optimal rankings improved the coverage of the underlying regression model: 22%

and 32% increase for GOOSE and STRIPS-HGN, respectively. Our optimal ranking approach also obtained higher total coverage than the perfect ranking one: 8% and 176% increase for GOOSE and STRIPS-HGN, respectively. The large increase in coverage obtained by OptRank(HGN) w.r.t PerfRank(HGN) can be partially attributed to: (i) STRIPSHGN being a slower model to train; and (ii) PerfRank(HGN) using quadratically more data than OptRank(HGN). The convergence time for all learned configurations is shown in Figure 3 and we observe that, for any framework, using STRIPSHGN to generate features is slower than using GOOSE.

The impact of using STRIPS-HGN is less pronounced on OptRank(HGN) due to its compact dataset that exploits transitivity and is nearly equivalent to that of PerfRank(HGN). Moreover, despite processing O(b) more data than GOOSE where b is the average branching factor of a domain, OptRank(GOOSE) converges in a similar amount of time. Hence, it processes training data much faster.

Domain-specific coverage. When considering individual domains, OptRank(GOOSE) obtains the highest coverage in 3 domains, namely Blocksworld, Childsnack and Transport, with 46% (16 problems), 15% (4 problems) and 12% (5 problems) more coverage than the second-best planner, respectively. PerfRank(GOOSE) has the highest coverage only on Spanner, where it solves one more problem (2%) than OptRank(GOOSE). In Floortile, all configurations perform very poorly. This domain is known to be hard because it requires a large receptive field and it has many state space symmetries.

GOOSE configurations. OptRank(GOOSE) improves GOOSE's coverage in 6 domains and obtains the same coverage in the other 4 domains, therefore using optimal rankings is highly beneficial for this regression model. E.g, in Blocksworld and Spanner, GOOSE solves none or hardly any of the medium-difficulty problems, whereas OptRank(GOOSE) solves a large fraction or all of them, demonstrating a greater ability to generalise to larger problem sizes. PerfRank(GOOSE) almost always improves the coverage of GOOSE and its coverage is marginally smaller (2 problems, representing about 9%) only in Rovers and Satellite. OptRank(GOOSE) has better coverage than PerfRank(GOOSE) in 5 domains, namely Blocksworld, Childsnack, Rovers, Satellite and Transport, with 46% (16 problems), 20% (5

problems), 7% (2 problems), 22% (6 problems) and 18% (5 problems) more coverage, respectively. Their coverage is the same for Sokoban and PerfRank(GOOSE) solves one more problem than OptRank(GOOSE) for Ferry, Floortile, Miconic and Spanner.

To better understand the differences between OptRank(GOOSE) and both GOOSE and PerfRank(GOOSE), Figure 4 compares them regarding the number of nodes expanded, the cost of the returned plan and the search time to find a plan. We observe that OptRank(GOOSE) generally expands fewer nodes than GOOSE while achieving similar plan quality. This means OptRank(GOOSE) spends less time exploring unpromising regions of the search space and shows that our learned ranking generalises better than the learned GOOSE heuristic to unseen problems. Although our framework guarantees to learn a total quasi-order, there is no guarantee that the learned quasi-order is an optimal ranking. This can be observed in the plan quality plots where other approaches find plans cheaper than OptRank(GOOSE) for some problems. We also observe that PerfRank(GOOSE) generally expands more nodes than OptRank(GOOSE) and provides plans of slightly lesser quality.

STRIPS-HGN configurations. Considering only configurations based on STRIPS-HGN, OptRank(HGN) has the highest coverage in all domains except in Miconic where it solves two fewer problems than HGN. As with GOOSE, the usage of optimal rankings is also highly beneficial for this regression model. Surprisingly, PerfRank(HGN)'s coverage is lower than HGN's except on Childsnack, Floortile and Spanner. Moreover, PerfRank(HGN) did not converge for Blocksworld and Ferry. Note that our experiments use the original version of STRIPS-HGN [Shen et al., 2020] whereas Chrestien et al. (2023) use an improved version of STRIPSHGN. This and the different benchmark problems for each domain could explain part of the discrepancy.

Comparison with hff . Finally, none of the learned models were able to surpass the coverage of hff . However, OptRank(GOOSE) is not far off with just 9 fewer problems solved. This is an improvement on the competition results where the deep learning entries attempting to directly learn a heuristic or a policy did not exceed the score of HGN in our experiments. Moreover, OptRank(GOOSE) generally expands fewer nodes and finds plans of better quality than hff . Hence it is the inference time of GNNmodels remains an impediment to their competitiveness with special-purpose planning heuristics.

7 Conclusion

Heuristic search algorithms conventionally assume heuristic functions mapping states to goal-distance estimates. Yet, as was previously observed, for the popular greedy best-first search algorithm, the heuristic function merely serves to rank states, which is an overkill. To find a plan without search, as we show here, we only require an "optimal" ranking relating the states on an optimal plan to its neighbours. While this observation has yet to be used to design model-based heuristics, as we show here it is highly relevant for learning, and enables us to obtain much better performance than heuristic functions learned using the same neural network representations - even compared to a closely related ranking-learning framework.

It remains of course a bit disappointing that, at least in the benchmarks used here, the classic hff heuristic still performs best overall. This may change though with further research into representations and training algorithms for learning rankings. Apart from this, our results raise interesting questions regarding learning search guidance information for other settings and algorithms, for instance: Can our approach be extended to non-unit-cost problems? Are there other algorithms (e.g., hill-climbing or beam search) in which the heuristic function can be replaced with a simpler function that can be efficiently learned? What about variants of greedy best-first search for other forms of planning, such as top-K?

Acknowledgements

We thank the reviewers for their comments which helped improving the paper. This work was supported by Australian Research Council grant DP220103815, by the Artificial and Natural Intelligence Toulouse Institute (ANITI) under the grant agreement ANR-19-PI3A-0004, and by the European Union's Horizon Europe Research and Innovation program under the grant agreement TUPLES No. 101070149.