💻 computer science

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

This paper introduces an efficient holistic encoding and an Abstracted IW(1) approach that leverages Relational GNNs to overcome scalability and expressivity limitations in generalized planning, achieving state-of-the-art performance on the IPC 2023 benchmark by surpassing prior methods including the classical planner LAMA.

Original authors: Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner

Published 2026-05-19

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Michael Aichmüller, Simon Ståhlberg, Martin Funkquist, Hector Geffner

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to solve a massive, ever-changing maze. The maze changes every time you play: sometimes there are 10 rooms, sometimes 10,000. The goal is to teach the robot a single "rulebook" (a policy) that works for any version of the maze, no matter how big it gets.

This paper presents a new way to teach that robot, solving two major problems that have held previous methods back: memory overload and slow thinking.

Here is the breakdown of their solution using simple analogies:

1. The Problem: The "Library of Babel"

In the past, when the robot tried to plan its next move, it would look at every possible future step one by one.

The Old Way: Imagine you are in a library with a million books. To decide which book to read next, you have to walk to every single book, read the first page, write down a note, and then walk back. If you have 1,000 books, that's 1,000 trips. If you have a million, you'll never finish.
The Limit: As the "maze" (the planning problem) gets bigger, the number of "books" (possible moves) explodes. Previous AI methods would run out of computer memory or take too long to think, especially when the number of objects (like blocks or cars) reached the thousands found in recent competitions.

2. The First Innovation: The "Delta Snapshot" (Aggregated-Delta Encoding)

The authors realized they didn't need to re-read the whole library every time. They only needed to know what changed.

The Analogy: Instead of taking a photo of the entire library every time you move a book, you just take a tiny "sticky note" that says: "Book A moved from Shelf 1 to Shelf 2."
How it works: The new method, called Aggregated-Delta (AD), treats the robot's planning tree like a single, connected map. Instead of processing every future state as a separate, heavy image, it only encodes the differences (the "deltas") between the current state and the next.
The Result: The robot can look at the entire map of possibilities in one single glance (a "forward pass") rather than checking them one by one. This reduced the memory needed by more than 10 times, allowing the robot to handle massive problems that previously crashed the computer.

3. The Second Innovation: The "Blurry Lens" (Abstracted Width)

Even with the new memory trick, the robot still had to check if a specific move was "new" or "novel." In a world with thousands of objects, checking every single specific detail is slow.

The Analogy: Imagine you are looking for a specific red car in a parking lot.
- The Old Way: You check every car individually: "Is this the red Ford? Is this the red Toyota? Is this the red Honda?"
- The New Way (Abstracted IW): You put on a "blurry lens." You stop checking the specific car models. Instead, you just ask: "Is there a red car here?" You treat all red cars as the same "type" of object.
How it works: They introduced Abstracted IW (AIW). When checking if a move is new, the AI ignores the specific identity of objects (like "Block #452") and only looks at their general type (like "Block").
The Result: This turns a search that grows exponentially with the number of objects into one that grows linearly. It's like checking a list of 100 types of cars instead of 10,000 individual cars. It's much faster, but it still finds the important "sub-goals" needed to solve the puzzle.

4. The Outcome: A Super-Planner

By combining the "Sticky Note" memory trick with the "Blurry Lens" thinking style, the authors created a planner that:

Scales Up: It can solve problems with hundreds of objects (like a 488-block tower) that stumped previous AI.
Outperforms the Best: In the 2023 International Planning Competition (a major test for AI planners), their method beat the previous champions, including a very strong classical planner called LAMA.
Handles Hard Puzzles: It solved complex domains (like "Satellite" and "Rovers") that require logic more advanced than what most AI models can usually handle.

Summary

The paper is about teaching an AI to stop trying to memorize every single detail of a massive, changing world. Instead, it teaches the AI to:

Only remember what changed (saving massive amounts of memory).
Group similar things together (thinking faster by ignoring unnecessary details).

The result is a general policy that can navigate huge, complex mazes efficiently, solving problems that were previously too big for computers to handle.

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

Problem Statement

Generalized planning aims to learn policies that generalize across large collections of planning instances within a single domain, differing only in initial states, goals, and object counts. While recent approaches using Graph Neural Networks (GNNs) have shown promise, they face significant scalability and expressivity limitations when applied to large-scale instances, such as those found in the International Planning Competition (IPC) 2023.

Specifically, prior work on Iterated Width (IW) policies utilizes IW(1) lookahead searches to define "jumps" over multiple transitions, simplifying problem structure. However, existing implementations suffer from two main bottlenecks:

Computational Inefficiency: Evaluating each successor state individually leads to redundant encoding of shared state descriptions, causing memory and compute costs to scale poorly as the number of objects and atoms increases.
Expressivity and Scaling Limits: Standard IW(1) novelty checks scale linearly with the number of ground atoms. In domains with thousands of objects, the number of ground atoms grows polynomially, rendering the lookahead search inefficient. Furthermore, models restricted to immediate successors often lack the expressivity to derive necessary features for complex domains (e.g., those requiring logic beyond the C2 fragment).

Methodology

