Return to Tradition: Learning Reliable Heuristics with Classical Machine Learning

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-04 16:59:06

Abstract: There has been a renewed interest in applying machine learning to planning due to recent developments in deep neural networks, with a lot of focus being placed on learning domain-dependent heuristics. However, current approaches for learning heuristics have yet to achieve competitive performance against domain-independent heuristics in several domains, and have poor overall performance. In this work, we construct novel graph representations of lifted planning tasks and use the WL algorithm to generate features from them. These features are used with classical machine learning methods such as Support Vector Machines and Gaussian Processes, which are both fast to train and evaluate. Our novel approach, WL-GOOSE, reliably learns heuristics from scratch and outperforms the $h^{\text{FF}}$ heuristic. It also outperforms or ties with LAMA on 4 out of 10 domains. To our knowledge, the WL-GOOSE learned heuristics are the first to achieve these feats. Furthermore, we study the connections between our novel feature generation methods, previous theoretically flavoured learning architectures, and Description Logic features.

Main paper: 
 introduction: 
 Learning for planning has regained traction in recent years due to advancements in deep learning (DL) and neural network architectures. The focus of learning for planning is to learn domain knowledge in an automated, domainindependent fashion in order to improve the computation and/or quality of plans. Recent examples of learning for planning methods using DL include learning policies (Toyer et al. 2018; Groshev et al. 2018; Garg, Bajpai, and Mausam 2019; Rivlin, Hazan, and Karpas 2020; Ståhlberg, Bonet, and Geffner 2022, 2023) , heuristics (Shen, Trevizan, and Thiébaux 2020; Karia and Srivastava 2021 ) and heuristic proxies (Shen et al. 2019; Ferber et al. 2022 ). However, learning for planning is not a new field and works capable of learning similar domain knowledge using classical statistical machine learning (SML) methods predate DL. For instance, learning heuristic proxies using support vector machines (SVMs) (Garrett, Kaelbling, and Lozano-Pérez 2016) and learning policies using reinforcement learning (Buffet and Aberdeen 2009) and decision lists (Yoon, Fern, and Givan 2002) . We refer to (Jiménez et al. 2012 ) for a more comprehensive overview of classical SML methods for learning.A notable advantage of DL methods over current SML methods for learning for planning is their ability to gen-eralise to unseen problems. For instance, DL-based generalised policies have demonstrated scalability to larger problems than previously possible (Toyer et al. 2020) , and heuristics learned using GNNs have shown generalisation across different domains (Shen, Trevizan, and Thiébaux 2020) . This added generalisation capability of DL comes with certain trade-offs, including a higher demand for data, a large number of hyperparameters and slower training and evaluation times compared to SML methods.In this paper, we introduce WL-GOOSE, a novel approach for learning for planning that combines the efficiency of SML-based methods with the generalisation capabilities of DL-based methods. WL-GOOSE uses a new graph representation for lifted planning tasks. However, differently from several DL-based methods, we do not use GNNs to learn domain knowledge and use graph kernels instead. More precisely, we use a modified version of the Weisfeiler-Lehman algorithm for generating features for graphs (Shervashidze et al. 2011) . This allows us to construct kernels using our graphs as input in order to train SML models. Another benefit of WL-GOOSE is its support for various learning targets, such as heuristic values or policies, without the need for backpropagation to generate features as in DL-based approaches. We also provide a theoretical comparison between our approach, GNNs for learning planning heuristics, and Description Logic features (Martín and Geffner 2000) .To demonstrate the potential of WL-GOOSE, we applied it to learn domain-specific heuristics using two classical SML methods: SVMs and Gaussian Processes (GPs). We evaluated the learned heuristics against the state-of-theart learning for planning on the 2023 International Planning Competition Learning Track benchmarks (Seipp and Segovia-Aguas 2023) . The learned heuristics generalised better than previous DL-based methods while also being more computationally efficient: our models took less than 10 seconds to train and are up to 421 times faster than GNNs which train on GPUs. Furthermore, our models were trained in a deterministic fashion with minimal parameter tuning, unlike DL-based approaches which require stochastic gradient descent and tuning of various hyperparameters. When used with greedy best-first search, our learned heuristics models achieved higher total coverage than h FF (Hoffmann and Nebel 2001) with an increase of 11% and 19% for SVMs and GPs, respectively. Moreover, our learned SVM and GP models outperformed or tied with LAMA (Richter and Westphal 2010) on 4 out of 10 domains. To our knowledge, these results make our learned heuristics using WL-GOOSE the first ones to surpass the performance of h FF and the best performing learned heuristics against LAMA. 
