Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning

Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner · 2026

Read Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning by Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18674.txt.

Introduction

Michael Aichmüller and three co-authors improve Iterated Width policies for general classical planning, published in 2026. Earlier work broadened successor scope through IW-lookahead search jumping over transitions, but each transition was scored alone, costing compute. Their holistic encoding of the whole search tree scores all transitions in one forward pass of a relational graph network. Abstracted IW(1) scales novelty checks by abstracting atoms to their types, shifting scaling from atoms to objects. On the hyperscaling IPC 2023 benchmark and diverse domains, policies beat the classical planner LAMA.

Catalog record

CREATORMichael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE73852
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.18674

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Efficient Lookahead Encoding and Abstracted Width for Learning General Policies in Classical Planning Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner Abstract Generalized planning aims to learn policies that generalize across large collections of instances within a classical planning domain. Recent approaches using Graph Neural Networks (GNNs) have shown the ability to learn nearly perfect policies for several domains. This work improves on the recently published idea of Iterated Width (IW) policies. Therein, the policy broadens its successor scope through an IW-lookahead search that offers to “jump” over multiple transitions, simplifying the problem structure. Yet, each transition is evaluated individually leading to unscalable compute and expressivity limitations. Furthermore, while an IW(1) search is attractive due to scaling linearly with the number of atoms in a problem, it still becomes inefficient once thousands of objects are considered like in the International Planning Competition (IPC) 2023 benchmark. In this work, we address both limitations. Firstly, we introduce a vastly more efficient holistic encoding of the entire search tree. It jointly represents IW(1)-reachable states only by their relational differences to the current state, which enables Relational GNNs (R-GNNs) to score all transitions in a single forward pass. Secondly, we define Abstracted IW(1) to improve scaling through relational abstraction during novelty checks. Rather than testing fully instantiated atoms, it abstracts each atom by replacing all but one of its arguments with their types. The original atom is then novel if any of its abstracted forms is. This structural compression shifts the scaling of the novelty search to be linear in the number of objects, rather than atoms, still capturing meaningful subgoal structure. Our contributions are evaluated on the hyperscaling IPC 2023 benchmark and across a broad range of domains, including those that require features beyond the C 2 C_{2} logic fragment. The results show that our policies achieve a new state-of-the-art performance, significantly surpassing prior work, including classical planners like LAMA. 1 Introduction Generalized planning aims to learn policies that generalize across large collections of planning problems within the same domain, differing only in initial states, goals, and object counts ( 31 ; 18 ; 19 ) . A general policy allows for solving diverse planning problems greedily, eliminating the need for search. Various approaches have been pursued to learn such policies from domain descriptions and training instances, ranging from symbolic to deep learning methods. While symbolic approaches offer transparency and potential correctness guarantees, they often struggle with scalability ( 20 ; 22 ; 13 ; 31 ; 7 ; 30 ; 14 ) . Conversely, deep learning approaches, though opaque, tend to scale more effectively ( 38 ; 3 ; 28 ; 34 ) . State-of-the-art generalized planning methods include supervised transformer-based approaches ( 29 ) and unsupervised reinforcement learning (RL) approaches using graph neural networks (GNNs), specifically relational GNNs. Both paradigms achieve impressive results on benchmarks, despite the known expressivity limitations of GNNs and transformers ( 39 ; 4 ; 15 ) . Recently, 1 introduced IW-policies, which use the Iterated-Width (IW) algorithm ( 21 ) to perform lookahead searches at each state to augment successor choices. This enables “jumps” over multiple transitions, often simplifying the problem structure and reducing expressivity requirements. These are integrated by replacing 1-step transitions (s,s^{\prime}) with multi-step transitions [s,s^{\prime}] identified by IW(1) from s ( 1 ) . However, the embeddings for each object o were inferred independently for states s and s^{\prime} , interacting only within the value-function readout. While feasible for small instances, this approach faces key computational and expressivity limitations as size increases, because a given state might have many successors, of which each receives a separate and complete encoding of s^{\prime} . Our primary contributions address scaling and expressivity through two key innovations. First, we introduce a novel joint encoding approach for an entire tree of state transitions (s,s^{\prime}) , which avoids wastefully re-encoding shared state descriptions. We propose processing atoms from both s and each s^{\prime} in an aggregated encoding within the R-GNN. By recreating the lookahead tree structure within the graph-encoding and representing successors merely by their atom differences to the current state, we compute all values in a single pass, reducing memory usage by over a magnitude. Second, we propose Abstracted IW( 1 ), a significantly relaxed variant of IW( 1 ). For novelty testing, this variant abstracts state atoms by iteratively replacing all but one argument with their most specific type and tests the abstracted atoms instead. This shifts the worst-case complexity of the search from being linear in the number of atoms to the number of objects. Consequently, Abstracted IW( 1 ) evaluates significantly faster while still capturing meaningful subgoals for task decomposition. Furthermore, this lookahead mitigates the expressivity limitations of models restricted to immediate successors; it simplifies the problem’s cost structure and removes the need for features the R-GNN inherently lacks the expressivity to derive. These improvements are essential for scaling to large state spaces with numerous successors, a necessity highlighted by the massive instances in the IPC 2023 Learning Track (e.g., a 488-block Blocksworld). Scaling to this level requires both highly efficient IW lookahead and excellent model generalization. By achieving this, our approach outperforms prior work on the benchmark, including the strong LAMA baseline. Finally, the proposed lookahead drives substantial improvements in domains requiring expressivity beyond the standard C_{2} logic fragment 12 . The paper is organized as follows. We begin with background on classical and generalized planning, and IW, including its use for state-space jumps. We then introduce R-GNNs, followed by the input encodings and the reinforcement learning training procedure. Finally, we present the experimental evaluation, discuss the results, and conclude. Related work is discussed throughout the paper. 2 Planning Classical Planning. A classical planning instance is a pair P=\langle D,I\rangle , where D=\langle\mathcal{T},\mathcal{P},\mathcal{A}\rangle is the domain and I=\langle\mathcal{O},s_{0},g\rangle specifies the instance. The domain D consists of a set of types \mathcal{T} organized in a hierarchy, along with a set of predicates \mathcal{P} and actions \mathcal{A} . A predicate P\in\mathcal{P} has an arity n and an associated tuple of types (\tau_{1},\dots,\tau_{n})\in\mathcal{T}^{n} , and an atom P(x_{1},\dots,x_{n}) is formed by applying P to a tuple of terms (x_{1},\dots,x_{n}) of matching types. If all terms are objects from \mathcal{O} , the atom is said to be ground. Actions in \mathcal{A} are defined by a name and a typed list of arguments. Each action is associated with a precondition (a set of atoms required to be true) and an effect (sets of atoms to be added or deleted). We denote the set of actions applicable in a state s as \mathcal{A}[s] . The instance I defines the set of objects \mathcal{O} , where each object o\in\mathcal{O} is assigned a type \tau\in\mathcal{T} , the initial state s_{0} , and the goal g , where states are sets of ground atoms. A state s is a goal state if g\subseteq s . A plan is a sequence of applicable actions that transforms s_{0} into a goal state. Generalized Planning. A generalized planning problem is a set \mathcal{Q} of planning instances P drawn from the same domain, possibly with different object sets, initial states, and goals. Unlike classical planning, where a solution is typically an open-loop sequence of ground actions, a

Read the complete text