The paper proposes a unified approach combining two key innovations: a novel Aggregated-Delta (AD) encoding for Relational GNNs (R-GNNs) and Abstracted IW(1) (AIW(1)) for lookahead search.

1. Aggregated-Delta (AD) Encoding

Instead of processing the current state $s$ and each successor state $s'$ independently, the authors introduce a holistic encoding that represents the entire lookahead tree as a single relational graph.

Joint Representation: The root state $s$ is encoded implicitly via its relation set. Successor states are represented not by their full state descriptions, but by state object-nodes ( $o_{s'}$ ) that encode only the differences (added and deleted predicates) relative to the root.
Tree Structure: The encoding includes explicit atoms representing transitions between successors and depth nodes to capture the search depth. This allows the R-GNN to exchange information directly between successor nodes and compute embeddings for all states in a single forward pass.
Efficiency: This approach avoids re-encoding shared state descriptions, reducing memory usage by over an order of magnitude (from >24GB to <4GB VRAM in tested scenarios) and enabling the evaluation of all transitions simultaneously.

2. Abstracted IW(1) (AIW(1))

To address the scaling bottleneck of novelty checks, the authors propose a relaxed variant of IW(1) that abstracts state atoms during novelty testing.

Relational Abstraction: Rather than testing fully instantiated atoms, AIW(1) iteratively replaces all but one argument of an $n$ -ary atom with its most specific type (e.g., replacing object $o$ with $type(o)$). An atom is considered novel if any of its abstracted forms is novel.
Complexity Shift: This modification shifts the worst-case complexity of the novelty search from being linear in the number of ground atoms to being linear in the number of objects.
Goal Preservation: Atoms mentioned in the goal are not abstracted to ensure goal detection remains precise.
Benefit: This allows the lookahead to scale to instances with thousands of objects while still capturing meaningful subgoal structures and simplifying the cost structure for the learning agent.

Training Procedure

The R-GNN is trained using deep Q-learning with a lifted variant of Hindsight Experience Replay (HER). The reward is defined as -1 per step, making the Q-value represent the negative expected number of transitions to the goal. An auxiliary ranking loss is introduced to enforce depth order in the lookahead tree, ensuring the agent learns to avoid dead-ends caused by jumping too far ahead (e.g., in the Spanner domain).

Key Contributions

Aggregated-Delta (AD) Encoding: A novel input encoding for R-GNNs that represents entire lookahead trees jointly via state differences. This enables single-pass evaluation of all successors, drastically reducing memory footprint and training time.
Abstracted IW(1) (AIW(1)): A scalable lookahead mechanism that reduces novelty search complexity from polynomial in atoms to linear in objects by utilizing type-based abstraction.
State-of-the-Art Performance: The combination of AIW and AD achieves new performance benchmarks on the IPC 2023 Learning Track and other domains, surpassing both previous learned policies and strong classical planners like LAMA.

Experimental Results

The authors evaluated their approach on the IPC 2023 benchmark (900 instances across 10 domains) and an extended set of domains (including Grid and Logistics).

IPC 2023 Performance: The AIW–AD method achieved a total coverage of 74% (668/900 instances), significantly outperforming:
- IW–AD (59%): Demonstrating the value of abstraction.
- AIW–Ext (51%) and IW–Ext (51%): Demonstrating the value of the AD encoding.
- LAMA (65%): The strong classical baseline.
- Flat AA (58%): Flat policies without lookahead.
Domain Specifics:
- Satellite: AIW–AD solved 98% of instances, fully solving the domain where other learned methods struggled.
- Rovers & Childsnack: Significant improvements were observed, though hard instances in Childsnack remain challenging due to massive branching factors (millions of actions).
- Sokoban & Floortile: Performance remained low, consistent with the known difficulty of these PSPACE-complete or structurally complex domains for search-free policies.
Scalability: The method successfully handled instances with up to 488 blocks (Blocksworld) and over 290,000 atoms (Rovers), where previous IW-policy formulations failed due to memory constraints.
Expressivity: The approach successfully generalized to domains requiring features beyond the C2 logic fragment (e.g., Satellite, Rovers, Grid, Logistics), suggesting that the lookahead mechanism reduces the expressive burden on the neural architecture.

Significance and Claims

The paper claims that efficient width-based lookahead is a critical enabler for scaling generalized planning. The significance of the work lies in two main areas:

Scalability: By decoupling the complexity of the lookahead search from the number of ground atoms (via AIW) and the complexity of the neural encoding from the number of transitions (via AD), the approach makes it feasible to learn policies for massive planning instances that were previously intractable for learned methods.
Reduced Expressivity Requirements: The lookahead mechanism simplifies the problem structure for the learning agent. By "jumping" over sequences of primitive decisions, the policy only needs to learn high-level decisions. This allows models with limited expressivity (standard R-GNNs) to solve domains that would otherwise require complex features beyond the C2 logic fragment.

The authors conclude that their approach represents a new state-of-the-art in generalized planning, demonstrating that combining principled search (lookahead) with efficient neural encoding allows learned policies to scale effectively while maintaining high performance across diverse and complex domains.