background and notation: 
 Planning A classical planning task (Geffner and Bonet 2013 ) is a state transition model given by a tuple Π = ⟨S, A, s 0 , G⟩ where S is a set of states, A a set of actions, s 0 ∈ S an initial state and G ⊆ S a set of goal states. An action a ∈ A is a function a : S → S ∪ ⊥ where a(s) = ⊥ indicates that action a is not applicable at state s, and otherwise, a(s) is the successor state when a is applied to s. An action also has an associated cost c(a) ∈ R. A solution or plan for this model is a sequence of actions π = a 1 • . . . • a n where s i = a i (s i-1 ) ̸ = ⊥ for i = 1, . . . , n and s n ∈ G. In other words, a plan is a sequence of applicable actions which progresses the initial state to a goal state when executed. The cost of a plan π is the sum of its action costs:c(π) = n i=1 c(a i ).A planning task is solvable if there exists at least one plan. A plan is optimal if there does not exist any other plan with strictly lower cost.We represent planning tasks in a compact form which does not require enumerating all states and actions. A lifted planning task (Lauer et al. 2021 ) is a tuple Π = ⟨P, O, A, s 0 , G⟩ where P is a set of first-order predicates, O a set of objects, A a set of action schemas, s 0 the initial state, and G the goal condition. A predicate P ∈ P has a set of parameters x 1 , . . . , x n P where n P ∈ N depends on P , and it is possible for a predicate to have no parameters. A ground proposition is a predicate which is instantiated by assigning all of the x i with objects from O or other defined variables. An action schema a ∈ A is a tuple ⟨∆(a), pre(a), add(a), del(a)⟩ where ∆(a) is a set of parameter variables, and the preconditions pre(a), add effects add(a), and delete effects del(a) are sets of predicates from P instantiated with elements from ∆(a) ∪ O. An action is an action schema where each variable is instantiated with an object. A domain D is a set of lifted planning tasks which share the same sets of predicates P and action schemas A.In a lifted planning task, states are represented as sets of ground propositions. The following are sets of ground propositions: states, goal condition, and the preconditions, add effects, and delete effects of all actions. An action a is applicable in a state s if pre(a) ⊆ s, in which case we define a(s) = (s\del(a))∪add(a). Otherwise a(s) = ⊥. The cost of an action is given by the cost of its corresponding action schema. A state s is a goal state if G ⊆ s.A heuristic is a function h : S → R ∪ {∞} which maps a state into a real number representing an estimate of the cost of the optimal plan to the goal, or ∞ representing that the state is unsolvable. A heuristic can be defined on problems by evaluating the heuristic at their initial state: h(Π) = h(s 0 ). The optimal heuristic h * returns for each state s the cost of the optimal plan to the goal if the problem is solvable from s, and ∞ otherwise.Algorithm 1: WL algorithm1 c 0 (v) ← c(v), ∀v ∈ V 2 for j = 1, . . . , h do for v ∈ V do 3 c j (v) ← hash c j-1 (v), { {c j-1 (u) | u ∈ N (v)} } 4 return j=0,...,h { {c j (v) | v ∈ V } } G 1 G 2Figure 1 : Two non-isomorphic graphs G 1 (6-cycle) and G 2 (two disjoint 3-cycles) which the WL algorithm returns the same outputs, thus failing to distinguishing them.We write ⟨V, E, c, l⟩ for a graph with coloured nodes and edges, where V is a set of nodes, E ⊆ V 2 is a set of undirected edges, c : V → Σ V maps nodes to a set of colours Σ V , and l : E → Σ E maps edges to a set of colours Σ E . The edge neighbourhood of a node u under edge colour ι isN ι (u) = {e = ⟨u, v⟩ = ⟨v, u⟩ ∈ E | l(e) = ι}. The neigh- bourhood of a node u in a graph is N (u) = ι∈Σ E N ι (u).We only focus on the WL algorithm which is a special case of the class of k-Weisfeiler-Lehman (k-WL) algorithms (Leman and Weisfeiler 1968) . The k-WL algorithms were originally constructed to provide tests for whether pairs of graphs are isomorphic or not. The k + 1-WL algorithm subsumes the k-WL algorithm as it can distinguish a greater class of non-isomorphic graphs, and furthermore is in correspondence with k-variable counting logics (Cai, Fürer, and Immerman 1992) . However, the complexity of the k-WL algorithms is exponential in k.The WL algorithm takes as input graphs without edge colours, i.e. ∀e ∈ E, l(e) = 0, and outputs a canonical form in terms of a multiset of colours, a set which is allowed to have duplicate elements. It has also been used to construct a kernel for graphs (Shervashidze et al. 2011 ) which converts the multiset of colours in the WL algorithm into a feature vector and then uses the simple dot product kernel. We denote a multiset of elements by { {. . .} }.The WL algorithm is shown in Alg. 1 which takes as input a graph G with coloured nodes only and a predefined number of WL iterations h. The algorithm begins by initialising the current colours of each node with the initial node colours. If no node colours are given in the graph, we can set them to 0. Line 3 updates the colour of each node v by iteratively collecting the current colours of its neighbors in a multiset and then hashing this multiset and v's current colour into a colour using an injective hash(•, •) function. In practice, hash is built lazily by using a map data structure and multisets are represented as sorted strings. Line 4 returns a multiset of the node colours seen over all iterations.If the WL algorithm outputs two different multisets for two graphs G 1 and G 2 , then the graphs are non-isomorphic. However, if the algorithm outputs the same multisets for two graphs we cannot say for sure whether they are isomor- Figure 2: ILG subgraph of facts and goal condition corresponding to the on predicate of a Blocksworld instance. The current state says that a stacked on b, which is stacked on c, and the goal condition is for c to be stacked on a.phic or not. The canonical example illustrating this case is in Fig. 1 where the two graphs are not isomorphic but the WL algorithm returns the same output for both graphs since it views all nodes as the same because they have degree 2. 
wl features for planning: 
 In this section we describe how to generate features for planning states in order to learn heuristics. The process involves three main steps: (1) converting planning states into graphs with coloured nodes and edges, (2) running a variant of the WL algorithm on the graphs in order to generate features, and then (3) training a classical machine learning model for predicting heuristics using the obtained features. We start by defining the Instance Learning Graph (ILG), a novel representation for lifted planning tasks. Definition 3.1. The instance learning graph (ILG) of a lifted planning problem Π = ⟨P, O, A, s 0 , G⟩ is the graphG = ⟨V, E, c, l⟩ with • V = O ∪ s 0 ∪ G • E = p=P (o1,...,on P )∈s0∪G ⟨p, o 1 ⟩ , . . . , ⟨p, o n P ⟩ • c : V → ({ap, ug, ag} × P) ∪ {ob} defined by u →        ob, if u ∈ O; (ag, P ), if u = P (o 1 , . . . , o n P ) ∈ s 0 ∩ G; (ap, P ), if u = P (o 1 , . . . , o n P ) ∈ s 0 \ G; (ug, P ), if u = P (o 1 , . . . , o n P ) ∈ G \ s 0 ; • l : E → N with ⟨p, o i ⟩ → i.Fig. 2 provides an example of an ILG. An ILG consists of a node for each object and the union of propositions that are true in the state s 0 and the goal condition G. A proposition is connected to the n object nodes which instantiates the proposition. The labels of the n edges correspond to the position of the object in the predicate argument. The colours of the nodes indicate whether the node corresponds to an object (ob), or determines whether it is a proposition belonging to s 0 (ap) or G (ug) only or both (ag), as well as its corresponding predicate. Hence ug stands for unachieved goal, ag for achieved goal, and ap for achieved (non-goal) proposition. Note that ILGs are agnostic to the transition system of the planning task as they ignore action schemas and actions.Since ILGs have coloured edges, we need to extend the WL algorithm to account for edge colours to generate features for ILGs. Our modified WL algorithm is obtained by replacing Line 3 in Alg. 1 with the update function where the union of multisets is itself a multiset. Note that edge colours do not update during this modified WL algorithm. It is possible to run a variant of the WL algorithm which modifies edge colours but this comes at an additional computational cost given that usually |E| ≫ |V |. Now that ILGs can be represented as multisets of colours, we can generate features by representing these multisets as histograms (Shervashidze et al. 2011) . The feature vector of a graph is a vector v with a size equal to the number of observed colours during training, where v[κ] counts how many times the WL algorithm has encountered colour κ throughout its iterations. Formally, let c j (v) ← f c j-1 (v), ι∈Σ E (c j-1 (u), ι) | u ∈ N ι (v) ,G 1 = ⟨V 1 , E 1 , c 1 , l 1 ⟩ , . . . , G n = ⟨V n , E n , c n , l n ⟩C = {c j i (v) | i ∈ {1, . . . , n}; j ∈ {0, . . . , h}; v ∈ V i } where c j i (v) is the colour of node v in graph G i during the j-th iteration of WL for j > 0 and c 0 i (v) = c i (v). Given a planning task Π and the set of colours C ob- served during training, Π's feature vector representation ⃗ v ∈ R |C| is ⃗ v = [count C (Π, κ 1 ), . . . , count C (Π, κ |C| )]where count C (Π, κ) is the number of times the colour κ ∈ C is present in the output of the WL algorithm on the ILG representation of Π. There is no guarantee that C contains all possible observable colours for a given planning domain and colours not in C observed after training are ignored. 
theoretical results: 
 In this section, we investigate the relationship between WL features and features generated using message passing graph neural network (GNN), description logic features (DLF) for planning (Martín and Geffner 2000) and the features used by Muninn (Ståhlberg, Bonet, and Geffner 2022, 2023) , a theoretically motivated deep learning model. Fig. 3 summarises our theoretical results.We begin with some notation. Let D represent the set of all problems in a given domain. We define WLF ILG Θ : D → R d as the WL feature generation function described in Sec. 3 which runs the WL algorithm on the ILG representation of planning tasks. We denote Θ the set of parameters of the function which includes the number of WL iterations and the set of colours C with size d observed during training. We similarly denote parametrised GNNs acting on ILG representations of planning tasks by GNN ILG Θ : D → R d . Parameters for GNNs include number of message passing layers, the message passing update function with fixed weights, and the aggregation function.We denote DLF generators (Martín and Geffner 2000) by DLF Θ : D → R d where the parameters for DLF include the maximum complexity length of its features (Bonet, Francès, and Geffner 2019) . DLFs have been used in several areas of learning for planning including learning descending dead-end avoiding heuristics (Francès et al. 2019) , unsolvability heuristics (Ståhlberg, Francès, and Seipp 2021) and policy sketches (Drexler, Seipp, and Geffner 2022) . Lastly, we denote the architecture from Ståhlberg, Bonet, and Geffner (2022) for generating features by Muninn Θ : D → R d . We omit their final MLP layer which transforms the vector feature into a heuristic estimate. Furthermore in our theorems, we ignore their use of random node initialisation (RNI) (Abboud et al. 2021) . The original intent of RNI is to provide a universal approximation theorem for GNNs but the practical use of the theorem is limited by the assumption of exponential width layers and absence of generalisation results. Thus, it is unclear what benefits RNI brings to Muninn for planning. Parameters for Muninn include hyperparameters for their GNN architecture and the learned weights for their update functions.In all of the aforementioned models, the parameters Θ consist of a combination of model hyperparameters and trained parameters based on a training set T D ⊆ D. The expressivity and distinguishing power of a feature generator for planning determines if it can theoretically learn h * for larger subsets of planning tasks. We begin with an application of a well-known result connecting the expressivity of the WL algorithm and GNNs for distinguishing graphs (Xu et al. 2019 ) by extending it to edge-labelled graphs.Theorem 4.1 (WLF ILG and GNN ILG have the same power at distinguishing planning tasks.). Let Π 1 and Π 2 be any two planning tasks from a given domain. If for a set of parameters Θ we have that GNN ILG Θ (Π 1 ) ̸ = GNN ILG Θ (Π 2 ), then there exists a corresponding set of parameters Φ such thatWLF ILG Φ (Π 1 ) ̸ = WLF ILG Φ (Π 2 ). Conversely for all Φ such that WLF ILG Φ (Π 1 ) ̸ = WLF ILG Φ (Π 2 ), there exists Θ such that GNN ILG Θ (Π 1 ) ̸ = GNN ILG Θ (Π 2 ).Proof.[⊆] The forward statement follows from (Xu et al. 2019 , Lemma 3) which states that GNNs are at most as expressive as the WL algorithm for distinguishing nonisomorphic graphs. We can modify the lemma for the edge labelled WL algorithm and GNNs which account for edge features. Then the result follows after performing the transformation of planning tasks into the ILG representation.[⊇] The converse statement follows from (Xu et al. 2019, Corollary 6 ) and modifying Eq. (4.1) of their GIN architecture by introducing an MLP for each of the finite number of edge labels in the ILG graph and summing their outputs at each GIN layer. The MLPs have disjoint range in order for injectivity to be preserved as to achieve the same distinguishing power of the edge labelled WL algorithm. This can be easily enforced by increasing the hidden dimension size and having each MLP to map to orthogonal dimensions.We proceed to show that GNNs acting on ILGs is similar to Muninn's GNN architecture (Ståhlberg, Bonet, and Geffner 2022). The idea of the proof is that encoding different predicates into the ILG representation is equivalent to having different weights for message passing to and from different predicates in Muninn. However, we also show that our model has strictly higher expressivity for distinguish planning tasks due to explicitly encoding achieved goals.Q(a,a) Q(b,b) Q(a,b) Q(b,a) a b (a) ILG of Π1 Q(a,b) Q(b,a) a b (b) ILG of Π2 Q(a,a) Q(b,b) Q g (a,b) Q g (b,a) a b (c) Implicit Muninn graph of Π1 Q(a,b) Q(b,a) Q g (a,b) Q g (b,a) a b (d) Implicit Muninn graph of Π2Theorem 4.2 (GNN ILG is strictly more expressive than Muninn at distinguishing planning tasks.). Let Π 1 and Π 2 be any two planning tasks from a given domain. For all Θ, if Muninn Θ (Π 1 ) ̸ = Muninn Θ (Π 2 ), then there exists a corresponding set of parameters Φ such thatGNN ILG Φ (Π 1 ) ̸ = GNN ILG Φ (Π 2 ).Furthermore, there exists a pair of planning tasks Π 1 and Π 2 such that there exists Φ withGNN ILG Φ (Π 1 ) ̸ = GNN ILG Φ (Π 2 ) but for all Θ, Muninn Θ (Π 1 ) = Muninn Θ (Π 2 ).Proof.[⊇] In order to show the inclusion, we show that a Muninn instance operating on a state can be expressed as a GNN operating on the ILG representation of the state. More explicitly, we show that the implicit graph representation of planning states by Muninn is the same graph as ILG. The message passing steps and initial node features are different but the semantic meaning of executing both algorithms are the same. The node features in the implicit graphs of Muninn are all the same when ignoring random node initialisation. Muninn differentiates object nodes and fact nodes by using different message passing functions depending on whether a node is an object or a fact, and depending on which predicate the fact belongs to. In the language of ILG, Muninn's message passing step on fact nodes p = P (o 1 , . . . , o n P ) isEQUATIONwhere h l+1 p denotes the latent embedding of the node p in the l + 1-th layer, h l oi denotes the latent embedding of the object node o i in the l-th layer, and MLP P is a multilayer perceptron, with a different one for each predicate. The message passing step of Muninn on object nodes o i isEQUATIONwhere o ∈ p denotes that o is an argument of the predicate associated with p. We note that having a different MLP in the message passing step for different nodes is equivalent to having a larger but identical MLP in the message passing step for all nodes. This is because the model can learn to partition latent node features depending on their semantic meaning and thus be able to use a single MLP function to act as multiple different functions for different node feature partitions. Thus, Eq. ( 1) and ( 2) can be imitated by a GNN operating on ILG since ILG features differentiate nodes depending on whether they correspond to an object, or a fact associated with a predicate. Different edge labels in the ILG allow it to distinguish the relationship between facts and objects depending on their position in the predicate argument.[⊋] To see how GNN ILG is strictly more expressive than Muninn, we consider the following pair of planning tasks. The main idea is that Muninn does not keep track of achieved goals and sometimes cannot even see that the goal has been achieved. Let Π 1 = ⟨P, O, A, s(1) 0 , G⟩ and 4 illustrates the ILG representation and the implicitly defined edge-labelled graph representation in Muninn's GNN architecture of Π 1 and Π 2 . It is clear that the ILG representation of Π 1 and Π 2 are different and hence GNN ILG differentiates between Π 1 and Π 2 . On the other hand without RNI, Muninn sees the pair of non-isomorphic graphs in Fig. 4 (c) and (d). However, any edge-labelled variant of the WL algorithm views the pair of graphs as the same, and hence so does Muninn.Π 2 = ⟨P, O, A, s (2) 0 , G⟩ with P = {Q}, O = {a, b}, A = ∅, G = s (2) 0 = {Q(a, b), Q(b, a)} and s (1) 0 = {Q(a, a), Q(b, b)}. Fig.Corollary 4.3 (WLF ILG is strictly more expressive than Muninn at distinguishing planning tasks.). Let Π 1 and Π 2 be any two planning tasks from a given domain. For all Θ, if Muninn Θ (Π 1 ) ̸ = Muninn Θ (Π 2 ), then there exists a corresponding set of parameters Φ such that WLF ILG Φ (Π 1 ) ̸ = WLF ILG Φ (Π 2 ). Furthermore, there exists a pair of planning tasks Π 1 and Π 2 such that there exists Φ with WLF ILG Φ (Π 1 ) ̸ = WLF ILG Φ (Π 2 ) but for all Θ, Muninn Θ (Π 1 ) = Muninn Θ (Π 2 ).Our next theorem shows that WLF ILG and DLF features are incomparable, in the sense that there are pairs of planning tasks that look equivalent to one model but not the other. We use a similar counterexample to that used for Muninn but with an extra predicate which WLF ILG does not distinguish but DLF can. Conversely we use the fact that DLFs are limited by the need to convert planning predicates into binary predicates to construct a counterexample pair of planning tasks with ternary predicates which DLF views as the same while WLF ILG does not. Theorem 4.4 (WLF ILG and DLF are incomparable at distinguishing planning tasks.). There exists a pair of planning tasks Π 1 and Π 2 such that there exists Φ with WLF ILG Φ (Π 1 ) ̸ = WLF ILG Φ (Π 2 ) but for all Θ, DLF Θ (Π 1 ) = DLF Θ (Π 2 ). Furthermore, there exists a pair of planning tasks Π 1 and Π 2 such that there exists Φ with DLF Φ (Π 1 ) ̸ = DLF Φ (Π 2 ) but for all Θ, We have that h * (Π 1 ) = ∞ as the problem Π 1 is unsolvable, while h * (Π 2 ) = 2 as the optimal plan contains actions o(a, b) and o(b, a). DL features are able to distinguish the two planning tasks by considering the role-value map (Q = W )(s) defined by {x | ∀y : Q(x, y) ∈ s ⇐⇒ W (x, y) ∈ s}, and the corre-WLF ILG Θ (Π 1 ) = WLF ILG Θ (Π 2 ). Proof. [∃<]sponding numerical feature |Q = W | (s) = |(Q = W )(s)|. We have that |Q = W | (s (1) 0 ) = 0 and |Q = W | (s (1) 0 ) = 2, meaning that DLF can distinguish between Π 1 and Π 2 .On the other hand, the ILG representations of Π 1 and Π 2 are indistinguishable to our definition of the edge-labelled WL algorithm. Fig. 5 illustrates this example and we note that it is similar to the implicit Muninn graph representations of the pair of planning tasks from Thm. 4.2.[∃>] We identify a pair of problems with ternary predicates which compile to the same problem with only binary predicates for which DL features are defined. For problems with at most binary predicates, DL introduces base roles on each predicate P (x, y) ∈ P by P s = {(a, b) | P (a, b) ∈ s} where s is a planning state. Then given an n-ary predicate R(x 1 , . . . , x n ), DL introduces n(n -1)/2 roles defined by R s P (c, b, c), P (a, d, c), P (c, d, a )} s , b, c), P (c, b, a), P (a, d, a), P (c, d, c )}. We have that h * (Π 1 ) = ∞ since there are no actions and the initial state is not the goal condition, while h * (Π 2 ) = 0 since G ⊆ sEQUATION(2) 0 = {P (a(2) 0 . The ILG for the two tasks are distinguished by the WL algorithm as the ILG of Π 1 has no achieved goal colour while Π 2 does. However, DL features view the two states s(1) 0 and s(2) 0 as the same due after the compilation from ternary to binary predicates:P 1,2 (a, b) P 1,2 (a, d) P 1,2 (c, b) P 1,2 (c, d) P 1,3 (a, a) P 1,3 (a, c) P 1,3 (c, a) P 1,3 (c, c) P 2,3 (b, a) P 2,3 (b, c) P 2,3 (d, a) P 2,3 (d, c).Thus any DL features will be the same for both s(1) 0 and s(2) 0 and thus cannot distinguish Π 1 and Π 2 .Our final theorem combines previous results and states that there exist domains for which all feature generators defined thus far are not powerful enough to perfect learn h * . Although this is not a surprising result, we hope to bring some intuition on what is further required for constructing more expressive features for learning for planning.Corollary 4.5 (All feature generation models thus far cannot generate features that allow us to learn h * for all domains.). Let F ∈ WLF ILG , GNN ILG , Muninn, DLF . There exists a domain D with a pair of planning tasks Π 1 , Π 2 such that for all parameters Θ for F, we have thatF Θ (Π 1 ) = F Θ (Π 2 ) and h * (Π 1 ) ̸ = h * (Π 2 ).In this section, we concluded that our WLF ILG features are one of the most expressive features thus far in the literature for representing planning tasks, the other being DLF features. We have done so by drawing an expressivity hierarchy between our WLF ILG features and previous work on GNN architectures (Ståhlberg, Bonet, and Geffner 2022) . We further constructed explicit counterexamples illustrating the difference between WLF ILG and DLF features, highlighting their respective advantages and limitations. 
experiments: 
 In this section, we empirically evaluate WL-GOOSE for learning domain-specific heuristics against the state-of-theart. We consider the domains and training and test sets from the learning track of the 2023 International Planning Competition (IPC) (Seipp and Segovia-Aguas 2023) . The domains are Blocksworld, Childsnack, Ferry, Floortile, Miconic, Rovers, Satellite, Sokoban, Spanner, and Transport. Each domain contains instances categorised into easy, medium and hard difficulties depending on the number of objects in the instance. For each domain, the training set consists of at most 99 easy instances and the test set consists of exactly 30 instances from each of the three easy, medium and hard difficulties that are not in the training set.The hyperparameters considered for WL-GOOSE are the number of iterations h for generating features using the WL algorithm and the choice of a machine learning model used and its corresponding hyperparameters. In all our experiments with WL-GOOSE, we use h = 4 and, since our learning target is h * , we consider the following regression models: support vector regression with the dot product kernel (SVR) and the radial basis kernel (SVR ∞ ), and Gaussian process regression with the dot product kernel (GPR). We choose SVR over ridge regression for our kernelised linear model due to its sparsity and hence faster evaluation time with use of the ϵ-insensitive loss function (Vapnik 2000) . The choice of Gaussian process allows us to explore a Bayesian treatment for learning h * providing us with confidence bounds on the learned heuristics.Furthermore, we experiment with the 2-LWL algorithm with h = 4 for generating features alongside SVR with the dot product kernel (2-LWL). The 2-LWL algorithm is a computationally feasible approximation of the 2-WL algorithm (Morris, Kersting, and Mutzel 2017) , which in turn is a generalisation of the WL algorithm where colours are assigned to pairs of vertices. While the features computed by the 2-WL algorithm subsume those of the WL algorithm, it is computationally more expensive to compute requiring quadratically more time than the WL algorithm.For any configuration of WL-GOOSE, we use optimal plans returned by scorpion (Seipp, Keller, and Helmert 2020) on the training set with a 30-minute timeout on each instance for training. We use 67% of the states and the corresponding cost to the goal from each optimal plan as training data and the remaining 33% were used as a validation set for logging loss scores.As baselines for heuristics, we use the domainindependent heuristic h FF and GNNs operating on the ILG representations of planning tasks. For the GNNs, we use 4 message passing layers and consider both max and mean aggregators. All heuristics are evaluated using greedy bestfirst search. We include LAMA (Richter and Westphal 2010) using its first plan output as a strong satisficing planner that uses multi-queue heuristic search and other optimisation techniques. We also compare against Muninn using the same weights trained in its entry of the 2023 IPC Learning Track. For all methods, we use a timeout of 1800 seconds per evaluation problem. With the exception of the GNNs using ILGs, the experiments were run on a cluster with single Intel Xeon 3.2 GHz CPU cores and a memory limit of 8GB. For the GNNs using ILGs, we used single Intel Xeon Gold 5218R 2.1GHz CPU cores and an NVIDIA RTX A6000 GPU with 48GB memory. However the GNNs never use more than 8GB of GPU or main memory before reaching the timeout. The other planners in the competition were not considered because they do not explicitly learn a heuristic.Tab. 1 summarises our experiments by showing the coverage per domain for each planner as well as their total IPC score. Next, we discuss our results in detail and we conclude this section by describing how to analyse the learned features of our models using an example.How well do heuristics learned from WL features perform? Considering total coverage and total IPC score (Tab. 1), we notice that SVR and GPR outperform all the other planners with the exception of LAMA-first, i.e., all learning-based approaches as well as h FF . Domain-wise, SVR and GPR outperform Muninn in all domains while outperforming GNNs using ILGs on 8 and 9 domains, respectively. Both SVR and GPR outperform or tie with LAMA on 4 domains, namely Blocksworld, Ferry, Miconic and Spanner. GPR is able to return better plans than LAMA on 5 domains (Blocksworld, Childsnack, Ferry, Miconic, Sokoban), while the reverse is true only on 3 domains (Rovers, Satellite, Spanner). For Spanner, this is because LAMA's heuristics are not informative for this domain, which leads to it performing like blind search and hence returning better plans.SVR and GPR also outperform or tie with h FF on 5 and 7 domains, respectively. We compare GPR and h FF in more detail in Fig. 6 by showing plan cost and nodes expanded per problem. We observe that the better performing planner on a domain generally has better plan quality and fewer number of expanded nodes. The only exception to this is Sokoban where GPR expands more nodes than h FF but solves more problems because it is faster with its heuristic evaluations. Overall, the domains in which GPR performs worse are domains that require traversing a map which WL features cannot express due to the finite number of WL iterations.Are our methods more computationally efficient to train? To answer this question, we compare the training time of GNNs using ILGs, SVR and GPR. Their mean and 95% confidence interval in seconds are 112.8 ± 54.3 (GNN max ), 142.7 ± 62.6 (GNN mean ), 0.8 ± 0.5 (SVR) and 2.6 ± 1.7 (GPR). Comparing against the most efficient GNN model per domain, we have that SVR is between 33x (Sokoban) to 421x (Rovers) more efficient and GPR is between 13x (Blocksworld) and 118x (Spanner) more efficient. Note that the GNNs have access to GPUs and they would take even more time to train on a CPU. Does kernelising help? As commonly done in classical machine learning, we combine our WL features with nonlinear kernels to obtain new non-linear features that can increase the expressivity of the regression models. Unfortunately, as shown in Tab. 1, this generally results in a decrease in the performance of the learned heuristic: the SVR ∞ model has significantly worse coverage than SVR despite theoretically having more expressive implicit features. The drop in performance can be explained by overfitting to the more expressive features which do not bring any obvious semantic information for planning tasks.Do higher order WL features help? The motivation for using higher-order WL features is similar to using higherorder kernels: to introduce more expressive features that may be correlated with the optimal heuristic. In Tab. 1, we see that the performance of 2-LWL is generally worse on all domains except for Transport. This again can be attributed to poorer generalisation. Furthermore, computing the 2-LWL features are slower to generate than WL features as they take time cubic in the size of the ILGs in the worst case. We also note that attempting to generate 3-LWL features causes out of memory problems during training as the size of features generated is extremely large, on the order of 10 7 and above.Are Bayesian variance estimates meaningful? One advantage of Bayesian models is that by assuming a prior distribution on the weights of our models, we are able to derive uncertainty bounds on the outputs of the learned posterior model. In Tab. 2, we analyse the Pearson's correlation coefficient between the standard deviation obtained by GPR and (1) the error between output mean and h * , and (2) the number of expanded nodes using the learned heuristic with greedy best first search. We see that there is a statistically significant strong correlation between the heuristic estimate error and the GPR variance outputs. This is reasonable given that the deriva- tion of the Bayesian model computes the uncertainty on its output prediction. The story is different for the number of expanded nodes during search where for easy problems there is no significant correlation depending on the domain. Interestingly, the correlation is more significant and stronger on harder problems for more domains. Thus, the Bayesian model is able to determine the difficulty of solving a problem within a domain by looking at the predicted standard deviation for h(s 0 ) but the quality of this prediction will depend on the domain.Another advantage of WL-GOOSE is that its set of features is explainable, and it is possible to see which features are chosen when using a linear inference model. The models can be understood by analysing the features with the highest corresponding linear weights, and by observing the distribution of such weights. The semantic meaning of the features can be understood by examining the generation of WL colours. This can be achieved by representing the observed WL colours as a directed acyclic graph (DAG) where each WL colour is a node and there is a directed edge from κ to κ ′ if κ ′ = hash(x, M ) and x = κ or ∃ι, (κ, ι) ∈ M .We provide an example of how to interpret the learned models by briefly studying the learned GPR model on Blocksworld. In this domain, a total of 8990 features were generated from the training data and Fig. 7 illustrates the DAG representation of feature 85's generation. Consider feature 10 in Fig. 7 , it computes the number of blocks that are correctly on the table and also have the correct block above it. We have that 10 = hash(0, { {(5, 1), (3, 2)} }), mean-ing that the colour 10 is generated from an object node (0 = ob) which is part of an achieved on-table goal (5 = (ag, on-table)) and achieved on goal (3 = (ag, on)). The corresponding edge label of the node colours indicate the position of the block object in the proposition. Thus, blocks b with colour 10 are in the first and only argument of on-table and the second argument of on. This means that the colour 10 is assigned to blocks correctly on the table and correctly underneath another block.Moreover, we observed that certain subsets of features were evaluated to the same value on all training states. As a result, the same learned weight value was assigned to each feature in these subsets. This can be seen in Fig. 7 where features 10, 28, 49 and 85 are semantically equivalent. The sum of their weight values is -1.70, the second largest in value from subsets of features. Thus, the learned weight rewards states satisfying this condition as blocks correctly on the table do not have to be moved.Note that, it is possible for features to evaluate to the same values on the training set but have different semantic meanings because the training set is finite. For example, in Blocksworld, a training set may satisfy that a block is correctly on the table if and only if it has the correct block above it. In this case, the count of colours 5 and 10 would be the same on all states despite not being semantically equivalent. 
conclusion: 
 We introduced WL-GOOSE, a novel approach that combines the efficiency of Statistical Machine Learning (SML) models with features commonly used by Deep Learning (DL) methods. To achieve this, we developed the Instance Learning Graph (ILG), a novel representation of lifted planning tasks and provided a method to generate features for ILGs based on the WL algorithm. Similar to Description Logic features for planning, our generated features are agnostic to the learning target and can be used without the need for backpropagation. Furthermore, unlike DL-based approaches, our models can be trained in a deterministic fashion with minimal parameter tuning. To validate the benefits of WL-GOOSE, we have used two classical SML models, namely support vector regression (SVR) and Gaussian process regression (GPR), to learn domain-specific heuristics and compared them to the state of the art.The experimental results showed that WL-GOOSE can efficiently and reliably learn domain-specific heuristics from scratch. Compared to GNNs applied to ILGs, our learned heuristics are between 13 to 421 times faster to train and solve up to 28.5% more problems. Our results also showed that both SVR and GPR are the first learned heuristics capable of outperforming h FF in terms of total coverage. Moreover, our learned heuristics outperform or tie with LAMA on 4 domains and, to our knowledge, this is the best performance of learned heuristics against LAMA. We also showed the theoretical connections between our novel feature generation method with Description Logic features and GNNs. Our future work agenda includes exploring how to best use the uncertainty bounds provided by GPR to improve search, as well as combining stronger satisficing search algorithms to further improve WL-GOOSE. 
 
 Appendix:  


Decision: This paper proposes an approach to learning domain-specific heuristic functions for classical planning which uses a graph representation and statistical learning methods.

Reviewer opinions were divided on this paper. Unfortunately, there was little discussion after the author rebuttal phase.

As metareviewer, I tend to agree with the assessment of paper strengths cited by the reviewers. Specifically, the paper proposes a novel graph representation (ILG), theoretically analyzes the capabilities of this model, and shows impressive experimental results compared to recent, domain-specific learning systems.

 The reviewer with the lowest score seems to base the low score on perceived weaknesses with the experimental evaluation, but I believe  the authors rebuttal adequately addresses these concerns, and I believe the experimental evaluation is convincing with respect to the goals of this paper as explained by the authors.

Reviews: review: strength_weakness: strength_weakness: 1. This paper shows better generalization than earlier ones, but it doesn't entirely look into how it can be used for many different planning tasks. There are concerns about how flexible the method is in difficult real-life situations because of this limitation.
2. There are problems with overfitting when non-linear kernels and higher-order WL features are added. This affects the performance. Because it is too good at fitting, the model might miss important dynamics in planning tasks with complex patterns, like manipulating robots in complex ways or making strategic decisions in games.
3. This model's experimental results show it is efficient, but there isn't enough in-depth research on the trade-off between how fast it works and how well it solves problems. This trade-off is significant for tasks requiring much computing power, like large-scale and complex domains.
4. Only certain areas from the International Planning Competition are used for the trials. Many test cases are needed to understand how robust the method is entirely. 
5. The model's experimental setup doesn't mention the problem's difficulty; even though it focuses on generalization in terms of objects and domains, the lack of information related to the difficulty of the problem instances doesn't assure the correct interpretations of the results in terms of performance.
6. Missing citations relevant to the publication, such as https://dspace.cuni.cz/handle/20.500.11956/180047 and others.
questions: questions: 1. What is WL-GOOSE's response time in places with dynamic state space?
2. Any comments on handling WL-GOOSE from overfitting when using more complex features, like non-linear kernels, in complex domains?
3. Please explain more about the concerns that come up when comparing the suggested method's speed to its optimality, especially when a lot of computing power is needed.
4. What does WL-GOOSE do when the domain's world model changes?
5. If the problems were the same level of hardness across all domains, and if the levels of hardness changed for specific items that required more steps to reach the goal state.

- When manipulating robots in ways that require fine or exact movements, the patterns that they need to learn are complicated and subtle. Knowing how WL-GOOSE keeps from overfitting in these situations is very important.
strength_weakness: strength_weakness: I don’t really sure why the authors select Lama-first for comparison. IPC Organizers select two different planners for learning track Fast Downward SMAC 2014 and Progressive Generalized Planner. I recommend comparing with this ones. Especially if we want to frame it in the same framework as the competition, as well as the domains used in it. And the results are in term of coverage not quality like in the competition.

The paper said: “The other planners in the competition were not considered because they do not explicitly learn a heuristic.” I think this is not a good reason to include them in the comparison.

I didn’t know what "Munnin" and there is  no reference in the paper. I think it is important to understand the comparison.

 Small issues: 

In the Abstract appear WL algorithm, I suppose should be Weisfeiler-Lehman algorithm, but I don’t sure about that, it is the first time that appear this acronym. In addition, the use of acronyms in the summary is not very common. 
Normally when references are used as part of a sentence, only the year should be enclosed in parentheses: “We refer to (Jimenez et al. 2012) for a more, this reference should be We refer to Jimenez et al. (2012)
questions: questions: Why do you compare the result with FDSS or GOFAI?  

Why table 1 is coverage? The results in learning track are in terms of quality. Lama gest 517.6 FDD 74.1 and SMAC 445.7, and the winner of the competition, GOFAI 508.5.
strength_weakness: strength_weakness: I think the experimental section of the paper is missing some experimental settings and results. I will address them in the question section.  
Although they are well-known, I think a brief background section on the SML models used, similar to the one for Classical Planning, would be useful.
questions: questions: 1) What are the ranges of objects for the easy, medium and hard problems in each domain? 
2) What are the performance on the different classes of problems in terms of coverage?